# Algorithmic state machines (ASM charts)

*A flowchart notation for state machines*

An algorithmic state machine (ASM) chart is a flowchart-style notation for a finite state machine, built from three boxes (a rectangular state box that names a state and lists its Moore outputs, a diamond decision box that tests one input and branches, and a rounded conditional-output box that asserts a Mealy output only on a chosen path), where one ASM block (a state box plus the decision and conditional-output boxes below it) is everything that happens in a single clock cycle.

Group: Processor
URL: https://digiwleea.wleeaf.dev/learn/asm-charts/

You can already design a [finite state machine](https://digiwleea.wleeaf.dev/learn/state-machine/) from a spec and draw it as a **state diagram**: a bubble per state, a labelled arrow per transition, and (from the [sequence detector](https://digiwleea.wleeaf.dev/learn/sequence-detector/)) a **Moore** output written in the bubble or a **Mealy** output written on the arrow. That drawing is perfect for a handful of states. It gets tangled the moment a controller has to assert several outputs at once, and it does not read like a program. This lesson introduces a second notation for the exact same machines, the **algorithmic state machine (ASM) chart**, which lays a state machine out as a flowchart you can read top to bottom, one clock at a time. It is the step between the state diagram and writing the machine as code.

## Why a second notation?

A state diagram answers 'which state do I go to next?' well, but it has nowhere clean to write everything a state *does*. A real datapath controller might, in one state, load a register, select a [mux](https://digiwleea.wleeaf.dev/learn/mux/), and enable a [bus](https://digiwleea.wleeaf.dev/learn/tristate/) driver all at once, and cramming three outputs inside one bubble is unreadable. An ASM chart gives each state a **box with room to list every output**, and it draws the input tests as a flow of decisions, so it reads like a flowchart (or a program) rather than a tangle of arrows. That resemblance is the point: an ASM chart maps almost line for line onto register-transfer-level (RTL) code, which is why it is the notation designers reach for on the way to an HDL.

## The three boxes

An ASM chart is drawn with exactly three shapes. Learn the shapes and what goes inside each and you can read any chart:

- **State box (rectangle).** Names one state and lists the **Moore** outputs asserted whenever the machine sits in that state. It has one entry at the top and one exit at the bottom. An output written here is unconditional: it is on for the whole clock the machine spends in this state, no matter what the inputs do.
- **Decision box (diamond).** Tests **one** input (or one boolean condition) and branches. It has two exits, labelled `1` and `0` for the two values of the tested input. A decision box does **not** cost a clock; it just routes the flow within the current state's block.
- **Conditional-output box (rounded rectangle).** Holds a **Mealy** output that is asserted only when the flow actually reaches it, that is, only for the branch of a decision box it hangs off. Because reaching it depends on both the state and the tested input, its output is a Mealy output, live only while that input path is active.

> **TIP:** The one-line memory aid: **rectangle = state (Moore output inside), diamond = a test, rounded box = a conditional (Mealy) output on a branch.** It is the same Moore-vs-Mealy split from the [sequence detector](https://digiwleea.wleeaf.dev/learn/sequence-detector/), just drawn with boxes: a Moore output goes in the **state box**, a Mealy output goes in a **rounded box** on the path that triggers it.

## One ASM block = one clock

The unit that ties an ASM chart to time is the **ASM block**: one state box together with all the decision and conditional-output boxes that follow it, up to the exits that lead to the *next* state box. An ASM block has exactly **one entry** (its state box) and one or more exits, and it represents **everything the machine does in a single clock cycle**: the Moore outputs listed in the state box, the input tests in the decision boxes, and any Mealy outputs on the taken path. Every box inside one block happens in the **same** clock. A clock edge is spent only when the flow crosses an exit into the next block's state box.

> **KEY:** This is the mental model to hold onto: draw an imaginary clock line just above each state box. Everything below the line and inside that block settles during one clock; on the next clock edge the machine jumps to whichever state box the block's active exit points at. So an ASM block is one iteration of the machine, exactly like one pass through the body of a loop in a program.

## Worked example: the detect-two-1s detector as an ASM chart

Take the Moore machine you already built in the [sequence detector](https://digiwleea.wleeaf.dev/learn/sequence-detector/) lesson: watch a serial input `X`, one bit per clock, and raise `Z` whenever the two most recent bits were both `1` (overlapping). It has three states: `S0` (last bit not a `1`, also reset), `S1` (just saw one `1`), and `S2` (saw two-or-more `1`s in a row, the only state where `Z = 1`). Converting its state diagram to an ASM chart is mechanical: one block per state, with a decision box on `X` inside each. I will write a block as its state box in square brackets, then where the `X` decision's `1` and `0` exits lead:

- **`[S0]` block.** State box `[S0]` (no output, so `Z = 0` here). One decision box tests `X`: the `1` exit goes to the `[S1]` block, the `0` exit loops back to `[S0]`.
- **`[S1]` block.** State box `[S1]` (no output). Decision box on `X`: `1` goes to the `[S2]` block, `0` goes back to `[S0]`.
- **`[S2]` block.** State box `[S2]` with the Moore output `Z = 1` written inside it (asserted the whole clock the machine sits in `S2`). Decision box on `X`: `1` stays in `[S2]` (the overlap self-loop), `0` goes back to `[S0]`.

That is the whole machine. Notice the ASM chart carries the same information as the state-transition table you filled in earlier: reading each block top to bottom gives you exactly one row per (current state, input) pair. Writing the states as `Q1 Q0` with `S0 = 00`, `S1 = 01`, `S2 = 10`:

| Q1 | Q0 | X | D1 | D0 | Z |
| --- | --- | --- | --- | --- | --- |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 | 1 |

_The same detector as a state-transition and output table (Q1 Q0 is the current state, X the input, D1 D0 the next state, Z the output). Each ASM block above supplies two of these rows, one per exit of its decision box: the [S0] block gives the first two rows, [S1] the middle two, [S2] the last two. The chart and the table are two views of one machine._

And the table is what compiles to gates and [flip-flops](https://digiwleea.wleeaf.dev/learn/dff/): `D1 = X AND (Q1 OR Q0)`, `D0 = X AND NOT Q1 AND NOT Q0`, `Z = Q1`. So the pipeline is spec -> state diagram -> ASM chart -> table -> hardware, with the ASM chart the readable middle step. Here is the circuit those three ASM blocks describe:

_Circuit diagram: The hardware the ASM chart specifies: two D flip-flops hold the state Q1 Q0, the gates compute D1 = X AND (Q1 OR Q0) and D0 = X AND NOT Q1 AND NOT Q0, and the Moore output Z = Q1. Open it in the lab and feed X one bit per clock (try 0 1 1 0 1 1 1): each block's decision box is the X test, and Z rises the clock after each pair of 1s._

## Adding a conditional output (the Mealy version)

The conditional-output box only appears when a machine has a **Mealy** output. Recall the Mealy detector for the same spec: two states, `M0` (last bit not a `1`) and `M1` (last bit was a `1`), with `Z` asserted on the transition out of `M1` when the new bit is also `1`. In an ASM chart that Mealy output lives in a rounded box on a decision branch:

- **`[M0]` block.** State box `[M0]` (no output). Decision box on `X`: `1` goes to `[M1]`, `0` loops back to `[M0]`.
- **`[M1]` block.** State box `[M1]` (no Moore output). Decision box on `X`: on the `1` exit, pass through a rounded conditional-output box `Z = 1`, then go to `[M1]`; on the `0` exit, go straight to `[M0]` with no output.

That rounded box is exactly the Mealy behavior `Z = Q AND X`: it fires only while the machine is in `M1` **and** the live input `X` is `1`, in the same cycle as that second `1`, and it drops the instant `X` goes to `0` even though the state has not yet changed. Compare that with the Moore chart, where `Z = 1` sat inside the `[S2]` **state box** and stayed on for the whole clock regardless of the input. Same detector, two output styles, drawn with two different boxes.

## Reading a chart back into a state diagram

The conversion runs both ways, and back is just as mechanical. Turn each **state box** into a **bubble**. Follow the decision boxes below a state box to find its exits: the sequence of `1`/`0` answers that reaches an exit becomes the label on the **arrow** to the next bubble. A Moore output written inside a state box becomes a label **inside** the corresponding bubble; a conditional-output box on a branch becomes a Mealy output written **on** that arrow. Nothing is lost or added: the ASM chart and the state diagram hold identical information, one drawn as a flow and one drawn as bubbles and arrows.

> **WARN:** **Common mistakes.** Treating each box as its own clock cycle: it is not. Everything inside one ASM block (the state box plus all the decision and conditional-output boxes below it) happens in the **same** clock; a clock edge is spent only when the flow crosses an exit into the next block's state box. Confusing the two output boxes: an output in the **rectangular state box** is Moore (on whenever the machine is in that state), while an output in the **rounded box** is Mealy (on only when that decision path is taken, and it can change mid-cycle if the input does). Letting an exit path reach two state boxes, or none: every path out of a block must land on exactly one state box (one entry per block). And drawing a decision box that tests the *next* state's input: a block always tests the inputs as they stand during its own clock.

> **KEY:** With ASM charts you have the design notation that scales all the way to a processor. The CPU's [control unit](https://digiwleea.wleeaf.dev/learn/control/) is a state machine whose ASM chart has one block per micro-step of fetch-decode-execute, each state box listing the control signals that step asserts (register loads, [mux](https://digiwleea.wleeaf.dev/learn/mux/) selects, [bus](https://digiwleea.wleeaf.dev/learn/tristate/) enables) and each decision box branching on the opcode. Because one ASM block maps almost directly onto the body of a clocked HDL process (a `case` on the current state, with the state's outputs and `if`/`else` branches mirroring the boxes), this notation is the true bridge from state-machine theory to real code.

**Q (Try it):** An ASM chart has an output `A` written inside a rectangular state box `[S2]`, and an output `B` written in a rounded box hanging off the `1` exit of a decision box inside `[S2]`. Classify `A` and `B` as Moore or Mealy, and say exactly when each asserts.

**A:** `A` is a **Moore** output: it sits in the state box, so it is asserted for the whole clock the machine is in `S2`, no matter what the inputs do (and, like any state output, it turns on the clock after the machine enters `S2`). `B` is a **Mealy** output: it lives in a conditional-output box on a decision branch, so it asserts only while the machine is in `S2` **and** the tested input is `1`, in the same cycle as that input, and it drops the moment the input goes to `0` even though the state has not changed. Same block, two output styles: exactly the Moore vs Mealy distinction from the [sequence detector](https://digiwleea.wleeaf.dev/learn/sequence-detector/).

### FAQ

**Q:** What is an ASM chart?

**A:** An algorithmic state machine (ASM) chart is a flowchart-style notation for a [finite state machine](https://digiwleea.wleeaf.dev/learn/state-machine/), built from three boxes: a rectangular **state box** (naming a state and listing its Moore outputs), a diamond **decision box** (testing one input and branching), and a rounded **conditional-output box** (a Mealy output asserted only on a chosen path). One ASM block, a state box plus the decision and conditional-output boxes below it, is everything that happens in a single [clock](https://digiwleea.wleeaf.dev/learn/clock/) cycle.

**Q:** What are the three boxes in an ASM chart?

**A:** A **state box** (rectangle) holds the state name and the Moore outputs asserted whenever the machine is in that state. A **decision box** (diamond) tests one input and has two exits, one for each value. A **conditional-output box** (rounded rectangle) holds a Mealy output asserted only when the decision path leading to it is taken. Rectangle for state, diamond for a test, rounded box for a conditional output.

**Q:** What is an ASM block?

**A:** An ASM block is one state box together with all the decision and conditional-output boxes that follow it before the next state box. It has exactly one entry (the state box) and represents everything the machine does in a single [clock](https://digiwleea.wleeaf.dev/learn/clock/) cycle: the Moore outputs in the state box, the input tests in the decision boxes, and any Mealy outputs on the taken path. Crossing from a block's exit into the next block's state box is where the clock edge is spent.

**Q:** What is the difference between an ASM chart and a state diagram?

**A:** They carry the same information about a [finite state machine](https://digiwleea.wleeaf.dev/learn/state-machine/) but lay it out differently. A **state diagram** uses bubbles for states and labelled arrows for transitions, which gets cramped when a state drives many outputs at once. An **ASM chart** uses a flowchart: a state box per state (with room to list every output), diamond decision boxes for the input tests, and rounded conditional-output boxes for Mealy outputs, read top to bottom, one block per clock. The ASM chart is closer to code, so it is the usual bridge to RTL and HDL.

Next you will put ASM charts to work on the real thing: the [control unit](https://digiwleea.wleeaf.dev/learn/control/) that sequences the CPU, the [datapath and control](https://digiwleea.wleeaf.dev/learn/datapath/) that wire it to the registers and [ALU](https://digiwleea.wleeaf.dev/learn/alu/), and finally coding a clocked controller in [Verilog](https://digiwleea.wleeaf.dev/learn/verilog-sequential/), where each ASM block becomes one branch of a `case` inside a clocked process.