Skip to content
Tutorials Center
My learning

Topics

Lesson 39 of 57 ยท State Machines

State Reduction and State Assignment

Remove redundant states from a finite state machine with the implication table and partition refinement, then pick binary, Gray or one-hot codes. Includes Python tools.

When you design a state machine by following a word description, the first draft is almost never the smallest one. You add a state for every situation you can think of, and some of them turn out to behave identically. Every extra state costs real hardware: more flip-flops, a larger next-state table, bigger K-maps, more gates and more power. State reduction (also called state minimization) is the step that finds the redundant states and merges them without changing what the machine does. State assignment is the step after it: deciding which binary code each remaining state gets, which changes the final circuit a lot.

This lesson fills the gap between the two steps of the design recipe. You will learn the idea of equivalent states, two methods to find them (the implication table and partition refinement), and the rules of thumb for state assignment, and you will run both methods on a deliberately wasteful machine.

Equivalent states

Two states are equivalent if no experiment can tell them apart. Feed the same input sequence to a machine starting in either state: if the outputs are always identical, no matter how long the sequence is, the states are equivalent and can be merged into one.

For a Mealy machine, where the output depends on state and input, this gives a neat recursive test. States P and Q are equivalent when:

  1. For every input, P and Q produce the same output, and
  2. For every input, their next states are also equivalent (or are the same state).

Condition 2 refers to equivalence itself, so the test is circular, and it is solved by starting with a rough guess and refining it until nothing changes. A Moore machine works the same way if you treat "same output" as "same state output".

Fewer states may also mean fewer flip-flops. A machine with N states needs ceil(log2 N) flip-flops in a binary encoding. Cutting from 5 states to 2 states saves two flip-flops (from 3 to 1). Merging 5 states to 4 saves nothing in flip-flop count, but it still simplifies the logic.

Method 1: the implication table

The implication table is the traditional paper method. It lists every pair of states in a triangle (A-B, A-C, B-C, and so on). For each pair you do the following:

  1. If the outputs differ for some input, mark the pair incompatible (cross it out).
  2. Otherwise write the implied pairs: the pairs of next states you need to be equivalent for this pair to be equivalent. A pair of identical states, or a pair that implies itself, adds no condition.
  3. Repeat until nothing changes: if a pair implies an already crossed-out pair, cross it out too.

When no more pairs can be crossed out, every surviving pair is equivalent. Equivalence is transitive for fully specified machines, so groups of equivalent states can be merged into one.

Method 2: partition refinement

The same result is found by a faster procedure that programs prefer:

  1. Start with one block for each distinct output pattern. States with different outputs can never be equivalent.
  2. For each block, look at where each state goes on each input, in terms of blocks. If two states in a block go to different blocks on some input, split the block.
  3. Repeat until no block splits. Each final block is one state of the minimal machine.
flowchart LR
    S["Group states by their outputs"] --> T["Check where each state goes, in terms of blocks"]
    T --> D{"Does any block split?"}
    D -- "yes" --> T
    D -- "no" --> M["Each block becomes one state"]

Refinement stops after at most N rounds, because each round that changes anything adds a block.

A machine with redundant states

The machine below detects two 1s in a row on input x: its output z is 1 whenever the current input is 1 and the previous one was also 1. Somebody designed it by adding a state for every situation, and it has five states.

State x = 0 x = 1
A (start) B / 0 C / 0
B B / 0 C / 0
C D / 0 C / 1
D A / 0 E / 0
E B / 0 C / 1

Each cell shows next state / output. Look at it for a moment: the states A, B and D all output 0 for both inputs, and C and E both output 0 on x = 0 and 1 on x = 1. The program below proves that these groups are equivalent and merges them.

Python Implication table and partition refinement

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The implication table lists A-B, A-D and B-D as equivalent, and C-E as equivalent, and every pair that mixes the two groups is "different". Partition refinement gets to the same two classes in a single refinement round: no block ever needs splitting. Five states collapse into two, which is exactly what you would have drawn if you had thought of "the last input was 0" and "the last input was 1" from the start.

Machines that are not fully specified

