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, ... , bnTo 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+1For 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.
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.
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.
| 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.
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.
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.
| 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.
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.
| 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."
| R5 | = | 1, 1, 0, 1, 0, 0 |
| F3 | = | 1, 0, 0 |
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.
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.
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.
