Difficulty: Medium · Puzzle 4 of 6 · Topic: Digital Logic Puzzles
Design a Mealy FSM that asserts hit for one cycle whenever input stream contains pattern 1011, with overlap allowed (e.g., 1011011 gives two hits). How many states are needed and why?
typedef enum logic [1:0] {S0, S1, S10, S101} state_t;
// S0: none matched, S1: saw 1, S10: saw 10, S101: saw 101
// state | in=0 -> next | in=1 -> next, hit
// S0 | S0 | S1
// S1 | S10 | S1
// S10 | S0 | S101
// S101 | S10 | S1, hit=1 (Mealy output on the transition)Each state should encode longest matched suffix that is also a prefix.
1) Track the longest suffix of the input that is also a prefix of 1011: empty, '1', '10', '101' => 4 states.
2) Transition table is in the code block. Check the two non-obvious entries: S101 on input 0 gives '1010', whose longest useful suffix is '10', so the next state is S10 (not S0); S10 on input 0 gives '100', no useful suffix, so S0.
3) In S101, input 1 completes 1011, so hit=1, and the trailing '1' is still a prefix, so the next state is S1 (overlap) rather than S0.
4) Trace 1011011: S0 -1-> S1 -0-> S10 -1-> S101 -1-> S1 (hit) -0-> S10 -1-> S101 -1-> S1 (hit). hit = 0001001, i.e. at the 4th and 7th bit.
5) Minimality: the four states are pairwise distinguishable by a short suffix. S0 vs S1: '011' (S1 hits, S0 does not). S0 vs S10 and S1 vs S10: '11'. S101 vs any other state: '1'. Different outputs for the same suffix means the states cannot be merged, so 4 is the minimum for a Mealy detector.Answer: Four states are sufficient and minimal: S0, S1, S10, S101.
Checked by running a model of the rule in a Python model. A computational check: the shown Mealy table matches an overlapping 1011 reference on all 32766 streams up to 14 bits, 3 states cannot do it, and a Moore version needs 5 states (4 is impossible).
Two common mistakes: resetting to S0 after a hit (loses the overlapping second hit in 1011011), and sending S101 on input 0 to S0 instead of S10 (the stream 101011 then misses its hit on the trailing 1011).
How does a Moore version change state count and output timing? Model answer: a Moore detector needs 5 states (add S1011 whose output is hit). The output depends only on the state, so hit appears one clock after the final 1 was sampled; from S1011, 1 goes to S1 and 0 goes to S10 to keep overlaps.
I track the longest suffix of the input that is also a prefix of 1011, so I need four states: empty, one, one-zero, and one-zero-one. In the one-zero-one state, an input of 1 completes the pattern, so the output goes high, and the trailing 1 is still a prefix, so I go to the one state instead of resetting; that gives overlap. In the same state, an input of 0 goes to one-zero, not to the start. Four states is the minimum, because those states are pairwise distinguishable by a short suffix. The trap is resetting to the start after a hit, which misses the second hit in 1011011.