State Reduction

A state machine with redundant states wastes flip-flops and increases gate count. State reduction — also called state minimisation — removes equivalent states and can cut the number of flip-flops needed, directly reducing chip area in ASICs and LUT usage in FPGAs.

Core Concept

Two states are equivalent if they produce identical outputs for every possible input and their next states are also equivalent (possibly the same pair). Merging equivalent states reduces the total state count without changing the machine''s external input-output behaviour.

The row-matching method works for small tables: scan the state table and identify rows that have identical output columns and identical next-state columns (or whose next-state pairs are themselves equivalent). For larger tables, the implication table method is systematic and guaranteed to find all equivalences.

In the implication table, you create a triangular grid of state pairs. Mark each pair with × if the output differs for any input. Then propagate: a pair (Si, Sj) is inequivalent if it implies a marked pair. Repeat until no new marks appear. Unmarked pairs are equivalent. State reduction before state assignment saves flip-flops and logic — critical for ASIC gate-count optimisation.

Boolean Expression

Two states Si and Sj are equivalent iff for every input X: Z(Si, X) = Z(Sj, X) (same output) AND NS(Si, X) ~ NS(Sj, X) (next states are equivalent to each other). This is a recursive definition resolved by the implication table. The reduced machine has exactly as many states as there are equivalence classes.

Reduce the following Moore machine (Z depends on state only):
State   Z   X=0 NS   X=1 NS
A       0   C        B
B       0   A        D
C       0   A        B
D       1   E        A
E       1   A        B

Step 1 — Mark pairs with different outputs:
  Pairs with Z mismatch (0 vs 1): (A,D),(A,E),(B,D),(B,E),(C,D),(C,E) → mark ×
  Remaining pairs: (A,B),(A,C),(B,C),(D,E)

Step 2 — Check remaining pairs:
  (A,B): X=0 NS: (C,A) — must check (A,C); X=1 NS: (B,D) — marked ×! → mark (A,B) ×
  (A,C): X=0 NS: (C,A) — same pair, OK; X=1 NS: (B,B) — trivially equivalent
         → (A,C) depends only on (A,C) itself → NOT marked → A ≡ C
  (B,C): X=0 NS: (A,A) OK; X=1 NS: (D,B) — check (B,D) → marked × → mark (B,C) ×
  (D,E): X=0 NS: (E,A) → check (A,E) → marked × → mark (D,E) ×

Step 3 — Equivalent pairs: only (A,C) is unmarked → A ≡ C

Step 4 — Substitute C → A everywhere:
Reduced table:
State   Z   X=0 NS   X=1 NS
A       0   A        B
B       0   A        D
D       1   E        A
E       1   A        B

Final Answer:
  Original: 5 states (need 3 flip-flops)
  Reduced: 4 states (need 2 flip-flops)
  Saving: 1 flip-flop and associated combinational logic

Exam Tip: A very common mistake in the implication table is forgetting to propagate marks iteratively. After the first pass, some pairs that looked safe may become marked because a pair they depend on got marked in the same pass. Always repeat until no new × appears. Also, for Moore machines check output equivalence first — it immediately eliminates many pairs without any NS checking. For Mealy machines, output must match for every input, not just the state.

Key Properties

• Equivalent states: identical outputs AND equivalent next states for all inputs
• Row-matching: fast for small tables; inspect for identical rows in state table
• Implication table: systematic triangular chart; propagate × marks until stable
• Moore equivalence: check output (Z of state) first; Mealy: check Z for each input
• Reduces flip-flop count: from ceil(log2(n)) to ceil(log2(m)) where m < n
• Mandatory step before state assignment in ASIC flow to minimise gate area
• FPGA synthesis tools (Vivado, Quartus) perform state reduction automatically

Quick Revision

• State reduction removes equivalent states without changing I/O behaviour
• Two states are equivalent if outputs match AND next states are equivalent
• Row matching: visual; implication table: systematic for large machines
• Mark pairs with output mismatch first, then propagate NS implications
• Iterate implication table until no new × marks appear
• Unmarked pairs after convergence are equivalent and can be merged
• Each saved state reduces flip-flop count by log2 factor
• Exam trap: stopping the implication table after one pass — equivalences only stabilise after full convergence, and missing a propagation step gives wrong merged states.