CS1103

ASM Charts
Algorithmic State Machine (ASM) Chart is a high-level
flowchart-like notation to specify the hardware
algorithms in digital systems.

Major differences from flowcharts are:

uses 3 types of boxes: state box (similar to operation box),

decision box and conditional box

contains exact (or precise) timing information; flowcharts
impose a relative timing order for the operations.

From the ASM chart it is possible to obtain

the control
the architecture (data processor)

CS1104-14

ASM Charts

Components of ASM Charts

The state box is rectangular in shape. It has at most
one entry point and one exit point and is used to
specify one or more operations which could be
simultaneously completed in one clock cycle.

state

binary
code

one or more
operations

CS1104-14

Components of ASM Charts

Components of ASM Charts

The decision box is diamond in shape. It has one
entry point but multiple exit points and is used to
specify a number of alternative paths that can be
followed.

deciding
factors

CS1104-14

deciding
factors

Components of ASM Charts

Components of ASM Charts

The conditional box is represented by a rectangle with

rounded corners. It always follows a decision box and

contains one or more conditional operations that are
only invoked when the path containing the conditional
box is selected by the decision box.

conditional
operations

CS1104-14

Components of ASM Charts

ASM Charts: An Example

An example:

T0
Initial state

A is a register; Ai
stands for ith bit of
the A register.

A = A4A3A2A1

T1

E and F are singlebit flip-flops.

A 0
F 0
A A+ 1

A2

E 0

E 1

A3

T2

1
F 1

CS1104-14

ASM Charts: An Example

Register Operations
Registers are present in the data processor for

storing and processing data. Flip-flops (1-bit

registers) and memories (set of registers) are also
considered as registers.

The register operations are specified in either the

state and/or conditional boxes, and are written in the

form:
destination register function(other registers)
where the LHS contains a destination register (or part of one)
and the RHS is some function over one or more of the
available registers.

CS1104-14

Register Operations

Register Operations
Examples of register operations:
A B
A 0
A A 1

CS1104-14

Transfer contents of register B into

register A.
Clear register A.
Decrement register A by 1.

Register Operations

Timing in ASM Charts

Precise timing is implicitly present in ASM charts.
Each state box, together with its immediately
following decision and conditional boxes, occurs
within one clock cycle.

A group of boxes which occur within a single clock

cycle is called an ASM block.

CS1104-14

Timing in ASM Charts

Timing in ASM Charts

T0
Initial state

1
T1

A 0
F 0
A A+ 1

3 ASM blocks

A2

E 0

E 1

A3

T2

1
F 1

CS1104-14

Timing in ASM Charts

10

Timing in ASM Charts

Operations of ASM can be illustrated through a
timing diagram.

Two factors which must be considered are

operations in an ASM block occur at the same time in one

clock cycle
decision boxes are dependent on the status of the previous
clock cycle (that is, they do not depend on operations of
current block)

CS1104-14

Timing in ASM Charts

11

Timing in ASM Charts

clock

10

11

12 13

states

T0

T0

T1

T1

T1

T1

T1

T1

T1

T2

T0

T0

input

S=0

S=1

A=2

A=3

A=4

register
values

Operations

T0

S=0
A=0
F=0

A=1

A=7
F=1

E=0
A0
F0

A=5 A=6

E=0

AA+1
E0
AA+1
E0

E=1

E=1

AA+1
E1

AA+1
E1

E=0

E=0

E=1

AA+1
E0

AA+1
E0

F1

AA+1
E1

A = A4A3A2A1

CS1104-14

Timing in ASM Charts

12

Timing in ASM Charts

T0
Initial state

clock

states

T0

T0

T1

T1

T1

T1

input

S=0

S=1

A=1

A=2

A=3

E=0

E=0

E=1

register
values

S=0
A=0
F=0

1
T1

A 0
F 0

A0
F0

Operations

A A+ 1

A2

E 0

T2

0
1

F 1

A = A4A3A2A1
CS1104-14

clock

10

11

12 13

states

T1

T1

T1

T2

T0

T0

T0

input

E 1
A3

AA+1
AA+1
E0
E1
AA+1
AA+1
E0
E1

register
values

A=4

A=5 A=6

A=7

E=1

E=0

