State Minimization and Encoding

The previous lesson's five-stage flow produced a correct state table from a specification, but "correct" and "minimal" are different properties, and a state table built directly from a written description often has more states than the behavior actually requires. This lesson covers two separate questions that both come after the state table exists and before the equations are written: are any of these states actually redundant, and once the real state count is settled, which bit pattern should represent each one.

Reading time: about 11 minutes.

6.1 Equivalent states

Two states are equivalent if, for every possible future input sequence, they produce the same output sequence and end up in the same (or another pair of equivalent) states. Practically, for a Mealy table, there is a quick test checkable by eye: if two states have identical rows — the same next state and the same output for every input — they are equivalent, and one of them can be deleted everywhere it is referred to, with the other taking its place. This is the row-matching method. It is a sufficient test, not a complete one: identical rows prove equivalence, but two equivalent states can have rows that never become identical. In the table P: 0→Q/0, 1→R/0; Q: 0→P/0, 1→R/0; R: 0→R/1, 1→R/1, P and Q are equivalent, yet P's row points to Q and Q's points to P, so no merge ever makes them match. The complete method is partition refinement (or, equivalently, an implication chart), shown as the cross-check below. Row matching is applied repeatedly, not once, because merging one pair of rows can make a second pair identical that was not identical before the merge.

Let us work an example. Take a Mealy table with five states, A through E:

Scanning the rows, two pairs are already identical before anything is merged: C's row (D/0, E/1) matches E's row (D/0, E/1), and B's row (D/0, C/0) matches D's row (D/0, C/0). Both pairs are equivalent on the first pass, so every reference to E can be replaced with C and every reference to D with B. Doing those replacements is the whole mechanism. Note that the merge also rewrites C's own row: its input-1 entry pointed to E, so it now points to C, and its output on that input stays 1.

This is where the method has to repeat rather than stop. A's row (B/0, C/0) and B's row (B/0, C/0) are now identical, but they were not in the original table: A went to B on input 0 while B went to D, and the two rows only became the same once D had been folded into B. A row-matching pass that ran only once would stop at three states when two is the real minimum. Merging B into A gives the final, minimized table:

A third pass finds no further matches, because A and C produce different outputs on input 1, so the table is done: five states reduced to two, in two rounds. The result is easy to read once it is this small: A means "the last input was 0, or nothing has arrived yet," C means "the last input was 1," and the output is 1 exactly when a 1 arrives while in C, so the original five-state table was a two-consecutive-1s detector all along. The complete method agrees. Partition refinement starts by grouping the original states by their outputs, giving {A, B, D} and {C, E}, then splits any group whose members send some input to different groups; here every state in each group sends each input to the same group, so neither group ever splits and the two groups are the two minimal states. Thus, row matching is a fixed-point process: keep scanning for identical rows and merging until a complete pass finds nothing left to merge, not until the first pass finds nothing, and confirm the result with partition refinement. The previous lesson's detector shows the other half of the definition. Its Moore S4 and S1 have the same next states, but S4's output is 1 and S1's is 0, so they are not equivalent; only in the Mealy version, where the output moves onto the transition, does that difference disappear and the two merge.

6.2 Why encoding is a separate decision

Once the minimal state count is settled, each state still needs a concrete bit pattern before the next-state and output equations can be written down. This choice changes nothing about the machine's behavior — the state table, and therefore every input/output sequence the FSM produces, is identical no matter which bit pattern represents which state — but it changes the resulting hardware. Two encodings dominate practice:

• Binary (or "sequential"): states numbered 0, 1, 2, ... in ceil(log2 N) bits — the minimum width a register could possibly use. This is what the previous lesson used by default.
• One-hot: one bit per state, with exactly one bit set at a time — N bits for N states, far wider than binary's ceil(log2 N), but each state corresponds to a single flip-flop being 1 rather than to a multi-bit pattern that combinational logic has to decode.

A third option, Gray encoding, assigns codes so that transitions between adjacent states change exactly one bit. That is only fully achievable where the transition graph allows it: a counter-like ring of states can be Gray-coded throughout, but a branching FSM generally cannot make every transition a one-bit change, so the assignment minimizes multi-bit transitions rather than eliminating them. Where it works, it is useful when it matters that only one state bit ever switches per clock edge, since no other bit's switching can glitch in between (lesson 8 covers why multi-bit transitions generally do not actually produce a problem in synchronous RTL, so this benefit is a lesser concern in a single clocked domain than it was in older asynchronous designs, but it still turns up in low-power contexts as a way of reducing simultaneous switching activity). This lesson does not build a Gray-coded example, since the comparison that matters most in practice is the binary-versus-one-hot trade-off below.

