Overlapping Sequence Detector (1011)

Hard

Problem Statement

Design a Moore finite-state machine that scans a serial bit stream, one bit per clock cycle, and detects every occurrence of the pattern `1011`, **including overlapping occurrences**. Ports: - `clk` — input, 1 bit, clock - `rst` — input, 1 bit, synchronous active-high reset - `bit_in` — input, 1 bit, serial data sampled on every rising edge of `clk` - `match` — output, 1 bit, asserted when the most recently sampled 4 bits form `1011` Behavior: On every rising edge of `clk`, if `rst` is high, the FSM synchronously resets to its initial state (no bits matched yet) and `match` must read 0, regardless of `bit_in`. Reset always takes priority over the current state. Otherwise, the FSM consumes `bit_in` and advances through 5 states tracking progress toward the pattern `1011`: - `S_A` (no progress): on `0` stay in `S_A`; on `1` go to `S_B`. - `S_B` (matched `"1"`): on `0` go to `S_C`; on `1` stay in `S_B`. - `S_C` (matched `"10"`): on `0` go to `S_A`; on `1` go to `S_D`. - `S_D` (matched `"101"`): on `0` go to `S_C`; on `1` go to `S_E`. - `S_E` (matched `"1011"` — full match): on `0` go to `S_C`; on `1` go to `S_B`. `match` is a **combinational (Moore) function of the current state**: `match = 1` if and only if the state is `S_E`, and `0` otherwise. Crucially, `match` must reflect the state immediately — do **not** add an extra register stage that delays `match` by one more cycle relative to the state. Because `S_E`'s own transitions (`0`→`S_C`, `1`→`S_B`) mirror partial progress rather than resetting to `S_A`, the detector correctly fires again on overlapping occurrences such as the bit stream `1011011`, which contains two overlapping matches of `1011` (at positions 1–4 and 4–7).

Verilog