Chapter 29 of 32

Sequence Detector Design

A sequence detector watches a stream of bits arriving one per clock and raises its output whenever a particular pattern, such as 101 or 1011, has just appeared. It is the most popular FSM question in university exams, GATE and hardware interviews, because it tests everything from the chapter Finite State Machines: Mealy & Moore: building a state diagram from words, Mealy vs Moore, state assignment, flip-flop equations and checking unused states.

Real uses are everywhere: finding the start-of-frame pattern in a serial link, spotting a preamble in a radio packet, recognising a key combination, or decoding a remote-control code. In this chapter we develop a reliable method for drawing the state diagram (the part where most students go wrong), then design complete circuits for 101 and 1011 and verify one with simulation.


The Problem and Two Important Choices

Sequence detector: a synchronous FSM with one serial input x and one output z, where z = 1 exactly when the most recent input bits match a given pattern.

Before drawing anything, every sequence-detector question fixes two choices. Read the question carefully for both:

  1. Mealy or Moore? Mealy: z = 1 during the same clock cycle the last bit of the pattern is present. Moore: z = 1 during the cycle after the last bit has been clocked in, from a special "pattern found" state.

  2. Overlapping or non-overlapping?

Overlapping detection: the last bits of one detected pattern may be reused as the first bits of the next. Non-overlapping detection: after a detection, the detector starts again from scratch, so bits of a found pattern are never reused.

Example with pattern 101 and input 0 1 0 1 0 1 1 0 1:

bit position :  1 2 3 4 5 6 7 8 9
input x      :  0 1 0 1 0 1 1 0 1
overlapping  :  0 0 0 1 0 1 0 0 1     (101 found ending at 4, 6 and 9;
                                       the 1 at position 4 is shared)
non-overlap  :  0 0 0 1 0 0 0 0 1     (after position 4 the detector restarts,
                                       so 0 1 at 5-6 is not enough)

(These rows show Mealy outputs, aligned with the bit that completes the pattern.)


The Method: States Remember "How Much Matches So Far"

The trick that makes sequence detectors easy is to name each state after the longest part of the pattern matched so far. For the pattern 101:

  • S0: nothing useful matched (the reset state).

  • S1: we have seen "1".

  • S2: we have seen "10".

  • (Moore only) S3: we have seen "101", output 1.

For each state and each input, ask one question:

Failure rule: after appending the new bit to what this state has matched, what is the longest suffix of that string which is also a prefix of the pattern? Go to the state for that prefix.

The "success" transitions (the next bit of the pattern) are obvious: each extends the match by one. The failure transitions are where people make mistakes, usually by jumping back to S0 too eagerly. Some examples for 101:

  • In S1 ("1") we receive 1: string "11". Longest suffix that is a prefix of 101: "1". Stay in S1, not S0.

  • In S2 ("10") we receive 0: string "100". Suffixes "00", "0" are not prefixes of 101 (which starts with 1). Go to S0.

  • In S2 ("10") we receive 1: string "101", the full pattern. Output 1. For overlapping, the suffix "1" is a prefix, so go to S1. For non-overlapping, go to S0.

Number of states for an n-bit pattern: a Mealy detector needs n states (matched 0 to n−1 bits), a Moore detector needs n + 1 (one extra state that holds the output 1). This is a common one-mark question.


Design 1: "101" Mealy, Overlapping

State Diagram and Table

        0/0             1/0
       ┌───┐           ┌───┐
       │   ▼   1/0     │   ▼    0/0
      +------+ ──────► +------+ ──────► +------+
      |  S0  |         |  S1  |         |  S2  |
      | none |         | "1"  | ◄────── | "10" |
      +------+         +------+   1/1   +------+
         ▲                                 │
         └────────────── 0/0 ──────────────┘
   label = input x / output z
Present statex = 0: next, zx = 1: next, z
S0 (none)S0, 0S1, 0
S1 ("1")S2, 0S1, 0
S2 ("10")S0, 0S1, 1

State Assignment and Equations (D Flip-Flops)

