Notes

Sequence Detection -- Introductory Notes

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.
Before we get started, some initial definitions are needed. 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.

Shift Register Design

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
While sequence detectors like that above work, there are several issues. First, the design is wasteful as the flag sequence length must equal the number of flip-flops in the circuit. In traditional logic design emphasis is placed on reducing the number of flip-flops used. Consider that a flag sequence 15 bits long requires 15 flip-flops. Each additional flip-flop in this circuit extends the detected sequence by only one bit. In contrast, in a state machine, each additional flip-flop doubles the number of possible states. In using a binary encoding, a state machine constructed with four flip-flops can represent 16 states, enough to detect a sequence 15 bits long.

However in designing with modern FPGAs, a device has an abundance of flip-flops so that last point is of little weight. In designing a sequence detector as a state machine, however the designer is free to choose between different encoding schemes. A shift register based sequence detector has a fixed state encoding. In designing a sequence detector as a Moore machine, the number of states in the minimal state diagram will equal one plus the number of bits in the flag sequence. For the equivalent minimal Mealy state diagram, the number of states will exactly equal the number of bits in the flag sequence.

A second problem with the shift register sequence detector is picking the initial flip-flop states. An incorrect choice may cause a premature detection. Suppose that initially the flip-flops in the above sequence detector are loaded with 0000. Inspection reveals that a detection is signaled after receiving the bits 1,0,0.

Identifying the Initial State

The minimal state diagram provides one formal way to identify a proper initial state. To produce the corresponding minimal state table from the non-minimal state table, implication charts can be used, but in examples such as this the equivalent states are more easily identified by inspection. Here we use the ordered quad Y1Y2Y3Y4 and the simple encoding such that S0 = 0000, S1 = 0001, S2 = 0010, ..., S15 = 1111. In examining the non-minimal state table, make special notice of the regular pattern.

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.
In examining the non-minimal state table it should be clear that states S0 and S1 satisfy these requirements, thus states S0 and S1 are equivalent. While states S2 and S3 have the same next states, the current outputs are different, hence state S2 and S3 are not equivalent. In using inspection here we can easily tell if the state table is minimal. Recall that such a minimal Moore type state table will have N+1 states, where N is the number of bits in the flag sequence.

Identify a pair of states that are equivalent
Draw a line through the second equivalent state
Replace all references to the second state with that of the first state
Write down the state equivalence, as in S0=S1
Go back to step 1
Start at the top of the state table and work your way down, you will note that as you eliminate equivalent states, new equivalences will appear. Once you have eliminated enough states, write the minimized state table. The minimized state table is shown below. In producing the minimal state table the following state equivalences were identified: S0=S1, S4=S5, S6=S7, S8=S9, S10=S11, S12=S13, S14=S15, S0=S3, S8=S10, S12=S14, S0=S6.

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
The initial state will be the state which has the longest short-path, leading to the detection state. To draw the minimal state diagram, first draw the detection state. Next, work your way to the left drawing each state along with an arc that leads to the the state you just have drawn.

State S4 leads to state S2
States S2 and S8 lead to S4, but state S2 is already drawn, so draw S8
Likewise, S0, S2, and S4 lead to S8, but states S2 and S4 are already drawn, so draw S0
States S2 and S12 lead to S0, but state S2 is already drawn, so draw S12
The state diagram below is not completed, but even so we can already identify the initial state. The initial state will be the one furthest from the detection state, that is state S12 or any of its equivalents. Note that to traverse the arcs, to detection, the entire flag sequence must be received.

To finish the diagram, just add the remaining arcs. Based on the diagram, state S12 or any of its equivalent states can be the initial state.


Prefix, Suffix, and GPSS

