F5 - FSM Modelling and Synthesis PDF

Download as pdf or txt
Download as pdf or txt
You are on page 1of 91

F5 : FSM Modelling & Synthesis

FSM Modelling Styles


• Moore Machine
• Mealy Machine
• Latched Mealy Machine
• (Latched Moore Machine)
Moore Machine

k='0'

k='1' S0|1 S1|0 k='0'

k='1'
Input vs Output - Moore

State is changed here

Input Sequence I1 I2
O1 O2 Output Sequence

Output is seen after state has changed


Moore Machine (ctd.)

Next State logic State register Output logic


Outputs

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

State is changed here

Input Sequence I1 I2
O1 O2 Output Sequence

Output is seen after input has changed


Mealy Machine (ctd.)
Next State logic State register Output logic
Outputs

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

Mealy with latched outputs  Moore Machine


Input vs Output – Latched Mealy

State is changed here

Input Sequence I1 I2
O1 O1 O2 Output Sequence

Output is determined here


Output is seen after state has changed
Mealy Machine with Latched Outputs

Next State logic State register Output logic


Outputs

Inputs

Clk

TD(I->DFF) TD(DFF->DFF) TD(DFF->O)

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)

State is changed here

Input Sequence I1 I2
O1 O1 O2 Output Sequence

Output is changed here


(dependent on state only) Output is seen 1 clock cycle
after state has changed
(Moore Machine with Latched
Outputs)

Next State logic State register Output logic


Outputs

Inputs

Clk

TD(I->DFF) TD(DFF->DFF) TD(DFF->O)


FSM Synthesis Example:
Mealy Machine

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?

FSM1 FSM2 FSM3 FSM4


Two Moore Machines

N.L. O.L.
N.L. O.L.
Outputs
Inputs

TD(I->DFF) TD(DFF->O) TD(I->DFF) TD(DFF->O)

C.P. TD=TD(DFF->O)+ TD(I->DFF)


关键路径
What is Critical Path?
• The Critical Path is the ”longest” or, more
correctly, the slowest path in the circuit, i.e., the
path through the circuit which takes the longest
time to finish execution of its functionality.

• Critical Path is calculated from Input to Output,


Input to a DFF register input, DFF register output
to Output or from DFF register output to DFF
register input
Two Mealy Machines

N.L. O.L.
N.L. O.L.
Inputs Outputs

TD(I->DFF) TD(DFF->O) TD(I->DFF) TD(DFF->O)

TD(I->O) TD(I->O)

C.P. TD=TD(I->O) + TD(I->O)


Two Latched Mealy Machines

N.L. O.L.
N.L. O.L.
Outputs
Inputs

TD(I->DFF) TD(DFF->DFF) TD(I->DFF) TD(DFF->DFF)

TD1=max(TD(I->DFF), TD(DFF->DFF)) TD2=max(TD(I->DFF), TD(DFF->DFF))

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")

A Manchester Decoder should perform this translation the other direction

01 => 0, 10 => 1

• How do we implement this?


Input speed twice of output speed => output two symbols instead of one
01 => 00, 10 => 11 (i.e., if a "01" is received it outputs '0')

• What about the input combinations 11 and 00?


Assume self-synchronisation => skip wrong samples (output = '-') and get
into sync as soon as possible
Understanding the specification
• Four input sequences, four output sequences
– In sync sequences
• 01 => 00
• 10 => 11

– Out of sync sequences


• 00- => - - -
• 11- => - - -
Parsing sequences
(NFA to DFA conversion)

Non-Deterministic Finite Automata

Deterministic Finite Automata


What is an NFA?

• Basically, when there is no way to know where to go with only 1


Lookahead symbol

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?

• Basically, when it is possible to know where to go with only 1


Lookahead symbol

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

• Any Language (or Computation problem) can be classified according to


as to what patterns its implementing Automata can recognize

• There are four types of Computer Languages (also called Chomsky


classes)

– Type 0 - Unrestricted Languages (EFSM with infinite memory)


– Type 1 - Context-Sensitive Languages (EFSM with bounded memory)
– Type 2 - Context-Free Languages (PDA - EFSM with stack)
– Type 3 - Regular Languages (normal FSM)

• Read more in a Computation Theory Course


Extended FSM - EFSM

Counter Counter
Control

Inputs State Register Outputs


NextState Output
Logic Logic
EFSM (ctd.)

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 Mealy Machine, 0|0 1|0 I1 I2


the output is
associated with the
Mealy
transition. O1 O2

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)

Conflicting outputs => intersect


0 1|0 横切
0

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:

I1|- I2|O1 I1|O2


I1 I2 I1
S0 S1 S2 S1
O1 O2
Step B – State Minimization

Next State Output

State K=0 K=1 K=0 K=1

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

Output • Fill in Don’t Cares (for


example with zeros)
State K=0 K=1
• All output combinations
S0 0 1
that are the same belong
S1 0 0 to the same class

S2 0 0 =>
S3 1 0 {S0},{S3},{S1,S2,S4}

S4 0 0
Step 2 – Check the future

Next State • States that have the same


future are equivalent
State K=0 K=1 E1 E2 E3
{S0},{S3},{S1,S2,S4}
S0 S1 S3
=>
S1 S0 S2 E1 E2 E31 E32
S2 S0 S0 {S0},{S3},{S2,S4},{S1}

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

• How do we assign minimal codes?

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

E=0.5*VDD*(VDD-VSS)*Co = (VSS=0 V) = 0.5*VDD*VDD*Co


