Medium · Finite State Machines
Design a finite-state machine that watches a serial bit stream and reports every occurrence of the pattern 1011, including overlapping occurrences.
| Port | Dir | Width | Meaning |
|---|---|---|---|
clk | input | 1 | Clock. |
rst | input | 1 | Synchronous, active-high reset. |
din | input | 1 | Serial input: one bit is sampled at every rising edge of clk where rst = 0. |
detected | output | 1 | Registered output: high for one cycle after the final 1 of 1011 is sampled. |
Let b[1], b[2], ... be the bits sampled at the rising edges since the last reset (bits are in time order; b[1] is sampled at the first edge with rst = 0). At the rising edge that samples b[n], the FSM sets
detected = (n >= 4) && b[n-3] == 1 && b[n-2] == 0 && b[n-1] == 1 && b[n] == 1and keeps that value until the next rising edge. In words: detected is 1 during the clock cycle immediately after the edge that samples the last 1 of the pattern (Moore-style timing: detected is driven by a flip-flop / depends only on the state, never combinationally on din).
1011011 contains two matches (bits 1–4 and bits 4–7), so detected pulses twice.
1011011011...).rst = 1, detected becomes 0 and all history is forgotten:bits sampled before (or at) a reset edge can never be part of a match.
Input 1 0 1 1 0 1 1 0 0 1 0 1 1 (sampled at edges 1..13, edge 0 is a reset edge):
| edge | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
din | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 |
detected after the edge | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 |
Sign up free to solve Overlapping Sequence Detector (1011) in your browser.