4x1 mux using NAND gates

In the post 2x1 mux using NAND gates, we discussed how we can use NAND gates to build a 2x1 multilexer. In this post, we will discuss how we can use NAND gates to build a 4x1 mux:

1. Using structural approach: As we know that a 4x1 mux can be structurally built from 2x1 muxes as shown in figure 1 below. Thus, in the same way, we can arrange the 2-input NAND gates to build 4x1 muxes as shown in figure 1.

Figure 1: 4x1 mux using NAND gates with structural approach

2. Building 4x1 mux directly from NAND gates: The logical equation of a 4x1 multiplexer is given as:

Y = (S1' S0' A + S1' S0 B + S1 S0' C + S1 S0 D)

where S1 and S0 are the selects of the multiplexer and A, B, C and D are the multiplexer inputs.

Now,  using De-morgan's law (m + n = (m'n')')

The above equation turns into,

Y = ((S1' S0' A)'  (S1' S0 B)' (S1 S0' C)' (S1 S0 D)')'

In other words,

Y = NAND (NAND(S1',S0',A),NAND(S1',S0,B),NAND(S1,S0',C),NAND(S1,S0,D)) 

Thus, we require four 3-input NAND gates and a 4-input NAND gate to implement a 4x1 mux. The implementation is shown in figure 2 below.

DESIGN PROBLEM : 4-bit increment by 2 circuit

Problem: Derive the logical expression for a 4-bit increment by 2 circuit and draw the architecture of it.

Solution: The task here is to design a circuit that increments its count by two. Since, it is a 4-bit circuit, the total number of possible states is 16. Each state transitions to the state which has a binary value two greater than it. Now, there are two possible scenarios based upon the initial state that the counter gets into:

1. It can count 0 -> 2 -> 4 -> 6 -> 8 -> 10 -> 12 -> 14 -> 0 (their binary equivalents)

2. It can count 1 -> 3 -> 5 -> 7 -> 9 -> 11 -> 13 -> 15 -> 1 (their binary equivalents)

The state transition table can be represented as shown below:

We can find the expression for outputs using K-maps as below.

Expression for D3(next): Let us first derive the expression for D3(next). The K-map can be represented as below:

The expression for D3(next) as derived from K-map is:

D3(next) = D3.D2' + D3.D1' + D3'.D2.D1

D3(next) = D3.(D2'+D1') + D3'.D2.D1.

D3(next) = D3.(D2.D1)'+D3'.(D2.D1)

D3(next) = D3 (exor) (D2.D1) 

Expression for D2(next): Given below is the K-map derived from state transition table for D2(next).

The expression for D2(next) as derived from K-map is:

D2(next) = D2'.D1 + D2.D1' = D2 (exor) D1

Expression for D1(next):  Given below is the K-map derived from state transition table for D1(next).

The expression for D1(next) is derived from K-map as:

D1(next) = D1'

Expression for D0(next): Given below is the K-map for D0(next).

The expression for D0(next) is:

D0(next) = D0

Combining all the expressions, the circuit is as given below:

Can you come up with a better solution for this problem? Let us know your views in comments.

This question was asked by one Himadri Roy Pramanik on our post your query page. You can also post your queries there. We will try to answer using our limited knowledge.

Clock gating checks in case of mux select transition when both clocks are running

PROBLEM: In the following figure, it is desired to toggle the select of the mux from CLOCK_DIV to CLOCK and both the clocks are running. What are the architectural and STA considerations for the same?

SOLUTION:
This is a very good example to understand how clock gating checks work, although you may/may not find any practical application for the same. We have to toggle the select of the multiplexer such that there is no glitch at the output. Let us consider architectural considerations first:

Architectural considerations:

Launching flip-flop of 'select' signal: In the post clock gating checks at a multiplexer, we discussed that if there is a mux getting clock at its inputs and select as data, then, there are two possible scenarios:

• If the other clock is at state "0", then AND type check is formed and select has to launch from negative edge-triggered flip-flop

• If the other clock is at state "1", then OR type check is formed and select has to launch from positive edge-triggered flip-flop

