Digital Design / Module 6: Finite state machines
34. Writing FSMs: encoding and style
Write FSMs that synthesize cleanly.
See it move
The idea
There is a standard way to write FSMs, and following it keeps them readable and free of latches. Use one block for the state register and another for next-state logic, plus outputs.
typedef enum logic [1:0] {IDLE, LOAD, RUN, DONE} state_t;
state_t state, next;
always_ff @(posedge clk or negedge rst_n)
if (!rst_n) state <= IDLE;
else state <= next;
always_comb begin
next = state; // default: stay
busy = 1'b0; // default output
case (state)
IDLE: if (start) next = LOAD;
LOAD: begin busy = 1'b1; next = RUN; end
RUN: begin busy = 1'b1; if (finished) next = DONE; end
DONE: next = IDLE;
default: next = IDLE;
endcase
endThe defaults at the top make latches impossible, and they keep each branch short.
State encoding
| Encoding | Flops for N states | Strengths |
|---|---|---|
| Binary | log2(N), rounded up | Few flops |
| One-hot | N | Simple, fast decoding, suits FPGAs |
| Gray | log2(N), rounded up | One bit changes for sequential paths |
One-hot has more flops but simpler next-state logic: each state is a single bit, so its condition is a small expression. FPGAs have plentiful flops, so tools often pick it there. ASIC designs weigh the total area, since both flops and logic count.
Let the tool help
Using an enum makes waveforms show state names, and it lets synthesis re-encode the states if you allow it. Avoid magic numbers. State names are the best documentation an FSM can have.
Common mistake
Forgetting that unused encodings exist. Five states in three binary bits leave three illegal codes, and a default branch is the way to handle them. See the Debugging lesson for why this matters.
Key ideas
- Separate next-state and state register blocks.
- Binary is compact; one-hot often suits FPGAs and speed.
- Use defaults to avoid latches.
Lab: your code, animated
Your exercise
Find the bug
This code has one deliberate bug. Read the symptom, then click the line you think is wrong.
The fix
always @(*) begin
busy = 1'b0;Why it failed
busy is assigned only in RUN, so in other states it must remember its value, which infers a latch. The usual pattern gives every output a default at the top of the combinational block, so each state lists only what differs.
Interview questions
coreFlops for 5 states, binary and one-hot?
Three and five.
basicWhy do most coding guides split an FSM into a clocked block for the state register and a combinational block for next state and outputs?
The clocked block only stores, so it is short and clearly maps to flops. The combinational block holds all the decisions and can be read case by case, each case being a state and each if being a transition. Keeping them apart makes it easier to see that the outputs are combinational and to avoid latches.
basicAn FSM has 12 states. How many flops does binary encoding need, how many does one-hot need, and how many unused codes does binary leave?
Binary needs $clog2(12) = 4 flops, and 16 - 12 = 4 codes are unused. One-hot needs 12 flops, one per state. Gray encoding would also use 4 flops.
coreIn this next-state block, busy is set in LOAD and RUN but has no default. What happens in simulation and in hardware?
always @(*) begin
next = state;
case (state)
IDLE: if (start) next = LOAD;
LOAD: begin busy = 1'b1; next = RUN; end
RUN: begin busy = 1'b1; if (finished) next = DONE; end
DONE: next = IDLE;
endcase
endIn states where busy is not assigned, the block leaves it unchanged, so it keeps its last value: in simulation it stayed 1 in DONE and back in IDLE, and was x before the machine first reached LOAD. Synthesis must build a latch to hold it. Adding busy = 1'b0; at the top of the block, next to next = state;, gives every path a value and removes the latch.
coreThe FSM goes IDLE to LOAD on start, LOAD to RUN always, RUN to DONE on finished, and DONE to IDLE always. Write the one-hot next-state equations.
Each state's next bit is the OR of every arrow into it: IDLE_next = (IDLE & ~start) | DONE, LOAD_next = IDLE & start, RUN_next = LOAD | (RUN & ~finished), and DONE_next = RUN & finished. Each equation is small, which is why one-hot logic is fast. Exactly one of the four is true on every cycle as long as the register starts one-hot.
coreThis FSM is written in one clocked block, and busy is assigned inside it. Is busy high in the same cycles as when the state is LOAD or RUN?
always @(posedge clk)
case (state)
IDLE: begin busy <= 1'b0; if (start) state <= LOAD; end
LOAD: begin busy <= 1'b1; state <= RUN; end
RUN: begin busy <= 1'b1; if (finished) state <= DONE; end
DONE: begin busy <= 1'b0; state <= IDLE; end
endcaseNo, it is one cycle late. busy is a flop, so it takes the value chosen while in a state at the edge that leaves that state: in simulation it was 0 while in LOAD, 1 in RUN and DONE, and 0 again in IDLE. If you want busy during LOAD and RUN, set it from the next state, or compute it combinationally from the current state.
coreA one-hot FSM has 5 state flops. How many bit patterns are illegal, and what simple check catches all of them?
There are 2^5 = 32 patterns and only 5 are legal, so 27 are illegal, including all zeros. The check is that exactly one bit is set. If it fails, the machine should be sent back to a safe state such as IDLE, and an assertion can flag it in simulation.
advancedYou add a default branch that sends unused state codes back to IDLE. Is the recovery guaranteed to be in the gates after synthesis?
Not necessarily. Unused codes are unreachable in normal operation, so a synthesis tool that extracts and optimises the FSM may treat them as don't-cares and remove the recovery logic. Many tools have an option to build a safe state machine that keeps recovery from illegal states, and that is what is needed when bit upsets are a concern. Check the tool's FSM report to see what was built.
advancedWhen would you choose one-hot, binary or Gray encoding for an FSM?
Binary uses the fewest flops but needs wider decode logic, which suits area-sensitive ASIC designs with many states. One-hot uses one flop per state with very simple next-state and output logic, which often suits FPGAs, where flops are plentiful, and high-speed designs. Gray changes one bit per step, which helps when the machine mostly moves along a fixed sequence or its state is read by another clock domain.