DS II 3 Design of Sequence Recognizer.pdf

Sequence recognizer using ff's

1. Sequential Circuits
Design of A Sequence Recognizer
Dr. Mohammed Majid Al Khalidy
Lesson 3
Ch14

2. 2
Design of Synchronous Sequential Circuits
Step 1:
Obtain a
state
diagram
State reduction
if necessary
Step 2:
Obtain State
Table
State
Assignment
Choose type of
flip-flops
Use FF’s
excitation table
to complete the
table
Step 3:
Derive state
equations
Use K-Maps
Obtain the FF
input equations
and the output
equations
Step 4:
Draw the
circuit
diagram
In general to design a sequential circuits you have to go through a
certain steps:

3. 3
Astringof0’sand1’sappliedtotheXinputand
generateanoutputZ=1onlywhenaprescribedinput
sequenceendingin101.Itwillbeassumed.Thecircuit
doesnotresetwhena1outputoccurs.Atypicalinput
sequenceandthecorrespondingoutputsequenceare:
Example 1: Design of A Sequence Recognizer

4. 4
Step1: State Diagram
Sequence to be detected: 101
➢We will start the circuit in a reset state designated S
0.
➢If a 0input is received, the circuit can stay in S
0. because the input
sequence we are looking for (101) does not start with 0.
➢If a 1is received, the circuit must go to a new state (S
1).
S
0
(By choosing Mealy FSM)

5. 5
➢If we receive a 0 inS
1, the circuit must change to a new state (S
2).
➢If we receive a 1in S
1the circuit can stay in S
1.
Sequence to be detected: 101
S
1: 101
➢If a 1is received in state S
2, the desired input sequence (101) is
complete and the output should be 1.
➢If a 0input occurs in state S
2, we have
received two 0’s in a row and must reset
the circuit to state S
0because 00 is not
part of the desired input sequence, and going
to one of the other states could lead to
an incorrect output.
S
2:
101

6. 6
➢State S
0is the starting state.
➢state S
1indicates that a sequence ending in 1 has been received.
➢state S
2indicates that a sequence ending in 10 has been received.
Sequence to be detected: 101
Summary:

7. 7
Step 2: State Table
▪State assignment
Choose FF
In this example, lets choose D-FFfor A and B

8. 8
I/P PS NS O/
P
X A BA+B+ Y
0 0 0 0 0 0
0 0 1 1 0 0
0 1 0 0 0 0
0 1 1 x x x
1 0 0 0 1 0
1 0 1 0 1 0
1 1 0 0 1 1
1 1 1 x x x
Or

9. 9
Step 3: State Equations
(Mealy)

10. 10
Step 4: Draw Circuit

11. 11
The procedure for finding the state graph for a Moore machine is
similar to that used for a Mealy machine, except that the output is
written with the state instead of with the transition between states.

12. 12
Example 2: Design of A Sequence Recognizer
Design a circuit that reads as inputs
continuous bits, and generates an output
of ‘1’ if the sequence (1011) is detected

13. 13
Step1: State Diagram
Sequence to be detected: 1011

14. 14
Step 2: State Table
OR

15. 15
State assignment

16. 16
Choose the FF
In this example, lets choose JK–FFfor A
and D-FFfor B

17. 17
Complete state table
use excitation tables for JK–FFand D-FF
D–FF excitation table
JK–FF excitation table

18. 18
Use k-map
J
A= BX’
K
A= BX + B’X’
D
B= X
Z = ABX’
Step 3: State Equations

19. 19
J
A= BX’
K
A= BX + B’X’
D
B= X
Z = ABX’
Step 4: Draw Circuit

20. 20
Guidelines for Construction of State
Graphs
Althoughthereisnoonespecificprocedurewhichcanbe
usedtoderivestategraphsortablesforeveryproblem,the
followingguidelinesshouldprovehelpful:
1.First,constructsomesampleinputandoutputsequences
tomakesurethatyouunderstandtheproblemstatement.
2.Determineunderwhatconditions,ifany,thecircuitshould
resettoitsinitialstate.
3.Ifonlyoneortwosequencesleadtoanonzerooutput,a
goodwaytostartistoconstructapartialstategraphfor
thosesequences.
4.Anotherwaytogetstartedistodeterminewhat
sequencesorgroupsofsequencesmustberemembered
bythecircuitandsetupstatesaccordingly.

21. 21
5.Eachtimeyouaddanarrowtothestategraph,determine
whetheritcangotooneofthepreviouslydefinedstatesor
whetheranewstatemustbeadded.
6.Checkyourgraphtomakesurethereisoneandonlyone
pathleavingeachstateforeachcombinationofvaluesof
theinputvariables.
7.Whenyourgraphiscomplete,testitbyapplyingtheinput
sequencesformulatedinpart1andmakingsuretheoutput
sequencesarecorrect.

22. 22
➢The vertical bars indicate the points at
which the circuit resets to the initial
state.
➢An input sequence of either 01or 10
followed by 01will produce an output of
Z = 1. Therefore, the circuit can go to the
same state if either 01 or 10 is received.
➢The partial state graph for the two
sequences leading to a 1 output is shown
in Figure.
➢The circuit resets to S
0when the fourth
input is received.
Solution

23. 23
➢Addarrowsandlabelstothegraphtotakecareofsequences
whichdonotgivea1output,asshowninFigurebelow.
➢S
5andS
6wasnecessarysothatthecircuitwouldnotreset
toS
0beforefourinputswerereceived.

24. 24
Solution
Q.

25. 25
Q :Define the type of FSM for each circuit below, is it Moore
or Mealy?

26. 26
Q :Define the type of Sequential digital circuit (FSM) below if it
is synchronous or asynchronous digital circuit?