Before discussing how to directly produce a minimized state diagram, a few more definitions are needed. The i-prefix in sequence Bn is defined to be the first i bits in Bn. The j-suffix in sequence Bn is the last j bits in Bn. The following example should cement these two definitions, the sequence B5 is given below, along with its 3-prefix and 3-suffix.
Example Sequence
B5 = 1, 0, 1, 1, 0
3-prefix = 1, 0, 1
3-suffix = 1, 1, 0
We will be concerned with identifying the largest subsequence that is the m-prefix of the flag sequence Fk and is also the m-suffix of the received sequence Rn, where m is the length of the subsequence. Note that detection happens when m = k, as in the example below. For convenience we refer to the m-subsequence as the Greatest common Prefix-Suffix Subsequence (GPSS). The acronym GPSS is pronounced "geps."

Example Detection
R5 = 1, 1, 0, 1, 0, 0
F3 = 1, 0, 0
Identifying GPSS

The following method is helpful for finding the GPSS of a pair of sequences. Consider the sequences F7 and R10 that are given.

Identify the length L of the shorter sequence and produce the L-prefix of F7 and the L-suffix of R10. In doing this by hand, much writing can be saved by simply crossing out bits as you go along.


Compare the prefix and suffix, if they are the same, you have the GPSS.
If the prefix and suffix are different, reduce the prefix and suffix lengths by one bit and go back to step 2. In the example, we find that GPSS = 1, 0, 1, 1 so that m = 4.

If all the bits end up being crossed out, then GPSS does not exist and m = 0. We say that GPSS is NULL.
Moore State Machine

The following Moore type state machine detects the sequence F3 = 0, 1, 0. Start by filling in a string of states, assuming that the sequence is immediately received. The legend shows that the state name of each bubble is drawn above the output, which is named detect. The state name Mm indicates that following a RESET, to arrive at the given state, the GPSS must have a length of m bits. You can also think of m as representing the current number of potential matches between the received sequence and flag sequence. The descriptive phrases above the bubbles indicate that after a RESET no matches are made, and that until a detection is made only potential matches exist between the received sequence and flag sequence.

Almost half the job is done already. To fill in the rest of the state diagram, remember that a one bit input causes each state to lead to two possible next states. Consider M0; Suppose that following a RESET, a '1' is received rather than a '0'. What will the next state be? Given R1 = 1 and F3 = 0,1,0, GPSS is NULL (m=0) so that the next state is M0. Another way to think of this is that 1 simply does not match the first bit in the flag sequence.


Next, following a reset suppose that R2 = 0,0 is received, what will the final state be? We know that the first bit in R2 brings us to M1, but what state follows M1? We find that GPSS is 0 (m=1) so the final state is M1. Another way to think of this is that only the new bit 0 serves as a potential match with the flag sequence.


Following a reset suppose that R3 = 0, 1, 1, what will the final state be? GPSS is NULL (m=0) so the last state is M0.


Following a reset suppose that R4 = 0, 1, 0, 0, what will the state be after detection? GPSS is 0 (m=1) so M1. Conversely if R4 = 0, 1, 0, 1, we find that GPSS is 0, 1 (m=2) so that the final state is M2. The preceding discussion leads to the following state diagram.


Summary

The analysis above is neatly summarized in the following table. Each row is a case that was considered. F3 is the flag sequence and Rn is a received sequence. Bits in F3 and Rn are crossed out to produce the GPSS, and m is the length of the GPSS.

To produce the Moore state diagram for an arbitrary sequence detector, first draw a sequence of states assuming that the flag sequence is immediately received. Next, produce a table like that above to fill in the rest of the state diagram.
This supplemental note-page was written by Jonathan Hill, initially for undergraduate students enrolled in the advanced logic circuits class at Worcester Polytechnic Institute. The document is now being maintained for students in the Electrical Engineering Dept. at the University of Hartford. This file may be down-loaded free of charge and used for educational purposes as-is, provided that this copyright note is kept intact. The author retains the copyright on this material. By the down-loading this file you agree to not charge for, or resell the resulting material. The author strives for error free notes, however errors may exist in this document. The author welcomes comments and constructive criticism, credits will be inserted as further improvements are made.
Copyright: Mon Oct