Project 13: Serial Pattern Detector (Find 10110)

Detect a specific bit pattern in a serial stream using an FSM.

Quick Reference

Attribute Value
Difficulty Advanced
Time Estimate 1 weekend
Main Programming Language Verilog (Alternatives: VHDL, SystemVerilog)
Alternative Programming Languages VHDL, SystemVerilog
Coolness Level Medium
Business Potential Low
Prerequisites FSMs, Serial streams
Key Topics Pattern detection, Overlapping matches

1. Learning Objectives

  1. Design a Mealy or Moore pattern detector
  2. Handle overlaps correctly
  3. Produce single-cycle match pulses

2. All Theory Needed (Per-Concept Breakdown)

Finite State Machine Design

Description/Expanded Explanation of the concept

FSMs model systems that move between discrete states. They are the backbone of controllers: traffic lights, vending machines, UARTs, and CPUs. A clear state diagram and correct next-state logic are essential.

Definitions & Key Terms
  • State -> encoded system condition
  • Moore FSM -> outputs depend only on state
  • Mealy FSM -> outputs depend on state and inputs
Mental Model Diagram (ASCII)
S0 --in--> S1 --in--> S2
 ^                 |
 +-----------------+

Three-state FSM loop

How It Works (Step-by-Step)
  1. Define states and transitions.
  2. Encode the states.
  3. Implement next-state combinational logic.
  4. Register the state on the clock edge.
Minimal Concrete Example
always @(posedge clk) begin
  if (reset) state <= IDLE;
  else state <= next_state;
end
Common Misconceptions
  • “State encoding doesn’t matter.” -> It affects area and speed.
  • “Mealy is always faster.” -> It can glitch if inputs change.
Check-Your-Understanding Questions
  1. When would you choose Moore over Mealy?
  2. How do you avoid glitches on outputs?
  3. How do you handle illegal states?
Where You’ll Apply It
  • This project: used in Section 3.2 and Section 4
  • Also used in: P11-traffic-light-controller.md, P13-serial-pattern-detector-finding-10110-in-a-bitstre.md, Final CPU

Verification with Testbenches and Waveforms

Description/Expanded Explanation of the concept

Testbenches are simulation-only modules that apply stimulus and check outputs. Waveforms (VCD) are the hardware engineer’s microscope; they reveal timing, glitches, and ordering problems. A good testbench is deterministic and covers edge cases.

Definitions & Key Terms
  • Testbench -> a non-synthesizable module that drives a DUT
  • VCD -> Value Change Dump waveform file
  • Deterministic test -> same inputs produce same outputs every run
Mental Model Diagram (ASCII)
[Testbench] -> [DUT] -> [VCD] -> [GTKWave]

Testbench DUT VCD GTKWave flow

How It Works (Step-by-Step)
  1. Initialize inputs to known values.
  2. Apply stimulus over time.
  3. Dump waveforms and check outputs.
  4. Add assertions or PASS/FAIL messages.
Minimal Concrete Example
initial begin
  $dumpfile("wave.vcd");
  $dumpvars(0, tb);
  a = 0; b = 1; #10;
  $finish;
end
Common Misconceptions
  • “If it simulates once, it’s correct.” -> Cover all relevant cases.
  • “Waveforms are optional.” -> They are often the only way to debug timing.
Check-Your-Understanding Questions
  1. Why keep testbench and DUT separate?
  2. What is the purpose of $dumpvars?
  3. How do you make a testbench deterministic?
Where You’ll Apply It
  • This project: used throughout Section 6 (testing)
  • Also used in: all other projects in this folder

3. Project Specification

3.1 What You Will Build

An FSM that asserts match when it sees 10110 in a serial stream.

3.2 Functional Requirements

  1. Requirement 1: Detect pattern with overlaps
  2. Requirement 2: Output a single-cycle match signal
  3. Requirement 3: Reset to known state

