Codiode

Lookahead FSM Sequence Detector

HardVerilog / SystemVerilogBuild

A combinational FSM output can glitch, and registering it costs a cycle. A lookahead output gets both: it is decoded from the next state and registered, so it is glitch-free and still on time.

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)

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 the problem's 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.

Part of FSM Coding

Problem 14 of 15 in the FSM Coding track.

Related problems

Browse all problems · Verilog practice problems · Learning tracks

Solve this on a laptopSend yourself the link and continue there.