Sequence Detector Design

Sequence detectors appear in every serial communication receiver — UART start-bit detection, SPI chip-select logic, and I2C address matching all identify a specific bit pattern in a stream. A sequence detector is a finite state machine that asserts its output exactly when the last n bits match a target pattern.

Core Concept

A sequence detector tracks how many leading bits of the target pattern have been received so far. Each state represents a prefix of the target sequence that has been matched. The number of states equals the pattern length plus one (Moore) or the pattern length (Mealy).

The key design decision is whether the detector is overlapping or non-overlapping. An overlapping detector checks whether the tail of one match can serve as the head of the next. For pattern 1011, if the input stream is ...10111011..., an overlapping detector finds two matches closer together. The state to return to after detection differs between the two modes.

The Knuth-Morris-Pratt (KMP) failure function from string-matching algorithms directly gives the return state for overlapping detectors. For any mismatch at position i, the failure function tells you the longest proper prefix of the pattern that is also a suffix of what was received — that prefix length is the state you return to.

Boolean Expression

For a 4-bit pattern using a Moore machine you need 5 states (S0–S4), 3 flip-flops. With assignment S0=000, S1=001, S2=010, S3=011, S4=100, the output is simply Z = Q2·Q1''·Q0'' (state S4 = 100). The next-state equations are derived from the transition table and minimised with K-maps. The D flip-flop inputs D2, D1, D0 are the minimised next-state expressions.

Design overlapping Moore sequence detector for pattern 1011

KMP failure function for 1011:
  Position: 1  0  1  1
  Failure:  0  0  1  2  → on mismatch after seeing prefix of length k, go to state f(k)

State transition table:
State  Meaning        X=0  X=1
S0     start/reset    S0   S1
S1     got ''1''        S2   S1
S2     got ''10''       S0   S3
S3     got ''101''      S2   S4
S4     got ''1011'' Z=1 S2   S1  (overlap: ''1'' at end can start new match)

Assign: S0=000, S1=001, S2=010, S3=011, S4=100
Z = Q2 (bit 2 is 1 only in state S4=100)

D2 next-state K-map (Q2 next = 1 only when going to S4):
  Goes to S4 when: PS=S3(011), X=1 → D2=1 only there
  D2 = Q1·Q0·X  (PS=011 is Q2=0,Q1=1,Q0=1 → simplifies to Q1·Q0·X)

D1 next-state K-map:
  NS=010: PS=S1,X=0 → Q2=0,Q1=0,Q0=1,X=0; PS=S3,X=0 → Q2=0,Q1=1,Q0=1,X=0; PS=S4,X=0 → Q2=1,Q1=0,Q0=0,X=0
  D1 = Q0·X'' + Q2·X'' (covers S1→S2, S3→S2, S4→S2 transitions)

D0 next-state K-map:
  NS=001: PS=S0,X=1; PS=S1,X=1; PS=S4,X=1
  D0 = Q2''·Q1''·X + Q2·X = X·(Q2''·Q1'' + Q2) = X·(Q1''+Q2)

Final Answer:
  D2 = Q1·Q0·X
  D1 = Q0·X'' + Q2·X''
  D0 = X·(Q1''+Q2)
  Z  = Q2
  Implement with 74HC175 (quad D-FF) + 74HC08/00/04 gates.

Exam Tip: The most common GATE trap in sequence detector design is getting the return state wrong after detection. For overlapping: use the KMP failure function — the return state is the length of the longest prefix that is also a suffix of the pattern. For 1011, the tail ''1'' matches the head ''1'', so after detection you go to S1 (''got 1''), not S0. For non-overlapping, always return to S0 after detection. Mix these up and your entire state table is wrong.

Key Properties

• Moore detector: pattern length + 1 states; Mealy detector: pattern length states
• Each state represents the longest matched prefix of the target pattern
• Overlapping vs non-overlapping: differs in return state after Z=1 asserted
• KMP failure function gives the correct return state for overlapping detection
• Output Z=1 for exactly one clock cycle per detection (Moore: in detection state)
• ICs: 74HC175 (4-bit state register, 14 ns tpd) with 74HC00/08/86 combinational gates
• FPGA: one-hot assignment preferred; synthesis tool handles equations automatically

Quick Revision

• Sequence detector: FSM that outputs 1 when last n inputs match the target pattern
• State count: n+1 for Moore, n for Mealy (n = pattern length)
• Each state = number of correct prefix bits matched so far
• Overlapping: use KMP failure to find return state after match
• Non-overlapping: always return to S0 after match
• For pattern 1011 overlapping: after detection, next state is S1 (not S0) because tail ''1'' restarts match
• Output equation for Moore: Z = AND of state bits corresponding to detection state
• Exam trap: returning to S0 after overlapping detection instead of the KMP-specified state — this misses valid overlapping matches in the input stream.