Three states need 2 flip-flops Q1Q0. Assign S0 = 00, S1 = 01, S2 = 10; code 11 is unused (don't-care). With D flip-flops, D = next-state bit:

Q1 Q0xD1 D0 (next)z
000000
001010
010100
011010
100000
101011
11xxxx

K-map for D1 (rows Q1, columns Q0x):

D1         Q0 x
           00   01   11   10
Q1   0  [   0    0    0    1  ]
     1  [   0    0    x    x  ]
                          └──┘ group the 1 at 010 with the x at 110
D1 = Q0·x̅

The full result (all three checked by computer minimisation with the don't-cares):

D1 = Q0 · x̅ ; D0 = x ; z = Q1 · x

D0 = x makes sense: the machine is in S1 (Q0 = 1) exactly when the last bit was 1. D1 = Q0·x̅ means "we were at '1' and got a 0", which is S2. And z = Q1·x is "we were at '10' and got a 1".

  x ──────────────────────────────► D0 ──► [FF0] ──► Q0
  x ──►[NOT]──► x̅ ──┐
                Q0 ──┴──►[AND]─────► D1 ──► [FF1] ──► Q1
                Q1 ──┐
  x ─────────────────┴──►[AND]───────────────────────► z

  (both flip-flops share one clock; reset gives Q1Q0 = 00)

Unused code 11. From 11: x = 0 gives 10 (S2) and x = 1 gives 01 (S1), so the machine recovers in one clock. But z = Q1·x = 1 in state 11 when x = 1, a possible false detection right after a glitch. If that matters, use z = Q1·Q̅0·x (one extra input) or simply rely on a proper reset.

Non-Overlapping Version

Only one transition changes: S2 with x = 1 goes to S0 instead of S1 (output still 1). The new equations:

D1 = Q0 · x̅ ; D0 = x · Q̅1 ; z = Q1 · x

The extra Q̅1 stops S2 from moving to S1 after a detection.


Design 2: "101" Moore, Overlapping

Moore needs a fourth state S3 = "101 found" whose output is 1. Its outgoing transitions use the failure rule on "101" + new bit:

  • S3 with x = 0: "1010", longest suffix that is a prefix of 101 is "10", so go to S2.

  • S3 with x = 1: "1011", longest such suffix is "1", so go to S1.

         0                 1
        ┌───┐             ┌───┐
        │   ▼             │   ▼
      +------+─── 1 ──► +------+─── 0 ──► +------+─── 1 ──► +------+
      | S0/0 |          | S1/0 |          | S2/0 |          | S3/1 |
      +------+          +------+          +------+          +------+
         ▲                 ▲                 │  ▲             │  │
         └─────── 0 ───────┼─────────────────┘  └───── 0 ─────┘  │
                           └───────────────── 1 ─────────────────┘

   state/output inside each box; arrow label = input x
PresentNext (x = 0)Next (x = 1)z
S0S0S10
S1S2S10
S2S0S30
S3S2S11

With S0 = 00, S1 = 01, S2 = 10, S3 = 11 (all codes used, no don't-cares):

D1 = Q0 · x̅ + Q1 · Q̅0 · x ; D0 = x ; z = Q1 · Q0

Compare with the Mealy design: one more state but the same number of flip-flops (2), and the output z = Q1Q0 now depends on the state only, so it is glitch-free and appears one clock later.


Design 3: "1011" Moore, Overlapping, with Simulation

A 4-bit pattern needs 5 Moore states: S0 (none), S1 ("1"), S2 ("10"), S3 ("101"), S4 ("1011", z = 1). Apply the failure rule to every state:

Present (matched)x = 0: string → nextx = 1: string → nextz
S0 ( )"0" → S0"1" → S10
S1 ("1")"10" → S2"11" → S10
S2 ("10")"100" → S0"101" → S30
S3 ("101")"1010" → S2"1011" → S40
S4 ("1011")"10110" → S2"10111" → S11

Look closely at S3 with x = 0: "1010" ends in "10", which is the start of 1011, so we go to S2, not S0. And S4 with x = 0: "10110" also ends in "10". These two transitions are where hand-drawn diagrams most often go wrong.

Five states need 3 flip-flops. Assign S0 to S4 the binary codes 000 to 100; codes 101, 110 and 111 are don't-cares. Minimising each D input over Q2Q1Q0x gives:

D2 = Q1·Q0·x
D1 = Q0·x̅ + Q2·x̅ + Q1·Q̅0·x
D0 = x·Q̅0 + x·Q̅1
z  = Q2

Check one entry by hand: S3 = 011 with x = 1 should go to S4 = 100. D2 = 1·1·1 = 1; D1 = 1·0 + 0·0 + 1·0·1 = 0; D0 = 1·0 + 1·0 = 0. Next = 100. Correct.

Verilog Implementation and Self-Check

The design below uses exactly these equations. The testbench runs a fixed stream so we can read the result, then 100 000 random bits, comparing the detector with a simple reference: a 4-bit shift register of the last inputs, compared with 1011.

// Moore detector for 1011 (overlapping), built from the derived equations
// states: S0=000 S1=001 S2=010 S3=011 S4=100 (S4 means "1011 seen")
module det1011 (input logic clk, rst, x, output logic z);
  logic [2:0] q, d;
  assign d[2] = q[1] & q[0] & x;
  assign d[1] = (q[0] & ~x) | (q[2] & ~x) | (q[1] & ~q[0] & x);
  assign d[0] = (x & ~q[0]) | (x & ~q[1]);
  assign z    = q[2];                       // Moore output: state bits only
  always_ff @(posedge clk)
    if (rst) q <= 3'b000; else q <= d;
endmodule

module tb;
  logic clk = 0, rst = 1, x = 0, z;
  logic [3:0] hist;                         // reference: last 4 input bits
  det1011 dut (.clk(clk), .rst(rst), .x(x), .z(z));
  always #5 clk = ~clk;
  always_ff @(posedge clk) if (rst) hist <= 0; else hist <= {hist[2:0], x};
  string in_s = "", out_s = "";
  int errors = 0;
  logic [0:19] stream = 20'b1011011101011010_1011;
  initial begin
    @(negedge clk) rst = 0;
    for (int i = 0; i < 20; i++) begin
      x = stream[i];
      @(negedge clk);                       // one clock later: output for bits so far
      in_s  = {in_s,  x ? "1" : "0"};
      out_s = {out_s, z ? "1" : "0"};
    end
    $display("input : %s", in_s);
    $display("z     : %s", out_s);
    for (int i = 0; i < 100000; i++) begin  // random test against the reference
      x = $urandom_range(0, 1);
      @(negedge clk);
      if (z !== (hist == 4'b1011)) errors++;
    end
    $display("random test: 100000 bits, errors = %0d", errors);
    $finish;
  end
endmodule

Output (Icarus Verilog, iverilog -g2012 det1011.sv && vvp a.out). Each z character is the Moore output during the clock period right after the bit above it was clocked in:

input : 10110111010110101011
z     : 00010010000010000001
random test: 100000 bits, errors = 0

The pattern is found at positions 4, 7, 13 and 20 (counting from 1). The detection at 7 reuses the final 1 of the first 1011 ("1011" + "011"), which is the overlap at work. The random test confirms the equations are right for every situation, not just our hand-picked stream.

Unused codes. From 101, 110 and 111 the machine reaches a legal state in one clock (for example 111 with x = 0 goes to 010). One catch: 111 with x = 1 goes to 100 (S4) and z = Q2 is also 1 in the unused codes, so a glitch into an unused state could produce a false detection. A reset at power-up avoids this; a stricter design would decode z = Q2·Q̅1·Q̅0.

A Neat Observation

The Mealy detector for 1011 (4 states, S0 to S3, same codes) has next-state equations D1 = Q0·x̅ + Q1·Q̅0·x, D0 = x, exactly the same as the Moore detector for 101, plus the output z = Q1·Q0·x. That is no accident: the Moore "101" machine's state S3 behaves like "101 has been seen", which is the Mealy "1011" machine's state S3. Here the Mealy detector's states and transitions coincide with those of the Moore detector for the pattern minus its last bit; only the output is computed differently.


A Shortcut: Shift-Register Detectors

Another way to detect an n-bit pattern is to keep the last bits in a shift register (from Registers & Shift Registers) and compare them with the pattern using an AND gate (with inverters on the 0 positions). It needs more flip-flops (n−1 for Mealy, n for Moore) but no state design at all, and it naturally does overlapping detection. The testbench's reference model above is exactly this circuit. FSM designs win when flip-flops are expensive or when the pattern is long; shift-register designs win on simplicity.

ApproachFlip-flops for an n-bit patternOverlapDesign effort
Mealy FSM⌈log2 n⌉Either (by design)State diagram + K-maps
Moore FSM⌈log2(n + 1)⌉Either (by design)State diagram + K-maps
Shift register + ANDn − 1 (Mealy style) or n (Moore style)Overlapping only (non-overlap needs extra logic)Almost none

Common Mistakes

  • Returning to S0 on every mismatch. Always apply the longest-suffix-that-is-a-prefix rule. For 1011, "11" goes to S1 and "1010" goes to S2.

  • Wrong overlap handling. Overlapping: after a detection, continue from the longest reusable suffix. Non-overlapping: restart from S0 (for Mealy) or leave the detect state as if nothing was seen (for Moore).

  • Wrong number of states. n-bit pattern: Mealy n, Moore n + 1 (before any state reduction; for most patterns these are already minimal).

  • Putting the Moore output on an arrow or the Mealy output in a circle.

  • Forgetting unused codes. With 3 or 5 states some codes are unused; check where they go and whether they can raise z falsely.

  • Misaligned timing. The Moore output appears one clock after the Mealy output for the same input stream.


GATE and Interview Questions

Q1. How many states are needed in a Moore machine and in a Mealy machine to detect the sequence 11011?

Pattern length 5: Mealy 5 states, Moore 6 states. Flip-flops: ⌈log2 5⌉ = 3 and ⌈log2 6⌉ = 3.

Q2. In an overlapping detector for 1101, the machine is in the state "110" and receives 0. Which state does it go to?

String "1100". Suffixes: "100", "00", "0". None is a prefix of 1101 (which starts with 1), so go to S0 (nothing matched).

Q3. Same detector (1101, overlapping, Mealy). In state "110" it receives 1 and outputs 1. Which state next?

String "1101". The longest proper suffix that is a prefix of 1101 is "1" ("01" and "101" are not prefixes). Go to S1 ("1").

Q4. Input 1 1 0 1 1 0 1 1 is applied to an overlapping Mealy detector for 1101. Where are the 1s in the output?

1101 ends at bit 4 (bits 1-4 = 1101) and at bit 7 (bits 4-7 = 1101, reusing bit 4). Output: 0 0 0 1 0 0 1 0. A non-overlapping detector would give 0 0 0 1 0 0 0 0, because after bit 4 it restarts and bits 5-8 (1 0 1 1) do not complete a new 1101.

Q5. A Mealy 101 detector uses D1 = Q0·x̅, D0 = x, z = Q1·x. What must change to make it non-overlapping?

Only the transition from S2 on x = 1 changes, from S1 to S0, which gives D0 = x·Q̅1. D1 and z stay the same.

Q6. Why might an interviewer prefer a Moore detector in a real chip even though it uses more states?

Its output comes straight from flip-flops, so it is glitch-free and has a full clock period of timing slack for whatever logic uses it. A Mealy output depends combinationally on the input, so input glitches and input timing pass straight to the next block.


Summary

  • A sequence detector raises z when the latest input bits match a pattern. First decide Mealy/Moore and overlapping/non-overlapping.

  • Name states by how much of the pattern is matched. On a mismatch, go to the state for the longest suffix that is also a prefix.

  • n-bit pattern: Mealy n states, Moore n + 1 states.

  • 101 Mealy overlapping: D1 = Q0x̅, D0 = x, z = Q1x. Non-overlapping: D0 = xQ̅1.

  • 101 Moore overlapping: D1 = Q0x̅ + Q1Q̅0x, D0 = x, z = Q1Q0.

  • 1011 Moore overlapping (3 flip-flops) verified by simulation with 100 000 random bits.

  • Shift register + AND is a simple alternative that uses more flip-flops.

  • Next, Memory & Programmable Logic Devices (ROM, PLA, PAL) shows how such logic is stored and programmed in real chips.