UNIT-IV.pptx

DIGITAL ELECTRONICS UNIT-III

1. UNIT IV ASYNCHRONOUS SEQUENTIAL CIRCIT Analysis of Asynchronous Sequential Circuits Design of Asynchronous Sequential Circuits Reduction of State and Flow Tables Race-free State Assignment Hazards.

2. Synchronous sequential circuits Asynchronous sequential circuits Memory elements are clocked flip flops Memory elements are either unclocked flip flops or time delay elements. The change in input signals can affect memory element upon activation of clock signal. The change in input signals can affect memory element at any instant of time. Maximum operating speed of clock depends on time delays involved. It operates faster than synchronous circuits. Easier to design More difficult to design

3. Types of Asynchronous Circuits

4. To ensure proper operation, it is necessary for synchronous sequential circuit to attain a stable state before the input is changed to a new value. Because of the unequal delays in the wires and gate circuits, it is impossible to have two or more input variables change at exactly same input. Therefore, simultaneous changes of two or more input variables are usually avoided. In other words, we can say that only one input variable is allowed to change at any one time and the time between two input changes is kept longer than the time it takes the circuit to reach a stable state. According to how input variables are to be considered, there are two types of asynchronous circuits: Fundamental mode circuits Pulse mode circuits

5. Fundamental mode circuit It assumes that: Input changes should be spaced in time by atleast Δ t, the time needed for the circuit to settle into a stable state following an input change. That is, the input variables should change only when the circuit is stable. Only one input variable can change at a given instant of time Inputs are levels and not pulses. Delay lines are used as memory elements.

6. Pulse mode circuit It assumes that: The input variables are pulses instead of levels. The width of the pulses is long enough for the circuit to respond to the input. The pulse width must not be so long that it is still present after the new state is reached. Pulses should not occur simultaneously on two or more input lines. Flip-flops are commonly used as a memory elements. Memory element transitions are initiated only by input pulses. Input variables are used only in the uncomplemented or the complemented forms, but not both.

7. Analysis of Asynchronous Sequential Circuits Fundamental mode asynchronous sequential circuit analysis requires careful attention because these circuits utilize unlocked memory and level inputs. The produce to analyze these circuits is as follows: Determine the next-secondary state and output equations from the given sequential circuit. Construct the state table. Construct the transition table. Construct output map.

8. 1. Analyze the fundamental mode asynchronous sequential circuit given. Step 1: Determine the next-secondary state and output equations:  

9. Step 2: Construct State table Present total state Next total state Stable total state Yes/No z Secondary State Inputs Next-secondary state Yes 1 Yes 1 1 Yes 1 Yes 1 1 No 1 1 1 No 1 1 1 1 Yes 1 1 No 1 1 1 1 Yes 1 1 1 1 No 1 1 1 1 1 1 1 Yes 1 1 1 1 1 No 1 1 No 1 1 No 1 1 1 No 1 1 1 No Present total state Next total state Stable total state Yes/No z Secondary State Inputs Next-secondary state Yes 1 Yes 1 1 Yes 1 Yes 1 1 No 1 1 1 No 1 1 1 1 Yes 1 1 No 1 1 1 1 Yes 1 1 1 1 No 1 1 1 1 1 1 1 Yes 1 1 1 1 1 No 1 1 No 1 1 No 1 1 1 No 1 1 1 No

10. Transition table: Output Map: I 1 I X 1 X 00 01 11 10 00 00 00 00 00 01 10 10 01 00 11 11 10 11 01 10 01 00 00 01 Circle represent stable states Unstable states I 1 I X 1 X 00 01 11 10 00 01 - - - 11 - 1 - 10 - - - -

11. 2. An asynchronous sequential circuit is described by the following excitation and output function. Y=X 1 X 2 + (X 1 +X 2 )Y; Z=Y ( i ) Draw the logic diagram of the circuit. (ii) Derive the transition table and output map. (iii) Describe the behavior of the circuit. Solution: Draw the logic diagram of the circuit.

