Build a Mealy finite state machine that detects the bit sequence 1011 arriving one bit per clock cycle on in. Unlike the Moore version of this detector, this one is overlapping: the trailing bits of one match can serve as the start of the next match.
Because this is a Mealy machine, the output is a function of the current state and the current input — it can change combinationally within a clock period, before the next active edge.
Interface
| Signal | Direction | Width | Description |
|---|---|---|---|
clk |
input | 1 | Clock, rising-edge triggered |
reset |
input | 1 | Synchronous reset to the initial state |
in |
input | 1 | Serial input bit, one per clock |
y |
output | 1 | Combinationally high exactly when the current (state, in) pair completes a match |
State diagram: (state, input) -> (next state, output)
| State | Meaning | in | Next state | y |
|---|---|---|---|---|
| S0 | no progress | 0 | S0 | 0 |
| S0 | no progress | 1 | S1 | 0 |
| S1 | matched “1” | 0 | S2 | 0 |
| S1 | matched “1” | 1 | S1 | 0 |
| S2 | matched “10” | 0 | S0 | 0 |
| S2 | matched “10” | 1 | S3 | 0 |
| S3 | matched “101” | 0 | S2 | 0 |
| S3 | matched “101” | 1 | S1 | 1 |
Notice the last row: on completing the match, the next state is S1 (not S0) — the trailing 1 of the just-completed 1011 is reused as the start of a potential new match, which is what makes overlapping detection possible. For example, the stream 1011011 matches at both bit 4 and bit 7, sharing bit 4 between the two matches.