Digital Design with the Verilog HDL - Chapter 6: Finite State Machine

Nội dung text: Digital Design with the Verilog HDL - Chapter 6: Finite State Machine

1. Digital Design with the Verilog HDL Chapter 6: Finite State Machine Dr. Phạm Quốc Cường Use some Prof. Mike Schulte’s slides (schulte@engr.wisc.edu) Computer Engineering – CSE – HCMUT 1
2. Sequential Machine - Definition • State of a sequential machine contains current information (t) • Next state (t + 1) depends on the current state (t) and inputs • The number of states in a sequential machine finite => Finite State Machine - FSM Input Present State Next state (PS) Next-state Logic Memory (NS) Feedback of present state Block Diagram of a sequential machine 2
3. Synchronous Sequential Machine • Synchronous State Machine uses clock to synchronize input states • Clock is symmetric or asymmetric • Clock cycle must be larger than time required for state transaction calculation • Synchronous FSMs: – Number of states – Using clock to control state transaction 3
4. FSM Models & Types • Explicit – Declares a state register that stores the FSM state – May not be called “state” – might be a counter! • Implicit – Describes state implicitly by using multiple event controls • Moore – Outputs depend on state only (synchronous) • Mealy – Outputs depend on inputs and state (asynchronous) – Outputs can also be registered (synchronous) 4
5. Mealy machine vs. Moore machine Block Diagram of a Mealy sequential machine Block Diagram of a Moore sequential machine 5
6. State Transaction Graph • Finite state machine can be described: – State transaction graph, State transaction table – Time chart – Abstract state machine • Finite state machine is a directed graph – Vertices show states (+outputs if Moore-style machine) – Edges show transactions from state to state • Edges’ name – Mealy machine: input/output – Moore machine: input 6
7. State Diagram • Outputs Y and Z are 0, a = 0 b = 0 unless specified otherwise. S0 a = 1/ S1 Z = 1 Y=1 • We don’t care about b = 1/ reset = 1 Z = 1 the value of b in S0, or the value of a in S1, or S2 either a or b in S2. 7
8. State Diagram: Mealy • Outputs Y and Z are 0, a = 0 a = x b = x/ b = 0/ unless specified Y = 0, Y = 1, otherwise. a = 1 Z = 0 Z = 0 b = x/ Y = 0, S0 S1 • We don’t care about Z = 1 the value of b in S0, or a = x the value of a in S1, or reset = 1 b = 1/ either a or b in S2. ab = xx/ Y = 1, YZ = 00 S2 Z = 1 8
9. State Diagram: Moore a = 0 b = 0 Outputs Y and Z are 0, unless specified otherwise. If an input isn’t listed for a S0 a = 1 S1 transition, we don’t care Y=1 about its value for that transition reset = 1 b = 1 S2 Z=1 9
10. Example - Mealy reset Next state/Output table Next state/output S_0 0/1 State input 1/0 0 1 1/0 S_1 S_2 S_0 S_1/1 S_2/0 0/1 0/0 1/1 S_1 S_3/1 S_4/0 0/0, 1/1 S_2 S_4/0 S_4/1 S_3 S_4 S_3 S_5/0 S_5/1 0/0 1/1 0/1 S_4 S_5/1 S_6/0 S_5 S_6 S_5 S_0/0 S_0/1 0/1 S_6 S_0/1 -/- State transition graph State transition table 10
11. Example 1/0 0/1 Next State/Output State Input S_2 S_0 S_1 0 1 S_0 S_1/0 S_2/1 1/1 0/0 S_1 S_0/1 - S_2 - S_0/0 0 S_0/0 S_1/0 Next State/Output State Input 0 1 1 1 0 0 S_0 S_1/0 S_3/1 S_1 S_2/1 - S_3 - S_0/1 S_3/1 S_2/1 1 S_2 S_1/0 S_3/0 State transition graph State transition table 11
12. Constraints • Each vertex describes only one state • Each edge describe exactly one transaction from current state to the next state • Each vertex has all out-going edges • At one edge, there is only one out-going edge at one time 12
13. BCD to Excess-3 code Converter Decimal BCD Excess-3 digit • Excess-3 is self- 0 0000 0011 complementing 1 0001 0100 – 610 = 01102 2 0010 0101 – 6excess-3 = 01102 + 00112 3 0011 0110 = 10012 4 0100 0111 5 0101 1000 6 0110 1001 7 0111 1010 8 1000 1011 9 1001 1100 13
14. Input/output Relation Bin = 8 (BCD) Bout = 8 (Excess-3) 1 1 0 1 0 0 0 1 Excess-3 MSB LSB MSB Code converter 1 0 0 0 0 0 1 1 clock MSB 1 0 1 1 LSB Input-output bit stream in a BCD to Excess-3 serial code converter 14
15. State Transaction Graph – State Transaction Table reset Next state/Output table Next state/output S_0 0/1 State input 1/0 0 1 1/0 S_1 S_2 S_0 S_1/1 S_2/0 0/1 0/0 1/1 S_1 S_3/1 S_4/0 0/0, 1/1 S_2 S_4/0 S_4/1 S_3 S_4 S_3 S_5/0 S_5/1 0/0 1/1 0/1 S_4 S_5/1 S_6/0 S_5 S_6 S_5 S_0/0 S_0/1 0/1 S_6 S_0/1 -/- State transition graph (Mealy type FSM) State transition table (Mealy type FSM) 15
16. State Encoding • States are stored by FFs Encoded Next state/output table • 7 states, using 3 FFs State Next state Output + + + q2q1q0 q2 q1 q0 State assignment Input Input q2q1q0 State 0 1 0 1 000 S_0 S_0 000 001 101 1 0 001 S_1 S_1 001 111 011 1 0 010 S_6 S_2 101 011 011 0 1 011 S_4 S_3 111 110 110 0 1 100 S_4 011 110 010 1 0 101 S_2 S_5 110 000 000 0 1 110 S_5 S_6 010 000 - 1 - 111 S_3 16 100 - - - -
17. Simplify State Transaction Function q B q B 0 in 00 01 11 10 0 in 00 01 11 10 q2q1 q2q1 00 1 1 1 1 00 0 0 1 1 01 0 X 0 0 01 0 X 1 1 11 0 0 0 0 11 0 0 1 1 10 X X 1 1 10 X X 1 1 + + q0 = q1’ q1 = q0 q B q B 0 in 00 01 11 10 0 in 00 01 11 10 q2q1 q2q1 00 0 1 0 1 00 1 0 0 1 01 0 X 0 1 01 1 X 0 1 11 0 0 1 1 11 0 1 1 0 10 X X 0 0 10 X X 1 0 + q2 = q1’q0’Bin + q2’q0Bin’ + q2q1q0 Bout = q1’Bin’ + q2Bin 17
18. Implementing BCD to Excess-3 Converter 18
19. FSM Example: Serial-Line Code Converter • 3 signals: – Clock – Handshaking signal – Data • Well-known encoding algorithms: – NRZ – NRZI: if input is 1, the previous output value is inversed while 0 input keeps output unchanged – RZ: if input is 1, output is 1 during the first half cycle and 0 during the second half cycle while 0 input produces 0 output – Manchester: if input is 0, output is 0 during the first half cycle and 1 during the second half cycle while 1 input produces 1 output during the first half and 0 output during the second half 19
20. Serial Encoding Examples • Clock_2’s frequency is double clock_1’s frequency to implement the NRZI, RZ, and Manchester encoding algorithms 20
21. Mealy FSM for Serial Encoding • The Manchester algorithm – Waiting state (S_0) – Just receiving 1 state (S_2) – Just receiving 0 state (S_1) 1/0 0/1 Next State/Output State Input S_2 S_0 S_1 0 1 1/1 0/0 S_0 S_1/0 S_2/1 State Next State Output S_1 S_0/1 - S_2 - S_0/0 q1q0 q1+q0+ Input Output q0 0 1 0 1 q1 0 1 S_0 00 01 10 0 1 0 S_0 S_1 S_1 01 00 00 1 - 1 S_2 S_2 10 00 00 - 0 21
22. Implementing the Mealy FSM B B B in 0 1 in 0 1 in 0 1 q1q0 q1q0 q1q0 00 0 1 00 1 0 00 0 1 01 0 0 01 0 0 01 1 1 11 - - 11 - - 11 - - 10 0 0 10 0 0 10 0 0 + + q1 = q1’ q0’Bin q0 = q1’ q0’Bin Bout = q1’( q0 + Bin) 22
23. Moore FSM for Serial Encoding • The Manchester Algorithm – S_0: starting/second half of the cycle receiving 1, the output is 0 – S_1: first half of the cycle receiving 0, the output is 0 – S_2: second half of the cycle receiving 0, the output is 1 – S_3: first half of the cycle receiving 1, the output is 1 0 Next State/Output S_0/0 S_1/0 State Input 1 1 0 0 0 1 S_0 S_1/0 S_3/1 S_3/1 S_2/1 S_1 S_2/1 - 1 S_3 - S_0/1 State Next State Output S_2 S_1/0 S_3/0 + + q1q0 q1 q0 Input 0 1 S_0 00 01 11 0 S_1 01 10 _ 0 S_3 11 _ 00 1 23 S_2 10 01 11 1
24. Implementing the Moore FSM B B in 0 1 in 0 1 q1q0 q1 00 0 1 00 0 0 01 1 X 01 1 1 11 - 0 10 0 1 + q1 = q1’ q0’Bin B in 0 1 q1q0 00 1 1 01 0 - 11 - 0 10 1 1 24
25. Simplify Equivalent States • Two states are equivalent: Next state Output – Output and the next states Input Input are the same in all inputs (c1) State 0 1 0 1 S_3 – Can be combined together S_0 S_6 0 0 S_6 without any changed S_1 S_1 0 1 S_4/S_ S_2 S_2 0 1 behavior (c2) 5 S_3 S_7 0 1 S_3 • Reducing two equivalent S_4 S_7 0 0 S_2 S_5 S_7 0 0 states reduces hardware S_2 S_6 S_0 0 0 S_1 cost S_7 S_4 0 0 S_3 • Each FSM has one and only one simplest equivalent Equivalents states FSM New state25
26. Simplify Equivalent States Algorithm • Step 1: Find basic equivalent states (c1) 0/0 0/0 S_1 S_1 1/0 1/1 0/0 1/0 1/1 0/0 S_6 S_0 0/0 S_4 is equivalent to S_5 S_6 S_0 0/0 1/0 1/0 1/1 S_4 S_3 1/1 0/0 S_4 S_3 0/0 1/0 1/0 1/1 0/0 0/0 0/0 1/0 0/0 1/0 1/1 S_2 S_7 0/0 0/0 S_2 S_7 1/0 0/0 S_5 26
27. Simplify Equivalent States Algorithm • Step 2: Create a possible equivalent states table (c2) – Let impossible equivalent cells be empty – Fill conditions upon which two corresponding states can be equivalent S_1 và S_0 không thể tương đương Outp Next state S_1 ut S_2 và S_1 tương đương khi Inpu Input S_2 S_6 S_4 S_6 và S_4 tương đương t S_1 S_7 S_2 S_7 Stat S_3 0 1 0 1 S_6 S_3 S_4 S_3 e S_6 S_7 S_0 S_6 S_3 0 0 S_4 S_3 S_2 S_1 S_1 S_6 0 1 S_2 S_2 S_4 0 1 S_7 S_0 S_6 S_3 S_1 S_3 S_7 S_3 0 1 S_2 S_1 S_4 S_7 S_2 0 0 S_0 S_4 S_7 S_6 S_4 S_2 S_3 S_6 S_0 S_1 0 0 S_1 S_3 S_7 S_4 S_3 0 0 S_0 S_1 S_2 S_3 S_4 S_6 27
28. Simplify Equivalent States Algorithm • Step 3: Consider equivalent conditions of any two states, delete corresponding cell if the cell contains any inequivalent couple S_0  S_7 1/1 S_1 S_1  S_2 S_4 S_3 S_4  S_6 1/1 0/0 S_2 S_6 S_4 0/0 1/0 S_1 S_7 S_2 S_7 S_3 S_6 S_3 S_4 S_3 S_2 1/0 0/0 S_7 S_6 S_7 S_4 S_3 S_2 0/0 S_7 S_0 S_6 S_3 S_1 S_2 S_1 S_0 S_4 S_7 S_6 S_4 S_2 S_3 S_1 S_3 S_0 S_1 S_2 S_3 S_4 S_6 28