E=1

F=1
E=0

AA+1
F1
E0
AA+1
AA+1
E0
E1

Operations

Timing in ASM Charts

13

ASM Chart => Digital System

ASM chart describes a digital system. From ASM
chart, we may obtain:

Controller logic (via State Table/Diagram)

Architecture/Data Processor

Design of controller is determined from the decision

boxes and the required state transitions.

Design requirements of data processor can be

obtained from the operations specified with the state

and conditional boxes.

CS1104-14

ASM Chart => Digital System

14

ASM Chart => Controller

Procedure:
Step 1: Identify all states and assign suitable codes.
Step 2: Draw state diagram.
Step 3: Formulate state table using

State from state boxes

Inputs from decision boxes
Outputs from operations of state/conditional boxes.
Step 4: Obtain state/output equations and draw circuit.

CS1104-14

ASM Chart => Controller

15

ASM Chart => Controller

T0

T2

A 0
F 0

Present
state

G1 G0

A A+ 1

A2

E 0

E 1

A3

T2

1
F 1

CS1104-14

T0 = 00
T1 = 01
T2 = 11

T1
1

T1

Assign codes to states:

T0

Initial state

0
0
0
0
0
1

0
0
1
1
1
1

Next
state

inputs

outputs

A2 A3 G1+ G0+ T0 T1 T2

0
1
X
X
X
X

X
X
0
1
1
X

X
X
X
0
1
X

0
0
0
0
1
0

0
1
1
1
1
0

1
1
0
0
0
0

0
0
1
1
1
0

0
0
0
0
0
1

Inputs from conditions in decision boxes.

Outputs = present state of controller.
ASM Chart => Controller

16

ASM Chart => Architecture/Data

Processor

Architecture is more difficult to design than controller.

Nevertheless, it can be deduced from the ASM chart.
In particular, the operations from the ASM chart
determine:
What registers to use
How they can be connected
What operations to support
How these operations are activated.

Guidelines:
always use high-level units
simplest architecture possible.

CS1104-14

ASM Chart => Architecture/Data

Processor

17

ASM Chart => Architecture/Data

Processor
Various operations are:

Counter incremented (A A + 1) when state = T1.

Counter cleared (A 0) when state = T0 and S = 1.
E is set (E 1) when state = T1 and A2 = 1.
E is cleared (E 0) when state = T1 and A2 = 0.
F is set (F 1) when state = T2.

Deduce:
One 4-bit register A (e.g.: 4-bit synchronous counter with

clear/increment).
Two flip-flops needed for E and F (e.g.: JK flip-flops).

CS1104-14

ASM Chart => Architecture/Data

Processor

18

Implementing the Controller

Once the state table is obtained, the controller can
be implemented using one of these techniques.

1. Traditional method: With JK flip-flops.

design done at gate level.
suitable for small controllers.
procedure: prepare state table, use K-maps to obtain next-

state/output functions.

2. Decoder + D flip-flops
suitable for moderately large controllers.
procedure: use decoder to obtain individual states; from the

state table, obtain the next-state functions by inspection.

CS1104-14

Implementing the Controller

19

Implementing the Controller

3. Multiplexers
a more structured approach to implement controller.
suitable for moderately large controllers.
three level structure:
first level consists of multiplexers that determine the next
state of the register;
second level is a register that holds the present state;
third level has a decoder to provide separate output for each
controller state.

CS1104-14

Implementing the Controller

20

Implementing the Controller

4. One flip-flop per state
also known as One-Hot Spot Method of ASM synthesis.
procedure: allocate one flip-flop per state; from state table,

determine the formulae to set each flip-flop; must ensure

that controller is properly initialised.

5. PLA/ROM
highly regular approach.
ROM approach uses a very simple table lookup technique

but suffers from large number of dont care states.

PLA can handle dont care states well but design method is
still at gate-level.

CS1104-14

Implementing the Controller

21

Implementing Controller:
With JK Flip-flops
State table

Present
state
G1 G0
0
0
0
0
0
1
0
1
0
1
1
1

obtained from
ASM chart:

inputs
S
0
1
X
X
X
X

A2
X
X
0
1
1
X

A3
X
X
X
0
1
X

