Designs based on Finite State Machines - Digital Design of Signal Processing Systems: A Practical Approach - page 398

9.4 Algorithmic State Machine Representation
9.4.1 Basics
Hardware mapping of signal processing and communication algorithms is the main focus of
this topic. These algorithms are mostly mapped on time-shared architectures. The architectures
require the design of FSMs to generate control signals for the datapath. In many designs the
controllers have algorithm-like functionality. The functionality also encompasses decision support
logic. Bubble diagrams are not flexible enough to describe the complex behavior of these finite state
machines. Furthermore, many design problems require gradual refinement and the bubble diagram
representation is not appropriate for this incremental methodology. The bubble diagram is also not
algorithm-like. The algorithmic state machine (ASM) notation is the representation of choice for
these design problems.
ASM is a flowchart-like graphical notation that describes the cycle-by-cycle behavior of an
algorithm. Each step transitioning from one state to another or to the same state takes one clock
cycle. The ASM is composed of three basic building blocks: rectangles, diamonds and ovals. Arrows
are used to interconnect these building blocks. Each rectangle represents a state and the state output
is written inside the rectangle. The state output is always an unconditional output, which is asserted
when the FSM transitions to a state represented by the respective rectangle. A diamond is used for
specifying a condition. Based on whether the condition is TRUE or FALSE, the next state or
conditional output is decided. An oval is used to represent a conditional output. As Moore machines
only have state outputs, Moore FSM implementations do not have ovals, but Mealy machines may
contain ovals in their ASM representations.
Figure 9.13 shows the relationship of three basic components in an ASM representation. For
TRUE or FALSE, T and F are written on respective branches. The condition may terminate in an
oval, which lists conditional output.

State Entry
Path

ASM Block

*

***

State
Name

STATE CODE

State Output List
--------------------------
--------------------------
--------------------------

State Box

T F

Condition

Condition Box

Conditional Output List
----------------

Output Box

Exit to other
ASM Block

Figure 9.13 Rectangle, diamond and oval blocks in an ASM representation