CS 2204: Digital Circuits
Lecture 17
Finite state machines
We will now discuss a general method to design sequential
circuits from a “specification”
Example: Car speed-limiter
w = 0 if below_limit,
1 if above limit.
Speed limiter
z = 0 no break,
1 apply break.
Apply break if car exceeds
speed-limit for two consecutive
intervals
State transition diagram
Two/
z=0
One/
z=0
Apply_Break/
z=1
START
w=1 w=1 w=1
w=0
w=0
w=0
Next state table after state assignment
Two
One
Apply_Brake
Dont care
Next state as a function of current state/input
Output as a function of current state
NOTE: but NOT input w. When the output is only a function of
the current state, we call it a “moore” machine.
Next-state Output
Final
implementation
Resetn
input
initializ
es FFs to
0,0 state
Timing diagram
Verilog implementation
Another example: Pattern detector
– Single bit input w.
– Output z = 1 if the last 4 bits are 1011, 0 otherwise.
A
z=0
B
z=0
C
z=0
START
w=1 w=0 w=1
w=0
w=1
w=1
w=0
D
z=0
E
z=1
w=0
w=0
w=1
Practice module pattern (Clock, Resetn, w, z);
input Clock, Resetn, w;
output z;
reg [3:1] y, Y;
parameter [3:1] A=3’b000, B=3’b001 ….;
always @(w,y)
case (y)
A: if(w) Y = B;
else Y = A;
B:….
endcase
Always @(negedge Resetn, posedge Clock)
if (Resetn==0) y<=A;
else y <= Y;
//Define output
assign z = (y==E);
endmodule
State encoding
Recall that you can arbitrarily assign states.
two
one
apply_break
New State Assignment
Why does this help?
Recall that you can arbitrarily assign states.
two
one
apply_break
New State Assignment
Y1 = w;
Y2 = w.y1;
z = y2;
Optimized circuit
“One-hot” encoding
A “simple” state encoding that uses N bits if there are N
states (note, in theory we only need logN bits).
Note: all one-hot encodings have the same circuit size!
two
one
apply_break
New spec.
We will now discuss a general method to design sequential
circuits from a “specification”
Example: Car speed-limiter
w = 0 if below_limit,
1 if above limit.
Speed limiter
z = 0 no break,
1 apply break.
IMMEDIATELY Apply break if car
exceeds speed-limit for two
consecutive intervals
Timing diagram
Previously, brake applied after two consecutive w=1
Now, we want brake applied immediately!
Moore Vs. Mealy machines
Moore Machine: output depends
only on the current state
We cant use a Moore
machine for immediate
braking!
Mealy Machine: output depends
on current state AND input.
Each edge has an
associated output
value!
State transition diagram for mealy machine
Two One Apply_Break
START
w=1/z=0 w=1/z=1 w=1/z=1
w=0/z=0
w=0/z=0
w=0/z=0
A further simplification
Two One Apply_Break
START
w=1/z=0 w=1/z=1 w=1/z=1
w=0/z=0
w=0/z=0
w=0/z=0
MERGE THESE TWO STATES!
Simplified state transition graph
A B
START
w=1/z=0 w=1/z=1
w=0/z=0
w=0/z=0
Practice Write Verilog for the 1011 pattern detector
Module pattern (Clock, Resent, w, z);
input Clock, Resent, w;
output z;
reg [ : ] y, Y;
parameter [ : ] A= ….
always @(w,y)
case (y)
….
endcase
Always @(negedge Resetn, posedge Clock)
if (Resetn==0) y<=A;
else y <= Y;
//Define output
….
endmodule
WHAT CHANGES?