L29: State Minimization

Objective
Minimize a finite state machine by removing unreachable states, merging equivalent states, and handling incompletely specified machines.


Before the Lecture

Required Textbook Reading:

  • 6.1–6.3 (State Machines)

Why Minimize?

Fewer states means fewer flip-flops and (usually) less combinational logic. Minimization also removes states that can never occur, which simplifies verification and makes the state diagram readable.

Unreachable States

A state is unreachable if no input sequence from the reset state leads to it. Remove it (and its transitions). Unreachable states often appear when a design was over-specified or when a state assignment left gaps.

Equivalent States

Two states $S_i$ and $S_j$ are equivalent iff for every possible input sequence the machine produces the same output sequence starting from either state. Equivalent states can be merged without changing the machine’s behavior (its “language”).

Partitioning Method

  1. Start with one block containing all states: $P_1 = (S_1 S_2 \dots S_n)$.
  2. Split states whose outputs differ for the same input.
  3. Repeatedly split blocks whose members have successors in different blocks.
  4. Stop when no block splits. Each final block is one minimized state.

The successor check is the key: two states are only equivalent if their corresponding successors are equivalent. This is an iterative refinement.

Example (partitioning trace)

Starting partition $P_1 = (ABCDEFG)$, successive refinement might give:

$$P_2 = (ABD)(CEFG),\quad P_3 = (ABD)(CEG)(F),\quad P_4 = (AD)(B)(CEG)(F)$$

with $P_4 = P_5$ (no further splits), so the minimized machine has four states.

Incompletely Specified FSMs

When some transitions/outputs are “don’t care” (unspecified), partitioning is not guaranteed to find the true minimum, because merging choices interact. Two reasonable conventions:

  • Assume unspecified outputs are 0, then minimize.
  • Assume unspecified outputs are 1, then minimize.

The two can yield different (but both valid) machines. This is a good reason to let a CAD tool handle incompletely specified machines – and to understand why its answer may differ from your hand calculation.

Case Study: Vending Machine

The vending machine FSM tracks money inserted and dispenses a product when enough has been deposited. Its original design has ~9 states; minimization merges states that differ only in how much money was inserted when the future behavior is the same. This is the classic illustration of why minimization matters for real designs.

When NOT to Minimize

Minimization is not free:

  • One-hot designs often become more complex after merging states, because merging destroys the “one flip-flop per state” simplicity.
  • Readability/debugging: a minimized machine can be harder to map back to the spec.
  • Tool-driven flows: the synthesizer may re-encode anyway.

The “minimal” FSM by state count is not always the cheapest or fastest implementation. State count is one cost metric among several.

JK Flip-Flops and Counters (looping in M4)

Minimization and flip-flop choice interact. For a counter, using JK flip-flops with the excitation table from L26 yields toggle equations like $J_i = K_i = \text{carry-in}$, which are much simpler than the D-flip-flop next-state equations. State minimization of a counter is trivial (all states reachable and distinct), but the implementation cost still depends heavily on the flip-flop type – which is exactly the M4 L24 “counters with T/JK flip-flops” idea applied to an FSM.

Partitioning Refinement

flowchart LR
    P1["P1 = (ABCDEFG)"] --> P2["P2 = (ABD)(CEFG)"]
    P2 --> P3["P3 = (ABD)(CEG)(F)"]
    P3 --> P4["P4 = (AD)(B)(CEG)(F)"]
    P4 --> P5["P5 = (AD)(B)(CEG)(F) = P4 (stable)"]

Looking Forward

L30 implements a minimized (or intentionally un-minimized) FSM in Verilog.