Day 7 · Finite State Machines

State Encoding

Video 3 of 4 · ~9 minutes

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

🌍 Where This Lives

In Industry

FPGA vendors publish encoding style guides (Xilinx UG901, Intel Quartus Handbook) that recommend one-hot for fast FPGA FSMs. ASIC flows (Synopsys DC, Cadence Genus) often pick binary for gate-count optimization. Clock-domain-crossing FSMs use Gray to prevent multi-bit transitions. The choice has measurable consequences in real silicon.

In This Course

Day 10 PPA exercise compares the same FSM across encodings and measures LUT count, timing, and power — directly. Day 14 retrospective revisits this decision. Today you learn the three encodings and the yosys stat evidence that distinguishes them.

⚠️ 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

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 logic structure — only the encoding changed

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.

🧪 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 -nofsm-recode; stat"
=== traffic_binary ===
  SB_DFF:    2
  SB_LUT4:   5
  Total cells: 7

ONE-HOT (3 bits, 3 states)

$ yosys ... -p "synth_ice40 -nofsm-recode; stat"
=== traffic_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. Use -nofsm-recode to see your literal encoding, or -fsm-expand to force one-hot.

▶ LIVE DEMO

Encoding Comparison Live

~4 minutes

▸ COMMANDS

cd labs/week2_day07/ex3_encoding/
make stat_binary
make stat_onehot
make stat_gray
diff stats/*.txt

▸ EXPECTED STDOUT

  BINARY:  7 cells (2F/5L)
  ONE-HOT: 6 cells (3F/3L)
  GRAY:    7 cells (2F/5L)
  FMAX (approx, iCE40):
    BINARY:  152 MHz
    ONE-HOT: 167 MHz  ← winner
    GRAY:    153 MHz

▸ 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.