6.3 Binary versus one-hot, measured

Let us take the previous lesson's 4-state Mealy detector and build it twice: once with the default binary assignment (S0=00, S1=01, S2=10, S3=11), and once one-hot (S0=0001, S1=0010, S2=0100, S3=1000). Both were driven with the identical bit stream through Icarus Verilog and agreed on every output bit, confirming the encoding choice changed nothing observable about the machine's behavior.

i=3 bit=1 binary_match=1 onehot_match=1
i=4 bit=1 binary_match=0 onehot_match=0
i=6 bit=1 binary_match=1 onehot_match=1
SELF-CHECK PASSED

Both were synthesized to Yosys's generic cell library twice. The first run used yosys -p "read_verilog <file>; synth -top <module> -nofsm; stat", which runs the full script, including ABC logic minimization, but skips FSM extraction and re-encoding, so the encoding written in the RTL survives. The second used plain synth, FSM pass included:

With the written encoding preserved, one-hot cost twice the cells: 2 extra flip-flops, but 18 logic cells against binary's 9. The growth is in the logic, and the cause is the RTL, not the encoding itself. mealy_onehot.v keeps the binary version's case (state) and state == S3, so every state is recognized by a full 4-bit compare, and one-hot's single-bit decoding is never used. Written to exploit it, the output would be state[3] & bit_in and each next-state bit a small OR of such terms; that variant was not built or measured here. Both versions passed Yosys's own check pass reported zero problems and no inferred latches for either version. The qualitative trade-off experienced designers describe is usually framed the other way for larger machines: one-hot's next-state and output logic for each state is often a simple AND of "are we in this state" with the relevant input, since the state variable itself is directly available as a single bit, rather than needing a multi-input decoder to first recognize a binary pattern — which is why one-hot shows up often on FPGAs, where flip-flops are comparatively cheap and plentiful (typically one or two flip-flops per LUT) and the simpler decode logic can mean a shorter critical path. Binary remains the usual default for state counts large enough that N flip-flops for one-hot would be a real area cost, and is often favored in ASIC flows where area is scarcer, though what a tool picks by default is tool-dependent: Yosys's default auto encoding chose one-hot for both versions here.

The full-synth column shows why the first run skipped the FSM pass: Yosys's FSM extraction recognized both state registers, its log reported mapping the auto encoding to one-hot for each, and both versions converged to the identical 4-flop, 12-cell result regardless of which encoding the RTL specified. Different synthesis tools and flows handle this differently, and some flows disable automatic re-encoding specifically so that a designer's chosen encoding survives into the gate-level netlist; if that matters for a specific tool, check its FSM-compilation options rather than assuming either behavior. The -nofsm column is the one that reflects the RTL as written.

6.4 Interview questions

How do you detect that two states in an FSM are equivalent? The quick test is row matching: identical rows (same next state and same output for every input) prove equivalence, and it has to repeat, because one merge can make another pair identical. It is sufficient but not complete, since equivalent states that point to each other may never get identical rows. The complete method is partition refinement or an implication chart: group states by output, then keep splitting any group whose members send some input to different groups until nothing splits.

Does changing a state's binary encoding ever change what the FSM does? No. Encoding only decides which bit pattern represents which already-determined state; the state table, and therefore every output sequence the machine produces for any input sequence, is unchanged. Only the resulting gate-level implementation — its size, and sometimes its timing — changes.

What is the basic trade-off between binary and one-hot state encoding? Binary uses the minimum number of flip-flops (ceil(log2 N) for N states) but needs decode logic to recognize each state as a multi-bit pattern. One-hot uses one flip-flop per state — more flops, more total registers — but each state is already a single bit, which can simplify the next-state and output logic built from it, especially where flip-flops are cheap relative to logic, as on an FPGA.

Why might a synthesis tool produce the same gate-level result for two different state encodings written in RTL? Many synthesis flows include an FSM-recognition and re-encoding optimization that replaces whatever encoding the designer wrote with one the tool derives itself. Whether this happens, and whether it can be disabled to preserve a specific encoding, is tool- and flow-dependent, which is why it is worth checking rather than assuming for any specific project.