Lookahead FSM Sequence Detector

HardVerilog / SystemVerilogBuild

High-speed packet parsers and network routers rely on sequence detectors to flag frame boundaries. Combinational FSM outputs are prone to glitches that can cause false triggers in downstream logic. Standard registered outputs solve the glitching but introduce a full clock cycle of latency. Lookahead registered outputs resolve both issues by decoding the output from the next-state logic, ensuring the output is glitch-free (driven directly by a flip-flop) while asserting in the exact same cycle the target state becomes active.

The module detects the overlapping serial bit sequence 101 on the din input. When the sequence is detected, the FSM enters a match state and asserts the detect output. The detect signal must be a registered output (driven by a flip-flop on the positive clock edge). To avoid latency, detect must be high during the exact cycle the FSM is in the match state. This requires the detect flip-flop to be driven by a comparison against the next-state logic, rather than the current-state logic.

Clock edge: posedge clk
Reset type: Asynchronous, active-low (rst_n)
Output reset: detect goes to 0 on reset
Priority: Reset takes priority over all other inputs
The sequence detection allows overlapping (e.g., 10101 produces two consecutive detections)

Cycle 1: rst_n=0 → state=IDLE, detect=0 Cycle 2: rst_n=1, din=1 → state=S1, detect=0 Cycle 3: din=0 → state=S10, detect=0 Cycle 4: din=1 → state=MATCH, detect=1 (Lookahead output asserts immediately) Cycle 5: din=0 → state=S10, detect=0 Cycle 6: din=1 → state=MATCH, detect=1 (Overlapping sequence triggers again)

flowchart LR
    RESET(( )) -->|reset| IDLE
    IDLE((IDLE)) -->|din=1| S1
    IDLE -->|din=0| IDLE
    S1((S1)) -->|din=0| S10
    S1 -->|din=1| S1
    S10((S10)) -->|din=1| MATCH
    S10 -->|din=0| IDLE
    MATCH(["MATCH ★"]):::out -->|din=1| S1
    MATCH -->|din=0| S10
    classDef out fill:#6C5CE7,stroke:#5B4FE8,color:#fff

{ "signal": [
  { "name": "clk",    "wave": "p........." },
  { "name": "rst_n",  "wave": "01........" },
  { "name": "din",    "wave": "x1.0.1.0.1" },
  {},
  { "name": "state",  "wave": "=.====.=.=", "data": ["IDLE","S1","S10","MATCH","S10","MATCH"] },
  { "name": "detect", "wave": "0....1.0.1" }
], "head": { "text": "Lookahead registered output asserts in the same cycle the state becomes MATCH." } }

| Signal | Direction | Width | Description | |--------|-----------|-------|-------------| | clk | input | 1 | Positive-edge triggered clock | | rst_n | input | 1 | Asynchronous active-low reset; resets FSM and detect to 0 | | din | input | 1 | Serial data input | | detect | output | 1 | Registered lookahead output; asserts to 1 when 101 is detected |

Constraints

The detect output must be driven directly by a flip-flop; no combinational logic is allowed between the register and the output port.
The detect output must assert in the exact same clock cycle that the FSM enters the match state.
The FSM must support overlapping sequence detection.
Reset is asynchronous and active-low.

Topics

FSMMoore MachineSequential LogicLookahead

Solve this problem

Write the module in Verilog, SystemVerilog or VHDL. Your submission is compiled and simulated against a real testbench — you get the waveform back, not a stored answer.

This problem is part of Codiode Pro. The statement above is free to read.

The circuit builder and code editor need a desktop screen. On a phone, read the problem here and open it on a laptop to solve.

Related problems

Browse all problems · Learning tracks