1. Home
2. Academy
3. State Machines from Zero
4. Volume 11

11.1 Illegal and unreachable states

A state register can hold more codes than the machine has states. The extra codes are illegal states - and in real hardware, a machine can land in one.

More codes than states

A machine with 5 states in binary needs 3 flip-flops, and 3 flip-flops can hold 8 codes. So 3 codes belong to no state. In one-hot, the same 5 states need 5 flip-flops, which can hold 32 codes - so 27 codes belong to no state. These codes are illegal states.

A related idea from Volume 10 is the unreachable state: a real state that no input sequence reaches from reset. Both kinds are never visited in normal work. The difference is that an unreachable state is part of your design, while an illegal code is not a state at all.

How does a machine get there?

A correct design never steps into an illegal code by itself. But real hardware is not always correct:

• a timing violation - a path too slow for the clock, so one state bit is caught late
• an unsynchronised input reaching the next-state logic (Volume 09)
• a reset released badly, so some flip-flops leave reset one cycle later than others (Volume 04)
• a power glitch
• a particle from space flipping a bit - the topic of sub-module 11.4

What happens then?

That depends on logic nobody designed. In Volume 03, the unused codes were marked "don't care", so their next states are whatever made the gates smallest. There are three possible outcomes:

• The machine happens to step back into a legal state.
• It sits in the illegal code for ever.
• It circles among illegal codes for ever.

The last two are called lock-up. The machine stops doing its job until someone resets it - and in a car or a satellite, there may be nobody to do that.

Two real examples

Take the Moore edge detector built from gates in Volume 03, with the unused code 11. Put in 11 and follow its formulas. Q1⁺ = Q0·b + Q1·b becomes b, and Q0⁺ = Q1'·Q0'·b becomes 0. So it steps to 00 or 10 - both legal. It recovers. But pulse = Q0, and Q0 is 1 in code 11, so while it is there it sends out a false pulse. Recovering is not the same as behaving.

The ring counter from Volume 07 is worse. If a glitch sets a second bit, both 1s go round and round for ever:

11.2 Recovery strategies

A safe state machine has a defined, tested way back from every illegal code - usually to its reset state, sometimes to a special safe state, sometimes by correcting the bits.

Three strategies

A safe state depends on the job. For a traffic light it is all lights red. For a motor controller it is motor off. For a serial receiver it is "drop this byte, go back to waiting".

Back to reset: the default branch

In Verilog, the recovery is one line: a default branch in the case statement, which catches every code not listed above it.

module safe_ctrl (
  input  wire clk, rst, go, fin,
  output wire busy, err
);
  localparam [1:0] IDLE = 2'b00, RUN = 2'b01, DONE = 2'b10;   // 2'b11 is illegal
  reg [1:0] state, next_state;

  always @(posedge clk)
    if (rst) state <= IDLE;
    else     state <= next_state;

  always @(*) begin
    next_state = state;
    case (state)
      IDLE:    if (go)  next_state = RUN;
      RUN:     if (fin) next_state = DONE;
      DONE:             next_state = IDLE;
      default:          next_state = IDLE;          // any illegal code: go home
    endcase
  end

  assign busy = (state == RUN);
  assign err  = (state != IDLE) && (state != RUN) && (state != DONE);   // an illegal code now
endmodule

One-hot machines need their own check

A one-hot machine written bit by bit, as in Volume 05, has no case statement, so there is no default branch to catch anything. Instead, check the pattern itself: it is legal only if exactly one bit is 1.

// s holds one bit per state; exactly one must be 1
wire illegal = (s == 5'b00000) || ((s & (s - 5'd1)) != 5'b00000);

always @(posedge clk)
  if (rst || illegal) s <= 5'b00001;        // back to IDLE on any illegal pattern
  else                s <= s_next;          // the normal one-hot next-state logic

The trick s & (s - 1) removes the lowest 1 from s. Take s = 00110: then s - 1 = 00101, and s & (s - 1) = 00100, which is not zero, so there were two or more 1s. For a legal code such as 00100, s - 1 = 00011, and the AND gives 00000.

Test it: inject a fault

A recovery path that has never run is a recovery path you hope works. In a testbench, write an illegal code straight into the design, and check what happens next. This is called fault injection:

@(negedge clk) dut.state = 2'b11;                     // a "particle hit" on the state
@(negedge clk)
  if (dut.state === 2'b00) $display("PASS: back in IDLE");
  else                     $display("FAIL: no recovery, state = %b", dut.state);

dut.state reaches inside the design by name - a testbench may do that, although a design should not. Try every illegal code, in every state, with every input value.

11.3 Safe-FSM synthesis settings

A default branch in your code is not enough on its own. The synthesis tool may prove that illegal codes never happen, and delete the recovery logic - unless you tell it to keep it.

The logic you wrote may not be the logic you get

Remember FSM extraction from Volume 05: the synthesis tool recognises your state machine, works out its states and arrows, and often re-encodes it. While doing that, it can also prove something about your code: starting from reset, the machine never reaches an illegal code. From the tool's point of view, the default branch can never run. So the logic for it looks useless, and it may be removed to make the design smaller and faster.

The tool is right about your code. It is wrong about your hardware, which can be hit by the faults in sub-module 11.1. The tool has no idea that particles exist.

Telling the tool to keep it

Every major synthesis tool has a setting for this.

In Vivado, the attribute sits on the state register, like the fsm_encoding attribute you met in Volume 05:

(* fsm_safe_state = "reset_state" *) reg [1:0] state;   // recover to the reset state

Its settings include going back to the reset state, and going to the state named in your default branch. One setting even adds extra bits, so that a single flipped bit is corrected automatically. The exact names are in the Vivado synthesis guide.

Beware of promises in the code

Some directives promise the tool that no other value can appear, and so give it permission to drop recovery logic. The old full_case directive does this, and so can SystemVerilog's unique case (Volume 04). Avoid them in machines that must be safe. The safe FSM section of the Verilog course shows the danger in detail.

Check the result, not the code

RTL simulation always runs the code you wrote - including the default branch - even if synthesis threw it away. So a passing RTL fault-injection test proves nothing about the chip. To be sure:

1. Read the synthesis report. It lists the state machines found, their encoding, and whether safe logic was added.
2. Run the fault-injection test on the netlist - the gate-level design that synthesis produced - not only on your RTL.

11.4 Radiation and single-event upsets

A particle from space, or from the chip's own materials, can flip a bit in a flip-flop. Machines that must be safe have to expect random bit flips.

Bits that flip by themselves

Particles pass through everything, all the time. High-energy particles from space strike the atmosphere and produce showers of neutrons, some of which reach the ground. Tiny traces of radioactive material in a chip's own packaging give off alpha particles. When such a particle passes through a transistor, it leaves behind a trail of electric charge. If that charge lands on the node that stores a flip-flop's value, it can flip it: a 0 becomes a 1.

This is a single-event upset, or SEU. Nothing is damaged - the next write puts a correct value back - so it is also called a soft error. But until then, the bit is wrong. In a state register, a wrong bit means a wrong state - perhaps an illegal one.

How often?

For a single flip-flop at sea level, an upset is very rare. But a chip holds millions of flip-flops and memory bits, and a product may run for many years, so over a whole fleet upsets do happen. The rate also rises sharply with height. Where aircraft fly, the flow of neutrons is hundreds of times stronger than at sea level. In space, there is no atmosphere to shield the chip at all.

Who must worry?

All of these fall under functional safety: engineering that keeps a system safe even when parts of it fail.

11.5 Protecting the state register (Hamming, TMR)

Extra bits can let a state register notice a flipped bit, or even correct it. Or three copies of the register can simply outvote a flip in any one of them.

Detect: a parity bit

Recall the Hamming distance from Volume 05: the number of bits in which two codes differ. If every legal code differs from every other in at least two bits, then flipping any single bit always lands on an illegal code. The flip cannot turn one legal state into another - so it can always be caught.

The simplest way to get there is a parity bit: an extra bit chosen so that every legal code has an even number of 1s. Here is the drink machine from Volume 03 with one:

Any single flip makes the number of 1s odd, which the machine checks with one XOR of all three bits, ^state in Verilog. On an odd count, it goes to a safe state. One-hot codes have the same property for free: any two legal one-hot codes differ in exactly two bits.

Correct: a distance-3 code

Push the distance up to three, and a single flip lands on a code that is still nearest to the original. It is one bit away from the original, and at least two bits away from every other legal code. The machine can then work out which state it should be in, and carry on as if nothing happened. This is the idea behind a Hamming code. For four states:

Every pair of these codes differs in at least three bits. The next-state logic treats every code within one bit of S1 as S1, and so on. This costs five flip-flops instead of two, and more logic - the price of never stopping.

Outvote: triple modular redundancy

The bluntest method keeps three copies of the state register and takes a vote. This is triple modular redundancy, or TMR. A majority voter outputs, for each bit, the value that at least two of the three copies agree on. A flip in any one copy is simply outvoted.

(* dont_touch = "true" *) reg [1:0] s_a, s_b, s_c;          // three copies - keep all three
wire [1:0] state = (s_a & s_b) | (s_b & s_c) | (s_a & s_c);  // bit-by-bit majority vote

always @(posedge clk)
  if (rst) begin s_a <= IDLE; s_b <= IDLE; s_c <= IDLE; end
  else     begin s_a <= next_state; s_b <= next_state; s_c <= next_state; end

// the next-state and output logic use the voted "state", as usual

Two details make it work:

• The voted state feeds the next-state logic, so at every clock edge all three copies are rewritten with the same, correct next state. A copy hit by a particle is repaired one cycle later, as Figure 11.4 shows.
• A synthesis tool sees three registers that always hold the same value, and will happily merge them into one - removing the protection. The dont_touch attribute tells Vivado to keep all three; other tools have their own "keep" settings.

Choosing the protection

Space hardware often goes further, triplicating the logic and the voters as well, because the voter itself could be hit.

What you learned

• A state register can hold more codes than there are states; the extras are illegal states, and faults can put the machine there.
• Unplanned logic may leave a machine stuck in an illegal code - lock-up - or recovering with a false output.
• A default branch, a legality check for one-hot machines, and a safe state give a defined way home - and fault injection tests it.
• Synthesis may remove recovery logic it proves unreachable; use a safe-state setting and check the report and the netlist.
• Particles cause single-event upsets - soft errors - which matter wherever chips must run safely for a long time.
• A parity bit detects a single flip, a distance-3 code corrects it, and TMR outvotes it and repairs the copy.

Key words from this volume

Every word below has a plain-English entry in the glossary.

• Illegal state
• Unreachable state
• Lock-up
• Safe state
• Fault injection
• FSM extraction
• Single-event upset (SEU)
• Soft error
• Functional safety
• Hamming distance
• Parity bit
• Hamming code
• Triple modular redundancy (TMR)
• Majority voter

Practice

Interview corner

Next, Volume 12 turns from designing machines to proving them right: tests that visit every state and every arrow, coverage, and assertions.