12. (ii) Derive the transition table and output map. Present total state Next total state Stable total state Yes/No Z Secondary State Inputs Next-secondary state Yes 1 Yes 1 1 1 No 1 1 Yes 1 No 1 1 1 Yes 1 1 1 1 1 Yes 1 1 1 1 Yes 1 Present total state Next total state Stable total state Yes/No Z Secondary State Inputs Next-secondary state Yes 1 Yes 1 1 1 No 1 1 Yes 1 No 1 1 1 Yes 1 1 1 1 1 Yes 1 1 1 1 Yes 1 X 1 X 2 Y 00 01 11 10 1 1 1 1 1 T ransition table State table X 1 X 2 Y 00 01 11 10 - 1 - 1 1 1 Output map (iii) The circuit gives carry output of the full adder circuit.

13. Design of Asynchronous Sequential Circuits The steps involved in designing of asynchronous sequential circuit. 1. Construction of a primitive flow table from the problem statement. An intermediate step may include the development of a state diagram 2. Primitive flow table is reduced by eliminating redundant states by using state reduction techniques. 3. State assignment is made. 4. The primitive fl ow table is realized using appropriate logic elements.

14. Derivation of Primitive Flow Table The flow table in the asynchronous sequential circuit is same as that of state table in the synchronous sequential circuit. In asynchronous sequential circuits state table is known as flow table because of the behaviour of the asynchronous sequential circuit. The state changes occur independent of a clock, based on the logic propagation delay, and cause the states to "flow" from one to another. A primitive flow table is a special case of flow table. It is defined as a flow table which has exactly one stable state for each row in the table. The design process begins with the construction of primitive flow table.

15. Develop the state diagram and primitive flow table for a logic diagram that has two inputs S and R and a single output Q. the device is to be an edge triggered SR flip-flop but without a clock.

16. Present State Next State, for inputs SR/Output Q 00 01 11 10 A A/0 C/0 -- B/0 B D/1 -- E/1 B/1 C A/0 C/0 F/0 -- D D/1 C/1 -- B/1 E -- C/0 E/0 G/0 F -- H/1 F/1 B/1 G A/0 -- E/0 G/0 H D/1 H/1 F/1 -- Primitive Flow Table

17. Reduction of Primitive Flow Table The next step in the design process is to reduce the primitive flow table using state reduction techniques. Here, we are going to use merger graph technique to reduce primitive flow table. Merger graph is state reducing tool used to reduce states in the incompletely specified machine. The merger graph is defined as follows It contains the same number of vertices as the state table contains states. Each compatible state pair is indicated by a line drawn between the two state vertices. Every potentially compatible state pair , with outputs not in conflict but whose next states are different, is connected by a broken line . The implied states are drawn in the line break between the two potentially compatible states If two states are incompatible, no connecting line is drawn.

18. Reduce the primitive flow table using merger graph method. Present State Next State, for inputs XY Output z 00 01 11 10 A A B -- C B A B D -- C A -- D C D -- B D E E A -- D E 1             Present State Next State, for inputs XY Output z 00 01 11 10 -- -- 1 Present State Next State, for inputs XY Output z 00 01 11 10 -- -- 1 Alternative I Alternative II Reduced primitive flow table (Alternative I) Present State Next State, for inputs XY Output z 00 01 11 10 -- 1 Present State Next State, for inputs XY Output z 00 01 11 10 -- 1 Reduced primitive flow table (Alternative II)

19. 2. Reduce the primitive flow table using merger graph method. Present State Next State, for inputs SR/Output Q 00 01 11 10 A A/0 C/0 -- B/0 B D/1 -- E/1 B/1 C A/0 C/0 F/0 -- D D/1 C/1 -- B/1 E -- C/0 E/0 G/0 F -- H/1 F/1 B/1 G A/0 -- E/0 G/0 H D/1 H/1 F/1 -- Present State Next State, for inputs SR/Output Q 00 01 11 10 A A/0 C/0 F/0 B/0 B D/1 C/1 E/1 B/1 C A/0 C/0 F/0 B/0 D D/1 C/1 E/1 B/1 E A/0 C/0 E/0 G/0 F D/1 H/1 F/1 B/1 G A/0 C/0 E/0 G/0 H D/1 H/1 F/1 B/1         Present State Next State, for inputs XY 00 01 11 10 ,0 ,0 Present State Next State, for inputs XY 00 01 11 10

