State Encoding and Next-State Logic in a Finite-State Machine

A finite-state machine is an abstraction with a state set, an input alphabet, a transition function, and an output function. Implementing it requires choosing a bit pattern for each state, and that choice is free as far as the abstract machine is concerned. It is not free in hardware: the encoding decides how many flip-flops the machine occupies, how complex the next-state logic is, whether the machine can transition through states that the specification never mentions, and how fast it can run.

The two output styles

Before encoding, the machine’s outputs must be classified. In a Moore machine the output depends only on the current state, so if the state is held in registers, the output comes from those registers and is stable for the whole cycle. In a Mealy machine the output depends on the current state and the current input, so there is a combinational path from input to output.

The Moore form is preferred for outputs that leave the block, because registered outputs are glitch free and their timing is the flip-flop’s clock-to-output delay rather than the delay of a logic chain. The Mealy form reacts one cycle earlier for the same number of states, which matters when latency is critical, and it can use fewer states because the output can encode information about the transition. Many practical machines are mixed: Moore outputs for control signals that drive other blocks, Mealy outputs for local conditions that are consumed within the same cycle.

The latency difference is exactly one cycle and is easy to lose track of. A Moore machine that asserts a request in response to an input asserts it one clock after the input was visible; a Mealy machine asserts it in the same cycle, at the cost of a combinational path. Pipelines that mix both styles in the same chain acquire a cycle of skew that must be accounted for at the interface.

What encoding decides

For a machine with $n$ states, the encoding assigns each state a binary code. Three families are in common use.

Binary encoding uses the minimum number of bits, $\lceil \log_2 n \rceil$. A 16-state machine fits in four flip-flops. The next-state logic must decode the current state from those four bits before computing the transition, and the decode is usually the dominant part of the logic.

One-hot encoding uses one flip-flop per state, so a 16-state machine uses 16. Each state is a single set bit. The next-state function for a given state is typically a small number of terms, because the state’s own signal is available directly as a literal; the decode that the binary encoding must perform is implicit in the flip-flop’s stored value. The cost moves from logic to flip-flops.

Gray encoding assigns adjacent codes to states that are adjacent in the most common transition sequence, so that a typical transition changes one bit. This minimizes switching activity along the sequence and, more importantly, makes the encoding safe to sample asynchronously: because only one bit changes per transition, a reader sampling during the transition sees either the old state or the new one.

Johnson encoding — a shift register with complemented feedback around a ring — produces codes with one bit change per shift and uses about half as many flip-flops as one-hot for a comparable number of states. It is regular and cheap to build, at the cost of a longer decode for arbitrary transitions because the transition graph must follow the ring order.

Encoding	Flops for 16 states	Next-state logic shape	Notes
Binary	4	decode depends on all state bits	illegal codes exist
One-hot	16	small per-state terms	illegal codes exist, easy to detect
Gray	4-5	depends on chosen ordering	safe for asynchronous sampling
Johnson	8	ring-structured	transitions restricted by structure

The trade is real but not decisive on its own. Which side wins depends on the cost of a flip-flop relative to the cost of a logic term in the target technology. In a fabric where flip-flops are abundant and each lookup table covers few inputs, one-hot encoding often wins despite using four times the storage; in a standard cell library where area is dominated by cells rather than by interconnect, binary encoding often wins. Synthesis tools expose the choice as an attribute or a command-line option precisely because no single answer is right.

Encoding modifies the transition function’s complexity

To see the mechanism, consider what the next-state logic for one state bit actually looks like under each encoding. Under one-hot, the next-state equation for state $S_i$ is the OR of the conditions that lead into $S_i$. Each condition is a conjunction of the source state’s signal, which is a single literal, and the input conditions for that transition. A state with three incoming transitions and one input bit has a next-state equation with three two-literal product terms.

Under binary encoding, the same state is one of several codes, and the logic that detects “the machine is in the source state” is a conjunction over the state bits — up to $k$ literals for $k$ state bits. The next-state equation is then a sum of products over both state and input literals, which can easily be several times larger in literal count than the one-hot version. The binary encoding pays for its smaller state register with a larger combinational cone in front of it.

The depth difference matters as much as the size difference. The one-hot next-state logic is often two levels deep because the source-state literal is available immediately. The binary version adds the decode level, so the next-state path is typically one level deeper, and under the timing budget that extra level is charged against the clock period. A machine with a long combinational next-state function may be the critical path of a block whose datapath is otherwise fast.

