Sequence Detector — "101"



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 → 1on 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
101handshake 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 clkOutput 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
1of one match can start the nextReset is active-high asynchronous
Input stream: 0 1 0 1 1 0 1 0 1
↑ ↑ ↑
start match! match! (overlapping)Port | Direction | Width | Description |
|---|---|---|---|
| input | 1-bit | Positive-edge triggered clock |
| input | 1-bit | Active-high asynchronous reset |
| input | 1-bit | Serial input bit, one per clock |
| 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.