20. Race Free State Assignment The state assignment step in asynchronous circuits is essentially the same as it is for synchronous circuits, except for one difference. In synchronous circuits, the state assignments are made with the objective of circuit reduction. In asynchronous circuits, the objective of state assignment is to avoid critical races. Races and Cycles When two or more binary state variables change their value in response to a change in an input variable, race condition occurs in an asynchronous sequential circuit. In case of unequal delays, a race condition may cause the state variables to change in an unpredictable manner. For example if there is a change in two state variables due to change in input variable such that both change from 00 to11. In this situation, the difference in delays may cause the first variable to change faster than the second resulting the state variables to change in sequence from 00 to 10 and then to 11. On the other hand if the second variable changes faster than the first, the state variables change from 00 to 01 and then to 11. If the final stable state that the circuit reaches does not depend on the order in which the state variable changes, the race condition is not harmful and it is called a noncritical race But, if the final stable state depends on the order in which the state variable changes, the race condition is harmful and it is called a critical race. Such critical races must be avoided for proper operation.

21. Cycles A cycle occurs when an asynchronous circuit makes a transition through a series of unstable states. When a state assignment is made so that it introduces cycles, care must be taken to ensure that each cycle terminates on a stable state. If a cycle does not contain a stable state, the circuit will go from one unstable state to another, until the inputs are changed. Obviously, such a situation must always be avoided when designing asynchronous circuits. Two techniques are commonly used for making a critical race free state assignment. 1. Shared row state assignment. 2. One hot state assignment. Shared row state assignment: Races can be avoided by making a proper binary assignment to the state variables. Here, the state variables are assigned with binary numbers in such a way that only one state variable can change at any one time when a state transition occurs. To accomplis h this, it is necessary that states between which transition occur be given adjacent assignments. Two binary values are said to be adjacent if they differ in only one variable. The technique is called shared row state assignment because in the technique extra state, i.e., extra row is introduced in a flow table. This extra state is shared between two stable states.

22. One hot state assignment: The one hot state assignment is an another method for finding a race free state assignment. In this method, only one variable is active or ‘hot’ for each row in the original flow table, i.e., it requires one state variable for each row of the flow table. Additional rows are introduced to provide single variable ch anges between internal state transitions. Transition Diagram Transition Diagram with race free state assignment

23. State variables State Inputs 00 01 11 10 1 A A B C C 1 B A B C D 1 C A B C C 1 D D B C D State variables State 00 01 11 10 1 A A B C C 1 B A B C D 1 C A B C C 1 D D B C D State variables State Inputs 00 01 11 10 1 A A B E C F C F 1 B A E B C D 1 C A F B G C C 1 D D B H C I D 1 1 E A B -- -- 1 1 F A -- C C 1 1 G -- B C -- 1 1 H -- B -- D 1 1 I -- -- C -- State variables State 00 01 11 10 1 A A B E C F C F 1 B A E B C D 1 C A F B G C C 1 D D B H C I D 1 1 E A B -- -- 1 1 F A -- C C 1 1 G -- B C -- 1 1 H -- B -- D 1 1 I -- -- C -- Flow Table One hot state assignment flow table

24. 1. Determine an asynchronous sequential circuit with 2 inputs X and Y and with one output Z .Whenever Y is 1, input X is transferred to Z. when Y is 0; the output does not change for any change in X. Present State Next State, for inputs XY Output z 00 01 11 10 A A B -- C B A B D -- C A -- D C D -- B D E 1 E F -- D E 1 F F B -- E 1 State Diagram Primitive flow table Step 1: Construction of a primitive flow table from the problem statement

25. Step 2: Reduction of primitive flow table using merger graph. Merger graph Present State Next State, for inputs XY Output z 00 01 11 10 A A B D C B A B D C C A B D C D F B D E 1 E F B D E 1 F F B D E 1     Present State Next State, for inputs XY Output z 00 01 11 10 1 Present State Next State, for inputs XY Output z 00 01 11 10 1

26. Step 3: State assignment Step 4: Realization of the circuit using logic gates Present State (F) Next State (F+), for inputs XY Output z 00 01 11 10 1 1 Present State (F) Next State (F+), for inputs XY Output z 00 01 11 10 1 1    

27. Construct a circuit with inputs A and B to give an output Z=1 when AB=11 but only if A becomes 1 before B, by drawing total state diagram, primitive flow table and output map in which transient state is included. Present State Next State, for inputs AB Output z 00 01 11 10 A A B -- C B A B D -- C A -- E C D -- B D C E -- B E C 1 Step 1: Construction of a primitive flow table from the problem statement Primitive flow table State Diagram

