Sequence Detector "1011" (Mealy, Overlapping)
advanced · state_machine · 220 XP
Sign in to write your solution, run it in the simulator and submit it for grading.
Sign in or create a free account →Problem
Sequence Detector "1011" — Mealy FSM, Overlapping
Same pattern detection as 11.01, but using a **Mealy FSM** with **overlapping** matches. The output asserts **combinationally** (same cycle as the last input bit) when the pattern is complete. Crucially, after a match, the FSM does **not** reset to IDLE — it stays in a state that allows the last bit(s) of the current match to become the start of the next match.
**Example (overlapping):**
```
Input: 1 0 1 1 1 0 1 1
Output: 0 0 0 1 0 0 0 1
↑ ↑
Matches at positions 4 and 8.
Note position 4 matches 1011.
Position 8 also matches 1011 — the 1 from position 4 is reused as the 1 at position 1.
```
**Interface** (same as 11.01)
| Port | Direction | Description |
|------|-----------|----------------------------|
| `clk` | input | Clock |
| `rst` | input | Async reset |
| `x` | input | Serial bit |
| `y` | output | Detection output (Mealy) |
**State Diagram:** 3 states minimum (vs 4+ for Moore):
- `IDLE`: no progress
- `S1`: last bit was `1`
- `S10`: last 2 bits were `10`
- `S101`: last 3 bits were `101`
On input `x=1` in state `S101`, output `y=1` **combinationally** (not registered), and **stay in S1** or a state that allows overlapping.
**Key difference from Moore:** output is **combinational from state + input**, and asserts **one cycle earlier** than Moore (in the same cycle as the 4th bit, not in a dedicated state).
Constraints
- Use 3-block FSM: State Register, Next-State (Block 2), Output (Block 3, combinational Mealy).
- Output y = f(state, x) — combinational, not registered.
- After detecting pattern, FSM transitions to a state allowing pattern overlap (typically back to the state corresponding to the last 1 bit).
- y asserts for exactly 1 cycle (via combinational logic), not a dedicated state.
Examples
Input: x: 1, 0, 1, 1
Output: y asserts on 4th clock (same cycle as 4th input)
Mealy output is combinational
Input: x: 1, 0, 1, 1, 1, 0, 1, 1
Output: y pulses at cycles 4 and 8 (overlapping)
Second match reuses the 1 from first match
Common questions
- What does the Sequence Detector "1011" (Mealy, Overlapping) problem ask you to build?
- Sequence Detector "1011" — Mealy FSM, Overlapping Same pattern detection as 11.01, but using a **Mealy FSM** with **overlapping** matches. The output asserts **combinationally** (same cycle as the last input bit) when the pattern is complete.
- What constraints does Sequence Detector "1011" (Mealy, Overlapping) have?
- Use 3-block FSM: State Register, Next-State (Block 2), Output (Block 3, combinational Mealy).; Output y = f(state, x) — combinational, not registered.; After detecting pattern, FSM transitions to a state allowing pattern overlap (typically back to the state corresponding to the last 1 bit).; y asserts for exactly 1 cycle (via combinational logic), not a dedicated state.
- What is an example input and output for Sequence Detector "1011" (Mealy, Overlapping)?
- Input x: 1, 0, 1, 1 gives output y asserts on 4th clock (same cycle as 4th input). Mealy output is combinational
- Which Verilog concepts does Sequence Detector "1011" (Mealy, Overlapping) practise?
- state_machine, FSM, Mealy, sequence-detect, interview.