State Encoding: Why the Same State Machine Can Cost Three Flops or Eight

A state machine with eight states needs three bits of state if the states are numbered, and eight if each state gets its own bit. The functions that compute the next state and the outputs change completely between those two choices, even though the machine’s behaviour does not. Nothing in the abstract definition of a state machine fixes the mapping from states to encodings, so the mapping is a design variable, and picking it is one of the few places where an RTL author can see the area and delay consequences of a coding decision directly in the synthesis report.

The general shape of the trade recurs across encodings: bits spent on the state register buy shallowness in the logic that decodes it. One-hot encoding sits at one extreme, binary at the other, and the interesting variants in between are chosen for what the state bits feed rather than for what they cost.

Binary encoding minimizes flops and deepens the logic

Numbering the states and storing the number uses $\lceil \log_2 N \rceil$ bits for $N$ states. Eight states cost three flip-flops, sixteen cost four. The savings on the register is real and grows slowly: doubling the state count adds one bit.

The cost appears in the decode. A next-state bit must be computed from all the state bits and all the inputs, and a machine with $k$ state bits and $m$ inputs has $2^{k+m}$ possible combinations of which most are don’t-cares. The synthesis tool exploits those don’t-cares, so the result is far smaller than the raw table suggests, but the number of logic levels needed to compute a next-state bit is typically larger than one-hot’s, and it grows with the state count rather than being fixed by the transition structure.

Binary encoding also leaves the largest number of unused encodings. A ten-state machine in a four-bit register has six encodings with no meaning, and a machine that reaches one of them, through an uninitialized register or a single-event upset, has a defined behaviour that comes only from whatever the code does with an unrecognized state. That is the safe-FSM problem described below.

One-hot encoding fixes the depth and pays in flip-flops

In one-hot encoding each state is a single bit of the state register, so $N$ states cost $N$ flip-flops. The next-state logic for state $i$ has a simple form: the state is entered if any of its predecessors is active and that predecessor’s transition condition holds.

/* One-hot: each next-state bit is an OR of predecessor terms. */
localparam S_IDLE = 0, S_RUN = 1, S_STOP = 2, S_ERR = 3;
reg  [3:0] state, nstate;

always @(*)
  begin
    nstate             = 4'b0;
    nstate[S_RUN]      = (state[S_IDLE] & start) | (state[S_RUN] & !done);
    nstate[S_STOP]     =  state[S_RUN]  & done;
    nstate[S_ERR]      =  state[S_RUN]  & fault;
    nstate[S_IDLE]     = (state[S_STOP] & !restart) | (state[S_ERR] & ack);
  end

Each assignment is an AND of a state bit with at most a few input terms, followed by an OR of the predecessor terms. In sum-of-products form that is two levels of logic whatever the state count: what grows is the fan-in of each OR, and a cell library implements a wide OR as a tree, so the depth after mapping grows with the logarithm of the fan-in rather than staying at two. A comparison of the two extremes for a machine with many inputs is therefore: binary spends fewer flip-flops and more logic levels, one-hot spends a flip-flop per state and shallow logic.

Two further consequences follow. One-hot states drive the output logic directly, so a Moore output that is asserted in exactly one state is that state’s bit, with no decode logic at all; and one-hot next-state logic needs fewer product terms per state bit, because each bit’s function covers only its own predecessors rather than decoding the whole state vector.

Gray and other encodings chosen for what the bits feed

Gray encoding assigns consecutive codes that differ in exactly one bit, so a machine that walks through its states in a fixed order changes only one state bit per transition. That matters when state bits feed combinational logic whose output glitches are undesirable, and it matters for dynamic power: two bits switching per transition consume more than one, and the difference is proportional to the switching activity of the state register, which is often the highest-activity register in a design.

The restriction is severe. A Gray sequence exists for a linear path of states, and branches into parallel paths generally break the single-bit property between two adjacent states in the graph. Gray encoding is therefore applied to counters and to machines whose transitions form a loop, not to general control logic.

A third option is to make the outputs part of the state vector: an output-encoded machine stores in its register exactly the output combination that each state produces. Output logic disappears entirely, outputs become registered and glitch-free, and the cost is that the register becomes as wide as the output vector and every state must produce a distinct output pattern, since two states with identical outputs cannot be told apart in the register. The technique is attractive for small machines driving wide control buses and impractical when outputs are numerous and independent.

Unreachable states and recovery

Every encoding except the one that enumerates all bit patterns leaves unused codes, and the difference between one-hot and binary here is instructive. Binary with $\lceil \log_2 N\rceil$ bits leaves $2^{\lceil \log_2 N\rceil} - N$ codes unused, which for a well-populated encoding is a small fraction. One-hot with $N$ bits leaves $2^N - N$ codes unused: one all-zero vector and $2^N - N - 1$ vectors with two or more bits set. The most likely illegal condition is not a random code but a state register with two bits asserted, which a single radiation event or a reset glitch can produce. Two active state bits in a one-hot machine activate the output terms of both states, so the failure is not a fall into a harmless unused code but a simultaneous assertion of two states’ behaviour.

Recovery is a property of the next-state logic, not of the encoding. A default branch that assigns a known state for any unrecognized code gives the machine a defined recovery path, and in a one-hot machine the same protection is written as a check that the state vector has exactly one bit set. The synthesis tool cannot add this: its data-flow view has no notion of which codes are legitimate, so the unused-space behaviour is whatever the code says, and default that assigns nothing is an inferred latch, as described in inferred latches and registers.

The encoding in the source is a suggestion

Many synthesis tools extract state machines, optimize them as machines, and assign a new encoding as part of that optimization. Extraction can change the number of states by merging equivalent ones, and the assignment can override the codes written in the source. There are good reasons for the tool to do this: a hand-chosen encoding that is good for logic depth may be bad for the library at hand, and the tool has the timing and area models to make the comparison.

Three things make the automatic behaviour worth knowing about. First, the report should be read: if the tool re-encoded a machine, the register count in the netlist is not the register count in the source, and an estimate of area based on the code will be wrong. Second, tool-specific attributes exist to force an encoding or to prevent extraction, which is sometimes necessary when the state bits are exported as an observable interface or when the encoding was chosen to satisfy a timing constraint that the tool’s own cost model does not capture. Third, verification should not assume the source encoding: a testbench that reads the state by poking a bit at a chosen index is testing an assumption, not the machine.

The encoding interacts with the rest of the flow as well. Retiming, discussed in register retiming and stage balancing, can move registers across the next-state logic and change which logic sits between the state register and the output; formal equivalence checking, discussed in equivalence checking after synthesis, has to cope with a netlist whose state encoding no longer matches the RTL’s, which is the point at which combinational equivalence stops being applicable without help.