Chapter-6-Synchronous Sequential Logic (2).pptx

ff

1. Sequential Circuits

2. STATE REDUCTION AND ASSIGNMENT Reduce the number of states C hecking of each pair of states for possible equivalence can be done systematically using Implication Table . U nused states are treated as don't-care condition  fewer combinational gates. 95

3. STATE REDUCTION AND ASSIGNMENT Implication Table ( extra reading ) – The state-reduction procedure for completely specified state tables is based on the algorithm that two states in a state table can be combined into one if they can be shown to be equivalent. -- There are occasions when a pair of states do not have the same next states, but, nonetheless, go to equivalent next states . 96

4. STATE REDUCTION AND ASSIGNMENT Implication Table ( extra reading ) S ystematically checking of each pair of states for possible equivalence in a table with a large number of . C hart that consists of squares : one for every possible pair of states, that provide spaces for listing any possible implied states. 98

5. STATE REDUCTION AND ASSIGNMENT 99 Next state Output Present state x = x = 1 x = x = 1 a d b b e a c g f 1 d a d 1 e a d 1 f c b g a e 1 Implication Table ( extra reading ) – Consider the following state table: Implication table:

6. STATE REDUCTION AND ASSIGNMENT State Assignment In order to design a sequential circuit with physical components, it is necessary to assign coded binary values to the states. To minimize the cost of the combinational circuits. For a circuit with m states, the codes must contain n bits where 2 n = ≥ m. Ex: with 3 bits it is possible to assign codes to 8 states denoted by binary numbers 000 trough 111. 104

7. STATE REDUCTION AND ASSIGNMENT State Assignment It is not necessary that we use all the possible combination of states. e.g., it is possible that 7 states out of 8 are used in table 1 and 1 state remains unused ; or 5 states out of 8 are used in table2 , while the remaining 3 state s are unused. Unused states treated as don’t care conditions. Since don’t care conditions usually help in obtaining a simpler circuit, it is more likely that the circuit with five states will require fewer combinational gates than the one with seven states. 105

8. STATE REDUCTION AND ASSIGNMENT State Assignment 106 P r es e nt state Assignment 1 Binary Assignment 2 Gray Code Assignment 3 One-hot a 000 000 00001 b 001 001 00010 c 010 011 00100 d 011 010 01000 e 100 110 10000

9. State Assignment Any binary number assignment is satisfactory as long as each state is assigned a unique number. Use binary assignment 1. STATE REDUCTION AND ASSIGNMENT 10 7 P r esent state Next state Output x = x = 1 x = x = 1 000 000 001 001 010 011 010 000 011 011 100 011 1 100 000 011 1

10. D E S I G N P R O C E DU R E The design of a clocked sequential circuit starts from a set of specifications and culminates in a logic diagram or a list of Boolean functions from which the logic diagram can be obtained. 109

11. D E S I G N P R O C E DU R E Derive a state diagram for the circuit from the word description. Reduce the number of states if necessary. Assign binary values to the states. Obtain the binary-coded state table. Choose the type of flip-flops. Derive the simplified flip-flop input equations and output equations. Draw the logic diagram. 110

12. D E S I G N P R O C E DU R E Example: We wish to design a circuit that detects three or more consecutive 1’s in a string of bits coming through an input line. State diagram: 111 S / S 1 / S 3 / 1 S 2 / 1 1 1 1

13. This is a Moore model sequential circuit since the output is 1 when the circuit is in State3 and otherwise. D E S I G N P R O C E DU R E 112 S / S 1 / 3 S / 1 2 S / 1 1 1 1 State A B S S 1 1 S 2 1 S 3 1 1

14. D E S I G N P R O C E DU R E 113 00 / 01 / 11 / 1 10 / 1 1 1 1 Present State I/P Next State O/P A B x A B y 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

15. D E S I G N P R O C E DU R E To implement the circuit, Two D flip-flops are chosen to represent the four states and label their outputs A and B. There is one input x. There is one output y. The characteristic equation of the D flip – flop is Q(t+1) = DQ. 114

16. To implement the circuit, – The flip – flop input equations can be obtained directly from the next – state columns of A and B and expressed in sum of minterms. – A ( t+1) = D A ( A, B , x ) = ∑ (3, 5, 7) – B ( t+1) = D B ( A, B , x ) = ∑ (1, 5, 7 ) – y( A, B , x ) = ∑ (6, 7) D E S I G N P R O C E DU R E 11 5 Present State I/P Next State O/P A B x A B y 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

17. Synthesis using D Flip - flops – A ( t+1) = D A ( A, B , x ) = ∑ (3, 5, 7 ) – B ( t+1) = D B ( A, B , x ) = ∑ (1, 5, 7 ) – y( A, B , x ) = ∑ (6, 7) D E S I G N P R O C E DU R E 11 6 D A ’ s K - Map Bx A B 1 1 1 1 A 1 m m 1 m 3 M 2 1 m 4 M 6 m 5 m 7 1 1 x D A = Ax + Bx

