ECE 448

Lecture 6

Finite State Machines

State Diagrams
vs.
Algorithmic State Machine (ASM) Charts

George Mason University

Required reading

• P. Chu, FPGA Prototyping by VHDL Examples

Chapter 5, FSM

2
 Recommended reading

• S. Brown and Z. Vranesic,

Fundamentals of Digital Logic with VHDL Design
Chapter 8, Synchronous Sequential Circuits
Sections 8.1-8.5
Section 8.10, Algorithmic State Machine (ASM)
Charts

3
Datapath
vs.
Controller

4
Structure of a Typical Digital System

Data Inputs Control & Status Inputs

Control
Signals
Datapath Controller
(Execution (Control
Unit) Unit)
Status
Signals
Data Outputs Control & Status Outputs

5
Datapath (Execution Unit)
• Manipulates and processes data
• Performs arithmetic and logic operations,
shifting/rotating, and other data-processing
tasks
• Is composed of registers, multiplexers, adders,
decoders, comparators, ALUs, gates, etc.
• Provides all necessary resources and
interconnects among them to perform specified
task
• Interprets control signals from the Controller
and generates status signals for the Controller
6
Controller (Control Unit)

• Controls data movement in the Datapath by

switching multiplexers and enabling or disabling
resources
Example: enable signals for registers
Example: select signals for muxes
• Provides signals to activate various processing
tasks in the Datapath
• Determines the sequence of operations
performed by the Datapath
• Follows Some ‘Program’ or Schedule

7
Finite State Machines
• Controllers can be described as Finite State
Machines (FSMs)
• Finite State Machines can be represented using
• State Diagrams and State Tables - suitable
for simple controllers with a relatively few
inputs and outputs
• Algorithmic State Machine (ASM) Charts -
suitable for complex controllers with a large
number of inputs and outputs
• All of these descriptions can be easily translated
to the corresponding synthesizable VHDL code

8
Hardware Design with RTL VHDL

Interface Pseudocode

Datapath Controller
Block Block State diagram
diagram diagram or ASM chart

VHDL code VHDL code VHDL code

9
 Steps of the Design Process
1. Text description
2. Interface
3. Pseudocode
4. Block diagram of the Datapath
5. Interface divided into Datapath and Controller
6. State diagram or ASM chart of the Controller
7. RTL VHDL code of the Datapath, Controller, and
Top-Level Unit
8. Testbench for the Datapath, Controller, and Top-Level
Unit
9. Functional simulation and debugging
10. Synthesis and post-synthesis simulation
11. Implementation and timing simulation
12. Experimental testing using FPGA board
10
 Steps of the Design Process
Introduced in Class Today
1. Text description
2. Interface
3. Pseudocode
4. Block diagram of the Datapath
5. Interface divided into Datapath and Controller
6. State diagram or ASM chart of the Controller
7. RTL VHDL code of the Datapath, Controller, and Top-
level Unit
8. Testbench for the Datapath, Controller, and Top-Level
Unit
9. Functional simulation and debugging
10. Synthesis and post-synthesis simulation
11. Implementation and timing simulation
12. Experimental testing using FPGA board
11
Finite State Machines
Refresher

12
Finite State Machines (FSMs)
• An FSM is used to model a system that transits
among a finite number of internal states. The
transitions depend on the current state and external
input.
• The main application of an FSM is to act as the
controller of a medium to large digital system
• Design of FSMs involves
• Defining states
• Defining next state and output functions
• Optimization / minimization
• Manual optimization/minimization is practical for small
FSMs only
13
Moore FSM
• Output is a Function of the Present State Only

Inputs Next State

function
Next State Present State
clock Present State
reset register

Output Outputs
function

14
Mealy FSM
• Output is a Function of the Present State and the
Inputs
Inputs Next State
function
Next State Present State
clock Present State
reset register

Output Outputs
function

15
State Diagrams

16
Moore Machine

transition
condition 1

state 1 / state 2 /
output 1 output 2
transition
condition 2

17
Mealy Machine

transition condition 1 /
output 1

