Before we get started, some initial definitions are needed.
We define a bit sequence B_{n} to be a set of bits,
as shown below.
The bit b_{1} is the *oldest* and is received first.
The bit b_{n} is the *youngest* and is last.
If another bit is received, it will be inserted into the sequence
as b_{n+1}.

BTo define sequence detection, suppose a sequence of bits R_{n}= b_{1}, b_{2}, ... , b_{n}

fFor instance, consider the flag sequence F_{k}= r_{n}, f_{k-1}= r_{n-1}, ... , f_{1}= r_{n-k+1}

R_{13}= 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
Y_{1}Y_{2}Y_{3}Y_{4}
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.

- 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.

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

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.

B_{5} |
= | 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 F_{k}
and is also the m-suffix of the received sequence
R_{n}, 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."

R_{5} |
= | 1, 1, 0, 1, 0, 0 |

F_{3} |
= | 1, 0, 0 |

Identify the length L of the shorter sequence and produce the L-prefix of F

_{7}and the L-suffix of R_{10}. 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.

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 R_{1} = 1 and F_{3} = 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 R_{2} = 0,0 is received,
what will the final state be?
We know that the first bit in R_{2} 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 R_{3} = 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 R_{4} = 0, 1, 0, 0, what will
the state be after detection? GPSS is 0 (m=1) so *M1*.
Conversely if R_{4} = 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.

This supplemental note-page was written by Krista Hill, initially for undergraduate students enrolled in the advanced logic circuits class at Worcester Polytechnic Institute (WPI). The author is now affiliated with the University of Hartford. This file may be down-loaded free of charge and used for educational purposes

Copyright: Mon Oct 7 22:02:32 2002

Revision date: Tue Jul 13 20:43:15 EDT 2004

You may send comments to the author at