Design a circuit that detect the sequence 0110 Draw the Moor

Design a circuit that detect the sequence 0110.

Draw the Moore state machine for detecting non-overlapping sequences

Write the truth table that shows the next state based on T flip flops

Draw the circuit

Re-do the More state machine graph for overlapping sequences (do the state machine only)

Solution

A)This sort of situation might arise for a simple code lock, where the user must enter the correct 4 bits to open the lock. If the user doesn’t input the correct 4 bits, they must start over. Or, it might be used in a simple communication system which receives bits off a line one at a time, and the word size is 4 bits. In this case, the patterns might be start and stop signals, or some other communication protocol-related information. The input is defined as X. Thus, the value of X is the value of the input line in a given clock cycle. The output, Y, goes high for 1 clock cycle as soon as it receives the 4th bit that matches a pattern. We have only one input and only one output, so we don’t need to use ASM charts. We can use a simple state diagram. Note that because the output must go high as soon as the 4th matching bit is received, we need this to be a Mealy machine. Also, note that in this example, when we are looking for 1010, we assume the most significant bit is the first bit received, so the order of the inputs would be 1-0-1-0, not 0-1-0-1.

Our state machine starts in a state in which we have received no bits. We will call this state START. The state transitions will be depending on whether the input X is a 0 or 1 – we can essentially use the states to record which values have been received. If the input is 0, we transition to a state called S0; if X is 1, we transition to S1. These states are named after the value received in the previous clock cycle. From each of S0 and S1, we can likewise go to new states based on the value of X. If in S0, and X is 0, we go to state S00; if X is 1, we go to state S01. Similarly, if in S1, and X is 0, we go to state S10; if X is 1, we go to state S11. Again, the states are named after the two previously received values. Now, each of those four states can again go to one of two possible states, based on the value of X. The states are S000, S001, S010, S011, S100, S101, S110, S111. At this point, the state machine knows we have received 3 bits, and knows what those 3 bits are. When it receives the next bit, it can determine whether a matching sequence was input, or whether we need to restart.

So, S000, S001, S010, S100, S110, and S111 all transition back to START and output 0, no matter what the input, because none of those states correspond to having received the first 3 bits of sequences 0110 or 1010. States S011 and S101, however, do depend on the input. They both still transition back to START, but if the input is 0, the output is 1. Otherwise, the output remains 0. Thus the state machine meets our design requirements.

So we have a state machine that has 15 states. 15 states is quite a lot. This requires at least 4 state variables (i.e. 4 flip-flops). If using one-hot design, there will be 15 flip-flops! Maybe we can reduce the number of states. We try to apply state reduction – look for redundancy or unnecessary repetition in the diagram or state table. We don’t necessarily care that the system knows what it has received exactly, so long as it sets the output appropriately to indicate a matching sequence has been detected. First, we notice that everything from S00 down and S11 down is identical. That is, the state machine behaves exactly the same after this point, with respect to receiving 0 and 1. So why not combine S00 and S11 and thus we can get rid of 3 states that way. So we combine them into S00_11, and the 2 states after become S110_000 and S111_001.

Now, we can also see that S01 and S10 are followed by the exact same structure. This is because the last 2 bits of the sequences we’re looking for are the same – 0110 and 1010. So we can combine this states, too, getting S01_10 which leads to S100_010 and S101_011. This gets rid of another 3 states.

So now we have only 9 states. Can we reduce more? Notice that now we have two branches of states, those which might be leading to a possible sequence match, and those which are definitely wrong. For the branches that are definitely wrong, we don’t need to bother with going to different states depending on whether 1 or 0 is input – we just need to go to another state in the “wrong” path. Combining all the “wrong” states into a single “wrong” path can save us a few more states.

Now we have only 7 states. That is less than half of what we started with, and we now only need 3 flip-flops instead of 4. The state table is simpler, as is the implementation. We can now write out our state table and excitation table. We’ll use 3 D-type flip-flops (Ck , Bk , and Ak ) and assign START = 000, S0 = 001, S1 = 010, S10_01 = 011, S11_00 = 100, S101_011 = 101, and SREST = 110.