State Machines
State Machines
State Machines
a_r 0 D Q D Q p_r
a_i 1 CE CE
b_r 0
b_i 1
D Q D Q p_i
b_sel CE CE
pp1_ce
pp2_ce clk clk
sub
p_r_ce
p_i_ce
clk
1 0 0 1 0 – 0 0
2 1 1 0 1 – 0 0
3 0 1 1 0 1 1 0
4 1 0 0 1 – 0 0
5 – – 0 0 0 0 1
Finite-State Machines
Used the implement control sequencing
A FSM is defined by
set of inputs
set of outputs
set of states
initial state
transition function
output function
States are steps in a sequence of transitions
There are “Finite” number of states.
FSM in Hardware
current_state next
D Q
state
reset reset logic
clk clk
output
logic outputs
inputs
Mealy FSM
only
State Encoding
Encoded in binary
N states: use at least log2N bits
Encoded value used in circuits for transition
and output function
encoding affects circuit complexity
Optimal encoding is hard to find
CAD tools can do this well
One-hot works well in FPGAs
Often use 000...0 for idle state
reset state register to idle
Digital Design — Chapter 4 — Sequential Basics 12
Verilog
FSMs in Verilog
Use parameters for state values
Synthesis tool can choose an alternative
encoding
Example
0, 0
0, 1
δ defined by diagram 0, 0
s3 0, 1
1, 1
1, 0
function
s1 1, 0 / 1, 0, 0 s2
Annotate states for 0, 0 / 0, 0, 0
1, 0 0, 0
Moore-style outputs
Annotate arcs for
1, 1 / 1, 1, 1
/ 0, 1, 1
Mealy-style outputs
Example 0, 0 / 0, 0, 0
s3 0, 1 / 0, 1, 1
x1, x2: Moore-style 1, 1 / 1, 1, 1
0, 1