advertisement

EECS 465: Digital Systems Lecture Notes # 5 Sequential Circuit (Finite-State Machine) Design SHANTANU DUTT Department of Electrical Engineering and Computer Science University of Illinois, Chicago Phone: (312) 355-1314: e-mail: dutt@eecs.uic.edu URL: http://www.eecs.uic.edu/~dutt 1 Finite State Machine (FSM) Design • FSMs are different from counters in the sense that they have external I/Ps, and state transitions are dependent on these I/Ps and the current state. • Example : Problem Statement There is a bit-serial I/P line. Design an FSM that outputs a ‘0’ if an even # of 1’s have been received on the I/P line and the outputs a ‘1’ otherwise. Note : If a synchronous sequential circuit is being designed, the counting of the # of 1s occur every clock cycle. x O/p y FSM CLK CLK x # of 1s even (0) odd (1) even (2) odd (3) odd (3) 2 • First determine the # of useful information classes required to solve the problem. • In this case, only 2 classes of information is required: whether an even # of 1s have been received, or an odd # of 1s have been received Solution 1: (Mealy) Solution 2: (Moore) 0 0/0 Reset Even Odd Even Input 1/1 1/0 Transition Arc Reset Output Output [0] O/P is dependent on current state and input in Mealy 0/1 Mealy Machine: Output is associated with the state transition, and appears before the state transition is completed (by the next clock pulse). 1 1 Odd [1] 0 Input Output is dependent only on current state Moore Machine: Output is associated with the state and hence appears after the state transition take place. 3 External I/Ps External O/Ps m1 Comb. Logic n even odd n Output Logic n n CLK External Outputs Moore Machine Model Mealy Machine Model Time t : Even I/P FFs m2 CLK t+ Next State Comb. Logic m2 FFs t External I/Ps m1 = propagation delay of logic of Mealy M/C t+TCLK t+TCLK+2 Even Odd O/P=1 O/P=1 x=1 (Moore) (Mealy) O/P=0 2 = propagation delay of O/P logic unit of Moore M/C 4 State Transition Table (Even-Parity Checker) Even State: 0 ; Present State Input Odd State: 1; Next State State Variable A Moore O/P Mealy O/P D-FF Excit. y1 y2 DA T-FF Excit. A x A+ 0 0 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 0 1 Input variables to comb. logic DA= Ax ; TA= x y1 = A for Moore y2 = Ax for Mealy TA Output functions y2 x N.S. & O/P Logic Q A FF x N.S. Logic Or Q DA CLK A O/P Logic FFs DA y1 5 Reset State=0 Even 0 0/0 Reset State=0 Even [0] 1/1 1/0 1 1 State=1 Odd N.S. Logic x State=1 Odd [1] Q 0/1 Q Mealy 0 D- FF D Moore CLK S.T. is complete. Assume single bit state information stored in a D-FF State Transition State Transition is occurring is occurring S.T. is complete. CLK x D even Q odd even even odd odd (state) y2 (Mealy O/P) 6 y1 Moore O/P) Moore M/C Implementation a) D-FF b) T-FF x 0 D x=1 Q R CLK A y2 T CLK Q R Q A y2 Q Reset Reset Moore O/P is synchronized with clock. Mealy M/C Implementation y1 0 1 D x=1 CLK Q R x T A CLK Q R y1 Q Q Reset a) D-FF Reset b) T-FF Mealy O/P is not synchronized with clock. 7 Difference Between Mealy and Moore Machine Mealy (1) O/Ps depend on the present state and present I/Ps (2) The O/P change asyn -chronously with the enabling clock edge (3) (4) A counter is not a Mealy machine A Mealy machine will have the same # or fewer states than a Moore machine Moore O/Ps depend only on the present state Since the O/Ps change when the state changes, and the state change is synchronous with the enabling clock edge, O/Ps change synchronously with this clock edge A counter is a Moore machine 8 Another example: A simple vending machine Here is how the control is supposed to work. The vending machine delivers a package of gum after it has received 15 cents in coins. The machine has a single coin slot that accepts nickels and dimes, one coin at a time. A mechanical sensor indicates to the control whether a dime or a nickel has been inserted into the coin slot. The controller’s output causes a single package of gum to be released down a chute to the customer. One further specification: We will design our machine so it does not give change. A customer who pays with two dimes is out 5 cents! Coin Sensor Reset Vending Machine FSM Open Gum Release Mechanism CLK Vending Machine block diagram States: 0C 5C 10C 15C 9 — The figure below show the Moore and Mealy machine state transition diagrams. ( N D Reset )/0 0 cent [0] Reset ND 0 cent Reset / 0 N D /0 N/0 N 5 cent [0] D ( N D Reset )/0 Reset / 0 Reset D/0 D N 10 cent [0] N+D 15 cent [1] Moore machine 5 cent D/1 N/0 ND 10 cent N D /0 N+D/1 15 cent Mealy machine Moore and Mealy machine state diagrams for the vending machine FSM 10 —State transition table for Moore and Mealy M/C.(Next state also gives D-FF excitation). Present State Q1 Q2 0 0 0 1 1 0 1 1 Inputs Next State D 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 Q 1+ 0 0 1 x 0 1 1 x 1 1 1 x 1 1 1 x N 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 Q2+ 0 1 0 x 1 0 1 x 0 1 1 x 1 1 1 x Moore Output Mealy Output Open 0 0 0 x 0 0 0 x 0 0 0 x 1 1 1 x Open 0 0 0 x 0 0 1 x 0 1 1 x 1 1 1 x Encoded vending machine state transition table. Q+ = D Q Q+ 0 0 0 1 1 0 1 1 D 0 1 0 1 11 Implementation using D-FFs Q1Q0 Q1Q0 00 01 11 10 00 0 0 1 1 01 0 1 1 11 x x 10 1 1 DN Q1Q0 00 01 11 10 00 0 1 1 0 1 01 1 0 1 x x 11 x x 1 1 10 0 1 K-map for D1 DN 00 01 11 10 00 0 0 1 0 1 01 0 0 1 0 x x 11 x x x x 1 1 10 0 0 1 0 DN K-map for Open (Moore) K-map for D0 Q1Q0 D1 = Q1 + D + Q0·N D0 N Q0 Q0 N Q1 N Q1 D OPEN = Q1·Q0 Moore OPEN = Q1·Q0 + D·Q0 + D·Q1 + N·Q1 00 01 11 10 00 0 0 1 0 01 0 0 1 1 DN 11 x x x x 10 0 1 1 1 Mealy K-map for Open (Mealy) 12 Q1 D1 D D Q0 N Q1 CLK Q R Q1 Q OPEN Reset N Q0 Q0 D0 N Q1 D CLK Q R Q Similarly, a Mealy implementation; only the OPEN function changes. Q0 Q0 N Reset Q1 D Vending machine FSM implementation based on D flip-flops(Moore). 13 Implementation using J-K FFS J-K Excitation D N Q 1+ Q2+ J1 K 1 J0 K 0 Q Q+ 0 0 0 0 0 x 0 x 0 1 0 1 0 x 1 x 0 0 1 0 1 0 1 x 0 x 0 1 1 1 x x x x x x 1 0 0 1 0 0 0 1 0 x x 0 1 1 0 1 1 0 1 x x 1 1 0 1 1 1 x x 0 1 1 x x x x x x 1 0 0 0 1 0 x 0 0 x 0 1 1 1 x 0 1 x 1 0 1 1 x 0 1 x 1 1 x x x x x x 1 1 0 0 1 1 x 0 x 0 0 1 1 1 x 0 x 0 1 0 1 1 x 0 x 0 1 1 x x x x x x Remapped next-state functions for the vending machine example. Q1 Q2 0 0 J 0 1 x x 14 K x x 1 0 Q1Q0 00 01 11 10 00 0 0 x x 01 0 1 x 11 x x 10 1 1 DN Q1Q0 00 01 11 10 00 x x 0 0 x 01 x x 0 0 x x 11 x x x x x x 10 x x 0 0 DN K-map for J1 K-map for K1 Q1Q0 Q1Q0 00 DN 00 01 0 1 01 11 10 x x 0 x x 1 00 01 11 10 00 x 0 0 x 01 x 1 0 x DN 11 x x x x 11 x x x x 10 0 x x 1 10 x 0 0 x K-map for J0 K-map for K0 K-maps for J-K flip-flop implementation of vending machine. J1 = D + Q0·N J 0 Q0 N Q1 D K1 = 0 K 0 Q1 N 15 N Q0 CLK D Q0 J Q K R Q Q1 Q1 OPEN N Q1 D CLK Q1 J Q K R Q Q0 Q0 N Reset J-K flip-flop implementation for the vending machine example (Moore). Similarly, a Mealy implementation; only the OPEN function changes. 16 Basic Steps in the FSM Design Procedure 1. Understand the problem and the different information classes (minimal number) required to solve it. 2. Convert these information classes into distinct states, and determine the state transition diagram of the FSM. 3. Encode states in binary, and obtain state transition table and FF excitation for desired FF type. 4. Minimize the FF input functions (using K-Maps, for example) and implement the FSM using these FFs and logic gates (or MUXes) that implement the FF’s input functions. 17 FSM Word Problem 1: • Design a system that outputs a ‘1’ whenever it receives a multiple of 3 # of 1’s (i.e., 0, 3, 6, 9, etc. # of 1’s) on a serial input line x. — Relevant information classes needed to solve the problem: (A) A multiple of 3 # is received. (B) A non-multiple of 3 # is received. Questions to consider: (1) How do we go from (A)(B) Ans.: If a ‘1’ is received (2) How do we go from (B)(A) Ans.: Not clear. Need to split up (B) further into (B1): 3y+1 # of 1’s received. Where y is an integer 0. (B2): 3y+2 # of 1’s received. 18 Note: (A): is 3y+0 = 3y # of 1’s received. • Now the transitions between the3 classes of information is clear: (A) (B1) (B2) (A) 1 received 1 received 1 received • Hence these classes of information can be considered states of the required as states of the required FSM: These 3 states can be represented by 3y+I, i = 0,1,2 00 Reset 0/1 i=0 0 Output Input Reset i=0 [1] 0/0 1/0 1/1 10 01 i=1 1/0 i=2 0/0 Mealy Machine 1 1 0 i=1 [0] i=2 [0] 1 0 19 Moore Machine FSM Word Problem 2: • Design a system that outputs a ‘1’ whenever it receives: (a) A multiple of 3 # of 1’s AND (b) A non-zero even # of 0’s # of 1’s E.g., ((0,2) , (3,2) , (3,4) , (6,2) ,···) # of 0’s — Relevant classes of information: - For # of 1’s: 3y+i, i = 0,1,2 [3 classes] - For # of 0’s: 2z+j, j = 0,1 For j = 0, we need to distinguish between zero (z = 0) and non-zero (z > 0) # of 0’s - Thus we have 3 classes: 2z+0, z = 0 ( 0 ) 2z+0, z > 0 ( non-zero even ) 2z+1 ( odd ) 20 The relevant # of 1’s can be represented by i = { 0, 1, 2 } ( # of 1’s = 3y+i ) — The relevant # of 0’s can be represented by j= { 00 , 0>0 , 1 } ( # of 0’s = 2z+j ) where the subscript of the 0 indicates whether z=0 or z>0. — Since at any point time, a certain # of 1’s and # of 0’s will have been received, the state of the system will be given by a combination of relevant # of 1’s and # of 0’s. — There are 9 combinations: { 0, 1, 2, } X { 00, 0>0, 1 } = (0,00), (0,0>0), (0,1), (1,00), (1,0>0), (1,1), (2,00), (2,0>0), (2,1) # of 1’s # of 0’s Cartesian Product 21 (0,00) (0,0>0) (1,00) (0,1) (2,00) (1,1) (2,1) (1,0>0) (2,0>0) 22 Note: 0>0 2z+j, j = 0 z>0 Reset (0,00) 1/0 0/0 1/0 (0,0>0) (1,00) 1/0 0/0 0/0 0/1 1/0 (0,1) (2,00) 0/0 (1,1) 0/0 1/0 1/0 0/0 (2,1) (1,0>0) 1/1 0/0 1/0 0/0 (2,0>0) 1/0 23