State Encoding
You design a machine with named states, IDLE, FETCH, DECODE, EXECUTE. At some point each name has to become a pattern of bits in flip-flops, because that is all a flip-flop can hold. The synthesis tool will choose the patterns for you, but the choice changes the circuit more than you might think: it decides the Boolean expressions for the next-state logic, and so the gate count, the critical path and the switching power. For four states with two bits there are 24 possible assignments; with more bits than the minimum there are far more. This article is about the four families of assignment that matter.
Binary
Number the states 0, 1, 2, … in binary. $N$ states need $\lceil \log_2 N \rceil$ flip-flops, the fewest possible.
IDLE = 00, FETCH = 01, DECODE = 10, EXECUTE = 11.
The flip-flop count is minimal, which is what matters on an ASIC where each flip-flop is real area. The cost is in the logic: many transitions change several bits at once (01 to 10 changes both), the next-state expressions are longer, and more bits switch, which is power.
One-hot
One flip-flop per state, exactly one of them set at any time.
IDLE = 0001, FETCH = 0010, DECODE = 0100, EXECUTE = 1000.
The next-state logic for the flip-flop of state $S_i$ is just the OR of the conditions of all transitions into $S_i$. If S0 and S2 both go to S3 on $x = 1$:
$$D_{S3} = Q_{S0} \cdot x + Q_{S2} \cdot x$$
Two small ANDs and an OR, and it never gets much more complicated than that. This is why FPGA tools default to one-hot: each state’s logic fits in one lookup table, the logic is two or three levels deep, and the fabric has flip-flops to spare. Debugging is easier too, since probing the register tells you the state directly. The cost is $N$ flip-flops instead of $\log_2 N$, and the fact that only $N$ of $2^N$ patterns are valid, so the machine needs a reset into a valid one and a way out of the others.
Gray code
Assign codes so that consecutive states differ in one bit: 00, 01, 11, 10.
IDLE = 00, FETCH = 01, DECODE = 11, EXECUTE = 10.
The point is switching power. Dynamic power is proportional to the activity factor, and a machine that mostly steps through its states in order switches one bit per step. Gray code is also what makes multi-bit values safe to pass between clock domains, as in the FIFO pointers of section 3.2, because a one-bit change cannot be sampled as a mixture of old and new. It suits machines whose transitions follow the code order; for machines with arbitrary transitions it gives no particular advantage.
Output-coded
Choose the state bits so that some of them are the outputs. If a Moore machine’s outputs are $z_1 z_0$ and the states are assigned so that the low two state bits equal $z_1 z_0$, the output logic is two wires.
| State | $Q_1 Q_0$ | $z_1 z_0$ |
|---|---|---|
| IDLE | 00 | 00 |
| LOAD | 01 | 01 |
| RUN | 10 | 10 |
| DONE | 11 | 11 |
No output gates and no output delay after the register. It only works when distinct states have distinct outputs, or when you add bits to make them so, and it constrains the encoding you would otherwise choose to simplify the next-state logic.
The four side by side
A four-state cyclic machine, IDLE, ACTIVE, HOLD, DONE, with one output done in the DONE state.
Binary. IDLE = 00, ACTIVE = 01, HOLD = 10, DONE = 11. Two flip-flops. $D_1 = Q_0$, $D_0 = \overline{Q_1}$. $done = Q_1 Q_0$.
One-hot. Four flip-flops. $D_{ACTIVE} = Q_{IDLE}$, $D_{HOLD} = Q_{ACTIVE}$, $D_{DONE} = Q_{HOLD}$, $D_{IDLE} = Q_{DONE}$. $done = Q_{DONE}$, a wire. Each next-state bit is just the previous flip-flop.
Gray. IDLE = 00, ACTIVE = 01, HOLD = 11, DONE = 10. Two flip-flops, one bit changing per step. $done = Q_1 \overline{Q_0}$.
Output-coded. With one output and four states you need a third bit to make done a wire: give DONE the code 100 and the others 000, 001, 010, so that $done = Q_2$. Three flip-flops, no output logic.
| Encoding | Flip-flops for 4 states | Next-state logic | Output logic | Suits |
|---|---|---|---|---|
| binary | 2 | moderate | gates | ASIC, area |
| one-hot | 4 | minimal | often a wire | FPGA |
| Gray | 2 | moderate | gates | low power, sequential machines |
| output-coded | 2 to 3 | moderate | wires | output-heavy ASIC |
What the tools do
Synthesis tools look at the target and choose. For an FPGA they default to one-hot. For an ASIC they usually try binary first and may explore others. You can override with an attribute (fsm_encoding in Vivado, for example) or by giving explicit values to a SystemVerilog enum. The RTL with named states is independent of all this: the same source gives a one-hot machine on an FPGA and a binary one on an ASIC, and both are correct.
Practice Exercise
Problem 1. A machine has 12 states. How many flip-flops for binary and for one-hot, and why does one-hot still often win on an FPGA?
Solution
Binary needs $\lceil \log_2 12 \rceil = 4$, one-hot needs 12. One-hot always uses more flip-flops, but its next-state logic is so much simpler that on an FPGA, where flip-flops are plentiful and LUT depth sets the clock rate, it is usually faster and no larger overall.
Problem 2. Assign a Gray code to RESET, WAIT, LOAD, COMPUTE, STORE and check it.
Solution
Three bits: 000, 001, 011, 010, 110. RESET to WAIT changes bit 0, WAIT to LOAD bit 1, LOAD to COMPUTE bit 0, COMPUTE to STORE bit 2. One bit per step.
Problem 3. An 8-state binary machine has a critical path of 8.5 ns; re-encoded one-hot it is 5.2 ns. What are the maximum clock rates?
Solution
About 118 MHz and 192 MHz. The simpler next-state logic shortens the path by more than a third, which is the main reason FPGA designs use one-hot.
In the next article we put all the pieces in order: the eight steps from a written specification to gates, including how to find and merge equivalent states.