Day 7 · Finite State Machines

FSM Design Methodology

Video 4 of 4 · ~10 minutes

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

FSM Theory3-Block TemplateState EncodingMethodology

🌍 Where This Lives

In Industry

Every serial-protocol controller is a pattern detector for the protocol's start sequence. CAN bus, Ethernet MAC, PCIe link training, USB SOF detection — all start-of-frame detection is a pattern-matching FSM. Packet inspection hardware in network switches runs dozens of pattern-detector FSMs in parallel.

In This Course

Your Day 11 UART RX detects the start bit using this pattern. Your Day 12 SPI detects chip select. Your capstone FSM will almost certainly be a pattern detector of some kind. Today's methodology is the template.

⚠️ Don't Start in the Editor

❌ Wrong Workflow

“I know the problem. I'll start writing Verilog, figure out states as I go, debug in simulation. The editor IS my thinking environment.”

✓ Right Workflow

Draw the state diagram on paper first. Enumerate states, transitions, outputs. Validate by walking through test inputs with a pencil. Only then open the editor, where you apply the 3-block template to your already-correct diagram. Debugging a diagram is seconds; debugging Verilog is hours.

The receipt: Every senior engineer in the industry owns a whiteboard. Every FSM starts there. The editor is where the already-correct design becomes code.

👁️ I Do — The Six-Step Methodology

  1. Identify inputs, outputs, and the sequential behavior — what does it do over time?
  2. Enumerate states — one per distinct behavior mode.
  3. Draw the state diagram on paper — transitions, conditions, outputs.
  4. Walk through test cases with a pencil — does it handle the expected inputs?
  5. Apply the 3-block template — now you're just transcribing.
  6. Write self-checking testbench — test every transition, including the error paths.
My thinking: Steps 1–4 happen on paper. Step 5 is mechanical. Step 6 uses last week's testbench skills to prove correctness. Time ratio: 60% design, 30% code, 10% test — beginners invert this and regret it.

🤝 We Do — Pattern Detector for “1011”

Detect when the input bit stream contains 1011. Assert o_detected for one cycle when the last 4 bits form the pattern. Overlapping patterns allowed.

  input:   0 1 0 1 1 0 1 1 0 1 1
  output:  0 0 0 0 1 0 0 1 0 0 1
                   ↑       ↑     ↑
                 match   match  match (overlapping)
States (enumerate distinct histories):
  • S0: haven't matched anything yet
  • S1: last bit was 1 (matched first bit of pattern)
  • S10: last two bits were 10
  • S101: last three bits were 101 — one more 1 completes the pattern

🤝 State Diagram (Completed)

         ┌─── 0 ───┐
         ↓         │
    ┌─ S0 ────── 1 ──→ S1
    │    ↑              │
    │    │              │
    0    0              0
    │    │              ↓
    │    └────────── S10
    │                   │
    │                   1
    │                   ↓
    └── 0 ──── S101 ──1──→ S101 (with o_detected=1)
                                 (and can immediately match
                                  again in overlapping case)
Key insight: From S101, a 1 completes the pattern AND we're now seeing ...11, which could be the start of the next overlapping match. So from S101 + input=1, we go to S1 (not S0), because we just saw 1. This is what makes pattern detectors subtle.

🧪 You Do — Walk the FSM

Input stream: 1 0 1 1 1 0 1 1. What's the state trajectory and where does o_detected pulse?

Trace (start in S0): 
Input:  1    0    1    1    1    0    1    1
State: S0 → S1 → S10→ S101→  ✓   → S10→ S101→  ✓
                            S1                  S1
                            (overlapping match!)
o_det:  0    0    0    0    1    0    0    1
▶ LIVE DEMO

Pattern Detector: From Diagram to Working FSM

~6 minutes

▸ COMMANDS

cd labs/week2_day07/ex4_pattern/
cat pattern_1011.v    # 3-block from diagram
make sim              # covers overlap cases
make wave
make stat

▸ EXPECTED STDOUT

PASS: detects 1011
PASS: ignores 1010
PASS: detects overlapping 10110111
PASS: reset → S0
=== 16 passed, 0 failed ===

  SB_DFF:  2
  SB_LUT4: 4

▸ GTKWAVE

Signals: i_bit · r_state · o_detected. Watch state traverse S0→S1→S10→S101. Detection pulses are 1-cycle wide. The overlapping pattern exercises the S101→S1 transition explicitly.

FSM Coding Checklist

  • ☐ State diagram drawn on paper before opening the editor
  • ☐ Hand-walk at least 2 test cases, including edge cases
  • ☐ 3 separate always blocks (state reg, next-state, output)
  • ☐ Block 1 is trivial (just DFF with reset)
  • ☐ Block 2: default assignment first (r_next = r_state;), default: case at end
  • ☐ Block 3: default output assignments for every output, default: case at end
  • ☐ States use localparam, never magic numbers
  • ☐ Nonblocking <= in sequential (Block 1); blocking = in combinational (Blocks 2, 3)
  • ☐ Self-checking testbench covers every transition, including error paths

🤖 Check the Machine

Ask AI: “Design an FSM that detects the pattern ‘110101’ in a serial bit stream. Include the state diagram description, 3-block Verilog, and a self-checking testbench with overlapping test cases.”

TASK

Ask AI for a complete FSM package.

BEFORE

Predict: 6 states + idle, 3-block Verilog, overlapping sequence tests.

AFTER

Strong AI handles overlaps. Weak AI only handles non-overlapping cases — subtle bug.

TAKEAWAY

Always test the overlap case. AI-written FSMs commonly miss it.

Key Takeaways

① Draw the state diagram before writing code.

② Walk test cases with a pencil. Catch bugs in diagrams, not in Verilog.

③ Pattern detector overlaps: new match can begin from a partial match.

④ Test every transition, including the edge cases.

Paper first. Template second. Testbench third. No shortcuts.

Pre-Class Self-Check

Q1: Why is the state diagram drawn before the Verilog?

Catching logic bugs on paper takes seconds; catching them in simulation takes hours. The diagram is the design; the Verilog is the transcription.

Q2: What transition happens when a pattern detector is in its near-final state and receives an input that completes an overlapping prefix?

Transition to the state representing that overlapping prefix — not back to start. Overlap handling is the main place pattern FSMs go wrong.

Pre-Class Self-Check (cont.)

Q3: For a 6-state FSM on iCE40, which encoding is likely more compact?

Binary (3 flops vs 6 flops). But measure — at this state count the crossover is near. Run both through make stat.

Q4: Name three cases your testbench must cover for a pattern detector.

(1) Exact pattern match. (2) Near-miss (last bit wrong). (3) Overlapping match. Professionals also add: reset during match, prefix that looks like the start of the pattern, back-to-back matches.

🔗 End of Day 7

Tomorrow: Modules Within Modules

Day 8 · Hierarchy, Parameters, Generate

▸ WHY THIS MATTERS NEXT

You've built modules up to a few hundred lines. Real designs have thousands of lines, across dozens of files, arranged hierarchically. Day 8 teaches the three Verilog features that make this scale: module hierarchy, parameters for configurable IP, and generate blocks for array-style replication. By end of Day 8 your growing module library will become a reusable toolbox.