Question 6.4: Design a three-bit sequence detector for detecting a sequenc......

Step 1 Construct the initial state diagram and initial state table.
Sequence detection is a act of recognizing a predefined series of input bits. The bits are input one by one. According to the requirement of detecting the predefined series of inputs “011,” we need to see whether they match the given sequences “011” for each three bits that are input. Thus, one sequential input variable, X, and one output variable, Y, are needed. X is the value of the input line in a given clock cycle. The output, Y, goes high for one clock cycle as soon as it receives the third bit that matches a pattern. There are at least four states required to construct the initial state diagram. State A is a waiting state in which the state machine waits for the first input bit “0”; state B represents the case detecting the first bit “0”; state C means the case detecting the continuous two bits “01”; and state D represents the case detecting the continuous three bits “011.” The output, Y, goes high for one clock cycle as soon as it receives the third bit that matches a pattern.
When the initial state is state A, the state transitions will depend on whether the input X is a 0 or 1. If the input X is a 1, the next state is still in state A; if the input X is a 0, the state transition will be from state A to state B. This means the first bit “0” occurs. The output Y is a 0.
If in state B and the input X is a 0, the next state does not change with an output of a 0; if the input X is a 1, the continuous two bits “01” are detected and the state will change from state B to state C with the output of a 0.
If in state C and the input X is a 0, the state will turn back state B with an output of a 0; if the input X is 1, the continuous three bits “011” are detected and the state will change from state C to state D with the output of a 1.
If in state D and the input X is a 0, the state will turn back state B and start new sequence detector; if the input X is 1, the state will turn to state A waiting for the first bit “0” with the output of a 0. According the aforementioned analysis, the initial state diagram for detecting a sequence input series “011” is shown in Figure 6.3.1. The initial state table can be deduced from the initial state diagram, as listed in Table 6.3.1.

Step 2 Minimize the number of states in the state table by state reduction.
The initial state table may contain some unnecessary states, which makes the following design more complex. So initial state diagram or state table should be minimized by state reduction. It can be seen from Table 6.3.1 that state A and state D have the same next state and the consistent output for each input value. Thus, these two states can be called as equivalent states. If two or more states are equivalent, they can be represented by one state. That is, state D can be taken place by state A. Note that state A and state B lead to the same output, but they do not lead to the same next state for each input value, and so state A and state B are not equivalent. The minimized state table is shown in Table 6.3.2.

Step 3 Encode states and determine the required number of flip-flops to represent states.
To perform a state assignment, each state should be assigned a unique binary code. Since there are three states, A, B, and C, there are at least two-bit binary codes required. There are several schemes for coded three states with two-bit binary codes. Here, natural binary codes are chosen for coded states A, B, and C. States A, B, and C can be assigned 00, 01, and 10, respectively. So the coded state table can be deduced from Table 6.3.2 to Table 6.3.3. The state of flip-flops is represented by Q_{1}Q_{0} . Since one flip-flop can store one-bit binary code, two flip-flops are required to store two-bit binary codes.

Step 4 Choose the type of flip-flops and derive the excitation equations and output equation.
Different types of flip-flops would lead to different complexities of the resulting synthesis of sequential logic circuits. Here, two T flip-flops are chosen for constructing the sequential circuit. In order to derive the excitation equations and output equation, a new style state/output table should be constructed by using the excitable table of T flip-flop and binary coded state stable as listed in Table 6.3.3. The excitation table illustrates the excitation input values of the corresponding flipflop needed to make the circuit go to the desired next coded state for each combination of coded state and input. Excitation table of T flip-flops can be deduced according to the function of T flipflop, as shown in Table 6.3.4.
A state transition table is shown in Table 6.3.5, which can be deduced by combining Tables 6.3.3 and 6.3.4.
According to Table 6.3.5, the Karnaugh maps of {{T}}_{1} and {{T}}_{0} are shown in Figure 6.3.2. State 11 is the used state and the corresponding two cells are treated as “don’t care” terms.
The minimized excitation equations can be obtained by simplifying the Karnaugh map:

T_{1}=Q_{1}+X Q_{0}                            (6.3.1)

T_{0}=\bar{X}\cdot\bar{Q}_{0}+X Q_{0}                          (6.3.2)

Since only one combination of current state and input make the output a 1, the output equation can be directly written as

Y=X Q_{1}\bar{Q}_{0}                              (6.3.3)

Step 5 Check if the synthesis of sequential logic circuits can be self-corrected.
In the state assignment, state 11 is unused corresponding to the unused state. If the circuit is in this unused state, it cannot automatically return to one of the used states and thus the circuit cannot be self-corrected. According to the aforementioned simplification process, the value of input {{T}}_{1} corresponding to two don’t care terms, 011 and 111, are both treated as 1; the value of input {{T}}_{0} are treated as a 0 for the combination of 011 and a 1 for the combination of 111. After state 11, the next state will be state 01 and state 00, which are listed in the last two rows in Table 6.3.5. Both state 00 and state 01 are the used states, so the design circuit can be self-corrected.

Step 6 Draw a logic diagram according to the resulting exciting equations and output equation.
According the excitation eqs. (6.3.1) and (6.3.2), and the output eq. (6.3.3), the logic diagram of a 011 sequence detector is drawn with two T flip-flops and logic gates, as shown in Figure 6.3.3.