F5 - FSM Modelling and Synthesis PDF
F5 - FSM Modelling and Synthesis PDF
F5 - FSM Modelling and Synthesis PDF
k='0'
k='1'
Input vs Output - Moore
Input Sequence I1 I2
O1 O2 Output Sequence
Inputs
Clk
TD(I->DFF) TD(DFF->O)
Three vs Two process model
• Three-process model
– One entity
– Model each functional box in separate processes
– Drawback: replication of code makes it harder to trace down bugs
• Two-process model
– One entity
– Combinational logic (Next state logic and Output logic) processes
are merged
– Sequential logic modelled in a separate process
– Advantage: no replication of code
FSM Double Process Model
Outputs
Inputs
NextState/
Output Next
State Registers
Decoder
Reset
Clk
Present State
Moore Machine (ctd.)
Architecture moore of fsm is
type state_type is (S0,S1);
signal next_state,pres_state:state_type;
begin
logic: process(pres_state,k)
begin
next_state <= pres_state;
case pres_state is
when S0 =>
q <= '1';
if (k='0') then
next_state <= S1;
end if;
when S1 =>
q <= '0';
if (k='1') then
next_state <= S0;
end if;
end case;
end process;
Moore Machine (ctd.)
regs: process(clk,reset)
begin
if (reset=‘1’) then -- asynchronous reset
pres_state <= S0;
elsif (clk=‘1’) and clk’event then
pres_state <= next_state;
end if;
end process;
end moore;
Mealy Machine
k='0'|0
k='1'|1 S0 S1 k='0'|0
k='1'|1
Input vs Output - Mealy
Input Sequence I1 I2
O1 O2 Output Sequence
Inputs
Clk
TD(I->DFF) TD(DFF->O)
TD(I->O)
Mealy Machine (ctd.)
Architecture mealy of fsm is
type state_type is (S0,S1);
signal next_state,pres_state:state_type;
begin
logic: process(pres_state,k)
begin
next_state <= pres_state;
case pres_state is
when S0 =>
if (k='0') then
q<='0';
next_state <= S1;
else
q<='1';
end if;
when S1 =>
if (k='1') then
next_state <= S0;
q<='1';
else
q<='0';
end if;
end case;
end process;
Latched Mealy vs Moore Machine
k='0'|0
k='1'|1 S0 S1 k='0'|0
k='1'|1
Input Sequence I1 I2
O1 O1 O2 Output Sequence
Inputs
Clk
TD(I->DFF)
Latched Mealy
Architecture latched_mealy of fsm is
type state_type is (S0,S1);
signal next_state,pres_state:state_type;
signal next_q:bit;
begin
logic: process(pres_state,k)
begin
next_state <= pres_state;
case pres_state is
when S0 =>
if (k='0') then
next_q<='0';
next_state <= S1;
else
next_q<='1';
end if;
when S1 =>
if (k='1') then
next_state <= S0;
next_q<='1';
else
next_q<='0';
end if;
end case;
…
Latched Mealy
regs: process(clk,reset)
begin
if (clk='1') and clk'event then
if (reset='1') then -- synchronous reset
q<='0';
pres_state<=S0;
else
q<=next_q;
pres_state<=next_state;
end if;
end if;
end process;
end latched_mealy;
Single-process FSMs = Latched Mealy
Architecture latched_mealy of fsm is
type state_type is (S0,S1);
signal state:state_type;
Begin
process(clk)
begin
if rising_edge(clk) then
case state is
when S0 =>
if (k='0') then
q<='0';
state <= S1;
else
q<='1';
end if;
when S1 =>
if (k='1') then
state <= S0;
q<='1';
else
q<='0';
end if;
end case;
end if;
end process;
end latched_mealy;
(Input vs Output – Latched Moore)
Input Sequence I1 I2
O1 O1 O2 Output Sequence
Inputs
Clk
k='0'|0
k='1'|1 S0 S1 k='0'|0
k='1'|1
FSM Synthesis Example:
Mealy Machine (ctd.)
Architecture mealy of fsm is
type state_type is (S0,S1);
signal next_state,pres_state:state_type;
begin
logic: process(pres_state,k)
begin
next_state <= pres_state;
case pres_state is
when S0 =>
if (k='0') then
q<='0';
next_state <= S1;
else
q<='1';
end if;
when S1 =>
if (k='1') then
next_state <= S0;
q<='1';
else
q<='0';
end if;
end case;
end process;
Communicating FSMs
What will happen when we connect two (or more) FSMs together?
N.L. O.L.
N.L. O.L.
Outputs
Inputs
N.L. O.L.
N.L. O.L.
Inputs Outputs
TD(I->O) TD(I->O)
N.L. O.L.
N.L. O.L.
Outputs
Inputs
C.P. TD=max(TD1,TD2)
Pros and Cons
• Moore
• Pros – Output stable during whole period
• Cons – Output response delayed 1 clock cycle, glitches may exist on
output (due to Hazard)
• Mealy
• Pros – Output change immediately
• Cons – Two communicating Mealy machines (may) create an
asynchronous loop, glitches may exist on output (due to Hazard)
• Latched Mealy (Moore)
• Pros – Good for synthesis (disjoint time domains for C.P.), critical path
Guaranteed to be glitch-free
• Cons – larger area due to more registers,
output response delayed 1 clock cycle (Latched Mealy - same as
Moore), 2 clock cycles for Latched Moore.
Designing an FSM
• Specification
• Minimization
• State Encoding
• Implementation (in VHDL)
Specification Example:
Manchester Decoder 曼彻斯特解码器
• A specification is often written in a natural language (e.g.
English)
– Build a Manchester decoder
– Skip wrong samples and get into sync as soon as possible
How does an Manchester
Encoder/Decoder work?
A Manchester Encoder performs the translation
0 => 01, 1 => 10 (i.e., doubling the frequency in the transmission
channel, if a '0' is received it outputs "01")
01 => 0, 10 => 1
k=0 k=0
S0 S1 S2 Accepting state(s)
k=0 k=1
S0 S3 S4
k=1 k=0
S0 S5 S6
k=1 k=1
S0 S7 S8
What is a DFA?
k=0 k=0
S0 S1 S2 Accepting state(s)
k=1
k=1
S4
k=0
S5 S6
k=1
S8
Classification of FSMs
Counter Counter
Control
S0 S1 Sn S30 S31
S32
S33
EFSMs (ctd.)
Count++
S1
Superstate
Count=33
S0 S0
Step A – Specification
(Manchester Decoder)
0 1
00
1 0
11
0 0 -
---
1 1 -
---
Deriving the FSM
Input Sequence
0 1 Output Sequence
00
Starting State
Accepting State
Mealy vs Moore
In a Moore Machine,
the output is
0 1 I1 I2
associated with the Moore
state. O2 O1 O2
0 0
Step 1 – Reducing the State Machine
Same Transitions => Merge!
0 1
00
Same Start State
0 0 -
---
1 1 -
---
1 0
11
Step 1 – Reducing the State Machine
0 1
00
0 -
---
-
---
1
1 0 11
Step 2 – Schedule the outputs
Mealy Machine
0 1|0
00
0 Moore Machine
0 -
---
-
---
1
1 0 11
Step 2 – Schedule the outputs (2)
0|- -|-
0 -=0 -
1 -=1
-|-
-
1 0=X 1|-
1 0|1 1
Step 2 – Schedule the outputs (3)
0|0 1|0
0|- -|-
-|-
1|-
1|1 0|1
Step 3 – State Labelling
S0
0|0 1|0
S0 S1
0|- -|-
S2 S0
S4 -|-
1|- S0
S0
S0 1|1 0|1
S3
Empty Intersection
• Schedule the outputs as early as possible
– In case of Empty Intersection (X), scheduling upwards
will result in a conflict. The remaining outputs will have
to be scheduled towards the end of the FSM.
– In case there are no more inputs available, borrow
input states from the next input frame to schedule the
outputs:
S0 S1 S3 0 1
S1 S0 S2 0 -
S2 S0 S0 - -
S3 S4 S0 1 0
S4 S0 S0 - -
Step 1 – Form Equivalent Classes
S2 0 0 =>
S3 1 0 {S0},{S3},{S1,S2,S4}
S4 0 0
Step 2 – Check the future
S3 S4 S0
S4 S0 S0
Final FSM
-|0
1|0
E32 0|0
0|0
E1 E31
1|1
E2 1|0
0|1
Step C – State Encoding
E32 0
0
4! = 24 possible encodings E1 E31
1
(using 2 FFs) E2 1
0
CMOS Power Consumption
VDD VDD
VL VH
VOH VOL
Co Co
VL VH
VSS VSS
2
2
E1=00,
E2=01,
2
E32 1
E31=10,
E1 E31
E32=11
1
=> E2 2
HD=1+1+1+2+2+2+2=11
1
State Assignment
• Minimal assignment!!!
2
1
E1=00,
E2=01,
1
E32 1
E31=11,
E1 E31
E32=10
1
=> E2 1
HD=1+1+1+1+1+1+2=8
1
Tricky example
S0=00, 00 P=0.5
S1=01, 01
S0 S1
P=0.5 P=0.25 P=0.75
S2=11, 10 P=0.5
P=0.75
S3=10, 11 P=0.25
=> S2 S3
P=0.5
HD=10, 10
P=0.5
S0=0001 S0 S1
S1=0010 P=0.5 P=0.25 P=0.75
P=0.5
P=0.75
S2=0100
P=0.25
S3=1000 S2 S3
=> P=0.5
attribute state_vector:string;
attribute state_vector of Moore:architecture is "pres_state";
attribute enum_encoding of pres_state:signal is "00,01,10,11";
ENTITY Counter03 IS
PORT (
clk : IN std_logic;
resetn : IN std_logic;
three : OUT std_logic);
END Counter03;
k=-| 0
State Output
k=0 k=1 Equivalence classes
S0 0 1
S1 1 1
S2 0 0 E1={S0,S4}
S3 1 1 E2={S1,S3,S5,S7}
S4 0 1 E3={S2,S6}
S5 1 1
S6 0 0
S7 1 1
State Minimization
State Next state
k=0 k=1 Equivalence classes
S0 S2 S3 E1={S0,S4}
S1 S3 S2 E2={S1,S3,S5,S7}
S2 S4 S4 E3={S2,S6}
S3 S5 S5
S4 S6 S7 S0->E3,E2; S4->E3,E2 -- Ok! keep E1
S5 S7 S6 S1->E2,E3; S3->E2,E2 -- Not Ok! Split E2
S6 S0 S0 S5->E2,E3; S7->E2,E2 =>
S7 S1 S1
E4={S1,S5}, E5={S3,S7}
State Minimization
No further Improvement possible!!!
E1={S0,S4}
k=-|0
E2={S1,S3,S5,S7} k=0 | 0
E3={S2,S6} E1 E3
k=1|1 k=1|1
E4={S1,S5}
E5={S3,S7} E4 E5
k=0 | 1
k=-|1
State Assignment
k=-|0
k=0 | 0
E1 E3
k=1|1
4! = 24 possible encodings k=1|1
(using 2 FFs)
E4 E5
k=0 | 1
k=-|1
State Assignment
E1=00, 1
1
E3=01,
E1 E3
E4=10,
2 2
E5=11
=>
E4 E5
HD=1+1+1+1+2+2=8
1
1
State Assignment
• Minimal assignment!!!
E1=00, 1
1
E3=01,
E1 E3
E4=11,
1 1
E5=10
=>
E4 E5
HD=1+1+1+1+1+1=6
1
1
Classification of FSMs
Advanced Finite State Machines
• Until now we’ve looked on
– Standard FSMs:
• Mealy, Moore, Mealy with Latched Outputs
– Extended FSMs:
• Standard FSMs with a memory
• FSMs with a Datapath
a b
a b
S0 S1 S2 S3
Type 2 - Context-Free Languages
• Context-Free Languages can be implemented using a
Pushdown Automata.
A PDA has a (possibly infinite) State Stack from which it can Push
and Pop the current state, i.e., basically an FSM that allows
Subroutine Calls (used in all computers).
a b
S0 S1 S2
b b
S3 S4 S5
b
S6
Problem: Exponential a
growth of # of states (2n+1)
A PDA recognizing anbn
a | n=1 b | cnt=n
S0 S1 S2
& (cnt=0)
S2 S3
Type 0 - Unrestricted Languages
• Unrestricted Languages can be implemented using a
Turing Machine.
Address
Counter (infinite)
Incr/Decr =0
RAM
(infinite)
Inputs Data
FSM
Outputs