Assuming that A, B, C and D are the four states. When detecting the sequence "1010", in the D state, if overlapping is not allowed, we have the following state diagram: State diagram for "D" only Complete state diagram

After detecting "1011", why does the detector go back to B instead of having a self-loop to D? Wouldn't it become overlapping if we consider the "1" as the first bit of sequence "1010", because then the input sequence would be "1011010"?


1 Answer 1


After detecting "1011", why does the detector go back to B

The diagram is correct for the non-overlapping sequence. To get into state D requires the sequence 101. If the next input is 1 (resulting in the 1011 pattern), then the sequence is starting from the condition where you detected the 1st bit as 1, as if you are in the B state.

To demonstrate that the diagram is correct, you can run this Verilog simulation on EDA Playground. It shows several example input data streams, but you can change the input sequence to whatever you want.

Wouldn't it become overlapping

It would not be overlapping. An example of overlapping is:

Input : 101010
Output: 000101

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.