Implement 3 and 4 variable function using 8:1 MUX

Three variable  function can be easily implemented using 8:1 multiplexer. connect 3 input lines to select lines of mux and connect 8 inputs of mux to logic 0 or 1 according to function output. For example, let us say Function is

                                      F(X,Y,Z) = Σ(0,1,3,6)

then X,Y,Z will be connected to select lines of Mux and I0 , I1, I3 and I6 will be connected to logic 1(VDD) and other will be connected to logic 0

For a 4 variable function, there are 16 possible combinations. To implement 4 variable function using 8:1 MUX, use 3 input as select lines of MUX and remaining 4th input and function will determine ith input of mux . Let us demonstrate it with an example :

                                  F(A,B,C,D) = Σ(1,5,7,9,10,11,12)

A	B	C	D	Decimal Equivalent	F
0	0	0	0	0	0
1	0	0	0	8	0
0	0	0	1	1	1
1	0	0	1	9	1
0	0	1	0	2	0
1	0	1	0	10	1
0	0	1	1	3	0
1	0	1	1	11	1
0	1	0	0	4	0
1	1	0	0	12	1
0	1	0	1	5	1
1	1	0	1	13	0
0	1	1	0	6	0
1	1	1	0	14	0
0	1	1	1	7	1
1	1	1	1	15	0

The 4 variable function represented using 8:1 mux

                                  ABar = ~A (inverted A)

As shown in figure, B,C,D are used as select lines and A will be used input  of Mux. from Truth table, if B,C,D  are 0 then output F is 0 irrespective of status of A so I0 = 0. For I5(BCD = 101) output depend upon A.

                                     for A = 0,  F  = 1
                                     for A = 1,  F =  0
                          Hence F = ~A (for BCD = 101)
                                    I4, (B = 1, C = 0, D = 0),  F = A
                                    I1, (B = 0, C =  0,D  = 1), F = 1 (irrespective of status of A)

similarly All other inputs can be inferred in the same way.  Thus we can conclude that to implement n variable function, we need 2^(n-1) to 1 MUX and an inverter. n-1 input lines shall be used as select lines and rest one will be used for input of MUX.

Also read:

• Binary to thermometer encoder
• Clock gating checks at a multiplexer
• Lockup latch - principle and application
• Carry look ahead adder
• Interesting problem - BCD multiply by 5 circuit

Race condition in digital circuits

In general, race condition refers to a situation in which the result depends upon the sequence in which events happen. In particular, a race condition occurs when a system/device is designed assuming a particular sequence of events without taking steps to ensure it. In logic gates, it happens when the inputs arrive at the gate in a sequence not assumed while deriving the function. This results, sometimes, in the anomalous behavior of the logic gate because of the unexpected dependence on the sequence of arrival of inputs. Since, the function of the logic gate is calculated assuming static inputs; the order of arrival may have impact on the output. We can consider race condition as a situation in which two or more signals are racing to have their effect on the output. This is how; race condition derives its name.

For a very simple example, consider the following logic function-

Z = A . A’

Figure 1: An example digital circuit having race condition

Theoretically, the output will always be ‘0’. However, this is true only if the non-inverted portion of the signal has greater delay in reaching the AND gate (we have considered ‘0’ -> ‘1’ transition of the input signal ‘A’). As shown in the figure above, the signal passing through inverter will have some delay of its own. If the signal through inverter reaches the AND gate later than the one without inverter, there will be a glitch as shown in the figure 2. For ‘1’ -> ‘0’ transition, the opposite will happen.

Figure 2: Glitch caused at the output of AND gate due to inverted signal being delayed than non-inverted signal

What can be the consequences: If the condition for race is violated, the design may enter an undefined state, the one which might not have been considered while designing. Hence, the whole system will malfunction in such a scenario leading to failure. It might be the case that some elements in the design enter metastable state, which can further cause problems. Hence, it is very important to give proper consideration to race conditions.