# A small machine: serial parity checker with an idle state.
# States: IDLE, EVEN, ODD. One input bit per cycle; the Moore output is the parity so far.
table = {
    ("IDLE", 0): ("EVEN", 0),
    ("IDLE", 1): ("ODD", 1),
    ("EVEN", 0): ("EVEN", 0),
    ("EVEN", 1): ("ODD", 1),
    ("ODD", 0): ("ODD", 1),
    ("ODD", 1): ("EVEN", 0),
}

one_hot = {"IDLE": 0b001, "EVEN": 0b010, "ODD": 0b100}
binary = {"IDLE": 0b00, "EVEN": 0b01, "ODD": 0b10}


def next_state(code, enc, inp):
    for (state, i), (nxt, out) in table.items():
        if enc[state] == code and i == inp:
            return enc[nxt], out
    raise ValueError(f"no transition from code {code:0b} on input {inp}")


def run(enc, inputs):
    code = enc["IDLE"]
    trace = []
    for i in inputs:
        code, out = next_state(code, enc, i)
        trace.append((format(code, "b").zfill(len(format(max(enc.values()), "b"))), out))
    return trace


bits = [1, 0, 1, 1, 1, 0]
print(run(one_hot, bits))
print(run(binary, bits))

Both encodings produce the same output sequence, because the encoding is not part of the machine’s behaviour. What differs is the logic and the state register. The example also shows the illegal-code problem concretely: the one-hot encoding of three states in three bits leaves five unused codes, and the binary encoding of three states in two bits leaves one, namely 11.

Illegal states and safe machines

Most encodings leave codes unused, and the abstract machine says nothing about them. A three-state one-hot machine in three bits has five codes that correspond to no state, and each has a defined next-state function — it is whatever the synthesized logic produces — even though it is not part of the specification.

Two things can put the machine into such a code. The first is power-up: unless a reliable reset forces the state register, the initial value is whatever the flip-flops happen to power up to, which in modern processes is not guaranteed to be uniform across the register. The second is a single-event upset: a particle strike can flip one state bit, turning a valid code into an invalid one.

If the next-state logic for unused codes was optimized using don’t-cares — treating unreachable states as free to map anywhere — then the machine’s behaviour on an invalid code is whatever minimization happened to choose, and it may be another invalid code. A single flipped bit in a one-hot code produces either the all-zero code, if the set bit cleared, or a two-hot code, if an idle bit set — never another valid one-hot code. The all-zero code is the dangerous case when every next-state equation is a plain sum of the conditions that enter its state: no condition is true, so every next-state bit is computed as zero, the register reloads zeros on every clock, and the machine never leaves the invalid code.

The remedy is to specify a default transition for every state, pointing back to the reset state, and to encode it as real logic rather than as a don’t-care. Synthesis attributes that force safe state machine encoding do exactly this, at the cost of some additional logic. A one-hot machine makes the repair cheap to extend: the condition “no state bit is set, or more than one is set” is a small function, and it can force the reset state in one cycle.

There is a second, subtler reason not to optimize unused-state logic. Even if the machine cannot reach an illegal state in the field, a formal equivalence check or a simulation that injects an illegal state will disagree with a reference model if the two implementations made different don’t-care choices. Deterministic behaviour on illegal states makes the implementation a total function, which is easier to reason about and easier to compare.

Registering outputs and the interface to a datapath

A state machine that drives a datapath should register its control outputs. The reason is the hazard argument: a control signal that is a combinational function of state and input can glitch, and the glitch is invisible if the consumer samples it on the clock but visible if the consumer is a level-sensitive element, a memory write enable, or a handshake line leaving the block.

Registering an output costs a cycle of latency and one flip-flop per signal. Both are usually acceptable, and the alternative — a control signal that occasionally produces a spurious write — is not a design trade but a defect.

The state register itself should be treated as the only storage in the controller. Control expressions that depend on the current input are Mealy outputs; control expressions that depend only on the state are Moore outputs. Mixing the two in the same decision without accounting for the one-cycle difference is how a machine ends up asserting an output one cycle too early or too late relative to a data path that was designed against the other convention.

For machines whose next-state function is large, the alternative organization is a microcode store: a memory addressed by state and input, with the next state and outputs stored in the table. The logic disappears into a lookup, the machine becomes regular and easy to modify, and the cost is a memory access time in the critical path — often worse than the logic it replaces, and occasionally better when the state graph is sparse and irregular. It is the same realization trade described for decoder-and-lookup structures, applied to the controller rather than to a combinational function.