28. Step 2: Reduction of primitive flow table using merger graph. Present State Next State, for inputs AB Output z 00 01 11 10 1 Present State Next State, for inputs AB Output z 00 01 11 10 1 Present State Next State, for inputs AB Output z 00 01 11 10 A A B D C B A B D C C A B E C D A B D C E A B E C 1      

29. Step 3: State assignment Present State Next State, for inputs AB Output z 00 01 11 10 1 Next State, for inputs AB Output z 00 01 11 10 1     Step 4: Realization of the circuit using logic gates

30. Design an asynchronous sequential circuit with two inputs x 1 and x 2 and one output Z. Initially, both inputs are equal to zero. When x 1 or x 2 becomes 1, the output Z becomes 1. When the second input also becomes 1, the output changes to 0. The output stays at 0 until the circuit goes back to the initial state. Design a two-input ( x 1, x 2 ), two-output ( Z 1, Z 2 ) fundamental-mode circuit that has the following specifications. When x 1 x 2 =00, Z 1 Z 2 =00. The output 10 will be produced following the occurrence of the input sequence 00-01-11. The output will remain at 10 until the input returns to 00 at which time it becomes 00. An output of 01 will be produced following the receipt of the input sequence 00-10-11. And once again, the output will remain at 01 until a 00 input occurs, which returns the output to 00.

31. Hazards The unwanted switching transients (glitches) that may appear at the output of a circuit are called Hazards. The hazards cause the circuit to malfunction . The main cause of hazards is the different propagation delays at different paths. Hazards occur in the combinational circuits, where they may cause a temporary false output value. When such combinational circuits are used in the asynchronous sequential circuits, hazards may result in a transition to a wrong stable state. There are two types of hazards: Static and Dynamic hazards A static hazard exists if a signal is supposed to remain at particular logic value when an input variable changes its value, but instead the signal undergoes a momentary change in its required value . A ccording to definition, the static hazards are further classified as static-0 hazard and static-1 hazard. In a combinational circuit, if output goes momentarily 0 when it should remain at 1, the hazard is known as static-1 hazard. On the other hand, if output goes momentarily 1 when it should remain at 0, the hazard is known as static-0 hazard. Another type of hazard is dynamic hazard in which output changes three or more times when it should change from 1 to 0 or from 0 to 1.

32. Eliminating a Hazard: The hazard exists because of the change of input results in a different product terms covering two minterms or different sum terms covering two maxterms. Whenever the circuit move from one product term to another or move one sum term to another, there is a possibility of a momentary interval when neither term is equal to 1, giving rise to an undesirable 0 output. Hazards can be eliminated by enclosing two minterms or maxterms.

33. Hazards in Sequential Circuits: We know that, in sequential circuits, the combinational circuits are associated with them to derive the flip-flop inputs. In synchronous sequential circuits, the hazards due to combinational circuits associated with them are not of concern. This is because momentary erroneous signals are not generally troublesome in synchronous circuits. However, if a momentary incorrect signal is fed back in an asynchronous sequential circuit, it may cause the circuit to go to the wrong stable state. Essential Hazards Another type of hazard that may occur in asynchronous sequential circuits is called an essential hazard . This type of hazard is caused by unequal delays along two or more paths that originate from the same input. An excessive delay through an inverter circuit in comparison to the delay associated with the feedback path may cause such a hazard. Essential hazards cannot be corrected by adding redundant gates as in static hazards. The problem that they impose can be corrected by adjusting the amount of delay in the affected path. To avoid essential hazards, each feedback loop must be handled with individual care to ensure that the delay in the feedback path is long enough compare with delays of other signals that originate from the input terminals.

34. Examples: Give hazard- free realisation for the following Boolean function, f(A,B,C,D)= Σm (0,2,6,7,8,10,12) Implement the switching function F=Σ(1,3,5,7,8,9,14,15) by a static hazard free two-level AND-OR gate network. Implement the switching function F=Σ(0,1,3,4,8-12) by a static hazard free two-level OR-AND gate network. Find a static and dynamic hazard free realization for the following function using ( i ) NAND gates (ii) NOR gates F( a,b,c,d )= Σm (1,5,7,14,15)