State Minimization & Assignment

A state diagram drawn directly from a word description of the desired behavior often has more states than it strictly needs — two states that look different on paper can turn out to behave identically in every way that matters. This page covers how to detect and merge those redundant states, how to pick binary codes for the states that remain, and then walks through the full design procedure — state diagram all the way to gate-level implementation — end to end.

Equivalent states

Two states are equivalent if, for every possible input sequence starting from either one, they produce exactly the same output sequence and end up in equivalent states again. If two states are equivalent, one of them is redundant — the FSM behaves identically whether it's in one or the other, so they can be merged into a single state without changing the circuit's behavior at all.

The standard way to find equivalent states is a implication chart (also called a state-equivalence table): start by listing every pair of states, ruling out any pair whose outputs already differ for some input (they clearly aren't equivalent), and iteratively check whether the remaining pairs also transition to equivalent states for every input — a pair only survives if its next-state pairs, for every input value, are themselves already known (or provisionally assumed) to be equivalent.

Example state table (before minimization):
State | X=0        | X=1
S0    | S1, 0       | S2, 0
S1    | S3, 0       | S2, 0
S2    | S1, 0       | S4, 1
S3    | S1, 0       | S2, 0
S4    | S1, 0       | S2, 1

Checking S1 vs S3: both output 0 for both inputs.
  X=0: S1→S3, S3→S1  (same pair, trivially consistent)
  X=1: S1→S2, S3→S2  (both go to S2 — consistent)
  → S1 and S3 are equivalent; merge them.

Checking S2 vs S4: both output 0 for X=0, both output 1 for X=1.
  X=0: S2→S1, S4→S1  (same target — consistent)
  X=1: S2→S4, S4→S2  (each other — consistent)
  → S2 and S4 are equivalent; merge them.

Minimized table (S1=S3, S2=S4):
State | X=0     | X=1
S0    | S1, 0    | S2, 0
S1    | S1, 0    | S2, 0
S2    | S1, 0    | S2, 1

Five states collapsed to three with no change in external behavior — fewer states means fewer flip-flops (a state count of n needs ⌈log₂ n⌉ flip-flops, so crossing a power-of-2 boundary during minimization can directly save a whole flip-flop) and generally simpler next-state and output logic once the states are assigned binary codes. For larger machines this process is run algorithmically rather than by hand — but the underlying idea is always the same: repeatedly rule out non-equivalent pairs until only genuinely interchangeable states remain, then merge them.

State assignment

Once the minimal set of states is fixed, each one needs a unique binary code before any next-state logic can be derived — this is state assignment, and unlike minimization, it doesn't have one objectively correct answer; different codings trade off differently:

• Binary (sequential) assignment — states numbered 0, 1, 2, ... in plain binary. Uses the minimum number of flip-flops (⌈log₂ n⌉ for n states), but the resulting next-state logic doesn't follow any particular pattern and can end up needing more combinational gates than other schemes.
• One-hot assignment — one flip-flop per state, with exactly one bit set at a time (the same "exactly one 1" structure as the ring counter two pages back). Uses far more flip-flops (n instead of ⌈log₂ n⌉), but each state's next-state and output logic tends to be simpler and faster to decode, since "am I in state S2" is just reading a single flip-flop rather than comparing several bits — a common choice in FPGAs, where flip-flops are comparatively cheap and plentiful but combinational logic (LUTs) is often the tighter resource.
• Gray-code assignment — consecutive states differ by exactly one bit, the same adjacency property from Karnaugh maps in Logic Minimization. Particularly useful when an FSM's states form a natural linear or cyclic sequence (like a counter, or a machine walking through a fixed protocol sequence step by step) — only one flip-flop toggles per transition, which reduces switching noise and avoids transient invalid-looking codes on the state bus, mirroring the same glitch concern that motivated Gray code originally in Digital Codes.

There's no universal "best" choice — it depends on whether flip-flops or combinational logic are the scarcer resource in the target technology, and whether the state structure naturally suggests one encoding over another. Binary assignment is the default when in doubt; one-hot and Gray-code assignment are reached for when their specific structural advantage — decode simplicity or single-bit-transition safety — is worth the extra flip-flops.

The complete FSM design procedure

Putting minimization, assignment, and the excitation-table method from the counter-design procedure together gives the full process for turning a state diagram into a working circuit:

1. State diagram → state table: capture every state, every transition, and every output as a table (as in FSM Fundamentals).
2. Minimize: merge equivalent states using the implication-chart method above, if any exist.
3. Assign codes: choose an assignment scheme (binary, one-hot, or Gray) and give each remaining state a unique bit pattern.
4. Derive excitation equations: for each flip-flop, and for each output, treat its required value as a Boolean function of the current-state bits (and, for a Mealy machine's outputs, the current inputs too) — exactly the excitation-table step from Counters, generalized to include real inputs instead of just "always advance."
5. Minimize the logic: K-map or otherwise simplify each derived expression, treating unused state codes (if the assignment doesn't use every available bit pattern) as don't-cares — the same technique from Logic Minimization.
6. Implement: wire the minimized next-state logic into the state register's flip-flop inputs, and the (possibly separate) output logic to the output pins — a Moore machine's output logic reads only the state bits; a Mealy machine's also reads the current inputs directly, per the block diagrams on the previous page.

This is a completely general procedure — every FSM in real digital design, from a two-state handshake protocol to a full CPU control unit, is built by walking through exactly these six steps, just with proportionally more states and inputs at each stage.

What's next

The next and final page of this section applies the full six-step procedure to one complete, original example — a serial receiver control FSM — deliberately built to reuse the shift registers and counters from the previous section, tying the whole Digital Design topic together end to end.