Paverage= dE/dt =1/T 0.5*VDD*VDD*Co =~ f* VDD*VDD*Caverage
all events
State Assignment

• Minimize Hamming Distance (the number of bits that differ)

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

• The second encoding consumes less power!!!


One-hot encoding

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

• Hamming distance between any two states always 2


• No need to select minimal codes
• Might require many FFs => *BIG* Design
Step D - Implementation
• Most synthesis tools have optimisation
constraints for synthesis!
• In order to use these tools the synthesis tool has
to be aware of the fact that an FSM exists.
• Synopsys (the leading tool vendor for ASIC
synthesis) has defined a set of attributes that
should be used for FSM modelling.
User Defined Attributes

• Language defined attributes return information about certain


items in VHDL
– Types, subtypes
– Procedures, functions
– Signals, variables, constants
– Entities, architectures, configurations, packages
– Components

• Attributes can be user-defined to handle custom situations


(user-defined records, etc.)
Example: User defined Attributes

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";

NB! Name of attribute is tool-dependent!!!


(but fortunately, most tools follow Synopsys naming standard)
Modeling of an FSM
(A modulo-4 counter)
LIBRARY ieee;
USE ieee.std_logic_1164.ALL;

ENTITY Counter03 IS
PORT (
clk : IN std_logic;
resetn : IN std_logic;
three : OUT std_logic);
END Counter03;

ARCHITECTURE FSM OF Counter03 IS


SUBTYPE state_type IS integer RANGE 0 TO 3;
SIGNAL pres_state, next_state : state_type := 0;
ATTRIBUTE STATE_VECTOR : string;
ATTRIBUTE STATE_VECTOR OF FSM : ARCHITECTURE IS "PRES_STATE";
Modeling of an FSM (ctd.)
(A modulo-4 counter)
BEGIN -- FSM
U0:
PROCESS (clk, resetn)
BEGIN -- PROCESS
IF resetn = '0' THEN
pres_state <= 0;
ELSIF clk'event AND clk = '1' THEN
pres_state <= next_state;
END IF;
END PROCESS;
Modeling of an FSM (ctd.)
(A modulo-4 counter)
U1:
PROCESS (pres_state)
BEGIN -- PROCESS
three <= '0';
CASE pres_state IS
WHEN 0 TO 2 => next_state <= pres_state + 1;
WHEN 3 => next_state <= 0;
three <= '1';
WHEN OTHERS => next_state <= 0;
END CASE;
END PROCESS;
END FSM;
Extracting the FSM
Some tools, like Synopsys
and Leonardo, let you choose
the FSM encoding.

Synopsys FSM encoding menues


Binary Encoding
Gray Encoding
One Hot Encoding
Comparison
(Modulo-4-Counter) 4模计数器

Setup Delay fmax Comb. Seq.


Time [ns] [ns] [Mhz] Area Area

Binary 0.35 0.87 816 9.75 4.5


Gray 0.35 0.66 990 3.00 4.5
OneHot 0.58 0.29 1149 0.00 10.75

• The design can be optimized a lot by choosing the best state


encoding style.
• It depends on the design, which style is most efficient
Appendix
State Minimization - Another Example

k=-| 0

k=0 | 0 k=-| 0 k=0 | 0


S0 S2 S4 S6
k=1|1 k=1|1 k=1|1
k=1|1
k=- | 1
S1 S3 S5 S7
k=0 | 1 k=0 | 1
k=-| 1
State Minimization

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

• How do we assign minimal codes?

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

• Minimize Hamming Distance (the number of bits that differ)

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

• How are they formally (=mathematically) defined?


Classification of FSMs

• Any Language (or Computation problem) can be classified according


to as to what patterns its implementing Automata can recognize

• There are four types of Computer Languages (also called Chomsky


classes)

– Type 0 - Unrestricted Languages


– Type 1 - Context-Sensitive Languages
– Type 2 - Context-Free Languages
– Type 3 - Regular Languages
Type 3 - Regular Languages
• Regular languages can be implemented using a Finite
Automata.

=> All problems of finite size can be modeled using a Deterministic


Finite Automata (although describing the problem as a DFA may
be unwieldy and cause a state explosion)

Equivalent problem: { ambn | m,n N)


An FSM for detecting anbm

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).

Equivalent problem: { anbn | n N}


A regular FSM recognizing anbn

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 | push State b | pop State

a | push State b | pop State Stack empty


S0 S1 S2 S3
Type 1 - Context-Sensitive Languages

• Context-Sensitive Languages can be implemented using a


Linear Bounded Automata that does not include
recognizing the Empty string ().

An LBA- is basically an Finite Automata with a Finite memory in


which it can store and retrieve data (including stack). An EFSM or
FSMD belong to this class.

Equivalent problem: { anbncn | n > = 1}


An EFSM for detecting anbncn
a | n++ b | cnt--

a | n=1 b | cnt=n
S0 S1 S2

c & (cnt=0) | cnt=n


c | cnt--

& (cnt=0)
S2 S3
Type 0 - Unrestricted Languages
• Unrestricted Languages can be implemented using a
Turing Machine.

A Turing Machine is basically an LBA with an infinite memory (or


infinite datapath). A language is called Turing Complete if it
includes the operations
{ increment, decrement, and compare to 0 }.

Equivalent problem: { an | fn(n) halts }


An EFSM “implementing” a Turing
Machine

Address
Counter (infinite)

Incr/Decr =0
RAM
(infinite)
Inputs Data
FSM

Outputs

Read more in a Computation Theory Course

You might also like