Detailed Reviewer: Algorithm State Machine (ASM) Charts
This reviewer provides a comprehensive breakdown of Algorithm State Machine (ASM)
charts as explained in the video. It covers the core concepts, components, diagrams,
and specific examples to help you master the material for your exam.
1. Introduction to ASM Charts
An ASM chart is a graphical method used to describe the behavior of a sequential
circuit or a Finite State Machine (FSM). It is equivalent to a state diagram but is often
preferred in digital design for several reasons:
● It is more descriptive and easier to understand.
● It provides a clearer path from a design concept to the final hardware
implementation.
● It visually organizes the design into modular blocks, which is helpful for complex
systems.
The chart shows the sequence of events, the timing relationships between states
(synchronized by a clock), and how inputs determine the transitions between states
and any resulting outputs.
2. Core Difference: ASM Chart vs. Software Flowchart
This is a fundamental distinction emphasized in the video. While they may look similar,
their purposes are entirely different.
| Feature | Software Flowchart | Algorithm State Machine (ASM) Chart |
| Purpose | Represents a software algorithm or process. It's a tool for programming. |
Represents a hardware algorithm for a synchronous digital system. It's a tool for digital
design. |
| Timing | Has no inherent concept of time. Steps execute sequentially as fast as the processor
allows. | Is fundamentally tied to timing. Transitions between states occur only on the active
edge of a clock pulse. Each state represents one clock cycle. |
| Structure | Shows the flow of computational steps and decisions. | Describes the behavior of
a Finite State Machine (FSM), detailing states and transitions. |
In short, a flowchart details a computational procedure, while an ASM chart
describes the behavior of physical hardware over discrete time intervals (clock
cycles).
3. The Three Components of an ASM Chart
ASM charts are constructed from three basic building blocks:
a. State Box
● Symbol & Structure: A rectangle.
● Purpose: Represents a single state of the FSM. The machine remains in this state
for the duration of one clock cycle.
● Contents: The state name (e.g., Idle), its optional binary code, and any
Moore-type outputs that are active in this state. Moore outputs depend only on
the current state.
+------------------+ <-- Entry Path
| State_Name |
| (State_Code) |
|------------------|
| Moore_Output=1 | (Active for the entire state)
+------------------+
| <-- Exit Path
V
b. Decision Box
● Symbol & Structure: A diamond.
● Purpose: Tests an input condition to decide the machine's next state or if a
conditional output should be generated.
● Paths: It has one entry path and two exit paths, labeled 1 (True) and 0 (False),
representing the outcome of the condition.
|
V
+-----------+
/ Input X \
/ \
+-----------------+
| |
(False) V 0 V 1 (True)
c. Conditional Output Box
● Symbol & Structure: An oval or a rectangle with curved sides.
● Purpose: Represents a Mealy-type output.
● Behavior: This output is generated only if the machine is in a specific state AND
the input condition leading to it is true.
(from a Decision Box '1' path)
|
V
+----------------+
| Mealy_Output=1 |
+----------------+
|
V
(to the next state)
4. The ASM Block
An ASM Block is a fundamental structure that encapsulates everything that happens
within one state during a single clock cycle. It consists of:
1. One State Box.
2. All the Decision Boxes and Conditional Output Boxes associated with that
state.
An ASM Block has a single entry point but can have multiple exit paths. Each exit path
defines a transition to a next state, which will be entered on the next clock pulse.
+------------------+ <-- Single Entry to the Block
| STATE_A |
+------------------+
|
V
+-----------+
/ Input X \
/ \
+-----------------+
| |
V0 V 1
| |
| +----------------+
| | Output_Z = 1 | (Conditional Output)
| +----------------+
| |
V V
(To STATE_B) (To STATE_C) <-- Multiple Exit Paths
5. Video Examples Explained in Detail
Example 1: Binary Counter (Moore Machine)
● Description: A 2-bit binary counter that cycles through states 00 -> 01 -> 10 ->
11 and then repeats. The outputs, A and B, are the state values themselves.
● Analysis: This is a Moore machine because the outputs (00, 01, 10, 11) depend
only on the current state, not on any external input. There are no inputs
controlling the transitions, so there are no Decision Boxes.
● ASM Chart Diagram:
[START]
|
V
+-----------------+
| S0 |
| (00) |
|-----------------|
| AB=00 | <-- Moore Output
+-----------------+
|
V
+-----------------+
| S1 |
| (01) |
|-----------------|
| AB=01 | <-- Moore Output
+-----------------+
|
V
+-----------------+
| S2 |
| (10) |
|-----------------|
| AB=10 | <-- Moore Output
+-----------------+
|
V
+-----------------+
| S3 |
| (11) |
|-----------------|
| AB=11 | <-- Moore Output
+-----------------+
|
+<------------------+
| |
+----->(Back to S0)--+
Example 2: Sequence Detector "101" (Mealy Machine)
● Description: A machine with one input X that detects the sequence "101". The
output Z becomes 1 when the third bit of the sequence (1) is detected.
● Analysis: This is a Mealy machine because the output Z=1 depends on being in
state S2 (having received "10") AND receiving an input X=1.
● ASM Chart Diagram:
[START]
|
V
+-----------------+
| S0 (Idle) |
+-----------------+
|
V
+-----------+
/ Input X \
/ \
+-----------------+
(0) | | (1)
+<---------+ V
| |
| (To S1)
| |
| V
+-----------------+
| S1 (Got "1") |
+-----------------+
|
V
+-----------+
/ Input X \
/ \
+-----------------+
(0) | | (1)
V +------> (Back to S1)
|
(To S2)
|
V
+-----------------+
| S2 (Got "10") |
+-----------------+
|
V
+-----------+
/ Input X \
/ \
+-----------------+
(0) | | (1)
| V
V +----------------+
(To S0) | Z=1 | <-- Conditional (Mealy) Output
+----------------+
|
V
(To S1)
6. Key Rules for Drawing ASM Charts
1. Unique Exit Path: For any possible combination of inputs, there must be exactly
one valid exit path from an ASM block. This ensures the machine knows precisely
which state to go to next.
2. Transitions Lead to States: All paths must eventually lead to a state box (the
next state). You cannot have a path that ends at a decision or conditional output
box.
3. No Feedback within a Block: A path cannot loop back to a decision box within
the same ASM block. All paths must exit the block to a defined next state.
Sample Quiz: ASM Charts
Test your knowledge with these questions. The answers are provided at the end.
Part I: Multiple Choice
1. What is the most significant difference between an ASM chart and a traditional
software flowchart?
A. ASM charts use different shapes.
B. ASM charts incorporate timing relationships via clock cycles.
C. Flowcharts are only for binary logic.
D. ASM charts cannot have conditional branches.
2. In an ASM chart, which component is used to represent a Mealy-type output?
A. State Box
B. Decision Box
C. Conditional Output Box
D. An arrow
3. An entire ASM Block (one state box and its associated decision/conditional boxes)
corresponds to the events happening in:
A. Multiple clock cycles
B. One clock cycle
C. Half a clock cycle
D. Only when an input changes
4. A Moore-type output, which depends only on the current state, is written inside
the:
A. Decision Box
B. Conditional Output Box
C. Next to the state name
D. State Box
5. How many entry and exit paths does a Decision Box have?
A. One entry, one exit
B. Two entries, one exit
C. One entry, two exits
D. Two entries, two exits
Part II: True or False
1. True / False: An ASM chart can only be used to design Moore machines.
2. True / False: For any given combination of inputs, it is possible to have multiple
valid exit paths from a single ASM block.
3. True / False: Every state in a sequential circuit corresponds to one State Box in
an ASM chart.
Part III: Short Answer
1. List the three main components of an ASM chart and briefly describe the purpose
of each.
2. Why is an ASM chart more suitable for designing a piece of digital hardware than
a flowchart?
Answer Key
Part I: Multiple Choice
1. B. ASM charts incorporate timing relationships via clock cycles. This is the
fundamental difference.
2. C. Conditional Output Box. Mealy outputs are conditional on both state and
input.
3. B. One clock cycle. An ASM block describes all actions within a single state for
one clock period.
4. D. State Box. Moore outputs are associated directly with the state.
5. C. One entry, two exits. The two exits correspond to the true (1) and false (0)
outcomes of the condition.
Part II: True or False
1. False. ASM charts can represent Moore machines, Mealy machines, or a
combination of both.
2. False. A critical rule is that there must be exactly one unique exit path for any
given input combination to avoid ambiguity.
3. True. There is a one-to-one correspondence between states and state boxes.
Part III: Short Answer
1. The three main components are:
○ State Box (Rectangle): Represents a state and contains Moore outputs.
Defines the machine's status for one clock cycle.
○ Decision Box (Diamond): Tests an input condition to decide the next path.
○ Conditional Output Box (Oval): Represents a Mealy output that is active
only under a specific input condition while in a certain state.
2. An ASM chart is more suitable because it is designed specifically for hardware. It
directly models the behavior of a Finite State Machine and, most importantly,
incorporates the concept of timing (clock cycles), which is essential for
designing synchronous digital circuits. A flowchart lacks this critical timing
concept.
