State Minimization: Partitions and Implication Charts
Find and merge equivalent states with the partition method and the implication chart, and see why equal outputs are not enough.
You Will Be Able To
- Define equivalent states: same outputs now and equivalent next states for every input.
- Reduce a machine with the partition method: split by output, then by next-state classes.
- Fill an implication chart pass by pass and read the merged states from it.
- Explain why merging states with equal outputs alone changes the machine.
- Lesson
- G7.5
- Time
- 35 min
- Runs on
- Your browser
- Check
- 5 questions
A reviewer looked at a six-state controller and saw that A and D had the same row. Merging them was safe. Then someone merged every state with the same output, and the controller broke. The lab checks every 12-bit stream.
| Version | States | 12-bit streams that differ from the original |
|---|---|---|
| Original | 6 | — |
| Equivalent states merged | 4 | 0 |
| Merged on outputs only | 2 | 3386 |
Measured: the lab below runs all 4096 streams of 12 bits from reset on Icarus Verilog 12.
Equivalent States
Two states are equivalent when no input stream can tell them apart by the outputs. Equivalently: their outputs are equal now, and for every input their next states are equivalent too.
| State | next on 0 | next on 1 | z |
|---|---|---|---|
| A | B | D | 1 |
| B | E | C | 1 |
| C | F | C | 0 |
| D | B | D | 1 |
| E | A | D | 1 |
| F | C | C | 0 |
The machine of this lesson, a Moore machine. A and D have identical rows.
The Partition Method
Start with one class per output value. Then split each class: two states stay together only if, for every input, their next states sit in the same class. Repeat until nothing splits.
- Neutral
- Structure
- Pass 1
On 1, B goes to C, in class {C F}. A, D and E go to D, in class {A B D E}. So B splits off.
- Pass 2
On 0, A and D go to B, now alone; E goes to A. E splits off.
- Pass 3
C and F go to {C F} on both inputs, A and D to the same states. Nothing splits: stop.
Read the diagram as text
- P0: by output: {A B D E} {C F}
- P1: {A D E} {B} {C F}
- P2: {A D} {E} {B} {C F}
- P3 = P2: no split: 4 states
- P0: by output → P1: B goes to C on 1
- P1 → P2: E goes to A, not to B
- P2 → P3 = P2
Four classes: AD, B, CF and E. Each becomes one state of the reduced machine.
Two States with Equal Outputs That Differ
A and E have the same output, and they stay together through pass 1. Still, one stream tells them apart.
This is why the method repeats. Each pass looks one input further ahead. When a pass changes nothing, no longer stream can tell the classes apart either.
The Implication Chart
An implication chart has one cell per pair of states. Cross a cell when the outputs differ. Otherwise write the pairs of next states it depends on. Then pass over the chart: cross every cell that implies a crossed cell. Stop when a pass crosses nothing.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| B | BE, CD ✗1 | ||||
| C | ✗0 | ✗0 | |||
| D | equivalent | BE, CD ✗1 | ✗0 | ||
| E | AB ✗2 | AE, CD ✗1 | ✗0 | AB ✗2 | |
| F | ✗0 | ✗0 | CF | ✗0 | ✗0 |
✗0: outputs differ. ✗1: crossed in pass 1 because CD is crossed. ✗2: crossed in pass 2 because AB is. AD and CF stay open: those states merge.
Asked in interviews
How do you minimize the states of a machine?
Partition the states by output. Then split each class by the classes of the next states, for every input, until a pass changes nothing. Each final class becomes one state. An implication chart reaches the same classes pair by pair.
Two states have the same outputs. Can you merge them?
Not on that alone. Their next states must also be equivalent for every input. Equal outputs only means they cannot be told apart in one cycle.
Why does a synthesis tool not always do this for you?
Merging changes the state set the designer wrote. Tools do remove unreachable and duplicate states in some flows, but a clean minimal table is the designer's job.
Try It
The bench feeds all 4096 streams of 12 bits from reset to the three versions. It compares z with the original in every cycle.
The reduced machine never differs. The outputs-only merge already differs on 000000000010. Ten 0s cycle A, B, E and leave the machine in B; the 1 takes B to C, where z = 0.
Change red4 so that state E goes to B on 0 (as if E were merged with A) and run it again.
reduced, 4 states: 0 of 4096 streams differ outputs only, 2 states: 3386 of 4096 streams differ, first 000000000010Read included file: tb.sv
// tb.sv: the bench (read-only). Every input stream of 12 bits, from reset, on all three versions.
module tb;
logic [2:0] so, so_n; logic [1:0] sr, sr_n; logic sm, sm_n;
logic x, zo, zr, zm;
orig6 o (.s(so), .x(x), .s_next(so_n), .z(zo));
red4 r (.s(sr), .x(x), .s_next(sr_n), .z(zr));
out2 m (.s(sm), .x(x), .s_next(sm_n), .z(zm));
int bad_r = 0, bad_m = 0, first_m = -1;
initial begin
for (int v = 0; v < 4096; v++) begin
bit diff_r, diff_m;
so = 0; sr = 0; sm = 0; diff_r = 0; diff_m = 0;
for (int t = 0; t < 12; t++) begin
x = v[11 - t];
#1;
if (zr !== zo) diff_r = 1;
if (zm !== zo) diff_m = 1;
so = so_n; sr = sr_n; sm = sm_n;
end
bad_r += diff_r; bad_m += diff_m;
if (diff_m && first_m < 0) first_m = v;
end
$display("reduced, 4 states: %0d of 4096 streams differ", bad_r);
$display("outputs only, 2 states: %0d of 4096 streams differ, first %b", bad_m, first_m[11:0]);
end
endmodule
Check Yourself
Common Mistakes
Wrong Merge every pair of states that have the same output.
Their futures may differ. In the lab, merging on outputs alone changed the answer on 3386 of 4096 streams.
Fix Merge only states that are still in one class after the partition stops changing.
Wrong Stop the partition method after one split.
A split can break the reason two other states looked alike. A and E split only on the second pass.
Fix Repeat until a pass makes no new split.
Wrong Cross only the cells whose outputs differ in an implication chart.
That is the first pass. A pair whose implied pair is crossed is also not equivalent, and that can chain.
Fix Pass over the chart again and again, crossing cells that imply a crossed cell, until nothing changes.
Wrong Treat a pair that implies itself as a problem.
C and F imply only (C, F). Nothing ever crosses it, so they are equivalent.
Fix A cell is crossed only by a crossed implied pair. A cell that implies only itself stays open.
Remember
- Equivalent states give the same outputs now and have equivalent next states for every input.
- Partition method: split by output, then by next-state classes, until a pass changes nothing.
- Implication chart: cross output-differing pairs, then pairs that imply crossed pairs, until stable.
- Equal outputs alone are not enough: merging on them changed the lab machine on most streams.