Now, since both the clocks are running simultaneously, both with act as "other clock" for each other. Let us choose to keep both the clocks at state "0" when select toggles. The same discussion holds true for the other scenario as well, just that appropriate values will hold. Thus,

(i) Both clocks required to be at state '0' when clock toggles

(ii) There is AND-type clock gating check formed between 'select' and both clocks 

(iii) 'select' launches from negative edge-triggered flip-flop.

Valid negative edges when 'select' can toggle: Now, as mentioned above both the clocks should be zero when select toggles. Figure below shows the valid and invalid edges where 'select' can toggle. As it turns out, select can toggle only on edges labelled "VALID" as both "CLOCK" and "DIV_CLOCK" will be zero then.

 So, to ensure that "SEL" toggles only when DIV_CLOCK is "0", we can add logic to the input of the flip-flop launching "SEL" such that it allows to propagate "SEL" only when DIV_CLOCK is "0".

In the above diagram, flip-flop launching "SEL" will hold its value when DIV_CLOCK = 0. We have to keep in mind that this implementation is just a representation of what needs to be done. the actual implementation may be more complex than this depending upon the requirements.

Timing considerations: Now coming to the timing considerations, we need to ensure that the setup and hold conditions are met, which are as shown in the figure below:

Also read:

• Clock gating interview questions

Intricacies in handling of half cycle timing paths

What is a half cycle path? A half cycle timing path is one in which launch and capture happen on different clock edges. A half cycle path can be in terms of both setup and hold. However, normally, in technical terms half cycle path is the one which has setup check getting formed as half cycle. For instance, following are some of the examples of half cycle timing paths:

1. A timing path from positive edge-triggered flip-flop to a negative edge-triggered flip-flop and vice-verse. Here, hold check is also half cycle on the previous edge
2. A timing path from a positive level-sensitive latch to a negative level-sensitive latch and vice-verse. Here, hold check is zero cycle
3. A timing path from a negative edge-triggered flip-flop forming a clock gating check on AND gate (Here, hold check is zero cycle)
4. A timing path from a positive edge-triggered flip-flop forming a clock gating check on OR gate (here, hold check is zero cycle)

There are also, some cases where hold check is half cycle and setup check is single/zero cycle. These are:

1. A timing path from a negative edge-triggered flip-flop forming a clock gating check on OR gate (Here, setup check is single cycle check)
2. A timing path from a positive edge-triggered flip-flop forming a clock gating check on AND gate (Here, setup check is single cycle check)

In addition, minimu pulse width checks should also be considered same as half cycle timing paths. But, in this case, start-point and end-point are the same register.

In this post, we will be considering only setup timings paths as example, although the complete discussion applies on all kinds of half cycle setup paths/checks. To start with, let us note down the most simple setup check equation for half cycle timing paths.

T_ck->q + T_prop + T_setup  < (T_period/2) + T_skew

Let us now discuss some of the intricacies that we should be aware of while dealing with half cycle timing paths:

Clock source duty cycle variation: There is always a variation in duty cycle of the clock source due to uncertainty in the relative timings of positive and negative edges. Duty cycle variation is always measured with respect to corresponding positive and negative edges. In other words, we can also say that duty cycle variation is the uncertainty in arrival of negative edge, given that positive edge has arrived at certain fixed point of time. Let us take an example. If we are given a clock with a period of 10 ns with ideal 50% duty cycle. Also, we are given that it has the clock has a duty cycle variation of +-5%. So, if we say that we saw positive edge of clock at 100 ns, we can expect to see negative edge of clock at any time between 14.5 ns and 15.5 ns. Following waveform illustrates this. You can read my earlier post duty cycle variation to have a more detailed elaboration.

So, the setup check equation modifies as:

T_ck->q + T_prop + T_setup  < (T_period/ 2- T_sdc) + T_skew

where T_sdc is the clock source duty cycle variation. Thus, the effective half clock period reduces by an amount equal to duty cycle variation.