18. Synthesis using D Flip – flops – A ( t+1) = D A ( A, B , x ) = ∑ (3, 5, 7) – B ( t+1) = D B ( A, B , x ) = ∑ (1, 5, 7 ) – y( A, B , x ) = ∑ (6, 7) D E S I G N P R O C E DU R E 11 7 D B ’ s K - Map Bx A B 1 1 1 1 A 1 m m 1 m 3 M 2 1 m 4 M 6 m 5 m 7 1 1 x D A = Ax + B’x

19. Synthesis using D Flip – flops – A ( t+1) = D A ( A, B , x ) = ∑ (3, 5, 7 ) – B ( t+1) = D B ( A, B , x ) = ∑ (1, 5, 7 ) – y( A, B , x ) = ∑ (6, 7) D E S I G N P R O C E DU R E 11 8 y ’ s K - Map Bx A B 1 1 1 1 m m 1 m 3 M 2 m 4 m 5 m 7 M 6 1 1 A 1 x y = AB

20. Synthesis using D Flip – flops D A = Ax + Bx D B = Ax + B’x y = AB D E S I G N P R O C E DU R E 11 9 Logic Diagram of Sequence Detector D Q Q A C L K x B D Q Q y

21. D E S I G N P R O C E DU R E When – D type flip-flops are employed, the input equations are obtained directly from the next state. This is not the case for the J K and T types of flip-flops. In order to determine the input equations for these flip flops, it is necessary to derive a functional relationship between the state table and the input equations. 120

22. D E S I G N P R O C E DU R E During the design process we usually know the transition from present state to the next state and wish to find the flip – flop input conditions that will cause the required transition. For this reason, we need a table that lists the required inputs for a given change of state. Such table is called an excitation table. 121

23. D E S I G N P R O C E DU R E 122 P r es e nt State Next State F.F. Input Q(t) Q(t+1) D 1 1 1 1 1 1 D Q (t+1) 1 1 D Flip – Flop Excitation table D Flip – Flop Characteristic Table Q(t+1) = D

24. D E S I G N P R O C E DU R E 123 P r es e nt State Next State F.F. Input Q(t) Q(t+1) J K X 1 1 X 1 X 1 1 1 X (No change) 1 ( Reset ) 1 ( Set ) 1 1 ( Toggle ) ( Reset ) 1 1 ( Toggle ) (No change ) ( S et ) J K Fl i p – F l op E x citatio n tab l e J K Fli p – Flo p Cha ra c teristi c T able J K Q (t+1) Q(t) 1 1 1 1 1 Q’(t) Q(t+1 ) = JQ ’ + K’Q

25. D E S I G N P R O C E DU R E 124 P r es e nt State Next State F.F. Input Q(t) Q(t+1) T 1 1 1 1 1 1 T Flip – Flop Excitation table T Fli p – Flo p Cha ra c teristi c T able T Q (t+1) Q(t) 1 Q’(t) Q(t+1 ) = T Q

26. D E S I G N P R O C E DU R E 125 1 1 1 1 Synthesis Using J - K Flip – Flops: Detect 3 or more consecutive 1’s S / S 1 / S 3 / 1 S 2 /

27. D E S I G N P R O C E DU R E 126 Synthesis Using J - K Flip – Flops: Detect 3 or more consecutive 1’s P r e s e n t State Input Next St a te Flip - Flop Inputs A B x A B J A K A X J B K B X 1 1 X 1 X 1 X X 1 1 1 1 1 X X 1 1 X 1 X 1 1 1 1 X 1 X 1 1 X 1 X 1 1 1 1 1 1 X X J A ( A, B , x ) = ∑ ( 3, 4, 5, 6, 7 ) K ( A, B , x ) = ∑ ( 0, 1, 2, 3, 4 , 6) A J B ( A, B , x ) = ∑ (1, 2, 3, 5, 6, 7) K B ( A, B , x ) = ∑ ( 0, 1, 2 , 3, 4, 5, 6)

28. S ynthesis Using J K F lip – F lop s : Detect 3 or more consecutive 1’s – J A ( A , B , x) = ∑ (3, 4, 5, 6, 7) – K A ( A, B , x) = ∑ (0, 1, 2, 3, 4, 6) B – J ( A , B , x) = ∑ (1, 2, 3, 5, 6, 7) J A ’ s K - M a p D E S I G N P R O C E DU R E 12 7 Bx A B 1 1 1 1 – K B (A, B, x) = ∑ (0, 1, 2, 3, 4, 5, 6) A 1 m m 1 m 2 m 3 1 m 4 m 5 m 7 m 6 X X X X x J A = Bx

29. S ynthesis Using J K F lip – F lop s : Detect 3 or more consecutive 1’s – J A ( A , B , x) = ∑ (3, 4, 5, 6, 7) – K A ( A, B , x) = ∑ (0, 1, 2, 3, 4, 6) B – J ( A , B , x) = ∑ (1, 2, 3, 5, 6, 7) K A ’ s K - M a p D E S I G N P R O C E DU R E 12 8 Bx A B 1 1 1 1 – K B (A, B, x) = ∑ (0, 1, 2, 3, 4, 5, 6) A 1 m m 1 m 3 m 2 X X X X m 4 m 5 m 7 M 6 1 1 x K A = x’