Next
state
G1+ G0+
0
0
0
1
0
1
0
1
1
1
0
0

outputs
T0
1
1
0
0
0
0

T1
0
0
1
1
1
0

T2
0
0
0
0
0
1

Corresponding state table using JK flip-flops:

Present
state

G1 G0
0 0
0 0
0 1
0 1
0 1
1 1
CS1104-14

inputs

S A2
0 X
1 X
X 0
X 1
X 1
X X

Next
state

Flip-flop
inputs

A3 G1+ G0+ JG1 KG1 JG0 KG0

X 0
0
0
X
0
X
X 0
1
0
X
1
X
X 0
1
0
X
X
0
0 0
1
0
X
X
0
1 1
1
1
X
X
0
X 0
0
X
1
X
1

Implementing Controller: With JK

Flip-flops

22

Implementing Controller:
Decoder + D Flip-flops

The flip-flop input functions can be obtained directly

from the state table by inspection.

This is because for the D flip-flops, the next state =

flip-flop D input.

Decoder is then used to provide signals to represent

different states.
?

G1

D Q

D Q

G0

2x4
decoder

T0
T1
unused
T2

clock
CS1104-14

Implementing Controller: Decoder

+ D Flip-flops

23

Implementing Controller:
Decoder + D Flip-flops
Given the

state table:

Present
state

G1 G0
0
0
0
0
0
1

0
0
1
1
1
1

Next
state

inputs

outputs

A2 A3 G1+ G0+ T0 T1 T2

0
1
X
X
X
X

X
X
0
1
1
X

X
X
X
0
1
X

0
0
0
0
1
0

0
1
1
1
1
0

1
1
0
0
0
0

0
0
1
1
1
0

0
0
0
0
0
1

We can directly determine the inputs of the D flipflops for G1 and G0.
DG1 = T1.A2.A3
DG0 = T0.S + T1
CS1104-14

Implementing Controller: Decoder

+ D Flip-flops

24

Implementing Controller:
Decoder + D Flip-flops
Flip-flop input functions:

DG1 = T1.A2.A3
DG0 = T0.S + T1

Circuit:
A2
A3

G1

D Q

D Q

G0

2x4
decoder

T0
T1
unused
T2

clock
CS1104-14

Implementing Controller: Decoder

+ D Flip-flops

25

Implementing Controller:
One Flip-flop per State

Require n flip-flops for n states; each flip-flop

represents one state. (Other methods: n flip-flops

for up to 2n states.)
?

D Q

T0

D Q

T1

:
:
clock

CS1104-14

Implementing Controller: One

Flip-flop per State

26

Implementing Controller:
One Flip-flop per State

Formulae for next state can be obtained directly

from state table:
1. If there is only one line going into the state, then

formula = input condition ANDed with the previous

state.
2. If there are more than one line, then formula = Ored of

all the conditions found in (1).

CS1104-14

Implementing Controller: One

Flip-flop per State

27

Implementing Controller:
One Flip-flop per State
State table:
Present
state

State diagram:

Next
state

inputs

S A2 A3
T0
T0
T1
T1
T1
T2

0
1
X
X
X
X

X
X
0
1
1
X

X
X
X
0
1
X

S=0

A2=0

S=1
T0
T1
T1
T1
T2
T0

T0

T1

T2

A2=1,
A3=0

A2=1,
A3=1

Flip-flop input functions:

DT0 = T2 + S'.T0
DT1 = S.T0 + A2'.T1 + A2.A3'.T1 = S.T0 + (A2.A3)'.T1
DT2 = A2.A3.T1
CS1104-14

Implementing Controller: One

Flip-flop per State

28

Implementing Controller:
One Flip-flop per State

Circuit diagram below. To initialise to state T0, set

flip-flop of T0 to 1 and clear the rest to zero.
preset

A2
A3

DT0 = T2 + S'.T0
DT1 = S.T0 + (A2.A3)'.T1
DT2 = A2.A3.T1
CS1104-14

D Q

T0

D Q

T1

D Q

T2

clock
clear
Implementing Controller: One
Flip-flop per State

29

Implementing Controller:
One Flip-flop per State

Alternative: Use Q' output for T0, and input function

for T0 is complemented. To initialise, clear all flipflops to zero.
D Q

