Digital circuits Ch 6b Page 1 (15)
ASM method 16.10.2013 Fe/KRL
ASM method
• ASM = Algorithmic State Machine = synchronous sequential circuit
• Suitable for designing both Moore and Mealy machines
• Can be used with
• HDL design
• Manual design
• ASM chart is a method of describing the sequential operations of a digital
system
• Resembles flow charts
• ASM chart contains all information that is needed to design a
synchronous sequential circuit
Digital circuits Ch 6b Page 2 (15)
ASM method 16.10.2013 Fe/KRL
SYNCHRONOUS SEQUENTIAL CIRCUIT DESIGN
This slide show is based on lecture slides of senior lecturer Esko Rautanen. Translated and edited by T. Karilinna, 2010
Digital circuits Ch 6b Page 3 (15)
ASM method 16.10.2013 Fe/KRL
State diagram
• A state diagram is a directed graph
defining how a sequential circuit
propagates from state to state
• An arch (directed arrow) represents
state change
• A state circle represents each state of the circuit
• Names of output signals activated in the state are written inside the
circle
• Name and state code of the state is written next to the circle
• If more than one arch from a state exist, a condition based on input
signal values has to be written next to each arch
Digital circuits Ch 6b Page 4 (15)
ASM method 16.10.2013 Fe/KRL
Design example 1: Neon sign for Jack’s bar, version 1
• Jack needs more customers and asks us to design a dynamic neon sign
• the sign is dark for two seconds
• the text appears in three phases each taking two seconds
2s
Delicious 2s
Delicious food at 2s
Delicious food at Jack’s bar 2s
Atanua demo JACK1
Digital circuits Ch 6b Page 5 (15)
ASM method 16.10.2013 Fe/KRL
Design example 1 continued
Basic principle
• A synchronous sequential circuit with four states
• Clock cycle 2 s
• No other inputs than CLK needed
Block diagram Signal names
Controller Lamps
f = 1/T
DEL
Oscillator Delicious
JACK1
CLK FOO
0,5 Hz food at
JAC
Clock cycle 2 s Jack’s bar
Digital circuits Ch 6b Page 6 (15)
ASM method 16.10.2013 Fe/KRL
Design example 1 continued
State diagram
• A unique name is assigned to each state
• One of the states is the initial state
• A unique binary state code is assigned to each state
Initial state
State name
State code
Output signals
activated
Digital circuits Ch 6b Page 7 (15)
ASM method 16.10.2013 Fe/KRL
State codes
• Every state has to be assigned a unique state code
• Each state code is a binary number
• If the sequential circuit has s states, each state code consists of k
bits such that 2k ≥ s i.e. k ≥ log2 s
• The state register of the sequential circuit is constructed of as many flip-
flops as there are bits in each state code
Digital circuits Ch 6b Page 8 (15)
ASM method 16.10.2013 Fe/KRL
ASM chart: state box and exit path
• One state box per ASM state
• State name, active outputs, state code
• Only active outputs are drawn in the state box
• Exit path describes transition from current state to next state
• Only one exit path from a state
State Example
name State code
= value of state register
BBB 010
OUT1 State box RUN
SN OPER
OUT2 NORM
Active outputs
Exit path
Digital circuits Ch 6b Page 9 (15)
ASM method 16.10.2013 Fe/KRL
ASM chart: input signals
• Input signals are drawn inside decision box (decision diamond)
• Decision box makes a two way decision based on the on the input signal
• If more than one input signal is needed decision boxes can be chained
• Decision boxes belong to the state where the exit path starts from
Example
BBB 010
OUT1 RUN
SN OPER
OUT2 NORM
1 1
IN1 SLOW
Input 0 Decision box 0
signal 1 0
IN2 FAST
0 1
Digital circuits Ch 6b Page 10 (15)
ASM method 16.10.2013 Fe/KRL
ASM chart: conditional outputs
• Conditional outputs are drawn inside an oval shaped conditional output box
• Conditional output box is always located on an exit path that comes from a
decision box
• Decision box indicates the signal that output depends on (or signals if
there are chained decision boxes)
• Conditional output box indicates active output 010
BBB OPER RUN
SN OUT1
OUT2 1
Example SLOW
1 NORM
IN1 0
0
0 Conditional FAST
Conditional output box
output OUT3 1
RAPID SLUGG
Digital circuits Ch 6b Page 11 (15)
ASM method 16.10.2013 Fe/KRL
Using clock signal for timing Example of
ASM chart
Timing
• Most of the state transitions are not affected by
an input signal
• Clock frequency determines the timing of
operations
• Accuracy and frequency of clock signal are
important
Applications
• Digital clock
• Serial data transmission
• wired (copper, fiber optic, etc.)
• wireless
• Processors
• AD/DA conversion
Digital circuits Ch 6b Page 12 (15)
ASM method 16.10.2013 Fe/KRL
Using clock signal for waiting Example of
ASM chart
Reacting to user actions
• User can be a person or a signal from another
system or a sensor
• Circuit stays in the same state
until an input signal changes
• Clock frequency must be high enough to fulfil
the timing requirements of the application
Applications
• Manually operated devices
• Keyboard
• Buttons and switches
• Reactions to external input
• Control systems
• Robots, etc.
Digital circuits Ch 6b Page 13 (15)
ASM method 16.10.2013 Fe/KRL
Example of
Using clock signal for timing and waiting ASM chart
Combination of the previous two
• In some parts of the circuit state changes are
affected by input signal and in other parts state
changes are based only on the clock signal 0
T
• Application determines the required accuracy and 1
frequency of the clock signal
Applications
• Most of the real world devices T
0
• Example: 1
• Wait for user input and then transmit serial data
based on user input
• Wait does not (typically) require accurate 0
T
timing
1
• Serial transmission requires accurate timing
T = 1 ⇒ run
T = 0 ⇒ stop
Digital circuits Ch 6b Page 14 (15)
ASM method 16.10.2013 Fe/KRL
Initialisation of a synchronous sequential circuit
• A synchronous sequential circuit is initialized with a
reset signal D 1D Q
• Typically reset signal clears (sets to zero) all flip CLK C1
flops RES R Q
• Typically reset signal is an active low signal
• Reset is connected to asynchronous reset signal
of the flip flops Example of
ASM chart
• Reset forces state machine to the initial state
• At power up RES
• When watchdog circuit detects an error 00
• When reset button is pressed
• Mark the initial state in the ASM chart with
• An arrow pointing to the initial state 10
• The name of the reset signal at the other end of 01
the arrow
Digital circuits Ch 6b Page 15 (15)
ASM method 16.10.2013 Fe/KRL
ASM – Moore machine
Jack’s super neon sign controller 000 Three
Flow chart state
OFF
bits
2s 2s
0 1
No Yes HH
Happy Hour? 101
2 s EAT 2s
001 EAT
EAJ AT
E EAT 1
2 s EAT AT 2s JAC
010 110
EAT EAT
2 s EAT AT JACK’S 6s EA AT EAJ AT
No Yes 2 JAC
Night?
Block diagram
011
0 EAT
NI HERK EAJ
1 EAT AT
0 JAC 3
HH JKS JASK
1 AT
CLK KUPP
1 0
0,5 Hz JACK’S NI
Clock period 2 s
Digital circuits Ch 6b Page 16 (15)
ASM method 16.10.2013 Fe/KRL
One hot state encoding 000001
• One flip-flop per state OFF Six
state
• The active state flip-flop is set to one bits
0 1
• Only one flip-flop is set to one at any HH
001000
one time 000010 EAT
• Next state expressions are often
E EAT
EAJ AT
1 JAC
simpler than with minimum flip-flop
encoding 000100 010000
• Suites well to modern FPGAs EA
EAT EAT
AT EAJ AT
• Modern FPGA consists of logical 2 JAC
elements that have a flip-flop plus
some combinational logic
100000
• Expressions for state activation can EAT
generated independently of each other AT EAJ
JAC 3
• No state tables are needed
1 0
NI
Clock period 2 s
Digital circuits Ch 6b Page 17 (15)
ASM method 16.10.2013 Fe/KRL
One hot state encoding 000001
• Use state names for flip-flop names OFF Six
state
• Need to take into account only those bits
states that have an arrow leading to the 0 1
HH
state under analysis 001000
000010 EAT
EAJ AT
E EAT 1 JAC
E = OFF ⋅ HH 000100
Condition 010000
EAT EAT
Previous state EA AT EAJ AT
2 JAC
EA = E
100000
Previous state (no condition) EAT
AT EAJ
JAC 3
1 0
NI
Clock period 2 s
Digital circuits Ch 6b Page 18 (15)
ASM method 16.10.2013 Fe/KRL
One hot state encoding 000001
• Use state names for flip-flop names OFF Six
state
• Need to take into account only those bits
states that have an arrow leading to the 0 1
HH
state under analysis 001000
000010 EAT
1 2 3 EAJ AT
E EAT 1 JAC
EAJ3 = EA + EAJ2 + EAJ3 ⋅ NI
000100 010000
Analyse each arrow EAT EAT
EA AT EAJ
separately and combine AT
2 JAC
them with OR
1
Incoming arrows from 2
three states 100000
EAT
AT EAJ
JAC 3
3
1 0
NI
Clock period 2 s
Digital circuits Ch 6b Page 19 (15)
ASM method 16.10.2013 Fe/KRL
One hot state encoding 000001
• One expression per state OFF Six
state
• Reset signal is connected to the bits
asynchronous set input of the initial 0 1
HH
state flip flop and reset input of all 001000
000010 EAT
other flip flops EAJ
E EAT AT
1 JAC
OFF = EAJ3 ⋅ NI 000100 010000
EAT EAT
E = OFF ⋅ HH EA AT EAJ AT
2 JAC
EA = E
EAJ3 = EA + EAJ2 + EAJ3 ⋅ NI 100000
EAT
AT EAJ
EAJ1 = OFF ⋅ HH 3
JAC
EAJ2 = EAJ1 1 0
NI
Clock period 2 s
Digital circuits Ch 6b Page 20 (15)
ASM method 16.10.2013 Fe/KRL
One hot state encoding 000001
• Outputs of Moore machine are generated OFF Six
state
by OR:ing the state bits where the input bits
is active 0 1
HH
001000
000010 EAT
EAJ AT
E EAT 1 JAC
000100 010000
EAT EAT
EA AT EAJ AT
2 JAC
EAT = E + EA + EAJ1 + EAJ2 + EAJ3 100000
EAT
AT = EA + EAJ1 + EAJ2 + EAJ3 AT EAJ
JAC 3
JAC = EAJ1 + EAJ2 + EAJ3
1 0
NI
Clock period 2 s
Digital circuits Ch 6b Page 21 (15)
ASM method 16.10.2013 Fe/KRL
The reset button is wired to
clear input of all other states
except the initial state.
Initial state The reset button is wired to
set input of initial state.
SET
RESET
