Week 5
Finite State Machine design examples
ENGN3213/6213
Digital Systems and Microprocessors
Whats on today
Three complete examples of finite state
machine designs
An alarm system
A pedestrian traffic controller
A vending machine
ENGN3213/6213 - Week 5
Resources
Wakerly Ch. 7.7 for yet another example
of FSM design
Wakerly Ch. 7.13 describes standards for
Verilog coding of state machines
ENGN3213/6213 - Week 5
Example 1: An alarm system
Problem statement:
The alarm should sound when the sensor is
triggered by the burglar walking through
The sound stops upon pressure of a reset
button (but only if the sensor at that time is not
picking up any intruders).
ENGN3213/6213 - Week 5
Example 1: An alarm system (2)
First we identify the inputs and outputs
Inputs:
The trigger (binary signal (triggered/non triggered))
The reset button (also binary (pressed/depressed))
States:
Quiet (Armed)
Sound alarm (Sound)
Outputs:
Alarm bell (on/off)
ENGN3213/6213 - Week 5
Example 1: An alarm system (3)
The FSM is a Moore machine
Trigger
State
Memory
Alarm
Reset
The output is a function of the state alone
When the state is Sound the output is 1 (Alarm ON)
When the state is Armed the output is 0 (Alarm OFF)
ENGN3213/6213 - Week 5
Example 1: An alarm system (4)
The state diagram
Reset
Trigger
S0
Armed
0
Trigger
S1
Sound
1
Reset AND
NOT(Trigger)
ENGN3213/6213 - Week 5
Example 1: An alarm system (4)
Next state table
A=Armed
S=Sound
T=Trigger signal
R=Reset signal
ENGN3213/6213 - Week 5
State
Input
Next
state
Output
TR
OFF
TR
OFF
TR
OFF
TR
OFF
TR
ON
TR
ON
TR
ON
TR
ON
8
Example 1: An alarm system (5)
Next state table with
binary inputs
Note that I use the
Gray code
I can use this table as
a Karnaugh Map to
find a function which
associates the inputs
with the next state.
Next state equation:
S* = T + RS
ENGN3213/6213 - Week 5
T
inputs
TR
00 01
11
10
state
S
RS
T
9
Example 1: An alarm system (6)
We are now ready to turn this into a circuit!
1 binary state = 1 flip flop
output = state (the output logic is trivial)
next state logic as per previous slide
S*
T
clk
ENGN3213/6213 - Week 5
CK Q
10
Example 1: An alarm system (7)
Now the Verilog code
module MyAlarm(input wire T, R, clk,
output wire alarm_ON);
reg state, Snext;
always @(*) Snext=T|(~R & state); //next-state logic
always @(posedge clk) state<=Snext; //state memory (flip flop)
assign alarm_ON=state; //output logic, trivial
endmodule
/*Design Finished! Hooray!*/
ENGN3213/6213 - Week 5
11
Example 2: A pedestrian traffic controller
Problem statement:
Design a traffic light controller with an input button:
request. There are 5 lights (outputs): WALK/HALT
for pedestrians and GREEN/ORANGE/RED for cars.
The pedestrian will press the request button and the
lights will shift for the cars until RED, then the WALK
sign will be illuminated. After some time, WALK will
shift to HALT and the cars will get a GREEN light until
the next pedestrian button press.
ENGN3213/6213 - Week 5
12
Example 2: A pedestrian traffic controller (2)
Identifying the main features
Inputs
Request button (well also need a reset input well see this shortly)
Outputs
The 5 lights: R,O,G, WALK, HALT
States
S0: GREEN, HALT
S1: ORANGE, HALT
S2: RED, WALK
S3: RED, HALT
Note how the states correspond to output combinations (the input
button has no direct effect on the lights).
This is how I can tell right away that it is a Moore Machine!
ENGN3213/6213 - Week 5
13
Example 2: A pedestrian traffic controller (3)
The state diagram
Reset
Request
Request
s0
00
G, HALT
s1
01
O, HALT
Timer
Timer
s2
11
R,WALK
s3
10
R,HALT
Timer
Note that the transition between s0 and s1 depends on the request
button, while s1s2s3s0 is going to be a timed sequence of
states. (for which we will use an event sequencer acting as a timer)
Note the reset function, it means that at any time if the system is
reset it will go to state 3, regardless of the state it is in.
ENGN3213/6213 - Week 5
14
Example 2: A pedestrian traffic controller (4)
Next state table
Again note the use of
Gray code
ENGN3213/6213 - Week 5
State
S[1:0]
Input
Next
state
Output
00
Req
01
G,H
01
Req
11
O,H
11
Req
10
R,W
10
Req
00
R,H
00
Req
00
G,H
01
Req
11
O,H
11
Req
10
R,W
10
Req
00
R,H
15
Example 2: A pedestrian traffic controller (5)
Karnaugh Maps for next
state logic
input
Req
00 01
11
00 01
11
10
input
Req
One for each state!
state
S
state
S
10
Table for S[1]*
0
S[1]* =S[0]
0
S[0]* = S[1](Req+S[0])
Table for S[0]*
ENGN3213/6213 - Week 5
16
Example 2: A pedestrian traffic controller (6)
Circuit diagram for state transitions (with reset)
Reset
S*[1]
D S Q
S[1]
CK
Req
S*[0]
S[0]
CK C
CK
ENGN3213/6213 - Week 5
17
Example 2: A pedestrian traffic controller (7)
Output logic (a simple decoder)
S[1]
State
S[1:0]
Output
00
G,H
01
O,H
11
R,W
10
R,H
S[0]
R
O
W
H
ENGN3213/6213 - Week 5
18
Example 2: A pedestrian traffic controller (8)
Delayed state transitions
The only problem with the design shown is that once the request
button is pressed the system will cycle through all the other
states in a matter of 4 clock cycles.
With a MHz clock that is not long enough to cross the road!
We need to introduce the last part of the circuit: the event
sequencer.
Implemented as a counter attached
0
S*
to a decoder which maps desired
1
count values with a 1 output.
This output can be used to
EN
enable the flip-flops.
de
Only on those pre-determined
Counter
co
counts will the transition be
der
allowed to occur.
CK
ENGN3213/6213 - Week 5
Q
CK
19
Example 2: A pedestrian traffic controller (9)
module Traffic(input wire Req, Reset, clk,
output reg R,O,G,W,H);
reg [1:0] S, Snext;
reg [31:0] count; //a 32-bit counter
reg En;
always @(*) begin //next-state logic
Snext[0]=~S[1]&(Req|S[0]);
Snext[1]=S[0];
end
always @(posedge clk) begin //state memory (flip flop)
if (Reset) S<=2b10;
else if (En||(S==2b00)) S<=Snext;
end
always @(posedge clk) begin //counter logic
if(S==2b00||Reset) count<=32d0; //reset at s0 or reset btn push
else count<=count+1;
end
/*continues in the next slide*/
ENGN3213/6213 - Week 5
20
Example 2: A pedestrian traffic controller (10)
always @(*) begin //decoder logic
case(count)
32d100000000 : En=1; //state s1 will last 100 clock cycles
32d500000000 : En=1; //state s2 will last 400 clock cycles
32d600000000 : En=1; //state s3 will last 100 clock cycles
default : En=0;
endcase
end
always @(*) begin //output logic
case(S)
2b00 : begin R=0; O=0; G=1; W=0; end
2b01 : begin R=0; O=1; G=0; W=0; end
2b11 : begin R=1; O=0; G=0; W=1; end
2b10 : begin R=1; O=0; G=0; W=0; end
default: begin R=1; O=0; G=0; W=0; end
endcase
H=~W;
end
endmodule
ENGN3213/6213 - Week 5
21
Example 3: A vending machine
Problem Statement
Design a state machine controller for a vending
machine to satisfy the following:
Sell one item worth 75c
Return change and deliver the item when the coins inserted
into the machine exceed the sum of 75c
Return all coins upon request without releasing the item
Input variables :
COIN indicating if a coin is deposited,
RETURN if the return change button is pushed
SUM which is the output of the coin tallying device internal to
the vending machine. SUM consists of three inputs indicating
whether the current coin entry is <,=,> the price of the product.
ENGN3213/6213 - Week 5
22
Example 3: A vending machine (2)
Inputs/Outputs
input
abbreviation
output
abbreviation
coin
return
CN
RTN
sum<75
sum=75
sum>75
change-available
SM0
SM1
SM2
CA
release-candy
return-change
return-all-coins
RC
RCH
RAC
ENGN3213/6213 - Week 5
23
Example 3: A vending machine (3)
State transition table
Present
state
Description
Next state
Release
candy
Return
all coins
Return
change
s0
idle
s0 if CN=0, RTN=0
s1 if CN=1, RTN=0
s5 if CN=0, RTN=1
s1
coin in, check total
s0 if SM0=1
s2 if SM1=1
s3 if SM2=1
s2
release candy
s0
s3
check for change
s5 if CA=0
s4 if CA=1
s4
return change
s2
s5
return all coins
s0
ENGN3213/6213 - Week 5
24
Example 3: A vending machine (3)
State codes
For this example we use a one-hot coding for the states
Only one flip-flop is storing a 1 at any one time.
Present
state
State code
(ABCDEF)
Description
s0
000001
idle
s1
000010
coin in, check total
s2
000100
release candy
s3
001000
check for change
s4
010000
return change
s5
100000
return all coins
ENGN3213/6213 - Week 5
25
Example 3: A vending machine (4)
State diagram
CNRTN
CNRTN
s5
return all coins
100000 (A)
s0 idle
000001 (F)
Reset
SM0
CN
s2
return candy
000100 (D)
s4
return change
010000 (B)
SM1
s1 coin in
000010 (E)
ENGN3213/6213 - Week 5
SM2
CA
CA
s3
check change
001000 (C)
26
Example 3: A vending machine (5)
General architecture of the system
6
CN
RTN
DA
D Q
CK
QA
DB
D Q
CK
QB
DC
D Q
CK
QC
DD
D Q
CK
QD
DE
D Q
CK
QE
DF
D Q
CK
QF
SM0
SM1
Next state
logic
SM2
CA
Reset
ENGN3213/6213 - Week 5
RC
Output
logic
RCH
RAC
clk
27
Example 3: A vending machine (6)
The Reset signal is wired so as to force the state s0=000001
The one-hot coding approach uses more flip flops than standard binary or
Gray coding (6 FF, 3 would be more than enough to map 3 states) but makes
next-state logic very simple (almost immediate from the state diagram)
Next-state logic:
DA = (QF CN RTN) + (QC CA)
(the next state will be A (s5) if the current state is C (s3) and CA=0 or if the current state
is F(s0) and RTN=1 with CN=0)
DB = QC CA
DC = QE SM2
DD = QE SM1 + QB
DE = QF CN
DF = (QF CN RTN) + (QE SM0) + QD + QA
ENGN3213/6213 - Week 5
28
Example 3: A vending machine (7)
The output logic is also very simple thanks to one-hot
coding:
RC = QD
RCH = QB
RAC = QA
ENGN3213/6213 - Week 5
29
Summing up
3 examples of state machine design
The main state machine design workflow ideas:
Identify inputs and outputs
Assign states (a variety of state encoding options available)
Determine transitions (with tables / diagrams) without ambiguity
Is the output a function of the state alone or of both state and input?
Moore / Mealy Machine?
Determine next-state and output logic
Assemble in circuit schematic / Verilog
Keep next-state logic, state memory and output logic separate
Keep next-state logic and output logic combinational
Keep state memory sequential
ENGN3213/6213 - Week 5
30
