Sequence Detectors

Design a detector for a bit pattern with one state per matched prefix, the right fallback on a mismatch, and overlap.

You Will Be Able To

  • Give a detector one state for each prefix of the pattern.
  • Find the fallback state on a wrong bit: the longest suffix that is still a prefix.
  • Choose overlapping or non-overlapping detection and draw the arc after a match.
  • Write test streams that catch the usual detector bugs.
Lesson
G7.4
Time
30 min
Runs on
Your browser
Check
5 questions

A frame receiver counted the start marks on a serial line. It missed one frame in every burst: the marks came back to back, and the last bit of one started the next. Here is the same detector built both ways on one stream.

Overlapping Matches of 1001One column per clock cycle, from the lab run. z is 1 in the cycle of the last bit of a match.
0123456789101112131415clkxz, overlapz, no overlapshares the 1 of cycle 3
Scroll horizontally ↔
  1. Cycle 3

    Bits 0 to 3 are 1001. Both detectors match.

  2. Cycle 6

    Bits 3 to 6 are 1001 too, sharing bit 3. Only the overlapping detector sees it.

  3. Cycle 14

    Four matches against three on the same stream.

Measured: the lab below, on Icarus Verilog 12.

One State per Matched Prefix

A detector must remember how much of the pattern it has seen. That is a prefix: nothing, 1, 10, 100. Each prefix is one state. A pattern of n bits needs n states in a Mealy detector and n + 1 in a Moore one.

A 1001 Detector You Can Edit
A 1001 Detector You Can Edit0/01/00/01/00/01/00/01/1A0nothingA1saw 1A10saw 10A100saw 100
  1. nothing · A0
    • ↓0 → A0 / 0
    • ↓1 → A1 / 0
  2. saw 1 · A1
    • ↓0 → A10 / 0
    • ↓1 → A1 / 0
  3. saw 10 · A10
    • ↓0 → A100 / 0
    • ↓1 → A1 / 0
  4. saw 100 · A100
    • ↓0 → A0 / 0
    • ↓1 → A1 / 1
StateInputNextOutput
A00A00
A01A10
A10A100
A11A10
A100A1000
A101A10
A1000A00
A1001A11

Current state: A1 · Output: 1

Sampled input, state and output waveformStepState0A01A12A103A1004A15A106A1007A1x—1001001z—0001001
Scroll horizontally ↔
Sampled waveform: Moore output after each edge; Mealy output on the taken arc.
Step01234567
Input—1001001
StateA0A1A10A100A1A10A100A1
Output—0001001

  1. Step 4. 1001 is complete: the arc A100 to A1 carries z = 1. The last 1 already counts as "saw 1".
  2. Step 7. The second match reuses that 1. Redirect the arc A100 on 1 to A0 and step again: only one match.

Each state is a prefix of 1001. Every state has an arc for 0 and for 1; the fallback arcs are the ones that do not move forward.

Where to Go on a Wrong Bit

On a wrong bit, the machine takes what it has seen plus that bit. It keeps the longest ending of that string that is still a start of the pattern.

Finding the Next State on Any BitArrows show the steps of the rule. It works for every bit, right or wrong.
  • Neutral
  • Step
  • Control / FSM
  • Structure
Finding the next state on any bitArrows show the steps of the rule. It works for every bit, right or wrong. neutral Bits seen the state: a prefix,such as 10 step Append the newbit 10 then 1 gives 101 step Longest suffixthat is a prefix 01 is not a prefix; 1is control Next state saw 1
  1. neutral Bits seenthe state: a prefix, such as 10
    • Append the new bit
  2. step Append the new bit10 then 1 gives 101
    • Longest suffix that is a prefix
  3. step Longest suffix that is a prefix01 is not a prefix; 1 is
    • Next state
  4. control Next statesaw 1
  1. Append

    Add the new bit to the prefix the state stands for.

  2. Cut

    Drop bits from the front until what is left starts the pattern.

Read the diagram as text
  • Bits seen: the state: a prefix, such as 10
  • Append the new bit: 10 then 1 gives 101
  • Longest suffix that is a prefix: 01 is not a prefix; 1 is
  • Next state: saw 1
  • Bits seen → Append the new bit
  • Append the new bit → Longest suffix that is a prefix
  • Longest suffix that is a prefix → Next state

A right bit keeps the whole string, so the machine moves forward. A wrong bit keeps less.

State (seen)Wrong bitSeen + bitLongest suffix that is a prefixGo to
nothing00noneA0
11111A1
1011011A1
10001000noneA0

The fallback arcs of the 1001 detector. The predict check below computes the same lengths by brute force.

Overlap or No Overlap

After a match there are two choices. With overlap, the end of one match may begin the next. Without it, the detector starts fresh after every match.

KindArc after a match of 1001Matches in 1001001100110010
Overlapto A1: the last 1 is a prefix4
No overlapto A0: start again3

Measured: the lab below. The spec must say which one it wants.

Streams That Catch Detector Bugs

A detector bug hides on an arc that a clean stream never takes. Good test streams aim at the arcs.

