Codiode

Zero-Latency Sequence Detector (Mealy FSM)

MediumVerilog / SystemVerilogBuild

A Mealy detector can flag a pattern in the same cycle its last bit arrives, because its output looks at the current input as well as the state.

The module continuously monitors a serial input stream on din. It searches for the overlapping bit sequence 101. When the final 1 of the sequence is present on the input, the output found asserts immediately in the same clock cycle. The output is purely combinational and depends on both the current state of the machine and the current input value.

  • Clock edge: posedge
  • Reset type: Asynchronous
  • Reset polarity: Active-low
  • Output values on reset: The FSM returns to its initial state, and found evaluates to 0.
  • Priority rules: If rst_n is asserted, it overrides any data on din, forcing found to 0 immediately.

Worked Trace

Cycle 1: rst_n=0, din=0 → state=S0, found=0
Cycle 2: rst_n=1, din=1 → state=S1, found=0
Cycle 3: rst_n=1, din=0 → state=S10, found=0
Cycle 4: rst_n=1, din=1 → state=S1, found=1 (Sequence 101 completed)
Cycle 5: rst_n=1, din=0 → state=S10, found=0
Cycle 6: rst_n=1, din=1 → state=S1, found=1 (Overlapping 101 completed)
Cycle 7: rst_n=1, din=0 → state=S10, found=0

State Diagram

Timing Diagram

Port Table

Signal Direction Width Description
clk input 1 Positive-edge triggered clock
rst_n input 1 Asynchronous active-low reset; state returns to initial, found goes to 0
din input 1 Serial data input
found output 1 Combinational output; 1 when 101 is detected, 0 otherwise

Constraints

  • Clock edge is posedge clk and reset is asynchronous active-low.
  • Output found must evaluate to 0 when rst_n is asserted.
  • The FSM must support overlapping sequences.
  • Output found must be purely combinational. Do not register the found output.

Topics

combinationalfsmmealysequence-detector

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 15 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.