BitFlow

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.