How can we prevent race condition: Normally, in digital designs, as long as setup and hold checks are met for each flip-flop, we do not need to worry about the race conditions in the design under consideration. But, there are some conditions like the output of the above AND gate might be used as a clock for some flop. In that case, we need to consider the race condition. We need to have proper sequencing of signals so as to have the desired output. Had the above case been in reality, it might be wise to delay the non-inverted signal. Race conditions in the design can be eliminated by using proper design techniques (e.g. K-map). Using these, designers and recognize and eliminate the race conditions before they cause problems.

Read also:

• Data checks: all about data setup and data hold check
• Synchronization schemes in VLSI design
• Ensuring glitch-free propagation of clock
• Design Quiz: multiply by 2 clock circuit
• Delay line based time to digital converter

Scan chains – the backbone of DFT

What are scan chains: Scan chains are the elements in scan-based designs that are used to shift-in and shift-out test data. A scan chain is formed by a number of flops connected back to back in a chain with the output of one flop connected to another. The input of first flop is connected to the input pin of the chip (called scan-in) from where scan data is fed. The output of the last flop is connected to the output pin of the chip (called scan-out) which is used to take the shifted data out. The figure below shows a scan chain.

A scan chain

Purpose of scan chains: As said above, scan chains are inserted into designs to shift the test data into the chip and out of the chip. This is done in order to make every point in the chip controllable and observable as discussed below.

How normal flop is transformed into a scan flop: The flops in the design have to be modified in order to be put in the scan chains. To do so, the normal input (D) of the flip-flop has to be multiplexed with the scan input. A signal called scan-enable is used to control which input will propagate to the output.

Figure showing transition of a normal flop to scan flop

  

If scan-enable = 0, data at D pin of the flop will propagate to Q at the next active edge

If scan-enable= 1, data present at scan-in input will propagate to Q at the next active edge

Scan terminology: Before we talk further, it will be useful to know some signals used in scan chains which are as follows:

• Scan-in: Input to the flop/scan-chain that is used to provide scan data into it 
• Scan-out: Output from flop/scan-chain that provides the scanned data to the next flop/output 
• Scan-enable: Input to the flop that controls whether scan_in data or functional data will propagate to output
  
  
  Purpose of testing using scan: Scan testing is carried out for various reasons, two most prominent of them are: 

•  To test stuck-at faults in manufactured devices 
•  To test the paths in the manufactured devices for delay; i.e. to test whether each path is working at functional frequency or not

How a scan chain functions: The fundamental goal of scan chains is to make each node in the circuit controllable and observable through limited number of patterns by providing a bypass path to each flip-flop. Basically, it follows these steps: 

1.  Assert scan_enable (make it high) so as to enable (SI -> Q) path for each flop 
2.  Keep shifting in the scan data until the intended values at intended nodes are reached 
3.  De-assert scan_enable (for one pulse of clock in case of stuck-at testing and two or more cycles in case of transition testing) to enable D->Q path so that the combinational cloud output can be captured at the next clock edge. 
4.  Again assert scan_enable and shift out the data through scan_out

How Chain length is decided: By chain length, we mean the number of flip-flops in a single scan chain. Larger the chain length, more the number of cycles required to shift the data in and out. However, considering the number of flops remains same, smaller chain length means more number of input/output ports is needed as scan_in and scan_out ports. As 

                Number of ports required = 2 X Number of scan chains

Since for each scan chain, scan_in and scan_out port is needed. Also,

               Number of cycles required to run a pattern = Length of largest scan chain in design

Suppose, there are 10000 flops in the design and there are 6 ports available as input/output. This means we can make (6/2=) 3 chains. If we make scan chains of 9000, 100 and 900 flops, it will be inefficient as 9000 cycles will be required to shift the data in and out. We need to distribute flops in scan chains almost equally. If we make chain lengths as 3300, 3400 and 3300, the number of cycles required is 3400.

Keeping almost equal number of flops in each scan chain is referred to as chain balancing.

Also read:

• MBIST (Memory Built-In Self-Test)
• Lockup latch - Principle and application
• Controllability and observability - basics of DFT
• LBIST
• How propagation of 'X' happens through different logic gates