Encoding and Safe State Machines

Five states in binary need three bits. Three bits have eight values. Three of them are not states you designed. If the register ever holds one, what happens? If your code does not say, nobody knows, the synthesiser included.

The encodings

Binary, $\lceil \log_2 N \rceil$ flip-flops:

localparam [1:0] RED    = 2'b00,
                 GREEN  = 2'b01,
                 YELLOW = 2'b10,
                 PED    = 2'b11;

reg [1:0] state, next_state;

Fewest registers, deeper decode, the ASIC default.

One-hot, one flip-flop per state:

localparam [3:0] RED    = 4'b0001,
                 GREEN  = 4'b0010,
                 YELLOW = 4'b0100,
                 PED    = 4'b1000;

reg [3:0] state, next_state;

“In GREEN” is state[1], one wire. On an FPGA usually smaller and faster despite the extra registers.

Gray, one bit changing per step:

localparam [1:0] RED    = 2'b00,
                 GREEN  = 2'b01,
                 YELLOW = 2'b11,
                 PED    = 2'b10;

Less switching in a machine that steps through its states in order; no help and more logic in one that does not.

For an FPGA, one-hot up to about a dozen states; for an ASIC, binary; and where the tool takes an attribute, say which you want and let it optimise within that:

(* fsm_encoding = "one_hot" *) reg [3:0] state, next_state;

Illegal states

A binary machine with $N$ states has

$$2^{\lceil \log_2 N \rceil} - N$$

encodings that are no state at all. For five states, three. They are values the register can physically hold, and there are ways to get there: a supply glitch, a bit flipped by a particle strike, which is a measured failure mode in space and not unknown on the ground, a reset released before every flip-flop had settled. Safety standards for cars and aircraft require an answer for each of these.

If the next-state case has no default, then in one of those states no arm matches, next_state takes whatever default was set at the top, which is state itself, and the machine sits there forever.

The one line

always @(*) begin
    next_state = state;
    case (state)
        IDLE:    if (start) next_state = ACTIVE;
        ACTIVE:  if (done)  next_state = DONE;
        DONE:               next_state = IDLE;
        default:            next_state = IDLE;    // any illegal encoding: go home
    endcase
end

Whatever the register holds, the next edge moves it toward a known state. For one-hot, the equivalent check is that no bit, or more than one bit, is set, which is also an illegal pattern, and the fix is the same: force IDLE. Formal tools can go further and prove that no reachable state and input sequence deadlocks, which is a guarantee rather than a net.

In automotive, aerospace and medical work this is a compliance requirement, not a style preference: every machine must handle every encoding, including the ones it was never meant to reach, and demonstrably return to a safe state.

Practice Exercise

A three-state machine in binary. Find the illegal encoding, add the default, and check recovery by forcing the register to the illegal value in simulation.

localparam [1:0] IDLE = 2'b00, RUN = 2'b01, DONE = 2'b10;

always @(*) begin
    next_state = state;
    case (state)
        IDLE:    if (go)   next_state = RUN;
        RUN:     if (stop) next_state = DONE;
        DONE:              next_state = IDLE;
        default:           next_state = IDLE;     // catches 2'b11
    endcase
end

The last article of the module builds three complete machines, the three from Module 3, with testbenches.