Duty cycle degradation:  In addition to source duty cycle variation, there can be assymmetry in rise delay vs fall delay of clock elements. For instance, a buffer may have nominal rise (0 -> 1) delay of 50 ns whereas 48 ns for fall delay (1 -> 0). So, if a clock pulse passes through it, it will eat a portion of this clock pulse as shown in figure 1 below. For more clarity, we have exaggerated the scenario with a fall delay of 30 ns.

So, a half cycle may be larger of smaller than actual half cycle at the clock pin. In the above case, positive to negative edge setup check will be tighter by 20 ns and negative-> positive setup check will be relaxed by same amount (neglective OCVs as of now). So, the modified setup equation, now, becomes:

T_ck->q + T_prop + T_setup  < (T_period/2 - T_sdc) + (T_skew - T_dcd)

As discussed above also, T_dcd can be positive or negative depending upon if rise-fall variation of cells is helping or oppsing.

Can you think of some other scenario that is specific only to half cycle timing paths? Do share, if you do.

Is hold always checked on the same edge?

One of the guys asked me a question, "Why is hold always checked on the same edge?" Normally, it is taught in books/colleges that hold is frequency independent because it is checked on same edge. But, is it really true? It is true only for some of the many cases. Hold can be checked on the same edge, next edge or previous edge depending upon the scenario. In this post, we will discuss those cases one by one, and try to generalize if this statement holds true.

How to determine the edge on which hold check needs to be checked: For most of us, it seems quite confusing to arrive at the conclusion of how to determine the hold edge. Let us try to use a state machine perspective here. In state machine theory, we study that synchronous digital circuits can be considered as state machines moving from one state to another. This state transition happens on each clock edge as shown in figure 1 below.

Figure 1: Each clock edge corresponds to a design state

If we look at each flip-flop, every positive edge-triggered flip-flop changes its state at positive clock edge and all negative edge-triggered flip-flops transition state at negative clock edge. Similarly, all negative edge-triggered flip-flops transition state at negative clock edge as shown in figure 2 below.

Figure 2: State transition for positive edge-triggered and negative edge-triggered flip-flops

Or, we can represent the states of positive edge-triggered and negative edge-triggered flops as separate as shown in figure 3 below.

Figure 3: States of positive and negative edge-triggered flops represented symbolically

Let us have a scenario of a timing path from a positive edge-triggered flop to a positive edge-triggered flop. In the figure 4 below, flip-flop "2" transitions to state (K+1) depending upon the value of flip-flop "1" at state (K).

Figure 4: A sample timing path from positive edge-triggered flip-flop to positive edge-triggered flip-flop

Here, the data launched from ff1 should help ff2 transition to state "K+1", meaning, it should be captured at the corresponding clock edge. This represents setup check. Also, it should not disturb state "K" of ff2, meaning it should not get captured at this edge. This represents hold check. So, in this case hold check is on the same edge as the present state of start and end flops is the same edge.

Figure 5: Setup and hold checks for positive-to-positive edge-triggered timing paths

Now, let us take a look on the scenario where-in hold check is not on the same edge. Let us take a timing path launching data from negative edge and capturing at positive edge. This scenario is shown in figure 6 below.

Figure 6: Timing path from negative-to-positive edge-triggered flop

Here, positive edge-triggered flip-flop transitions states on positive edge and negative edge-triggered flop transitions on negative edges. So, the data launched from negative edge-triggered flop corresponding to state "X" should get captured on positive edge-triggered flop on state "Y+1", which corresponds to setup check. And it should not get captured on state "Y", which corresponds to hold check.

Thus, we have looked upon different cases of hold capturing edge being same or different than the launch edge. For all the possible cases of setup and hold checks, you can follow below posts:

• Setup and hold checks
• Setup checks and hold checks for register to register timing paths
• Setup checks and hold checks for register-to-latch timing paths
• Setup checks and hold checks for latch-to-reg timing paths
• Can hold check be frequency dependant

Design puzzle : 2-input mux glitch issue

Problem statement: A 2-input multiplexer has both of its inputs getting value of "1". Will there be any toggle (glitch) happening at the output of the multiplexer? If yes, is that expected? What if both the inputs are getting value of "0"?

