Before I explain your question, you first know about what Sequence Detector is?
In a computer network like Ethernet, digital data is sent one bit at a time, at a very high rate. Such a movement of data is commonly called a bit stream. One characteristic is unfortunate, particularly that any one bit in a bit stream looks identical to many other bits. Clearly it is important that a receiver can identify important features in a bit stream. As an example, it is important to identify the beginning and ending of a message. This is the job of special bit sequences called flags. A flag is simply a bit sequence that serves as a marker in the bit stream. To detect a flag in a bit stream a sequence detector is used. This document shows you how to produce a Moore type state diagram for a binary sequence detector.
We define a bit sequence Bn to be a set of bits, as shown below. The bit b1 is the oldest and is received first. The bit bn is the youngest and is last. If another bit is received, it will be inserted into the sequence as bn+1.
Bn = b1, b2, ... , bn
To define sequence detection, suppose a sequence of bits Rn = r1, r2, ... , rn is received. The flag sequence Fk = f1, f1, ... , fk is said to occur at time n if the corresponding bits match.
fk = rn, fk-1 = rn-1, ... , f1 = rn-k+1
For instance, consider the flag sequence F4 = 0, 1, 0, 1. Given the received sequence below, detection occurs at times 5, 7, and 13.
R13 = 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1
The difference between a Mealy and a Moore type sequence detector is that a Mealy sequence detector immediately flags the detection. With the Moore machine, you must wait for the next clock tick to allow the machine to enter a detection state that flags the detection.
One way to construct a sequence detector is to use a string of flip-flops wired as a shift register, along with a large AND gate. The circuit below will produce logic high at its output for one clock cycle, whenever the sequence 0, 1, 0, 0 is received.
Simple Sequence Detector
Identifying the Initial State
Non-Minimized State Table
| State |
Input = 0 |
Input = 1 |
| ----- |
---------- |
---------- |
| S0 |
S0, 0 |
S8, 0 |
| S1 |
S0, 0 |
S8, 0 |
| S2 |
S1, 1 |
S9, 1 |
| S3 |
S1, 0 |
S9, 0 |
| S4 |
S2, 0 |
S10, 0 |
| S5 |
S2, 0 |
S10, 0 |
| S6 |
S3, 0 |
S11, 0 |
| S7 |
S3, 0 |
S11, 0 |
| S8 |
S4, 0 |
S12, 0 |
| S9 |
S4, 0 |
S12, 0 |
| S10 |
S5, 0 |
S13, 0 |
| S11 |
S5, 0 |
S13, 0 |
| S12 |
S6, 0 |
S14, 0 |
| S13 |
S6, 0 |
S14, 0 |
| S14 |
S7, 0 |
S15, 0 |
| S15 |
S7, 0 |
S15, 0 |
|
---------- |
---------- |
|
State+, |
detect |
For a pair of states to be equivalent the following two conditions must be true.
- Both states must lead to the same next state.
- The current outputs for both states must be the same.
Minimized State Table
| State |
Input = 0 |
Input = 1 |
| ----- |
---------- |
---------- |
| S0 |
S0, 0 |
S8, 0 |
| S2 |
S0, 1 |
S8, 1 |
| S4 |
S2, 0 |
S8, 0 |
| S8 |
S4, 0 |
S12, 0 |
| S12 |
S0, 0 |
S12, 0 |
|
---------- |
---------- |
|
State+, |
detect |
STATE DIAGRAM:-
