State Assignment, Encoding and Safe State Machines
Choose state codes, write the machine so the tool keeps them, and send every unused code back to a known state.
You Will Be Able To
- Encode one machine in binary, Gray and one-hot codes, read an output as a state bit, and compare their measured cost.
- Apply the adjacency rules for choosing state codes.
- Write an FSM with an enum, three blocks and a default arm, and keep its codes in synthesis.
- Explain lock-up from an unused code, and add a check and a recovery path.
- Lesson
- G7.6
- Time
- 35 min
- Runs on
- Icarus service
- Check
- 5 questions
A designer chose Gray codes for a five-state detector to save power. The synthesis report showed five flip-flops, not three. The tool had picked its own codes. Here is the same machine in five encodings, each kept with an attribute.
| Encoding | Codes S0 to S1011 | Cells | Flip-flops | Levels |
|---|---|---|---|---|
| Binary | 000 001 010 011 100 | 18 | 3 | 4 |
| Gray | 000 001 011 010 110 | 16 | 3 | 4 |
| One-hot, as a case on 5-bit codes | 00001 00010 00100 01000 10000 | 30 | 5 | 7 |
| One-hot, bit by bit (the lab) | 00001 00010 00100 01000 10000 | 15 | 5 | 3 |
| Binary codes, z read as s[2] | 000 001 010 011 100 | 17 | 3 | 4 |
Yosys output: the pinned flow (Yosys 0.70+290, synth -flatten with ABC), each version with (* fsm_encoding = "none" *). Re-run by tools/probes/digital/g7-probes.mjs (g76).
Four Ways to Number the States
A state assignment gives each state a code. The register stores the code. Five states need at least three bits, because two bits give only four codes.
Binary numbers the states 0, 1, 2 and so on. Gray orders them so codes in a chain differ in one bit. One-hot uses one flip-flop per state, with exactly one bit set. An output code picks codes so that an output is a state bit.
| State | Binary | Gray | One-hot |
|---|---|---|---|
| S0 | 000 | 000 | 00001 |
| S1 | 001 | 001 | 00010 |
| S10 | 010 | 011 | 00100 |
| S101 | 011 | 010 | 01000 |
| S1011 | 100 | 110 | 10000 |
The codes of the hook's table. The binary codes already leave S1011 alone at 1xx, so z can be read as s[2]. The last row of the hook uses those same codes; only its decode of z differs.
Choosing the Codes
With three bits there are many ways to place five states. Hand rules try to make the next-state maps form large groups. Here are three classic rules.
Same next state
States that go to the same next state on the same input get adjacent codes (one bit apart).
Next states of one state
The next states of one state get adjacent codes.
Same output
States with the same output get adjacent codes, so the output map groups well.
In the detector, S101 and S1011 both go to S10 on x = 0. Their Gray codes, 010 and 110, are adjacent, as the first rule asks.
One-hot skips the puzzle. Each bit's next value is the OR of the arcs that enter its state. It costs more flip-flops but its logic is shallow: 3 levels in the lab against 4.
The rules can pull in different directions. The program counts, for the detector, the rule pairs whose codes are adjacent.
Writing the Machine so the Codes Survive
An enum with explicit values names each code. The three blocks stay as in G7.1: an always_ff register, an always_comb case and the output logic. The case ends with a default arm.
typedef enum logic [2:0] {S0 = 3'b000, S1 = 3'b001, S10 = 3'b010,
S101 = 3'b011, S1011 = 3'b100} state_t;
(* fsm_encoding = "none" *) state_t s; // keep these codes
...
default: s_next = S0; // 101, 110 and 111Which versions does the flow leave alone? It is not about the enum. The table runs the detector without the attribute in five forms.
| Version, no attribute | Outputs | Cells | Flip-flops | Levels | Codes |
|---|---|---|---|---|---|
| Binary, enum and case | z = (s == S1011) | 17 | 5 | 3 | re-encoded |
| Binary, localparams and case (no enum) | z = (s == S1011) | 17 | 5 | 3 | re-encoded |
| Binary, enum, and s also on a port st | z = (s == S1011), st = s | 18 | 3 | 4 | kept |
| Binary codes, z read as s[2] | z = s[2] | 17 | 3 | 4 | kept |
| One-hot, bit by bit (the lab) | z = s[4] | 15 | 5 | 3 | kept |
Yosys output: the pinned flow (Yosys 0.70+290), re-run by tools/probes/digital/g7-probes.mjs (g76). A plain localparam case was re-encoded too. Every kept version has a state bit driving an output port.
Unused Codes and Safe Machines
Binary leaves 3 of 8 codes unused here. One-hot leaves 27 of 32 unused. An upset can put any of them in the register. A safe machine leads every unused code back to a known state.
| After the upset | det_bin from 110 | det_hot from 00000 |
|---|---|---|
| Edge 1 | 000 | 00000 |
| Edge 2 | 000 | 00000 |
| Edge 3 | 001 | 00000 |
Measured: the lab below. The default arm returns det_bin to S0. det_hot has no bit set, so no equation can set one.
One-hot has a second failure: two hot bits. Each one runs through the machine like its own token, and z can fire on the wrong stream.
The cure has two parts. A check flags any code that is not one-hot, such as !$onehot(s). A recovery rule then loads the reset state at the next edge.
- Control / FSM
- Control
- Upset
A glitch, a bad reset or a wrong force puts a code no state has into the register.
- Catch it
For binary codes the default arm names every unused code. For one-hot, a check flags any code without exactly one 1.
- Recover
The next edge loads the reset state, and the machine runs normally again.
Read the diagram as text
- Legal codes: the states you drew
- Unused code: after an upset
- Default arm or check: default, !$onehot(s)
- Reset state: at the next edge
- Legal codes → Unused code: upset
- Unused code → Default arm or check
- Default arm or check → Reset state: next edge
- Reset state → Legal codes
In the lab, det_bin takes this path through its default arm. det_hot has no check, so 00000 never leaves.
Asked in interviews
Binary or one-hot for an FSM?
Binary needs the fewest flip-flops. One-hot needs one per state but has simple, fast next-state logic, which suits FPGAs with many flops. Measure both: in our detector one-hot bit by bit was 15 cells and binary 18.
What is a safe state machine?
One where every unused code leads to a known state. Write a default arm, keep the codes in synthesis, and test it by forcing each unused code. For one-hot, add a check that the code has exactly one 1.
Why did my FSM come out one-hot when I coded binary?
Synthesis tools extract FSMs and choose their own encoding. Yosys does unless the register has (* fsm_encoding = "none" *). Other tools have their own attributes.
Try It
The first seven lines are after each edge of 1011011. Both machines find the two matches.
Then the bench forces 110 and 00000. det_bin's default arm takes it to S0. det_hot stays at 00000: it is locked up.
Add a check: when s is not one-hot, load 5'b00001. Predict the last three lines, then run it. Synthesize to see what the check costs.
Synthesize the design to measure its cells and inspect the mapped gates.
x=1 bin s=001 z=0 hot s=00010 z=0 x=0 bin s=010 z=0 hot s=00100 z=0 x=1 bin s=011 z=0 hot s=01000 z=0 x=1 bin s=100 z=1 hot s=10000 z=1 x=0 bin s=010 z=0 hot s=00100 z=0 x=1 bin s=011 z=0 hot s=01000 z=0 x=1 bin s=100 z=1 hot s=10000 z=1 upset: bin s=110, hot s=00000 x=1 bin s=000 z=0 hot s=00000 z=0 x=0 bin s=000 z=0 hot s=00000 z=0 x=1 bin s=001 z=0 hot s=00000 z=0Original design · 15 cells · 5 flip-flops · 0 latches · 3 logic levels. Synthesis uses Yosys; counts depend on the toolchain.
Read included file: tb.sv
// tb.sv: the bench (read-only). Both machines see 1011011. Then an upset hits both state registers.
module tb;
logic clk = 0, rst = 1, x = 0, zb, zh;
det_bin b (.clk(clk), .rst(rst), .x(x), .z(zb));
det_hot h (.clk(clk), .rst(rst), .x(x), .z(zh));
task automatic edge_with(input logic bit_in); // one bit, one rising edge, then print
x = bit_in; #1 clk = 1; #1 clk = 0;
$display("x=%b bin s=%b z=%b hot s=%b z=%b", x, b.s, zb, h.s, zh);
endtask
initial begin
#1 clk = 1; #1 clk = 0; rst = 0;
edge_with(1); edge_with(0); edge_with(1); edge_with(1); edge_with(0); edge_with(1); edge_with(1);
$display("upset: bin s=110, hot s=00000");
force b.s = det_pkg::state_t'(3'b110); // 110 is no member of the enum: a cast is needed
force h.s = 5'b00000; #1 release b.s; release h.s; // the values stay until the next edge
edge_with(1); edge_with(0); edge_with(1);
end
endmodule
Check Yourself
Common Mistakes
Wrong Expect the synthesis report to show the codes written in the enum.
The pinned flow found the state register and re-encoded it one-hot. The binary and Gray versions both became 5 flip-flops.
Fix Put (* fsm_encoding = "none" *) on the state register when the codes matter, and read the flop count.
Wrong Leave out the default arm because "the machine never reaches the other codes".
An upset, a bad reset or a wrong force can put any code in the register. With no arm for it, the machine may hold it forever.
Fix Give every unused code a path to a known state, and test it by forcing those codes.
Wrong Trust that a one-hot register always has exactly one hot bit.
In the lab, 00000 stayed 00000 for ever: every next-state equation ORs only hot bits, and there were none.
Fix Check the code every cycle. When it is not one-hot, go to the reset state at the next edge.
Wrong Write one-hot as a case on whole 5-bit codes.
Each arm then compares all five bits. The lab's case version needed 30 cells against 15 for the bit-by-bit equations.
Fix Write one equation per state bit: the OR of the arcs that enter that state.
Remember
- Binary uses the fewest flip-flops; one-hot uses one per state and has the simplest next-state logic.
- Give adjacent codes to states with a common next state, a common parent or a common output.
- Synthesis tools re-encode FSMs: keep your codes with an attribute when they matter.
- A safe machine sends every unused code to a known state; one-hot also needs a one-hot check.