Here is how to design a Sequence Detector in 10 easy steps. | applied electronics engineering

Latest

Here is how to design a Sequence Detector in 10 easy steps.

By Applied Electronics - Wednesday, September 3, 2014 1 Comment
Let the sequence of bits to be detected be 101. Let the input sequence be x = 0010101110010110 and z be the output. At each clock edge the sequence detector checks the input bit of x and remembers the input bit and proceeds to check the next bit. When the sequence 101 is found, it outputs z as 1.

1. Create a State Diagram

At each state, think what happens when the received bit x is 0 and what happens when it is 1. Create new state, when you want to remember current bit. In state S1, when 0 is received the machine stays in the same state and output z is 0 but when 1 is received the machine goes to new state S2 and outputs z = 0 because the sequence is not detected. When the machine is in the new state S2 and 0 is received it goes to new state S3 because 0 is part of required sequence to be detected, 101, where 1 and 0 part is what S3 detects. Once in the state S3, when 1 is received, then we get the desired sequence to be detected 101. So when 1 is received at S3 it goes back to state S2 and outputs z = 1.

sequence detector state diagram for 101


Next work on the alternative input at S2 and S3. When at S2, 1 is received it stays in the same state. When at S3, 0 is received it goes back to state S1.

2. Create a State Table

From the above state diagram construct the state table as shown below:

Present State
Next State
Output
X = 0
X = 1
X = 0
X = 1
S1
S1
S2
0
0
S2
S3
S2
0
0
S3
S1
S2
0
1

3. State Assignment

There are 3 states and one flip flop can store two bits. Therefore two flip flop can be used for assigning 3 states as follows-

State - AB
----------------
S1    -  0 0
S2    -  0 1
S3    -  1 0

4. State Table to State Transition Table using State Assignment

Substitute state names S1, S2 and S3 with 00, 01 and 10(which are AB) to convert the state table into state transition table.

Present State(AB)
Next State(A+B+)
Output
X= 0
X = 1
X= 0
X = 1
00
00
01
0
0
01
10
01
0
0
10
00
01
0
1

5. Draw Karnaugh Map

From the state transition table draw the Karnaugh Map and solve for next state

AB
x
00
01
11
10
0
0
1
x
0
1
0
0
x
0
Solution: A+ = BX’
AB
x
00
01
11
10
0
0
0
x
0
1
1
1
x
1
Solution: B+ = X
AB
x
00
01
11
10
0
0
0
x
0
1
0
0
x
1
Solution: Z = XA

6. Find Next State and Output Equation

From the Karnaugh Map from step 5 find the next state equation and output equation:

Next state equation is: A+ = BX' and B+ = X
Output Equation is: Z = XA

7. Select Flip Flop and Find out Characteristic equation

Let us choose D Flip Flop then the characteristic equation is,
Q+ = D

8. Find Flip Flop Input and Output Equation

Insert Next State and Output Equation into the characteristics equation to find out the Flip Flop input and output equation

From steps(5) and (6),

DA = A+ = BX'
DB = B+ = X
Z = XA

9. Draw the Circuit

Use the input/ output equation to draw the circuit. The circuit implementation is shown below,

sequence detector xilinx

10. Verify Circuit Operation

To verify the circuit it was stimulated in Xilinx ISE design suite to get the following digital waveform:

sequence detector xilinx

In the above waveform graph, when 101 is detected z is indeed 1 as required.

Another example of sequence detector design- FPGA Programming Tutorial: 010 Sequence Detector with VHDL

Tags:

1 comment to '' Here is how to design a Sequence Detector in 10 easy steps. "

ADD COMMENT
  1. vhsl code that gives state diagram as output when we enter the sequence to be detected

    ReplyDelete