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.
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:
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.
5. Draw Karnaugh Map
From the state transition table draw the Karnaugh Map and solve for next state
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,
10. Verify Circuit Operation
To verify the circuit it was stimulated in Xilinx ISE design suite to get the following digital waveform:
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
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.
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,
10. Verify Circuit Operation
To verify the circuit it was stimulated in Xilinx ISE design suite to get the following digital waveform:
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
vhsl code that gives state diagram as output when we enter the sequence to be detected
ReplyDelete