Topic 7 · Finite State Machines

State Encoding

Video 3 of 4 · ~9 minutes

Dr. Mike Borowczak · Electrical & Computer Engineering · CECS · UCF

🌍 Where This Lives

Where it shows up

In aerospace, a single cosmic-ray-induced bit flip can crash a flight computer. In a medical device, a glitch on an output line can deliver a wrong dose. In a car, a 30-nanosecond pulse on the airbag firing line can deploy at 70mph for no reason at all. The exact bit-pattern an engineer chooses to label “step 3 of the wash cycle” or “configuration A” is not a stylistic choice. It is a safety choice.

When it goes wrong

Mariner 1 was destroyed 293 seconds after launch because of a single character missing in a guidance equation. Multiple automakers have recalled airbag controllers after EMI glitches caused phantom deployments. Therac-25 had encoded its operating modes such that a single corruption could push it into a mode it should never have been able to reach. Same machine, same logic, different bit-pattern: different outcome under noise.

⚠️ Three Encodings, Three Optima

Encoding	Bits (N states)	Example (4 states)	Best for
Binary	`$clog2(N)`	00, 01, 10, 11	ASIC, small FPGA, many states
One-Hot	`N`	0001, 0010, 0100, 1000	FPGA, fast decode, few states
Gray	`$clog2(N)`	00, 01, 11, 10	clock-domain-crossing FSMs

The fundamental tradeoff: Binary uses the fewest state flops but more decode logic. One-hot uses more flops but simpler decode (next-state depends on a single bit). On FPGAs with cheap flops and expensive wide-input logic, one-hot often wins. On ASICs where flops cost area, binary usually wins.

👁️ I Do — Write It With `localparam`

// Use localparam for state names — never magic numbers
localparam [1:0] S_GREEN  = 2'd0;
localparam [1:0] S_YELLOW = 2'd1;
localparam [1:0] S_RED    = 2'd2;

reg [1:0] r_state, r_next_state;

always @(*) begin
    r_next_state = r_state;
    case (r_state)
        S_GREEN:  if (timer_done) r_next_state = S_YELLOW;
        S_YELLOW: if (timer_done) r_next_state = S_RED;
        S_RED:    if (timer_done) r_next_state = S_GREEN;
        default:                  r_next_state = S_GREEN;
    endcase
end

Binary encoding RTL: 2 DFFs hold r_state[1:0]; next-state logic on the left; output decoder on the right produces o_green/o_yellow/o_red

2 flops · output decoder needed

My thinking: Write the FSM in binary encoding using localparam names. Don't use 2'd1 scattered in your code — the compiler lets you, but no human can read it. Yosys's fsm_recode pass will convert to the optimal encoding at synthesis time anyway.

🤝 We Do — Convert to One-Hot

// One-hot encoding: N bits, only one high at a time
localparam [2:0] S_GREEN  = 3'b001;
localparam [2:0] S_YELLOW = 3'b010;
localparam [2:0] S_RED    = 3'b100;

reg [2:0] r_state, r_next_state;

// Same next-state structure — only the encoding changed
// Outputs become single-wire taps:
assign o_green  = r_state[0];
assign o_yellow = r_state[1];
assign o_red    = r_state[2];

One-hot encoding RTL: 3 DFFs each tied directly to an output (o_green/o_yellow/o_red) with no decoder LUTs

3 flops · outputs = direct wires

Together: Only three things changed: state width (2→3), state values (binary→one-hot), register width. The case structure is identical. The output logic gets faster because, e.g., o_green = r_state[0] — a single wire, no decoder. That's the one-hot win.

🔍 Encoding → RTL Impact

Same FSM. Different encoding. The shape of the hardware changes.

Side-by-side RTL: binary encoding uses 2 flops plus an output decoder; one-hot uses 3 flops and direct output wires.

Read it carefully: Binary trades flops for a small decoder. One-hot trades a decoder for an extra flop and turns every output into a single wire from a single flop. On an FPGA with cheap flops, that single-wire output is a real timing-and-power win.

⚙️ What the Tool Does Behind Your Back

Synthesizers run dozens of optimization passes on your FSM. Most are invisible — until they bite.

Common passes (Yosys / Synopsys / Quartus)

FSM extraction & re-encoding — Yosys's fsm_recode may silently convert your binary localparams to one-hot (or vice versa).
State minimization — equivalent states merged; unreachable states removed.
Output retiming — combinational output logic pushed into or out of the state register.
Logic flattening / sharing — LUTs combined across blocks; gate-level cleanup.
Constant propagation — tied-off inputs simplify whole branches away.

Ramifications

