Sequence Detector — "101"

AMD
Qualcomm
Microsoft
Intel

Problem Description

You're a verification engineer at a chip company. The hardware team just taped out a new SoC and the boot ROM uses a serial handshake protocol — the processor only proceeds to boot if it detects the exact pattern 1 → 0 → 1 on a dedicated status line coming from the power management unit (PMU).

Your job: design the pattern detector module that sits between the PMU and the boot controller. It watches the status line one bit per clock and tells the boot controller the moment a valid 101 handshake is seen.

One catch — the PMU sometimes sends back-to-back handshakes with overlapping bits to save time. Your detector must catch every one of them.

Constraints:

  • Input arrives one bit per clock cycle, synchronous to posedge clk

  • Output must be a registered pulse — high for exactly 1 cycle, appears the cycle after the third bit is seen

  • Overlapping matches are valid — the last 1 of one match can start the next

  • Reset is active-high asynchronous

Input stream:  0  1  0  1  1  0  1  0  1
               ↑        ↑           ↑
               start    match!      match! (overlapping)

Port

Direction

Width

Description

clk

input

1-bit

Positive-edge triggered clock

reset

input

1-bit

Active-high asynchronous reset

din

input

1-bit

Serial input bit, one per clock

match

output

1-bit

Registered pulse; high 1 cycle on 101 match

States:
  S0 (IDLE)  — no progress
  S1 (GOT1)  — seen first '1'
  S2 (GOT10) — seen '1' then '0'
  S3 (MATCH) — seen '101' → match fires, transition based on last bit

Transitions:
  S0 --1--> S1
  S0 --0--> S0
  S1 --0--> S2
  S1 --1--> S1  (new '1' resets progress to GOT1, not IDLE)
  S2 --1--> S3
  S2 --0--> S0
  S3 --1--> S1  (overlapping: last '1' starts new attempt)
  S3 --0--> S2  (overlapping: '10' starts new attempt... wait, output already fired)

Verilog

Code Editor Access

Log in to write, run and submit your solution to this interview question. It's free.

Output

Output goes here...