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.
- Cycle 3
Bits 0 to 3 are 1001. Both detectors match.
- Cycle 6
Bits 3 to 6 are 1001 too, sharing bit 3. Only the overlapping detector sees it.
- 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.
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.
- Neutral
- Step
- Control / FSM
- Structure
- Append
Add the new bit to the prefix the state stands for.
- 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 bit | Seen + bit | Longest suffix that is a prefix | Go to |
|---|---|---|---|---|
| nothing | 0 | 0 | none | A0 |
| 1 | 1 | 11 | 1 | A1 |
| 10 | 1 | 101 | 1 | A1 |
| 100 | 0 | 1000 | none | A0 |
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.
| Kind | Arc after a match of 1001 | Matches in 1001001100110010 |
|---|---|---|
| Overlap | to A1: the last 1 is a prefix | 4 |
| No overlap | to A0: start again | 3 |
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 feature | Catches |
|---|---|
| Two matches that share bits | the arc after a match goes to the start (no overlap) |
| A near miss followed by the pattern, such as 1011001 | a fallback that goes to the start |
| A match in the first bits after reset | a reset state or first cycle handled wrongly |
| A match followed by a non-match bit | an output held for two cycles, or shown a cycle late |
| Long runs of 0s and of 1s | self-loops that go to the wrong state |
Asked in interviews
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.
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.
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.
Synthesize the design to measure its cells and inspect the mapped gates.
x 1001001100110010 overlap ...^..^...^...^. 4 matches no overlap ...^......^...^. 3 matchesOriginal 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
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.