30. S ynthesis Using J K F lip – F lop s : Detect 3 or more consecutive 1’s – J A ( A , B , x) = ∑ (3, 4, 5, 6, 7) – K A ( A, B , x) = ∑ (0, 1, 2, 3, 4, 6) B – J ( A , B , x) = ∑ (1, 2, 3, 5, 6, 7) J B ’ s K - M a p D E S I G N P R O C E DU R E 12 9 Bx A B 1 1 1 1 – K B (A, B, x) = ∑ (0, 1, 2, 3, 4, 5, 6) A 1 m m 1 m 3 m 2 1 X X m 4 m 5 m 7 M 6 1 X X x J B = x

31. S ynthesis Using J K F lip – F lop s : Detect 3 or more consecutive 1’s – J A ( A , B , x) = ∑ (3, 4, 5, 6, 7) – K A ( A, B , x) = ∑ (0, 1, 2, 3, 4, 6) B – J ( A , B , x) = ∑ (1, 2, 3, 5, 6, 7) K B ’ s K - M a p D E S I G N P R O C E DU R E 13 Bx A B 1 1 1 1 – K B (A, B, x) = ∑ (0, 1, 2, 3, 4, 5, 6) A 1 m m 1 m 3 m 2 X X 1 1 m 4 m 5 m 7 m 6 X X 1 x K B = A ’ + x’

32. S ynthesis Using J K F lip – F lop s : Detect 3 or more consecutive 1’s J A = Bx K A = x’ J B = x K B = A ’ + x ’ Logic Diagram of Sequence Detector D E S I G N P R O C E DU R E 13 1 J Q K Q CLK x A B J Q K Q y

33. D E S I G N P R O C E DU R E 132 Synthesis Using T Flip – Flops: 3-bit Counter. An n-bit binary counter consists of n flip – flops that can count in binary from to 2 n – 1. 000 001 010 011 100 101 110 111

34. D E S I G N P R O C E DU R E 133 Synthesis Using T Flip – Flops: 3-bit Counter. P r e s e n t State Next St a te Flip - Flop Inputs A 2 A 1 A A 2 A 1 A T A2 T A1 T A0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 T A 2 ( A 2 , A 1 , A ) = ∑ ( 3, 7) T A 1 ( A 2 , A 1 , A ) = ∑ (1, 3, 5, 7) T A0 ( A 2 , A 1 , A ) = ∑ (0, 1, 2, 3, 4, 5, 6, 7)

35. S ynthesis Using T F lip – F lop s : 3 - bit Counter. – T A 2 (A 2 , A 1 , A ) = ∑ (3, 7) – T A 1 (A 2 , A 1 , A ) = ∑ ( 1, 3, 5, 7) – T A (A 2 , A 1 , A ) = ∑ (0, 1, 2, 3, 4, 5, 6, 7) T A2 ’ s K-Map D E S I G N P R O C E DU R E 13 4 A 1 A A 2 A 1 1 1 1 1 A 1 m m 1 m 2 m 3 1 m 4 m 5 m 7 m 6 1 A T A2 = A 1 A

36. S ynthesis Using T F lip – F lop s : 3 - bit Counter. – T A 2 (A 2 , A 1 , A ) = ∑ (3, 7) – T A 1 (A 2 , A 1 , A ) = ∑ ( 1, 3, 5, 7) – T A (A 2 , A 1 , A ) = ∑ (0, 1, 2, 3, 4, 5, 6, 7) T A1 ’ s K-Map D E S I G N P R O C E DU R E 13 5 A 1 A A 2 A 1 1 1 1 1 A 1 m m 1 m 3 m 2 1 1 m 4 m 5 m 7 m 6 1 1 A T A1 = A

37. S ynthesis Using T F lip – F lop s : 3 - bit Counter. – T A 2 (A 2 , A 1 , A ) = ∑ (3, 7) – T A 1 (A 2 , A 1 , A ) = ∑ ( 1, 3, 5, 7) – T A (A 2 , A 1 , A ) = ∑ (0, 1, 2, 3, 4, 5, 6, 7) T A0 ’ s K-Map D E S I G N P R O C E DU R E 13 6 A 1 A A 2 A 1 1 1 1 1 A 1 m m 1 m 3 m 2 1 1 1 1 m 4 m 5 m 7 m 6 1 1 1 1 A T A0 = 1

38. S ynthesis Using T F lip – F lop s : 3 - bit Counter. T A 2 = A 1 A T A 1 = A – T A = 1 D E S I G N P R O C E DU R E 13 7 Logic Diagram of 3-bit Binary Counter T Q A 2 Q T Q Q T Q Q CLK A 1 A 1