Stream featureCatches
Two matches that share bitsthe arc after a match goes to the start (no overlap)
A near miss followed by the pattern, such as 1011001a fallback that goes to the start
A match in the first bits after reseta reset state or first cycle handled wrongly
A match followed by a non-match bitan output held for two cycles, or shown a cycle late
Long runs of 0s and of 1sself-loops that go to the wrong state
Asked in interviews
  1. Design a detector for 1011 with overlap.

    States for nothing, 1, 10 and 101. On a wrong bit, go to the longest suffix that is a prefix. In a Mealy machine, the arc 101 on 1 outputs 1 and goes to "1". The final 1 starts a new match.

  2. What is the difference between overlapping and non-overlapping detection?

    With overlap, bits at the end of one match can start the next one. Without overlap, the detector returns to the start after each match. They differ only in the arc taken after a match.

  3. How would you test a sequence detector?

    Back-to-back and overlapping matches, and near misses that use each fallback arc. Add a match right after reset, and random streams checked against a model.

Try It

The bench runs two copies on one stream: OVERLAP = 1 and OVERLAP = 0. ^ marks a cycle with z = 1.

The match in cycle 6 reuses the 1 of cycle 3. Only the overlapping copy reports it.

Change the A1 arc on 1 to s_next = A0 and run: 2 matches with overlap, 1 without. The matches in cycles 10 and 14 start with the second 1 of an 11, and are lost.

RTLIcarus Verilog · in your browser · Lint: Verilator service · Synthesize: Yosys service
Edit the design, then Run, Lint or Synthesize
Expected: x 1001001100110010 overlap ...^..^...^...^. 4 matches no overlap ...^......^...^. 3 matches

Original design · 8 cells · 3 flip-flops · 0 latches · 2 logic levels. Synthesis uses Yosys; counts depend on the toolchain.

Read included file: tb.sv
// tb.sv: the bench (read-only). Two copies, with and without overlap, on one stream.
module tb;
  logic clk = 0, rst = 1, x = 0;
  logic z_ov, z_no;
  det1001 #(.OVERLAP(1)) ov (.clk(clk), .rst(rst), .x(x), .z(z_ov));
  det1001 #(.OVERLAP(0)) no (.clk(clk), .rst(rst), .x(x), .z(z_no));
  string stream = "1001001100110010";
  string line_ov = "", line_no = "";
  int n_ov = 0, n_no = 0;
  initial begin
    #1 clk = 1; #1 clk = 0; rst = 0;
    for (int i = 0; i < stream.len(); i++) begin
      x = (stream[i] == "1");
      #1 line_ov = {line_ov, z_ov ? "^" : "."}; line_no = {line_no, z_no ? "^" : "."};
      n_ov += z_ov; n_no += z_no;
      #1 clk = 1; #1 clk = 0;
    end
    $display("x          %s", stream);
    $display("overlap    %s  %0d matches", line_ov, n_ov);
    $display("no overlap %s  %0d matches", line_no, n_no);
  end
endmodule

Check Yourself

ConceptA 1001 detector is in state "100" and sees a 0. Where should it go?
ConceptWhich stream is the weakest test for a 1001 detector?
Predict the outputThe lab's overlapping 1001 detector runs on 100110011001 after reset. The program prints the number of matches. Predict the exact line.
module tb;
  typedef enum logic [1:0] {A0, A1, A10, A100} state_t;
  state_t s = A0;
  string x = "100110011001";
  int n = 0;
  initial begin
    for (int i = 0; i < x.len(); i++)
      case (s)
        A0:   if (x[i] == "1") s = A1; else s = A0;
        A1:   if (x[i] == "1") s = A1; else s = A10;
        A10:  if (x[i] == "1") s = A1; else s = A100;
        A100: if (x[i] == "1") begin n++; s = A1; end else s = A0;
      endcase
    $display("%0d", n);
  end
endmodule
ConceptIn the 1001 detector, which arc differs between the overlapping and the non-overlapping versions?
ConceptWhy does a 1001 detector in state "1" stay there on another 1?

Common Mistakes

Wrong Send every wrong bit back to the start state.

The bits just seen may already begin a new match. From "10" a 1 gives "101", whose last 1 is the start of 1001.

Fix Fall back to the longest suffix of what was seen that is also a prefix of the pattern.

Wrong Forget the arc out of the last state after a match.

With overlap, the end of one match can start the next. Going to the start state lost a match in the lab.

Fix After a match, go to the state of the longest proper suffix of the pattern that is a prefix (for 1001, "1").

Wrong Test a detector with one clean copy of the pattern.

One clean copy never reaches a fallback arc or the arc after a match. Most bugs live there.

Fix Use back-to-back and overlapping matches, near misses, and a match that starts right after reset.

Wrong Make the output a register by habit when the match is needed in the same cycle.

A registered z, or a Moore match state, shows the match one cycle after its last bit.

Fix Decide the timing first: a Mealy z in the same cycle, or a Moore z one cycle later.

Remember

  • A detector has one state per matched prefix: n states for an n-bit pattern, Mealy style.
  • A wrong bit leads to the longest suffix of the bits seen that is still a prefix.
  • Overlap and no overlap differ only in the arc taken after a match.
  • Test with overlapping matches, near misses, a match right after reset and random streams.

Practice

Report a problem with this page