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.

VersionStates12-bit streams that differ from the original
Original6—
Equivalent states merged40
Merged on outputs only23386

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.

Statenext on 0next on 1z
ABD1
BEC1
CFC0
DBD1
EAD1
FCC0

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.

Splitting the ClassesEach box is the partition after one pass. Arrows show the next pass.
  • Neutral
  • Structure
Splitting the classesEach box is the partition after one pass. Arrows show the next pass. neutral P0: by output {A B D E} {C F} neutral P1 {A D E} {B} {C F} neutral P2 {A D} {E} {B} {C F} neutral P3 = P2 no split: 4 states B goes to C on 1E goes to A, not to B
  1. neutral P0: by output{A B D E} {C F}
    • B goes to C on 1 → P1
  2. neutral P1{A D E} {B} {C F}
    • E goes to A, not to B → P2
  3. neutral P2{A D} {E} {B} {C F}
    • P3 = P2
  4. neutral P3 = P2no split: 4 states
  1. 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.

  2. Pass 2

    On 0, A and D go to B, now alone; E goes to A. E splits off.

  3. 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.

ABCDE
BBE, CD ✗1
C✗0✗0
DequivalentBE, CD ✗1✗0
EAB ✗2AE, CD ✗1✗0AB ✗2
F✗0✗0CF✗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
  1. 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.

  2. 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.

  3. 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.

RUNIcarus Verilog · in your browser
Edit the code, then run it
Expected: reduced, 4 states: 0 of 4096 streams differ outputs only, 2 states: 3386 of 4096 streams differ, first 000000000010
Read 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

ConceptWhen does the partition method stop?
ConceptAn implication chart cell for P and Q lists the pair RS, and RS is crossed. What happens to PQ?
Predict the outputThe program counts the pairs of lesson states with equal outputs. Predict the exact line.
module tb;
  logic [5:0] out = 6'b011011;          // z of F..A: bit 0 is A
  initial begin
    int n = 0;
    for (int i = 0; i < 6; i++)
      for (int j = i + 1; j < 6; j++)
        if (out[i] == out[j]) n++;
    $display("%0d", n);
  end
endmodule
ConceptA machine has 9 states and reduces to 5. How many state flip-flops does binary coding save?
ConceptWhich pair of the lesson machine is split last by the partition method?

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.

Practice

Report a problem with this page