Your source-level encoding may not match the silicon — stat shows what's actually built.
Waveform signal names may disappear or rename. Use (* keep *) / (* mark_debug *) to preserve them.
A bug visible in sim can vanish (or appear) post-synthesis if optimizations rewrite the FSM.
Two engineers, identical RTL, different tool versions → different gate counts.

Turning them off: synth_ice40 -nofsm (Yosys) disables FSM recoding/optimization. (* fsm_encoding = "user" *) / "one_hot" / "binary" (Vivado, Quartus) pin a specific encoding. (* keep = "true" *) on signals prevents constant-prop / sharing. Use these sparingly — they're for debugging or hard timing constraints, not as a default.

🧪 You Do — Predict the Difference

Same FSM with 8 states. Predict iCE40 cell counts for binary vs one-hot.

Binary

Flops: $clog2(8) = 3
Decode (next-state): ~4–6 LUTs
Output decode: ~3 LUTs per output
Total: ~12 cells

One-Hot

Flops: 8
Decode (next-state): ~8 LUTs (simpler per transition)
Output decode: 0 LUTs (direct bit)
Total: ~16 cells

Answer: One-hot uses more cells here (16 vs 12). But: one-hot has a shorter critical path (less decode), so it can run faster. It's a gate-count vs clock-speed tradeoff, not a strict winner.

🔧 The Pedagogy Is This Slide

Same traffic-light FSM. Two encodings. Side-by-side Yosys output:

BINARY (2 bits, 3 states)

$ yosys -p "synth_ice40 -top traffic_light \
            -nofsm; stat" day07_ex01_fsm_template.v
=== traffic_light ===
  SB_DFF:    2
  SB_LUT4:   5
  Total cells: 7

ONE-HOT (3 bits, 3 states)

$ yosys -p "synth_ice40 -top traffic_light_onehot \
            -nofsm; stat" day07_ex01_traffic_onehot.v
=== traffic_light_onehot ===
  SB_DFF:    3
  SB_LUT4:   3
  Total cells: 6

What to notice:

One-hot has more flops (3 vs 2) but fewer LUTs (3 vs 5).
Total cells: one-hot wins on this tiny FSM (6 vs 7).
That flips at larger state counts. The crossover on iCE40 is typically 6–8 states.
Run the experiment on your design — never guess, measure.

Pro note: Yosys's fsm_recode pass auto-re-encodes FSMs by default. Pass -nofsm to synth_ice40 to see your literal localparam encoding instead of the tool's choice.

▶ LIVE DEMO

Encoding Comparison Live

~4 minutes

▸ COMMANDS

cd lecture_examples/week2_day07/d07_s2_ex1/
make stat_binary    # day07_ex01_fsm_template.v
make stat_onehot    # day07_ex01_traffic_onehot.v
make stat_gray      # day07_ex01_traffic_gray.v
make stat_all       # side-by-side summary

▸ EXPECTED STDOUT

=== Encoding comparison summary ===
--- stats/binary.txt ---
  SB_DFF   2 · SB_LUT4   5  (~7 cells)
--- stats/onehot.txt ---
  SB_DFF   3 · SB_LUT4   3  (~6 cells)
--- stats/gray.txt ---
  SB_DFF   2 · SB_LUT4   5  (~7 cells)
ONE-HOT wins area on this 3-state FSM.

▸ OBSERVATION

One-hot wins both area AND speed on this tiny FSM. At 3 states, the cost of 1 extra flop is dwarfed by the savings in decode LUTs. This is why FPGA vendor guides recommend one-hot for small FSMs.

🤖 Check the Machine

Ask AI: “Which state encoding is best for a 5-state FSM on an iCE40 FPGA?”

TASK

Ask AI for encoding recommendation.

BEFORE

Expected: “depends — run both encodings, compare. Binary saves flops, one-hot saves LUTs.”

AFTER

Weak AI gives a single answer. Strong AI says “measure both.”

TAKEAWAY

There's no universal “best”. Measurement beats opinion.

Key Takeaways

① Three encodings: binary (compact), one-hot (fast decode), Gray (CDC-safe).

② Use localparam for state names. Never magic numbers.

③ Tradeoff: flops vs. decode LUTs. FPGAs often favor one-hot for small FSMs.

④ Measurement beats opinion. Run make stat with each encoding.

Synthesize both. Let the tool tell you which wins.

🔗 Transfer

FSM Design Methodology

Video 4 of 4 · ~10 minutes

▸ WHY THIS MATTERS NEXT

You know the template and the encoding options. Video 4 puts them into a complete methodology: how to go from a problem specification to a working, tested FSM. You'll see a pattern-detector example from scratch — the process you'll reuse for every FSM in the course.