state 1 state 2
transition condition 2 /
output 2

18
 Moore FSM - Example 1
• Moore FSM that Recognizes Sequence “10”
0 1
0
1
S0 / 0 S1 / 0 1 S2 / 1

reset
0
S0: No S1: “1” S2: “10”
Meaning elements observed observed
of states: of the
sequence
observed

19
Mealy FSM - Example 1
• Mealy FSM that Recognizes Sequence
“10”
0/0 1/0 1/0

S0 S1

reset 0/1
S0: No S1: “1”
Meaning elements observed
of states: of the
sequence
observed
20
Algorithmic State Machine (ASM)
Charts

21
Algorithmic State Machine

Algorithmic State Machine –

representation of a Finite State Machine
suitable for FSMs with a larger number of
inputs and outputs compared to FSMs
expressed using state diagrams and state
tables.

22
Elements used in ASM charts (1)
State name

Output signals 0 (False) 1 (True)

Condition
or actions
expression
(Moore type)

(a) State box (b) Decision box

Conditional outputs
or actions (Mealy type)

(c) Conditional output box

23
State Box
• State box – represents a state. State name
• Equivalent to a node in a state diagram or
a row in a state table. Output signals
or actions
• Contains register transfer actions or (Moore type)
output signals
• Moore-type outputs are listed inside of
the box.
• It is customary to write only the name of
the signal that has to be asserted in the
given state, e.g., z instead of z<=1.
• Also, it might be useful to write an action
to be taken, e.g., count <= count + 1, and
only later translate it to asserting a control
signal that causes a given action to take
place (e.g., enable signal of a counter).
24
Decision Box
• Decision box –
indicates that a 0 (False) 1 (True)
Condition
given condition is to expression

be tested and the

exit path is to be
chosen accordingly.
The condition
expression may
include one or more
inputs to the FSM.

25
Conditional Output Box
• Conditional
output box
• Denotes output Conditional outputs
or actions (Mealy type)
signals that are of
the Mealy type.
• The condition that
determines
whether such
outputs are
generated is
specified in the
decision box.
26
ASM Chart of Moore Machine
reset
S0

0
input
1
S1

1
input

S2 0

output

1 0
input

27
ASM Chart of Mealy Machine
reset

S0

0
input

1 output
S1

1 0
input

28
 Moore & Mealy FSMs without delays

clock
0 1 0 0 0
input

state S0 S0 S1 S2 S0 S0
Moore
output

state S0 S0 S1 S0 S0 S0
Mealy
output

29
 Moore & Mealy FSMs with delays

clock
0 1 0 0 0
input

state S0 S0 S1 S2 S0 S0
Moore
output

state S0 S0 S1 S0 S0 S0
Mealy
output

30
ASMs representing simple FSMs

• Algorithmic state machines can model both

Mealy and Moore Finite State Machines
• They can also model machines that are of
the mixed type

31
Generalized FSM

Present State
Next State

Based on RTL Hardware Design by P. Chu

32
Moore vs. Mealy FSM (1)

• Moore and Mealy FSMs Can Be

Functionally Equivalent
• Equivalent Mealy FSM can be derived from
Moore FSM and vice versa
• Mealy FSM Has Richer Description and
Usually Requires Smaller Number of States
• Smaller circuit area

33
Moore vs. Mealy FSM (2)

• Mealy FSM Computes Outputs as soon as

Inputs Change
• Mealy FSM responds one clock cycle sooner
than equivalent Moore FSM
• Moore FSM Has No Combinational Path
Between Inputs and Outputs
• Moore FSM is less likely to affect the critical
path of the entire circuit

34
Moore vs. Mealy FSM (3)
• Types of control signal
• Edge sensitive
• E.g., enable signal of a counter
• Both can be used but Mealy is faster
• Level sensitive
• E.g., write enable signal of SRAM
• Moore is preferred

35
Which Way to Go?
Mealy FSM Moore FSM

Fewer states

Safer.
Lower Area Less likely to affect
the critical path.
Responds one clock
cycle earlier

36