Day 7 · Finite State Machines

FSM Theory & Architecture

Video 1 of 4 · ~14 minutes

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

🌍 Where This Lives

In Industry

UART / SPI / I²C controllers. PCIe link trainers. Memory arbiters. Cache coherence protocols. The instruction issue logic of every CPU you own. When a RTL engineer says “control path,” they mean the FSM layer.

In This Course

Traffic light (today's demo) · Pattern detector (Video 4) · UART TX (Day 11) · UART RX (Day 12) · Memory test engine (Day 9) · Your Barcelona capstone traffic controller. Get comfortable here → the rest of the course unlocks.

Career tag: “FSM design” and “control-path verification” appear in ~90% of entry-level digital-design job postings. The FPGA/ASIC hiring bar assumes you can write a clean 3-block FSM on a whiteboard in under 5 minutes.

⚠️ If You're Thinking Like a Programmer…

❌ Wrong Model

“An FSM is just a big switch statement inside a while(true) loop. I'll cram it all into one always block with nested ifs and it'll work.”

✓ Right Model

An FSM is three pieces of physical hardware: a state register (flip-flops), combinational next-state logic, combinational output logic. All three exist simultaneously. The case statement describes — it does not execute.

Why this matters: The “one big always block” instinct is the #1 source of inferred latches, race conditions, and sim/synthesis mismatches in student FSMs. We'll see a real example in today's demo.

What Is a Finite State Machine?

An FSM is a sequential circuit defined by:

A finite set of states (always in exactly one)

Transitions governed by input conditions

Outputs that depend on state (and possibly inputs)

Formally: M = (S, S₀, Σ, δ, Λ) — states, start state, input alphabet, transition function, output function.

Memorize this sentence: “State is memory. It's what we have to remember about the past in order to react correctly to the future.”

Moore vs. Mealy

	Moore	Mealy
Outputs depend on	State only	State + inputs
Output changes	On clock edge (with state)	Can change mid-cycle
Timing	Clean, registered	Faster, can glitch
States needed	Typically more	Typically fewer
Debug difficulty	Easy (outputs track state)	Harder (outputs ≠ state)

Our default: Moore. Safer, easier to debug, cleaner timing closure. Use Mealy only when you need same-cycle reaction — and flag it in code comments.

FSM Block Diagram — Three Pieces of Hardware

FSM block diagram: state register feeds next-state logic and output logic; next-state logic feeds back to state register

State Register
sequential · flip-flops · always @(posedge clk)

Next-State & Output Logic
combinational · LUTs/gates · always @(*)

👁️ I Do — A Traffic Light in 4 Lines

Three states. Three outputs. One timer input. Here's the state diagram:

  ┌───────────┐ timer ┌────────────┐ timer ┌─────────┐
  │  S_GREEN  │─────▶ │  S_YELLOW  │─────▶│  S_RED  │
  │ o_green=1 │       │ o_yellow=1 │      │ o_red=1 │
  └───────────┘       └────────────┘      └─────────┘
       ▲                                        │
       └────────────── timer ───────────────────┘

My thinking: I named states by what they mean, not by number. S_GREEN is more useful than S0 in a waveform trace. Outputs are inside each state bubble — that's the Moore convention.

🤝 We Do — Predict the Trajectory

Given the state diagram, with timer asserting every 4 cycles, fill in the next 12 cycles starting from S_GREEN:

cycle:   0  1  2  3  4  5  6  7  8  9  10 11 12
state:   G  G  G  G  Y  ?  ?  ?  ?  ?  ?  ?  ?
timer:   0  0  0  1  0  0  0  1  0  0  0  1  0
o_red:   0  0  0  0  0  ?  ?  ?  ?  ?  ?  ?  ?
o_green: 1  1  1  1  0  ?  ?  ?  ?  ?  ?  ?  ?

Answer: state: G,G,G,G, Y,Y,Y,Y, R,R,R,R, G. o_green: 1,1,1,1,0,0,0,0,0,0,0,0,1. Key observation: the state changes on the clock edge after timer=1 — outputs follow state, not timer. That one-cycle latency is Moore's signature.

🧪 You Do — Before We Run It

Take 60 seconds. Without looking at code, predict:

How many flip-flops will Yosys use for the state register?
Will the total flop count be less than, equal to, or greater than 3?
What should the GTKWave trace of r_state look like if we dump it as ASCII (Hint: you'll see the state names).

Predictions: ⌈log₂(3)⌉ = 2 flops (binary encoding — or 3 flops if Yosys picks one-hot). · Total flops: exactly equal to state flops (no counters yet in this minimal version). · Trace: S_GREEN (4 cycles) → S_YELLOW (4) → S_RED (4), repeating.

▶ LIVE DEMO

Traffic Light FSM — Simulation + Synthesis

labs/week2_day07/ex1_traffic_light/ · ~5 minutes

▸ COMMANDS

cd labs/week2_day07/ex1_traffic_light/
make sim       # iverilog + vvp
make wave      # GTKWave on dump.vcd
make stat      # yosys synth_ice40 + stat

▸ EXPECTED STDOUT

[@ 120ns] PASS: S_GREEN active
[@ 280ns] PASS: S_GREEN→S_YELLOW
[@ 440ns] PASS: S_YELLOW→S_RED
[@ 600ns] PASS: S_RED→S_GREEN
=== 4 passed, 0 failed ===

▸ GTKWAVE — WHAT TO LOOK FOR

Signal order: i_clk · i_rst · i_timer_done · r_state · o_red · o_yellow · o_green. Right-click r_state → Data Format → ASCII to see S_GREEN etc. instead of 0/1/2. Watch for the 1-cycle delay between i_timer_done rising and r_state changing.

🔧 What Did the Tool Build?

Running make stat on the traffic light:

$ yosys -p "read_verilog traffic_light.v; \
             synth_ice40; stat" -q

=== traffic_light ===

   Number of wires:                  12
   Number of cells:                   8
     SB_DFF                           2  ← state register
     SB_LUT4                          6  ← next-state + output

Match your prediction?

3 states → ⌈log₂3⌉ = 2 flops ✓
Yosys chose binary encoding (default for small FSMs on iCE40)
6 LUTs: ~3 for next-state case, ~3 for output decoding

Red flag if you see: ≥4 flops (you inferred a latch — check Block 2 defaults).

Generate this yourself: yosys -p "read_verilog traffic_light.v; synth_ice40; show -format svg -prefix fsm_synth" — produces fsm_synth.svg showing the actual gates and flops Yosys built.

This slide is the bridge between “I wrote Verilog” and “there is physical hardware on a chip.” Two flip-flops. Six LUTs. That's the entire traffic light controller. [Key teaching moment] Every student should be able to predict flop count from state count BEFORE running synthesis. That's the mental-model check. If you predict 2 and Yosys builds 2, your abstraction is intact. If you predict 2 and Yosys builds 5, either the tool used one-hot (fine, not wrong) or you've inferred latches (bad, needs fixing). [Generation command at bottom] Students can regenerate the schematic themselves. Encourage them to — seeing their own code become gates is the single biggest “oh, this is real hardware” moment of the course.

🤖 Check the Machine

Ask an AI assistant: “Given this 3-state traffic light FSM in Verilog, what happens if I remove the default assignment r_next = r_state; from the top of Block 2?”

TASK

Paste the code to the AI with the default line removed.

BEFORE

Your prediction: “Simulation still works, every state case is covered.”

AFTER

AI should flag: without default, the case incompletely assigns r_next in some paths → latch inferred.

TAKEAWAY

Yosys reports the same via synth_ice40 -verbose. AI catches it from code alone.

Rule: AI is never your first step. Predict first, simulate, then ask AI to explain anything surprising. If AI contradicts your simulation, trust the simulation — then figure out why the AI was wrong. That's where the real learning lives.

Key Takeaways

① FSM = states + transitions + outputs. State is memory.

② Moore (outputs = f(state)) is our default — clean timing, easier to debug.

③ FSMs are three pieces of hardware: state reg + next-state logic + output logic.

④ Flop count should equal ⌈log₂(states)⌉. Extra flops = latch trouble.

One always block per hardware piece. One hardware piece per always block.

🔗 Transfer

The 3-Always-Block Template

Day 7, Video 2 of 4 · ~15 minutes

▸ WHY THIS MATTERS NEXT

You just saw an FSM is three hardware pieces. In Video 2 you'll learn the Verilog template that keeps those three pieces separated — one always block per piece. This isn't just style: it's the coding pattern that prevents the #1 FSM bug (inferred latches) and makes your FSMs synthesize cleanly on both FPGA and ASIC targets. Every FSM you write for the rest of this course (UART, memory test, capstone) uses this template.