Real designs often contain don't-care outputs or next states: input combinations that never occur. Then the neat equivalence relation weakens into compatibility. Two states are compatible if their outputs agree wherever both are specified, and the next states of each input are compatible. Compatibility is not transitive: A can be compatible with B and B with C, while A and C are not. Finding the best merge becomes a covering problem: choose a set of compatible groups that covers every state and is closed (the next states of any group are all inside some chosen group). The implication table still does the work, but the final choice may need search, and a greedy merge can get stuck. Tools use exact or heuristic algorithms for this.

State assignment

After reduction you have N states and must give each a binary code. Any assignment works functionally. The cost differs in three ways: the number of flip-flops, the size of the next-state and output logic, and how many bits flip on each transition (switching power and glitch risk).

The common choices:

  • Binary uses ceil(log2 N) flip-flops, the minimum. Neighbouring states can differ in many bits.
  • Gray code uses the same number of flip-flops, but chooses codes so that consecutive states differ in one bit. It is good for machines that walk through states in a fixed order, and it reduces glitches because only one flip-flop changes at a time.
  • One-hot uses one flip-flop per state, with exactly one flip-flop set. It uses the most flip-flops, but each state is detected by a single bit, the next-state logic is shallow and fast, and it is the standard choice in FPGAs, which have flip-flops in abundance. State machine patterns shows the illegal-state problem it creates.
  • Output-coded assignments choose the state bits so they equal the outputs, which removes the output logic entirely. This is common for Moore machines such as counters and traffic-light controllers.

Two heuristics help with hand design, and both aim to put 1s next to 1s in the K-maps:

  1. States that have the same next state for some input should get adjacent codes (codes that differ in one bit).
  2. States that are the next states of the same state should also get adjacent codes.

Remember that a 3-bit code for 5 states leaves three unused codes. Treat them as don't-cares to simplify the logic, but check that the machine returns to a valid state if it ever lands on one, as explained for counters in Counter Design.

Python Comparing state encodings

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Gray coding keeps every normal step at a single bit change, but the abort edge S2 -> S0 still flips two bits, because on a cycle of four states you cannot make every possible edge a neighbour. One-hot always flips exactly two bits (the old state off, the new state on), and uses four flip-flops instead of two.

A checklist

  1. Write the state table from the specification without worrying about size.
  2. Merge equivalent (or compatible) states with the implication table or refinement.
  3. Choose an encoding that fits the goal: fewest flip-flops (binary), fewest glitches (Gray), fastest logic in an FPGA (one-hot), or no output logic (output-coded).
  4. Treat the unused codes as don't-cares, then check that the machine recovers from them.
  5. Simulate the reduced machine against the original, as the program above did.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. When are two states of a Mealy machine equivalent?

    Equivalence means no input sequence can distinguish them: equal outputs now, and equivalent successors for every input.
  2. 2. In partition refinement, what is the first partition?

    States with different outputs can never be merged, so the process starts with groups of identical output behavior and splits them according to where they go next.
  3. 3. A reduced machine has 5 states. How many flip-flops does a binary encoding need, and how many does one-hot need?

    Binary needs ceil(log2 5) = 3 flip-flops. One-hot needs one flip-flop per state, so 5.
  4. 4. Why is a Gray-code assignment attractive for a machine that steps through its states in order?

    Gray code uses the same number of flip-flops as binary, but a single changing bit per step reduces switching and glitches.

Summary

  • State reduction merges states that no input sequence can distinguish, which saves flip-flops and logic without changing behavior.
  • The implication table checks every pair: different outputs mean incompatible, and a pair is crossed out if it implies a crossed-out pair. Partition refinement starts from output groups and splits blocks until they are stable.
  • Machines with don't-cares need compatibility, which is not transitive, and a closed cover of compatible groups.
  • State assignment picks the codes: binary (fewest flip-flops), Gray (one-bit steps), one-hot (shallow, fast logic) or output-coded (no output logic).
  • Put states with a common next state, or a common predecessor, on adjacent codes, and always check what happens in unused codes.

Next, see more design problems and fixes in State Machine Patterns and Pitfalls.