Contemporary Logic Design
Finite State Machine Design
Chapter #8: Finite State Machine Design
Contemporary Logic Design
Randy H. Katz University of California, Berkeley
June 1993
© R.H. Katz Transparency No. 8-1
Contemporary Logic Design
Finite State Machine Design • Counters: Sequential Circuits where State = Output
• Generalizes to Finite State Machines:
Outputs are Function of State (and Inputs)
Next States are Functions of State and Inputs
Used to implement circuits that control other circuits “Decision Making” logic
• Application of Sequential Logic Design Techniques Word Problems
Mapping into formal representations of FSM behavior Case Studies
Motivation
© R.H. Katz Transparency No. 8-2
Chapter Overview
Concept of the State Machine
• Partitioning into Datapath and Control
• When Inputs are Sampled and Outputs Asserted
Basic Design Approach
• Six Step Design Process
Alternative State Machine Representations
Contemporary Logic Design
Finite State Machine Design
• State Diagram, ASM Notation, VHDL, ABEL Description Language
Moore and Mealy Machines
• Definitions, Implementation Examples
Word Problems
• Case Studies
© R.H. Katz Transparency No. 8-3
Concept of the State Machine
Computer Hardware = Datapath + Control
Qualifiers
Control
Contemporary Logic Design
Finite State Machine Design
FSM generating sequences of control signals
Instructs datapath what to do next
“Puppeteer who pulls the strings”
Control Signal Outputs
Registers
Combinational Functional
Units (e.g., ALU) Busses
Control
State
Datapath
Qualifiers and Inputs
“Puppet”
© R.H. Katz
Transparency No. 8-4
Concept of the State Machine
Example: Odd Parity Checker
Contemporary Logic Design
Finite State Machine Design
Assert output whenever input bit stream has odd # of 1’s
Reset
Present State Input Next State Output Even 0 Even 0 Even 1 Odd 0
Odd 0 Odd 1 Odd 1 Even 1
Symbolic State Transition Table
Present State Input Next State Output 0000 0110 1011
0 [0]
Even
1
0
Diagram
1
Odd [1]
State 1101
Encoded State Transition Table
© R.H. Katz Transparency No. 8-5
Concept of the State Machine
Example: Odd Parity Checker
Next State/Output Functions NS=PSxorPI; OUT=PS
Contemporary Logic Design
Finite State Machine Design
TQ RQ
NS
\Reset
Input CLK
\Reset
Output
Input
CLK
PS/Output
DQ RQ
D FF Implementation
T FF Implementation
Input00 00 0
1
11
1
111
Clk O utput
000011
Timing Behavior: Input 1 0 0 1 1 0 1 0 1 1 1 0
© R.H. Katz Transparency No. 8-6
111
11
1
Concept of State Machine
Timing:
Contemporary Logic Design
Finite State Machine Design
When are inputs sampled, next state computed, outputs asserted? State Time: Time between clocking events
• Clocking event causes state/outputs to transition, based on inputs
• For set-up/hold time considerations:
Inputs should be stable before clocking event
• After propagation delay, Next State entered, Outputs are stable
NOTE: Asynchronous signals take effect immediately Synchronous signals take effect at the next clocking event
E.g., tri-state enable: effective immediately
sync. counter clear: effective at next clock event
© R.H. Katz Transparency No. 8-7
Contemporary Logic Design
Finite State Machine Design Example: Positive Edge Triggered Synchronous System
Concept of State Machine
State Time
On rising edge, inputs sampled outputs, next state computed
After propagation delay, outputs and next state are stable
Immediate Outputs:
affect datapath immediately
could cause inputs from datapath to change
Delayed Outputs:
take effect on next clock edge
propagation delays must exceed hold times
Clock Inputs
Outputs
© R.H. Katz Transparency No. 8-8
Concept of the State Machine
Communicating State Machines
One machine’s output is another machine’s input X
Contemporary Logic Design
Finite State Machine Design
A
C
A
D
B
D
FSM 1
CLK FSM1
X
Y=0 AC2
FSM 2
Y
Y=0
[1]
X=0
X=0
[0]
X=1 Y
X=1
D [1]
Machines advance in lock step Initial inputs/outputs: X = 0, Y = 0
FSM
Y=1
B
Y=0,1 [0] X=0
© R.H. Katz
Transparency No. 8-9
Basic Design Approach
Six Step Process
1. Understand the statement of the Specification 2. Obtain an abstract specification of the FSM
3. Perform a state mininimization
4. Perform state assignment
Contemporary Logic Design
Finite State Machine Design
5. Choose FF types to implement FSM state register 6. Implement the FSM
1, 2 covered now; 3, 4, 5 covered later;
4, 5 generalized from the counter design procedure
© R.H. Katz Transparency No. 8-10
Basic Design Approach
Example: Vending Machine FSM General Machine Concept:
deliver package of gum after 15 cents deposited single coin slot for dimes, nickels
no change
Block Diagram
Coin Sensor
N D
Reset Clk
Contemporary Logic Design
Finite State Machine Design
Step 1. Understand the problem: Draw a picture!
Vending Machine FSM
Open
Gum Release Mechanism
© R.H. Katz
Transparency No. 8-11
Contemporary Logic Design
Finite State Machine Design Step 2. Map into more suitable abstract representation
Vending Machine Example
Tabulate typical input sequences:
three nickels nickel, dime dime, nickel
two dimes
two nickels, dime
Draw state diagram:
Inputs: N, D, reset Output: open
N
Reset
S0
ND
S1 S2
D N D
S3 S4 S5 S6 [open] [open] [open]
ND
S7 S8 [open] [open]
© R.H. Katz Transparency No. 8-12
Vending Machine Example
Step 3: State Minimization
Reset
0¢
N
5¢
D
N
10¢ D
N, D
15¢ [open]
reuse states whenever possible
Present State
Inputs D N
Contemporary Logic Design
Finite State Machine Design
Next Output State Open
0¢ 00 0¢ 0 01 5¢ 0 1 0 10¢ 0 11XX 5¢ 00 5¢ 0 0 1 10¢ 0 1 0 15¢ 0 11XX 10¢ 0 0 10¢ 0 0 1 15¢ 0 1 0 15¢ 0 11XX 15¢ X X 15¢ 1
Symbolic State Table
© R.H. Katz Transparency No. 8-13
Vending Machine Example
Step 4: State Encoding
Present State Inputs Q1 Q0 D N
Contemporary Logic Design
Finite State Machine Design
Next State Output D1 D0 Open
0000000 01010 10100 11XXX 0100010 01100 10110 11XXX 1000100 01110 10110 11XXX 1100111 01111 10111 11XXX
© R.H. Katz
Transparency No. 8-14
Vending Machine Example
Step 5. Choose FFs for implementation D FF easiest to use
Contemporary Logic Design
Finite State Machine Design
Q1 Q0 Q1 Q1 Q0 Q1 Q1 Q0 Q1 DNDNDN
NNN DDD
Q0 Q0 Q0
K-map for D1
K-map for D0
Q1 D
D1
CLK \ Q1
K-map for Open
D1 = Q1 + D + Q0 N
D0=NQ0 + Q0N + Q1N + Q1D OPEN = Q1 Q0
8 Gates
Q1
DQ RQ
Q0 N
N \ Q0
Q0 \N
Q1 N
Q1 D
\reset
D0 CLK
\reset
OPEN
Q0 \ Q0
DQ RQ
© R.H. Katz
Transparency No. 8-15
Vending Machine Example
Step 5. Choosing FF for Implementation J-K FF
Contemporary Logic Design
Finite State Machine Design
Present State Inputs Next State J1 K1 J0 K0 Q1Q0 DN D1D0
0000000X0X
01 10 11
01 00 01 10 11
10 00 01 10 11
11 00 01 10 11
010X1X 101X0X XXXXXX 010XX0 101XX1 111XX0 XXXXXX 10X00X 11X01X 11X01X XXXXXX 11X0X0 11X0X0 11X0X0 XXXXXX
Remapped encoded state transition table
© R.H. Katz Transparency No. 8-16
Vending Machine Example
Implementation:
Q1 Q0 Q1 Q1 Q0 Q1 DN DN
NN DD
Contemporary Logic Design
Finite State Machine Design
Q0
Q0
J1=D + Q0N K1 = 0
J0=Q0N + Q1D K0 = Q1 N
K-map for J1
K-map for K1
Q1 Q0 Q1
Q1 Q0 Q1
DN DN
N
N NQ0 Q1
J KRQ
DD Q0
Q0
D \ Q0
N
Q1
D
\ Q1
N
\reset
CLK
CLK
\ Q1
Q0 \ Q0
OPEN
K-map for J0
K-map for K0
JQ KR Q
Q
© R.H. Katz
7 Gates Transparency No. 8-17
Moore and Mealy Machine Design Procedure
Contemporary Logic Design
Finite State Machine Design
Mealy Machine
Outputs depend on state AND inputs
Input change causes an immediate output change
Asynchronous signals
Definitions
Xi Inputs
Z k Outputs
State Feedback
Combinational Logic for Outputs and
Next State
Xi Inputs
Moore Machine
Outputs are function solely of the current
state
Outputs change synchronously with
state changes
State Register
State Register
Combinational Logic for Next State (Flip-flop Inputs)
Clock
state feedback
Clock
Comb. Logic for Outputs
Zk Outputs
© R.H. Katz Transparency No. 8-25
Moore and Mealy Machines
State Diagram Equivalents
Contemporary Logic Design
Finite State Machine Design
Mealy Machine
Reset/0
Reset/0
(N D + Reset)/0 0¢
N/0
N D + Reset
Moore Machine
Reset
0¢
5¢ N D/0
[0] Reset N
5¢
[0] N
10¢
D [0] N+D
15¢ [1]
D/0
N D/0
Reset/1
N D
D
N D
Reset
D/1
N/0 10¢
N+D/1 15¢
Outputs are associated with Transitions
Outputs are associated with State
© R.H. Katz Transparency No. 8-26
Moore and Mealy Machines
States vs. Transitions
Contemporary Logic Design
Finite State Machine Design
Mealy Machine typically has fewer states than Moore Machine for same output sequence
0 0
[0] 0
1
[0] 1
2 [1]
0/0
1/0 1
1/1
Same I/O behavior: Assert a single output whenever at least two 1’s have been received in a sequence.
0
1
0
0/0
Different # of states
S0 00
IN
S1 01
1
S0 0
IN
S1 1
IN H.OUT
Equivalent ASM Charts
IN
S2 H.OUT
IN
10
© R.H. Katz
Transparency No. 8-27
Moore and Mealy Machines
Timing Behavior of Moore Machines
Reverse engineer the following:
Contemporary Logic Design
Finite State Machine Design
J C
Q KRQ
X \B
XA \A
FFa Clk
XZ
\B \Reset
Input X Output Z State A, B = Z
\Reset
J
Q C
KRQ
X \A
FFb
Two Techniques for Reverse Engineering:
• Ad Hoc: Try input combinations to derive transition table • Formal: Derive transition by analyzing the circuit
© R.H. Katz Transparency No. 8-28
Moore and Mealy Machines
Ad Hoc Reverse Engineering
Contemporary Logic Design
Finite State Machine Design
Behavior in response to input sequence 1 0 1 0 1 0:
100
X
Clk
A
Z \Reset
Reset X=1 X=0 X=1 X=0 X=1 X=0 X=0 AB = 00 AB = 00 AB = 11 AB = 11 AB = 10 AB = 10 AB = 01 AB = 00
Partially Derived State Transition Table
AB X A+B+ Z 000??0 1110 010001 1??1 100100 1010 110111 1101
© R.H. Katz Transparency No. 8-29
Moore and Mealy Machines
Formal Reverse Engineering
Contemporary Logic Design
Finite State Machine Design
Derive transition table from next state and output combinational functions presented to the flipflops!
Ja = X Ka = X • B Z = B Jb = X Kb = X xor A
FF excitation equations for J-K flipflop:
A+ = Ja • A + Ka • A = X • A + (X + B) • A B+=Jb•B + Kb•B = X•B + (X•A + X•A)•B
Next State K-Maps: AB
00 01 11 10 00011 1111
X
XAB00 01 11 10
0001 1110
A+
State 00, Input 0 -> State 00 State 01, Input 1 -> State 11
0
B+
© R.H. Katz
Transparency No. 8-30
Moore and Mealy Machines
Reverse Engineering a Mealy Machine
Contemporary Logic Design
Finite State Machine Design
Clk
\A AXB
A X
B
Z
DA
\A
\Reset
DA \X B
\XX A
\B
\Reset
DQ CRQ
JQ C KRQ
\X
Input X, Output Z, State A, B
State register consists of D FF and J-K FF
© R.H. Katz
Transparency No. 8-32
Moore and Mealy Machine
Ad Hoc Method
Contemporary Logic Design
Finite State Machine Design
Signal Trace of Input Sequence 101011:
100
X
Clk
A
B
Z \Reset
Note glitches in Z!
Outputs valid at following falling clock edge
Reset AB=00
X=1 X=0
AB=00 AB=00 AB=01
X=1 X=1 AB=10 AB=01
X=1 X=0 AB=11
Z=0 Z=0 Z=0 Z=0 Z=1 Z=1 Z=0
Partially completed state transition table based on the signal trace
ABX A+B+Z 000010 1000 010??? 1110 100??? 1011 110101
1???
© R.H. Katz Transparency No. 8-33
Moore and Mealy Machines
Formal Method
A+ = B • (A + X) = A • B + B • X
B+=Jb•B + Kb•B = (AxorX)•B + X•B
=A•B•X + A•B•X + B•X
Contemporary Logic Design
Finite State Machine Design
Z=A•X+B•X
Missing Transitions and Outputs:
State 01, Input 0 -> State 00, Output 1 State 10, Input 0 -> State 00, Output 0 State 11, Input 1 -> State 11, Output 1
© R.H. Katz Transparency No. 8-34
Moore and Mealy Machines
Synchronous Mealy Machine
Contemporary Logic Design
Finite State Machine Design
Clock
Combinational Logic for Outputs and
Next State
Xi Zk
Inputs
Outputs
state feedback
State Register
Clock
latched state AND outputs avoids glitchy outputs!
© R.H. Katz
Transparency No. 8-36
Contemporary Logic Design
Finite State Machine Design Mapping English Language Description to Formal Specifications
Four Case Studies:
• Finite String Pattern Recognizer
• Complex Counter with Decision Making • Traffic Light Controller
• Digital Combination Lock
We will use state diagrams and ASM Charts
Finite State Machine Word Problems
© R.H. Katz
Transparency No. 8-37
Finite State Machine Word Problems
Finite String Pattern Recognizer
Contemporary Logic Design
Finite State Machine Design
A finite string recognizer has one input (X) and one output (Z). The output is asserted whenever the input sequence …010… has been observed, as long as the sequence 100 has never been seen.
Step 1. Understanding the problem statement
Sample input/output behavior:
X: 00101010010… Z: 00010101000…
X: 11011010010… Z: 00000001000…
© R.H. Katz
Transparency No. 8-38
Finite State Machine Word Problems
Finite String Recognizer
Contemporary Logic Design
Finite State Machine Design
Step 2. Draw State Diagrams/ASM Charts for the strings that must be recognized. I.e., 010 and 100.
S1 [0]
S2 [0]
S3 [1]
S4 [0]
S5 [0]
S6 [0]
Moore State Diagram Reset signal places
FSM in S0
Reset [0]
S0
Outputs
Loops in State
© R.H. Katz
Transparency No. 8-39
Finite State Machine Word Problems
Finite String Recognizer
Contemporary Logic Design
Finite State Machine Design
Exit conditions from state S3: have recognized …010 if next input is 0 then have …0100!
if next input is 1 then have …0101 = …01 (state S2)
S1 [0]
S2 [0]
S3 [1]
S4
Reset [0]
S0
0
[0]
1
S5 [0]
S6 [0]
0
© R.H. Katz
Transparency No. 8-40
Finite State Machine Word Problems
Finite String Recognizer
Contemporary Logic Design
Finite State Machine Design
Exit conditions from S1: recognizes strings of form …0 (no 1 seen) loop back to S1 if input is 0
Exit conditions from S4: recognizes strings of form …1 (no 0 seen) loop back to S4 if input is 1
0
S1
[0]
S2 [0]
S3 [1]
0
[0]
1
Reset [0]
S0
S4
1
S5 [0]
S6 [0]
0
© R.H. Katz
Transparency No. 8-41
Finite State Machine Word Problems
Finite String Recognizer
S2, S5 with incomplete transitions
Contemporary Logic Design
Finite State Machine Design
S2 = …01; If next input is 1, then string could be prefix of (01)1(00) S4 handles just this case!
S5 = …10; If next input is 1, then string could be prefix of (10)1(0) S2 handles just this case!
0
S1
[0]
S2 [0]
S3 [1]
0
[0]
1
Reset [0]
S0
S4 1
Final State Diagram
1
1 S5 [0]
0 S6 [0]
© R.H. Katz
Transparency No. 8-42
Finite State Machine Word Problems
Finite String Recognizer
Contemporary Logic Design
Finite State Machine Design
Review of Process:
• Write down sample inputs and outputs to understand specification
• Write down sequences of states and transitions for the sequences to be recognized
• Add missing transitions; reuse states as much as possible
• Verify I/O behavior of your state diagram to insure it functions like the specification
© R.H. Katz Transparency No. 8-44
Finite State Machine Word Problems
Complex Counter
Contemporary Logic Design
Finite State Machine Design
A sync. 3 bit counter has a mode control M. When M = 0, the counter counts up in the binary sequence. When M = 1, the counter advances through the Gray code sequence.
Binary: 000, 001, 010, 011, 100, 101, 110, 111 Gray: 000, 001, 011, 010, 110, 111, 101, 100
Valid I/O behavior:
Mode Input M 0
0
1
1
1
0
0
Current State 000
001
010
110
111
101
110
Next State (Z2 Z1 Z0) 001
010
110
111
101
110
111
© R.H. Katz
Transparency No. 8-45
Finite State Machine Word Problems
Complex Counter
One state for each output combination Add appropriate arcs for the mode control
Contemporary Logic Design
Finite State Machine Design
Reset [000]
S1 [001]
S2 [010]
S0
S0
000
S1
001 0M1
H.Z0
S3 M0 [011]
1
M
S4 [100]
S5 [101]
S6 [110]
S7 [111]
S6 110 0
H.Z2 S4 100 H.Z1 H.Z2
S7111 M
H.Z2 0 H.Z1
1
S2 010 S3 011 H.Z1 H.Z1 H.Z0
1
H.Z0
0M1 H.Z0
S5 101 H.Z2
0M1
© R.H. Katz Transparency No. 8-46
Finite State Machine Word Problems
Traffic Light Controller
Contemporary Logic Design
Finite State Machine Design
A busy highway is intersected by a little used farmroad. Detectors C sense the presence of cars waiting on the farmroad. With no car on farmroad, lights remain green in highway direction. If vehicle on farmroad, highway lights go from Green to Yellow to Red, allowing the farmroad lights to become green. These stay green only as long as a farmroad car is detected but never longer than a set interval. When these are met, farm lights transition from Green to Yellow to Red, allowing highway to return to green. Even if farmroad vehicles are waiting, highway gets at least a set interval as green.
Assume you have an interval timer that generates a short time pulse (TS) and a long time pulse (TL) in response to a set (ST) signal. TS is to be used for timing yellow lights and TL for green lights.
Farmroad
C FL
Highway
HL
Highway
FL C
HL Farmroad
© R.H. Katz
Transparency No. 8-48
Finite State Machine Word Problems
Traffic Light Controller
Picture of Highway/Farmroad Intersection: Farmroad
C FL
Contemporary Logic Design
Finite State Machine Design
HL
Highway
Highway
FL C
HL Farmroad
© R.H. Katz
Transparency No. 8-49
Finite State Machine Word Problems
Traffic Light Controller
• Tabulation of Inputs and Outputs:
Contemporary Logic Design
Finite State Machine Design
Input Signal
reset C
TS TL
Output Signal
HG, HY, HR FG, FY, FR ST
Description
place FSM in initial state detect vehicle on farmroad short time interval expired long time interval expired
Description
assert green/yellow/red highway lights assert green/yellow/red farmroad lights start timing a short or long interval
• Tabulation of Unique States: Some light configuration imply others
State Description
S0 Highway green (farmroad red)
S1 Highway yellow (farmroad red)
S2 Farmroad green (highway red)
S3 Farmroad yellow (highway red)
© R.H. Katz Transparency No. 8-50
Finite State Machine Word Problems
Traffic Light Controller
Compare with state diagram:
Contemporary Logic Design
Finite State Machine Design
S0 TL•C/ST
TL + C Reset
TS/ST S3
S0: HG S1: HY S2: FG S3: FY
TS
S1 TS/ST
TS
TL + C/ST S2
TL • C
Advantages of State Charts:
• Concentrates on paths and conditions for exiting a state
• Exit conditions built up incrementally, later combined into single Boolean condition for exit
• Easier to understand the design as an algorithm
© R.H. Katz Transparency No. 8-55
Finite State Machine Word Problems
Digital Combination Lock
Contemporary Logic Design
Finite State Machine Design
“3 bit serial lock controls entry to locked room. Inputs are RESET, ENTER, 2 position switch for bit of key data. Locks generates an UNLOCK signal when key matches internal combination. ERROR light illuminated if key does not match combination. Sequence is: (1) Press RESET, (2) enter key bit, (3) Press ENTER, (4) repeat (2) & (3) two more times.”
Problem specification is incomplete:
• how do you set the internal combination? • exactly when is the ERROR light asserted?
Make reasonable assumptions:
• hardwired into next state logic vs. stored in internal register
• assert as soon as error is detected vs. wait until full combination has been entered
Our design: registered combination plus error after full combination © R.H. Katz Transparency No. 8-57
Finite State Machine Word Problems
Digital Combination Lock
Contemporary Logic Design
Finite State Machine Design
Understanding the problem: draw a block diagram …
Combination Lock FSM
Operator Data
Internal Combination
Inputs:
Reset Enter Key-In L0, L1, L2
RESET
ENTER
KEY-IN
UNLOCK
ERROR
L0
L1
L2
Outputs:
Unlock Error
© R.H. Katz Transparency No. 8-58
Finite State Machine Word Problems
Reset + Enter Reset
Start
Reset • Enter
Comp0
Contemporary Logic Design
Finite State Machine Design
Digital Combination Lock
KI = L0
Enter
Idle0
Enter
Comp1 KI = L1
Idle1
Enter Comp2
KI ° L0
Equivalent State Diagram Enter
Enter Idle0′
Enter Error1
Enter
Idle1′ Enter
Error2
KI ° L1
KI = L2
KI ° L2
Reset
[Unlock]
Reset Start
Reset [Error]
Reset Start
Done
Error3
© R.H. Katz
Transparency No. 8-62
Chapter Review
Basic Timing Behavior an FSM
Contemporary Logic Design
Finite State Machine Design
• when are inputs sampled, next state/outputs transition and stabilize
• Moore and Mealy (Async and Sync) machine organizations outputs = F(state) vs. outputs = F(state, inputs)
First Two Steps of the Six Step Procedure for FSM Design
• understanding the problem
• abstract representation of the FSM
Abstract Representations of an FSM
• ASM Charts, Hardware Description Languages
Word Problems
• understand I/O behavior; draw diagrams
• enumerate states for the “goal”; expand with error conditions • reuse states whenever possible
© R.H. Katz Transparency No. 8-64