Digital Design / Module 6: Finite state machines
36. Non-overlapping detection
Change one transition and see the behaviour change.
Lab: your code, animated
The idea
The same pattern, with a different specification: once a match is found, its bits can't be reused. Only one transition changes, yet the behaviour differs on many streams.
The change
| From S1101 on input | Overlapping | Non-overlapping |
|---|---|---|
| 1 | S11 | S1 |
| 0 | S0 | S0 |
After a match in the non-overlapping version, the previous bits don't count. A new 1 is just the first bit of a brand-new attempt, so the machine goes to S1.
Comparing them on a stream
Take 1101101.
- Overlapping: two matches, ending at positions 4 and 7, sharing position 4.
- Non-overlapping: one match, ending at position 4. The remaining
101can't complete a pattern, which requires a leading11.
Which one do you need?
It depends on what the data means. A frame marker in a continuous stream may need non-overlapping detection, so that one marker isn't counted twice. Signal monitoring may need to catch all occurrences. Read the specification closely, since the phrase "non-overlapping" is easy to miss. In an interview, ask which one is meant before you start. That question alone shows good habits.
Try it
The lab above is set to non-overlapping. Adapt your earlier detector by changing that one line, then run it on the same stream.
Common mistake
Going to S0 regardless of the input after a match. Then the new 1 is thrown away, and a match beginning immediately after another is missed. Test 11011101: the second match starts right after the first, and it should still be found.
Key ideas
- After a match, return to the start.
- 1101101 now gives a different number of matches.
- Read the specification's wording carefully.
Your exercise
Find the bug
This code has one deliberate bug. Read the symptom, then click the line you think is wrong.
The fix
S1101: state <= din ? S1 : S0;
Why it failed
din ? S11 : S0 is the overlapping rule, as it reuses the final 1 of the match. For non-overlapping detection, the old bits no longer count, so a new 1 is only the first bit of a new attempt. It goes to S1.
Interview questions
core1101101 without overlap?
One. The 101 remaining after the first match can't complete a new pattern, since it needs a leading 11.
basicStarting from an overlapping 1101 detector, what is the minimum change to make it non-overlapping?
Only one transition changes: from S1101 on a 1, go to S1 instead of S11. In the overlapping version, the final 1 of the match is reused as the start of the next attempt. In the non-overlapping version, the bits of a finished match can't be reused, so the new 1 is just the first bit of a fresh attempt. The S1101 on 0 transition stays at S0 in both.
basicHow many matches does a 1101 detector report on 1101101101, with overlap and without?
With overlap it reports 3, ending at bits 4, 7 and 10. Without overlap it reports 2. After the first match at bit 4, the next bits 1, 0 give S1 then S0, and a fresh 1101 is found only in bits 7 to 10. Both counts were confirmed in simulation.
coreA designer made the detector non-overlapping by sending S1101 straight back to S0, whatever the input. What goes wrong, and which stream shows it?
S1101: state <= S0; // intended as non-overlapping
The 1 that arrives right after a match is thrown away, so a match that starts immediately after another is missed. On 11011101, the correct non-overlapping machine finds 2 matches, ending at bits 4 and 8. This version finds only 1, because bit 5 (a 1) is discarded and it then needs a fresh 11. The fix is S1101: state <= din ? S1 : S0.
coreWhy does the non-overlapping machine go to S1, and not S0, on a 1 straight after a match?
Non-overlapping means the bits of the previous match can't be counted again. The new 1 is not part of that match. It is a new bit, and it is a valid first bit of a new 1101. Going to S0 would treat a fresh, useful bit as garbage, so a back-to-back pattern would be missed.
coreIn a Mealy version of the 1101 detector (states S0, S1, S11, S110), where does the overlap choice show up?
The match is detected on the arrow out of S110 on a 1, so that arrow's destination carries the choice. For overlap, the final 1 can start a new attempt, so it goes to S1. For non-overlap, nothing of the match may be reused, so it goes to S0. Everything else is the same, and both versions fire one clock earlier than the matching Moore machine.
coreAn interviewer says 'design a 1101 detector'. What should you ask before drawing anything, and why does it matter?
Ask whether matches may overlap, and whether the output should be Moore (from the state, one cycle later) or Mealy (in the same cycle as the last bit). Overlap changes the count on many streams. For example, 1101101 gives 2 matches with overlap and 1 without. Asking first shows you read specifications closely, since 'non-overlapping' is an easy word to miss.
advancedThe stream 1101101101101 (13 bits) is fed to both 1101 detectors. Give both counts, and explain why the ratio between them is not fixed.
With overlap there are 4 matches, ending at bits 4, 7, 10 and 13, since each new 101 completes another match. Without overlap there are 2, ending at bits 4 and 10, because after each match the next 101 is wasted rebuilding the leading 11. The counts depend on how the stream lines up with the pattern's self-overlap, so on random data the ratio changes. Both counts were confirmed in simulation.
advancedDo overlapping and non-overlapping detectors for the pattern 1000 behave differently?
No. Overlap only matters when an ending of the pattern is also a beginning of it. For 1000, the proper endings are 0, 00 and 000, and none of them begins with 1. So no two matches can ever share bits, and from the match state both versions go to S1 on a 1 and S0 on a 0. Patterns like 1101 or 1011 have such a shared part, which is why the choice matters for them.