Skip to question

Q074FreeSystemVerilog

Overlapping 101 sequence detector

Difficulty
Easy
Topic
RTL Design
Language
SV
Interview prompt

Question

A serial control stream needs a one-cycle marker whenever its most recent three sampled bits are 101. Matches may overlap. Design a synthesizable SystemVerilog FSM and preserve the final 1 as the prefix of a possible next match.

Candidate starting point

Implementation scaffold

module detect_101 (
  input  logic clk,
  input  logic rst_n,
  input  logic bit_in,
  output logic detect
);
  typedef enum logic [1:0] {S_NONE, S_1, S_10} state_t;
  state_t state, next_state;
  logic next_detect;

  always_comb begin : decode_prefix
    // TODO: decode the longest useful suffix and next match indication.
  end

  always_ff @(posedge clk) begin : register_prefix_and_match
    // TODO: implement the specified sampled reset and sequential behavior.
  end
endmodule
Reviewed example

Trace one case

Input
After reset: bit_in = 1, 0, 1, 0, 1
Expected output
detect = 0, 0, 1, 0, 1

After each 101 match, the final 1 becomes the prefix state for the next overlapping match.

What to cover

Requirements

  1. On each rising edge with rst_n=1, sample bit_in. Register detect=1 for the full cycle immediately after an edge that accepts the final 1 of a 101 match, and register detect=0 on every other nonreset edge.
  2. Allow overlap: after recognizing 101, retain that final 1 as the possible first bit of the next match.
  3. When rst_n is 0 at a rising edge, enter the no-prefix state and drive detect low.
  4. Use only synthesizable state and output logic; detect must remain low for all nonmatching input histories.
Continue practicing
Q799 · RTL DesignDetect overlapping 1101 sequencesMediumPQ204 · FSMsDetect overlapping 1011 sequencesMediumP