VLSI DV Interview Puzzles · All levels

Overlapping 1011 Sequence Detector

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?

Puzzle

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?

Code

systemverilog

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).

Hint

Each state should encode longest matched suffix that is also a prefix.

Step-by-step solution

diagram

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

Answer: Four states are sufficient and minimal: S0, S1, S10, S101.

Why candidates get it wrong

Resetting to S0 after a hit loses overlapping detections.

Interviewer follow-up

How does a Moore version change state count and output timing?

Navigate