Q'

A2
A3

DT0 = (T2 + S'.T0)'

DT1 = S.T0 + (A2.A3)'.T1
DT2 = A2.A3.T1
CS1104-14

T0

D Q

T1

D Q

T2

clock
clear
Implementing Controller: One
Flip-flop per State

30

Implementing Controller:Multiplexers
Purpose of multiplexer is to produce an input to its
corresponding flip-flop equals to the value of the next
state.

The inputs of multiplexers are determined from the

decision boxes and state transitions in the ASM chart.

CS1104-14

Implementing Controller:
Multiplexers

31

Implementing Controller:Multiplexers
Example 1: Given
the state table.

Reformat the
state table.

CS1104-14

Present
state

G1 G0
0
0
0
0
0
1
0
1
0
1
1
1
Present
state

inputs

S
0
1
X
X
X
X

Next
state

G1 G0 G1
0 0
0
0 0
0
0 1
0
0 1
0
0 1
1
1 1
0

Next
state

A2 A3 G1+ G0+
X X
0
0
X X
0
1
0 X
0
1
1 0
0
1
1 1
1
1
X X
0
0

G0+

Input
conditions

0
1
1
1
1
0

S'
S
A2'
A2. A3'
A2. A3
1

Implementing Controller:
Multiplexers

Multiplexer
inputs

MUX1

MUX0

?
32

Implementing Controller:Multiplexers
Obtain multiplexer inputs:
Present
state

Next
state

G1 G0 G1
0 0
0
0 0
0
0 1
0
0 1
0
0 1
1
1 1
0

CS1104-14

G0
0
1
1
1
1
0

Input
conditions

S'
S
A2'
A2. A3'
A2. A3
1

Multiplexer
inputs

MUX1

MUX0

A2. A3

A2' + A2. A3' + A2. A3

=1

Implementing Controller:
Multiplexers

33

Implementing Controller:Multiplexers
Present
state

Draw circuit:

G1 G0
0 0
0 1
1 1

T0
T1
T2

A2
A3

0
0

0
1 MUX1
2
3
S1 S0

D Q

S1 S0
0
1 MUX0
2
3

D Q

MUX0
S
1
0

G0

T0
T1
T2

clock

Determine next
state of register
CS1104-14

MUX1
0
A2. A3
0

G1

2x4
decoder

S
1

Multiplexer
inputs

Hold present
state

Implementing Controller:
Multiplexers

34

Implementing Controller:Multiplexers
Present
state

Example 2:
T0

T1

0
T3

0
0

0
w
1 01

11

y
1

CS1104-14

G1 G0 G1
0
0
0
0
0
0
0
1
1
0
1
1
1
0
0
1
0
1
1
0
1
1
1
0
1
1
1
1
1
1

00

T2

1
1

Next
state

Present
state

10

y
0

T0
T1
T2
T3

G0
0
1
0
1
0
0
1
1
0
1

Input
conditions

w'
w
x
x'
y'
y.z'
y.z
y'.z
y
y'.z'

Multiplexer
inputs

G1 G0
MUX1
MUX0
0
0
0
w
0
1
x+x'=1
x'
1
0 y.z' + y.z
y.z
=y
1
1
y + y'.z'
y'.z +
= y + z' y'.z' = y'

Implementing Controller:
Multiplexers

35

Implementing Controller:Multiplexers
Present
state

T0
T1
T2
T3

y
z'

0
1
y

G1 G0
0 0
0 1
1 0
1 1

Multiplexer
inputs

MUX1
0
1
y
y + z'

0
1 MUX1
2
3
S1 S0

D Q

MUX0
w
x'
y.z
y'

G1

2x4
decoder

y
z

CS1104-14

w
x'
y'

S1 S0
0
1 MUX0
2
3

D Q

G0

T0
T1
T2
T3

clock

Implementing Controller:
Multiplexers

36

Implementing Controller: PLA/ROM

Similar to the design using D flip-flops and a decoder.
The only difference is PLA essentially replaces the
decoder and all the gates in the inputs of the flipflops.
External
command

PLA/ROM

Present
state

Commands to
architecture

Next
state

Register to represent states

CS1104-14

Implementing Controller:
PLA/ROM

37

End of segment