# State minimization and encoding

*Fewer states, and the codes you give them*

State minimization is the process of merging the equivalent states of a finite state machine (states that produce the same outputs and transition to equivalent states for every input) so the machine uses as few states, and therefore as few flip-flops, as possible; the related state assignment chooses a binary code for each remaining state, which fixes how complex the next-state and output logic becomes.

Group: Processor
URL: https://digiwleea.wleeaf.dev/learn/state-minimization/

A [finite state machine](https://digiwleea.wleeaf.dev/learn/state-machine/) is a state register plus next-state logic, and you usually design one by drawing a **state diagram** first: a bubble per state, an arrow per transition. But the first diagram you draw is rarely the most efficient one. Two refinements turn it into lean hardware. First, **state minimization** removes redundant states, which can save whole [flip-flops](https://digiwleea.wleeaf.dev/learn/dff/). Second, **state assignment** chooses the binary code for each remaining state, which decides how much gate logic the machine needs. This lesson is the rigor that follows the state-machine sketch.

## Equivalent states

Two states are **equivalent** when no outside observer could ever tell them apart. Concretely, states `P` and `Q` are equivalent if both:

- they produce the **same output** for every input value, and
- for **every** input value, they transition to states that are themselves equivalent.

The second condition is **recursive**, and it is the part people forget: matching outputs is not enough, the *futures* the two states lead to must also be indistinguishable. If two states are equivalent, you can delete one and redirect its incoming arrows to the other with **zero** change in the machine's behavior.

> **TIP:** An analogy: imagine two rooms in a building whose every door leads to identically furnished rooms, with identical signs and identical exits, all the way down. A blindfolded visitor dropped into either room could never figure out which one they are in, no matter how they move. So you can knock down the wall between them and have one room: nothing any visitor experiences changes. Equivalent states are rooms no visitor can distinguish, merged into one.

## The implication-chart method

To find every equivalent pair systematically, use the **implication chart** (also called the pair table). The procedure is mechanical:

1. List a cell for every unordered **pair** of states.
2. Cross out any pair whose **outputs differ** for some input. Different outputs make states distinguishable immediately, so they can never be equivalent.
3. For each surviving pair, write its **implied pairs**: the pairs of next-states the two states lead to, one implied pair per input value. The pair can be equivalent only if all its implied pairs are.
4. **Iterate:** cross out any pair one of whose implied pairs has just been crossed out. Repeat the sweep until a full pass changes nothing (a fixed point).
5. Every pair still un-crossed is an equivalent pair. Merge equivalent pairs (transitively) into combined states.

> **TIP:** The same job has a cleaner modern phrasing: **partition refinement**, the algorithm that also minimises a finite automaton. Start with states split into blocks by their output behavior, then repeatedly split any block whose members, under some input, jump to *different* blocks. When no block splits any further, each remaining block is one merged state. The implication chart and partition refinement compute the same equivalence classes; pick whichever you find easier to run by hand.

## Worked example: reducing a 5-state machine

Take this Moore machine (output `z` depends on the state alone) with one input `x` and five states `S0` through `S4`:

| Present | Next (x=0) | Next (x=1) | z |
| --- | --- | --- | --- |
| S0 | S1 | S2 | 0 |
| S1 | S3 | S0 | 0 |
| S2 | S4 | S0 | 0 |
| S3 | S0 | S4 | 1 |
| S4 | S0 | S3 | 1 |

_The original 5-state table. States S0, S1, S2 output 0; states S3, S4 output 1. Five states need 3 flip-flops (since 2 flip-flops cover only 4 states)._

1. **Group by output.** `{S0, S1, S2}` all output `0`; `{S3, S4}` both output `1`. Any equivalent pair must live inside one group, so only same-group pairs survive step 2.
2. **Test `S3, S4`.** Same output (`1`). On `x = 0` both go to `S0` (matched). On `x = 1`, `S3 -> S4` and `S4 -> S3`, the implied pair `(S3, S4)`, which is the pair itself, so it is self-consistent. Nothing forces a cross-out: **`S3` and `S4` are equivalent.** Merge them; call the merged state `S3`.
3. **Test `S1, S2`.** Same output (`0`). On `x = 0`, `S1 -> S3` and `S2 -> S4`, the implied pair `(S3, S4)`, which we just proved equivalent (matched). On `x = 1` both go to `S0` (matched). So **`S1` and `S2` are equivalent.** Merge them; call the merged state `S1`.
4. **Test `S0` against `S1`.** Same output, but on `x = 0`, `S0 -> S1` while `S1 -> S3`, the implied pair `(S1, S3)`, whose members have *different* outputs (`0` vs `1`). That pair is crossed out, so `S0` is **not** equivalent to `S1`. `S0` stays on its own.

Two merges took the machine from five states to three (`S0`, the merged `S1`, the merged `S3`):

| Present | Next (x=0) | Next (x=1) | z |
| --- | --- | --- | --- |
| S0 | S1 | S1 | 0 |
| S1 | S3 | S0 | 0 |
| S3 | S0 | S3 | 1 |

_The minimized 3-state table, identical in behavior to the original. Three states need only 2 flip-flops, so the merge saved one flip-flop and shrank the next-state logic._

## State assignment: the codes change the cost

> **TIP:** **Two separate knobs.** Reducing states and choosing an encoding are independent steps: neither forces the other. Minimisation shrinks *how many* states you must encode, and the encoding then fixes the *shape* of the next-state logic. You can encode a machine you never minimised, and a minimised machine can still be encoded any way you like, so treat the reduction above and the codes below as two dials you turn separately.

Minimizing the *count* of states is only half the job. You still have to give each state a **binary code** to store in the flip-flops, and that choice, the **state assignment**, directly sets how complex the next-state and output logic is. The very same 3-state machine costs different amounts of gates under different encodings. Three common schemes:

- **Binary (minimal):** `ceil(log2 n)` flip-flops for `n` states. Our three states fit in 2 flip-flops (`S0 = 00`, `S1 = 01`, `S3 = 10`). Fewest flip-flops, but the next-state logic is a tangle of [Karnaugh-map](https://digiwleea.wleeaf.dev/learn/karnaugh/) equations over the encoded bits, and several bits can change in one transition.
- **One-hot:** one flip-flop per state, exactly one of them high (`S0 = 001`, `S1 = 010`, `S3 = 100`). Many flip-flops (`n` of them), but the next-state logic becomes trivial and fast: each state's flip-flop is set by a simple OR of the transitions that lead into it. Outputs are often a single flip-flop. This is the usual choice on an FPGA, where flip-flops are plentiful and speed matters.
- **Gray encoding:** assign codes so states that follow each other in the sequence differ in exactly one bit. Fewer bits flip per transition means fewer transient glitches and lower switching power on the state register, which suits counters and other near-linear sequences. (It is the same single-bit-change idea as [Gray code](https://digiwleea.wleeaf.dev/learn/gray-code/).)

To see the contrast concretely, look at the flip-flop that drives the merged state `S3` under one-hot. `S3` is entered from `S1` on `x = 0` and from `S3` itself on `x = 1`. So its next-state input is just one OR of two product terms, reading the state bits directly:

```
one-hot:   D(S3) = (S1 AND x') OR (S3 AND x)
```

There is one such clean term per incoming arrow, and you can read the equation straight off the state diagram with no minimisation. Under the binary encoding you would instead build a [Karnaugh map](https://digiwleea.wleeaf.dev/learn/karnaugh/) for each of the two state bits as functions of `(bit1, bit0, x)` and minimise, fewer flip-flops but more thinking and usually a deeper logic path. That is the real trade: one-hot spends flip-flops to buy simple, fast logic; binary spends logic to buy fewer flip-flops.

## The one-hot method: read the logic off the diagram

That `D(S3)` shortcut is not a one-off, it is a full design method. Give **every** state its own flip-flop and hold exactly **one** of them high at a time, the single high bit marking where the machine currently is. To find the logic that feeds each flip-flop you never build a next-state table: you look only at the arrows that point **into** that state. Each incoming arrow contributes one product term, the **source** state's flip-flop ANDed with the input condition that arrow needs, and the flip-flop's `D` input is just the **OR of those terms**. One arrow in means one term, two arrows in means an OR of two.

Run it on our minimized three-state machine (`S0`, `S1`, `S3`), one flip-flop per state, by tracing the arrows into each bubble:

- `S0` is entered from `S1` on `x = 1` and from `S3` on `x = 0`. Two arrows in, so `D(S0) = (S1 AND x) OR (S3 AND x')`.
- `S1` is entered from `S0` on **both** input values (`S0` goes to `S1` whether `x` is `0` or `1`). That is `(S0 AND x') OR (S0 AND x)`, which collapses to just `D(S1) = S0`.
- `S3` is entered from `S1` on `x = 0` and from itself on `x = 1`, the same OR of two terms we read off above: `D(S3) = (S1 AND x') OR (S3 AND x)`.

```
one-hot:   D(S1) = (S0 AND x') OR (S0 AND x) = S0
```

Three flip-flops, each driven by at most a two-term OR you wrote **by inspection**, with no state table and no [Karnaugh map](https://digiwleea.wleeaf.dev/learn/karnaugh/). The outputs are just as cheap: a Moore output that is `1` in some states is an OR of exactly those states' flip-flops, so here `z = S3` is a single wire (state `S3` is the only one that outputs `1`). Compare the binary build of the very same machine: encode the states, tabulate the next state, then minimise a K-map for each state bit. That gap is the whole tradeoff.

**Binary versus one-hot, in one breath.** For `n` states, binary uses `ceil(log2 n)` flip-flops and one-hot uses `n`, so one-hot always spends **more** flip-flops. In exchange its next-state logic stays shallow (one OR per state) and usually faster, and you can read it straight off the diagram, while binary's logic is denser and typically deeper. That is why one-hot is a common default on an **FPGA**, where flip-flops are plentiful and the clock speed is set by the longest logic path, whereas a binary (or near-binary) encoding tends to win on an **ASIC**, where every flip-flop costs silicon area. Same machine, same behavior, opposite thing being economised.

## Unused states and self-correcting machines

Encoding 3 states in 2 flip-flops uses codes `00`, `01`, `10` and leaves `11` **unused**. Nothing in the design says what happens if the machine ever finds itself in `11`, yet at power-up the flip-flops come up in some arbitrary state, and a glitch could momentarily push the register there. A **safe** (self-correcting) FSM defines the next state of every unused code to be a known good state, usually the reset state, so the machine *recovers* on the next clock instead of locking up or wandering. One-hot encoding has even more unused codes (every non-one-hot pattern, including all-zero), so it also needs a defined recovery, often a reset that forces the legal start state.

> **WARN:** **Common mistakes.** Equivalence needs **both** matching outputs **and** equivalent next-states for every input; matching outputs alone is not enough, and the next-state condition is recursive. Run the implication chart to a **fixed point**: one cross-out can trigger another, so keep sweeping until nothing changes. Minimal *states* is not the same as minimal *logic*: a clever state **assignment** often matters more than removing one extra state. One-hot uses **more** flip-flops, not fewer, it trades them for simpler, faster logic. And never leave **unused states** undefined, or the machine can hang in an illegal code with no way back.

**Q (Try it):** Two states `P` and `Q` of a Moore machine both output `0`. On input `0` both go to state `R`; on input `1`, `P` goes to `S` and `Q` goes to `T`. What extra condition makes `P` and `Q` equivalent? If they are, and the machine had exactly 5 states, how many flip-flops does merging them save?

**A:** `P` and `Q` already match on outputs and on the `x = 0` transition (both to `R`). They are equivalent only if their `x = 1` successors `S` and `T` are **themselves equivalent**, that is, the implied pair `(S, T)` must hold (same output, equivalent next-states). Equivalence is recursive, so you cannot stop at `P` and `Q`. If they do merge, the machine drops from 5 states to 4. Five states need `ceil(log2 5) = 3` flip-flops and four states need `ceil(log2 4) = 2`, so the merge **saves one flip-flop**.

> **KEY:** State minimization and assignment are exactly what an FSM synthesis tool does between your state diagram and the final gates, and the encoding is a genuine engineering knob: one-hot for FPGA speed, binary for ASIC area, Gray for low-power sequential counters. It matters here because the CPU's [control unit](https://digiwleea.wleeaf.dev/learn/control/) is a finite state machine, the one that walks fetch, decode, execute, so these choices set how compact and how fast the whole processor's controller is. With states reduced and encoded, the next group assembles the storage and control blocks into [memory](https://digiwleea.wleeaf.dev/learn/ram/) and the datapath of a working machine.

### FAQ

**Q:** What is state minimization in an FSM?

**A:** State minimization is merging the equivalent states of a finite state machine so it uses as few states as possible. Fewer states need fewer flip-flops (the register width is `ceil(log2 states)`) and usually less next-state logic, with no change in the machine's externally observable behavior.

**Q:** When are two states of a finite state machine equivalent?

**A:** Two states are equivalent when, for every input value, they produce the same output AND transition to states that are themselves equivalent. The second condition is recursive: matching outputs alone is not enough, the entire future behavior reachable from each state must be indistinguishable.

**Q:** What is the implication chart method?

**A:** A systematic way to find every equivalent pair. List a cell for each pair of states, cross out pairs whose outputs differ, note each surviving pair's implied next-state pairs, then iterate: cross out any pair whose implied pair was crossed out, repeating until nothing changes. The pairs left un-crossed are equivalent and can be merged.

**Q:** What is the state assignment problem?

**A:** State assignment is choosing the binary code stored in the flip-flops for each state of an FSM. The choice does not change behavior, but it directly sets the complexity of the next-state and output logic, so different assignments of the same machine can need very different amounts of gates and have different speeds.

**Q:** What is the difference between one-hot and binary state encoding?

**A:** Binary uses the fewest flip-flops, `ceil(log2 n)` for `n` states, but its next-state logic is denser and several bits can change per transition. One-hot uses one flip-flop per state with exactly one high, so it needs more flip-flops but makes the next-state logic a simple, fast OR of incoming transitions, which is why FPGAs favour it.

**Q:** How do you find the next-state logic for a one-hot state machine?

**A:** Give each state its own flip-flop, then for every state look at the arrows entering it on the state diagram. Each incoming arrow becomes one product term, the source state's flip-flop ANDed with the input condition on that arrow, and the flip-flop's `D` input is the OR of those terms. You read the equations straight off the diagram with no next-state table and no Karnaugh map, which is why one-hot is fast to design even though it uses one flip-flop per state.