3.3 Non-Functional Requirements

  • Performance: Stable operation at the target clock and interfaces.
  • Reliability: Deterministic outputs on all defined inputs.
  • Usability: Clear ports and documented behavior.

3.4 Example Usage / Output

{p['example_usage']}

3.5 Data Formats / Schemas / Protocols

{p[‘data_format’]}

3.6 Edge Cases

  • Overlapping patterns
  • Reset mid-stream

3.7 Real World Outcome

3.7.1 How to Run (Copy/Paste)

vvp pattern_tb

3.7.2 Golden Path Demo (Deterministic)

Run the demo command above with the provided testbench and confirm the outputs match the golden transcript.

3.7.3 CLI Transcript

stream=110101101001
match at bit index 6

3.7.4 Failure Demo (Expected)

# Example failure case
ERROR: Output mismatch at vector 3
Expected: 0x0A, Got: 0x0B
EXIT CODE: 1

Notes:

  • Exit code 0 indicates all tests passed
  • Exit code 1 indicates a test failure

4. Solution Architecture

4.1 High-Level Design

[inputs] -> [core logic] -> [outputs]

Core logic flow

4.2 Key Components

Component Responsibility
fsm Pattern detection FSM

4.3 Data Structures (No Full Code)

// Example signals (adapt to your design)
reg [7:0] state_reg;
reg [7:0] data_reg;

4.4 Algorithm Overview

Key Algorithm: Core control flow

  1. Initialize state/reset conditions.
  2. Apply inputs and compute outputs.
  3. Update state on clock edges (if sequential).

Complexity Analysis:

  • Time: O(1) per cycle
  • Space: O(N) for registers and logic

5. Implementation Guide

5.1 Development Environment Setup

iverilog -v
# Ensure GTKWave is installed for waveform viewing

5.2 Project Structure

project-root/
|-- src/
|   |-- top.v
|   |-- core.v
|-- tb/
|   |-- tb.v
|-- Makefile
|-- README.md

Project folder structure

5.3 The Core Question You’re Answering

“How does hardware recognize patterns in a live data stream?”

5.4 Concepts You Must Understand First

  • FSMs
  • Serial streams

5.5 Questions to Guide Your Design

  • Moore or Mealy output?
  • How will you handle overlaps?

5.6 Thinking Exercise

Draw the state diagram for 10110 with overlaps.

5.7 The Interview Questions They’ll Ask

  • How do overlaps change the FSM?
  • Why can Mealy detect one cycle earlier?

5.8 Hints in Layers

  • Create states for each partial match.
  • On mismatch, fall back to the longest suffix state.

5.9 Books That Will Help

Topic Book Chapter
FSMs Digital Design and Computer Architecture Ch. 3.4

5.10 Implementation Phases

Phase 1: Foundation

Goals:

  • Establish core module structure
  • Implement minimal behavior

Tasks:

  1. Scaffold module ports and internal signals
  2. Write a minimal testbench that compiles

Checkpoint: Simulation runs without errors

Phase 2: Core Functionality

Goals:

  • Implement full logic
  • Verify edge cases

Tasks:

  1. Complete core logic
  2. Add directed tests for edge cases

Checkpoint: All tests pass and waveforms match expectations

Phase 3: Polish & Edge Cases

Goals:

  • Improve readability
  • Document behavior

Tasks:

  1. Add comments and README notes
  2. Expand tests for unusual inputs

Checkpoint: Design is deterministic and documented

5.11 Key Implementation Decisions

Decision Options Recommendation Rationale
Reset strategy Sync / Async Sync Simpler timing closure
Test coverage Directed / Exhaustive Exhaustive for small logic Prevents missed cases

6. Testing Strategy

6.1 Test Categories

Category Purpose Examples
Unit Tests Test core logic Small vectors
Integration Tests Test modules together Full system
Edge Case Tests Boundary conditions Max/min values

6.2 Critical Test Cases

  1. Test 1: Input 10110110 and check for two matches
  2. Test 2: Reset mid-stream clears state

6.3 Test Data