Answer: 

We all know that a multiplexer's output is equal to

IN0 if SEL = 0

IN1 if SEL =1

So, if both IN0 and IN1 are getting same logic value, output must not toggle. However, if we observe carefully, there is a high chance of a momentary glitch at the output in case both inputs are at value "1" and select toggles from "1" to "0". To understand this, we need to look into the internal structure of the mux, which is as shown in figure 2 below.

The figure says that output goes momentarily to "0" before finally settling down to "1". Why is this so? The reason behind this is the two paths going from SEL to OUT and toggling of both the inputs of final OR gate. And there is asymmetry of delays with one inverter being extra in one of the paths. This causes the output of the mux to go momentarily to zero.

Let us analyze this with the help of timing waveforms (assuming delay of each element to be 1 unit):

Thus, it is clear from the timing waveforms that there is a glitch in the output. It is possible to minimize the extent of this glitch by minimizing the difference of delays between the two paths getting formed between the SEL and OUT. However, it cannot be guaranteed even with greatest of precision during design as there are mismatches in fabrication of individual gates. So, even the best of multiplexers will have this limitation, however small it may be, unless designed specifically for this purpose. Can you suggest a design improvement that can help in this scenario?

One is forced to think here that what can be the consequences of such a glitch and what remedies can be there for this. I had written a post Glitches in combinational circuits that discussed what can be the consequences of glitches in combinational circuits. This scenario is a special case, but with some twist. Let us discuss all the cases one by one.

• If this case is in a data path for synchronous circuits, there is no issue as discussed in one of the points in our post Glitches in combinational circuits.
• If this case happens for a data path in asynchronous circuits, this can be an issue. So, synchronization circuits have to be designed with utmost care and following the rules of data synchronization
• If this scenario occurs in either path of clock or reset, this is an issue as this glitch can alter the state of the design by either letting the flop capture data at "D" pin by acting as an extra clock pulse, or can reset the flop.

Setup time and hold time - origin

In our previous post, Setup and hold – the state machine perspective, we discussed how setup and hold can be defined in respect of state machines. Interestingly, there is another perspective of setup and hold – that in repect to devices, known as setup and hold time requirements. For a device, (for example a flip-flop, a latch or an SoC), setup and hold times are defined as:

Setup time: Setup time of a device is defined as the minimum time before the clock edge the data should be kept stable so that it is reliably sampled by the clock.

Hold time: Hold time of a device is defined as the minimum time after the clock edge the data should be kept stable so that it is reliably sampled by the clock.

In other words, every device has a setup and hold window surrounding the active clock edge within which data should be kept stable. As is shown in figure 1, brown line represents the active clock edge, blue line represents setup window and red line represents hold window. As is shown, data can toggle at any time except between setup and hold windows. Toggling of data between setup-hold window means flip-flop might go into metastable state and the output of flip-flop does not remain predictable.

Figure 1: Setup and hold checks

Origin of setup and hold timing requirements: Let us consider a positive edge-triggered flip-flop. Figure 2 shows a most simplistic circuit for a practical flip-flop. Inverters I1, I2 and Transmission gates G1, G2 constitute master latch and I3, I4, G3, G4 constitute slave latch.

Figure 2: A typical practical circuit for negative edge-triggered flip-flop

Figure 3 below shows the origin of setup time requirement. For data to get latched properly, it should complete the feedback loop of master latch before the closing edge of clock at transmission gate G4. So, setup time requirement of the flip-flop is:

T_setup = T_G3 + T_I1 + T_I2 + T_G4

Figure 3: Figure demonstrating delays constituting setup check

Similarly, figure 4 below shows the origin of hold timing requirement. For data to get latched properly, the next data should not cross inverter I1. So, hold timing requirement of the flip-flop is:

T_hold = -(T_G3 + T_I1)

In other words, hold time is the minimum time required for the data to change after the clock edge has passed so that new data does not get captured at the present clock edge.

Figure 4: Delays constituted in hold check

Thus, in this post, we have discussed the origin of setup and hold checks for a device.