Non-overlapping detection

Also called: non-overlapping, non-overlapping sequence detection, non-overlapping detector

A sequence detector mode in which the bits of a match are used up, so the search starts afresh after each match; 1111 then contains two matches of 11.

In non-overlapping detection, once a sequence detector finds its pattern, those bits are consumed. The next match has to be built entirely from new bits.

Count 11 in 1, 1, 1, 1 by scanning left to right: bits 1–2 match, so skip past them; bits 3–4 match. Two matches, not three.

In the machine, only the arrow at a match changes compared with the overlapping version:

Mealy: the arrow that completes the match (with output 1) goes back to the no-progress state.
Moore: the arrows leaving the match state go where they would from the no-progress state.

Every other arrow keeps its suffix rule target. Some patterns, like 110, give the same machine either way, because no ending of the pattern starts a new match.

Non-overlapping detection suits framed data, where a pattern marks the start of a block and the bits after it belong to the block.

Worked example

Example

Non-overlapping 010

The diagram is the non-overlapping Mealy 010 detector. It matches the overlapping one except that C on 0 now goes to A. Apply 0, 1, 0, 1, 0.

1.
0: A → B, 0. 1: B → C, 0.
2.
0: C → A, 1. The bits are used up.
3.
1: A → A, 0. The 1 can't start 010.
4.
0: A → B, 0.
5.
Outputs 0, 0, 1, 0, 0: one match, where the overlapping version found two.

Common mistakes

Changing every arrow back to the start. Only the match arrow (Mealy), or the arrows out of the match state (Moore), change.
Counting matches with a sliding window. For non-overlapping, skip past each match before looking for the next.

Practice Non-overlapping detection

Interactive questions with instant feedback and a worked solution for every wrong answer.

Finite State Machines lesson full course

And 3 more in the Finite State Machines lesson.

Practice exams

Learn it step by step

Non-overlapping detection is taught in Finite State Machines.

Finite State Machines →

All terms