Difficulty: Hard · 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
// From S101 on input 1 -> hit=1 and next state S1 (overlap).Each state should encode longest matched suffix that is also a prefix.
1) Track matched prefix lengths of target 1011.
2) Need states for suffixes: empty, '1', '10', '101' => 4 states.
3) In S101, input 1 completes 1011 so hit=1.
4) After detection, suffix '1' remains relevant for overlap, so next state is S1, not S0.
5) This yields minimal Mealy implementation with 4 states.Answer: Four states are sufficient and minimal: S0, S1, S10, S101.
Resetting to S0 after a hit loses overlapping detections.
How does a Moore version change state count and output timing?