Use deterministic vectors and document expected outputs.

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

Pitfall Symptom Solution
No overlap Second match missing Add overlap transitions

7.2 Debugging Strategies

  • Inspect waveforms at key internal signals
  • Add temporary debug outputs to verify state
  • Reduce testcases to the smallest failing case

7.3 Performance Traps

  • Overly wide counters or combinational paths can reduce max clock

8. Extensions & Challenges

8.1 Beginner Extensions

  • Add parameterization for widths
  • Add optional features (enable, reset)

8.2 Intermediate Extensions

  • Add configuration registers
  • Build a simple driver or demo program

8.3 Advanced Extensions

  • Integrate with another project in this series
  • Implement a hardware demo on FPGA

9. Real-World Connections

9.1 Industry Applications

  • Digital control systems and embedded peripherals
  • FPGA prototyping and validation
  • Yosys / nextpnr toolchain for open-source FPGA flow
  • Example HDL projects in the FPGA community

9.3 Interview Relevance

  • Demonstrates RTL thinking and verification skills

10. Resources

10.1 Essential Reading

  • Digital Design and Computer Architecture - Focus on Ch. 3.4

10.2 Video Resources

  • Search for project-specific HDL walkthroughs and waveforms

10.3 Tools & Documentation

  • Icarus Verilog
  • GTKWave
  • See adjacent projects in VERILOG_FROM_ZERO_PROJECTS/

11. Self-Assessment Checklist

11.1 Understanding

  • I can explain the core concept without notes
  • I can predict waveform behavior for basic inputs

11.2 Implementation

  • All functional requirements are met
  • All tests pass
  • Edge cases are documented

11.3 Growth

  • I can explain this project in an interview
  • I documented at least one lesson learned

12. Submission / Completion Criteria

Minimum Viable Completion:

  • Functional requirements implemented
  • Testbench passes
  • Waveforms inspected

Full Completion:

  • All minimum criteria plus
  • Edge cases covered and documented

Excellence (Going Above & Beyond):

  • Hardware demo on FPGA
  • Clear write-up of lessons learned

    Appendix A: Deep Dive Walkthrough

A.1 Signal Map and Invariants

  • Inputs: clk, reset, bit_in
  • Output: match

Invariant: match is a one-cycle pulse when the stream contains 10110 (with overlap if enabled).

A.2 State Progression (Overlap Enabled)

S0 --1--> S1 --0--> S2 --1--> S3 --1--> S4 --0--> MATCH
 ^       0|      1|      0|      0|          1|
 +--------+-------+-------+-------+-----------+

Pattern detector FSM

A.3 Deterministic Test Stream

  • Input: 10110110
  • Expected matches at positions ending at bits 5 and 8.

A.4 Debugging Tip

If matches are missed, your transition on partial overlaps is probably wrong. Probe the state bits in the waveform to verify partial matches are retained.

13. Deep Dive Appendix

13.1 Timing and Resource Budget

  • Pattern detection can be done with a small FSM or a shift register + compare.
  • FSM uses guaranteed minimal logic and handles overlaps cleanly.
  • Shift-register approach uses more bits but is easy to visualize.

13.2 Waveform Interpretation Guide

  • Watch bit_in, state, and match together.
  • For overlaps, confirm that a match does not reset to idle if the pattern suffix matches a prefix.

Example (pattern=10110):

input: 10110110
match: ----1--1

13.3 Hardware Bring-Up Notes

  • Use a button or switch to clock in bits manually.
  • Display match on an LED so you can see detection.
  • A shift-register display of the last 5 bits helps debug.

13.4 Alternate Implementations and Trade-offs

  • FSM: optimal for overlapping matches.
  • Shift+compare: simpler for non-overlapping detection.
  • Parameterized generator: accept pattern as a parameter.

13.5 Additional Exercises

  • Add a match counter that increments per detection.
  • Support multiple patterns with parallel FSMs.
  • Implement a programmable pattern stored in a small register.