Finite State Sachine - Digital system two

Digital system 2 - EENG352 - Finite State Machine

1. Finite State Machine
Dr. Mohammed Majid Al Khalidy
Lesson 02
Chapter13

2. 2
Logic circuits: The classification of logic circuits is given below
Dr. Mohammed Majid Al Khalidy

3. 3
Q :Define the type of Sequential digital circuit (FSM) below
if it is synchronousor asynchronous digital circuit?
Dr. Mohammed Majid Al Khalidy

4. 4
➢SequentialcircuitsarealsocalledFiniteStateMachines
(FSMs),becausethefunctionalbehaviorofthesecircuits
canberepresentedusingafinitenumberofstates(flip
flopoutputs).
➢DesigningsequentialcircuitsusingtheFiniteStateMachine
methodisapowerfulinDigitalLogicDesign.
Finite State Machines
Dr. Mohammed Majid Al Khalidy

5. 5 Dr. Mohammed Majid Al Khalidy

6. ➢Mealymachinesarecharacterizedbyproducingoutputs
whenatransitionistaken.
➢Mooremachine,producesoutputswhenthemachineisina
state,ratherthanwhenatransitionistaken.Thatis,the
outputisdefinedbythecurrentstateratherthanbythe
currenttransition.
6Dr. Mohammed Majid Al Khalidy

7. 7
Q :Define the type of FSM for each circuit below, is it
Moore or Mealy?
Figure. a
Figure. b
Dr. Mohammed Majid Al Khalidy

8. 8 Dr. Mohammed Majid Al Khalidy

9. 9 Dr. Mohammed Majid Al Khalidy

10. 10
Steps: Design of 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
Digital circuit
In general to design a sequential circuits you have to go through
a certain steps:
Dr. Mohammed Majid Al Khalidy

11. •Draw the state
diagram from a
description
11
X = 001100011100011110101
Y = 000000000100000110000
Design a sequential circuit that detect 3or more consecutive 1’s
in input.
Dr. Mohammed Majid Al Khalidy

12. •Draw the state
diagram from a
description
12
Design a sequential circuit that detect 3or more consecutive 1’s
in input.
Dr. Mohammed Majid Al Khalidy
X = 001100011100011110101
Y = 000000000100000110000

13. 13
▪Obtain State Table
Dr. Mohammed Majid Al Khalidy

14. 14
CS i/p NS o/p
A B XA
+
B
+
Y
0
1
0
1
0
1
0
1
▪Obtain State Table
Dr. Mohammed Majid Al Khalidy

15. 15
https://www.geogebra.org/scientific?lang=en
Dr. Mohammed Majid Al Khalidy

16. 16 Dr. Mohammed Majid Al Khalidy

17. 17
AB
00
01
11 Moore depends on state only
Dr. Mohammed Majid Al Khalidy

18. 18
CS i/p NS o/p
A B XA
+
B
+
Y
0 000 00
0 010 10
0 100 00
0 111 00
1 000 00
1 011 10
1 100 01
1 111 11
Dr. Mohammed Majid Al Khalidy

19. 19 Dr. Mohammed Majid Al Khalidy

20. 20 Dr. Mohammed Majid Al Khalidy

21. 21 Dr. Mohammed Majid Al Khalidy

22. 22
The input is two binary numbers,(x
n…x
1x
0)
2and (y
n…y
1y
0)
2
At each step, we can compute (x
i+y
i) starting with (x
0+y
0).
–If (x
i+y
i)=0, we output 0.
–If (x
i+y
i)=1, we output 1.
–If (x
i+y
i)=2, we have a problem.
The problem is we need a carry bit.
In fact, our computation needs to know the carry bit at each step
(so we compute x
i+y
i+c
iat each step), and be able to give it to
the next step.
We can take care of this by using states to represent the carry bit.
Example:Binary Adder
Use FSMto construct the state diagram and the state table for a
binary adder toadd two numbers.
Design:
Dr. Mohammed Majid Al Khalidy

23. 23
We will use the following states
–StateS
0occurs if the carry bit is 0
–StateS
1occurs if the carry bit is 1
Since when we begin the computation, there is no carry, we
can use S
0as the start state,
So, how does which state we are in affect the output?
If we are in state S
0(we have a carry of 0)
–If (x
i+y
i)=0, we output 0, and stay in state S
0
–If (x
i+y
i)=1, we output 1, and stay in state S
0
–If (x
i+y
i)=2, we output 0, and go to state S
1
If we are in state S
1(we have a carry of 1)
–If (x
i+y
i+1)=1, we output 1, and go to state S
0
–If (x
i+y
i+1)=2, we output 0, and stay in state S
1
–If (x
i+y
i+1)=3, we output 1, and stay in state S
1
Dr. Mohammed Majid Al Khalidy

24. 24
Next State Output
Input Input
State0001101100011011
S
0 S
0S
0S
0S
10110
S
1 S
0S
1S
1S
11001
▪We will
choose Mealy
FSM
▪The state
table is:
Dr. Mohammed Majid Al Khalidy

25. 25
Example: 2-bit gray-code counter with enableand ‘z’ output: 00, 01, 11,
10, 00, … The output ‘z’ is 1when the present count is ‘10’. The count is the
same as the states encoded in binary.
First step: Draw the State Diagram and State Table. If we were to implement
the state machine in VHDL, this is the only step we need.
Secondstep:StateAssignment.Weassignuniqueflipflopstatestoourstate
labels(S1,S2,S3,S4).Noticethatthisisarbitrary.However,wecansave
resourcesifweassigneachstatetothecountthatwedesire.Then,theoutput
‘count’isjusttheflipflops’outputs.
gray-code
Dr. Mohammed Majid Al Khalidy

26. 26
ThereflectedbinarycodeorGray
codeisanorderingofthebinary
numeralsystemsuchthattwo
successivevaluesdifferinonlyone
bit(binarydigit).Graycodesarevery
usefulinthenormalsequenceof
binarynumbersgeneratedbythe
hardwarethatmaycauseanerroror
ambiguityduringthetransitionfrom
onenumbertothenext.So,theGray
codecaneliminatethisproblem
easilysinceonlyonebitchangesits
valueduringanytransitionbetween
twonumbers.
Gray code
Dr. Mohammed Majid Al Khalidy

27. 27
E
CS NS
Z
Q
oQ
1
Q
o
+
Q
1
+
0
0
0
0
1
1
1
1
ECSNSNC Z
0S1S1 0
0S2S2 0
0S3S3 0
0S4S4 1
1S1S2 0
1S2S3 0
1S3S4 0
1S4S1 1
Dr. Mohammed Majid Al Khalidy

28. 28
Third step: Excitation table. Here, we replace the state labels by the flip flop
states:
Fourth step:Excitation equations and minimization. ??????1(??????+ 1) and ??????0(??????+ 1) are
the next state of the flip flops, i.e. these signals are to be connected to the
inputs of the flip flops.
Dr. Mohammed Majid Al Khalidy

29. 29
Fifth step: Circuit implementation:
Dr. Mohammed Majid Al Khalidy

30. FSM Vs. Counter
Example:3-bit Binary Upcounter
Decide to implement with
Toggle Flipflops
What inputs must be
presented to the T FFs
to get them to change
to the desired state bit?
30Dr. Mohammed Majid Al Khalidy

31. K-maps for Toggle
Inputs:
Resulting Logic Circuit:T
CLK
\Reset
Q
Q
S
R
QA
T
CLK
Q
Q
S
R
QB
T
CLK
Q
Q
S
R
QC
Count
+ TB = A
TC = A • B
T A = 1
CB
A
C
00 01 11 10
0
1
B
1 1 1 1
1 1 1 1
CB
A
C
00 01 11 10
0
1
B
0 0 0 0
1 1 1 1
CB
A
C
B
00 01 11 10
0
1
0 0 0 0
0 1 1 0
31Dr. Mohammed Majid Al Khalidy

32. Count
\Reset
Q
C
Q
B
Q
A
100 Timing Diagram:
32Dr. Mohammed Majid Al Khalidy

33. More Count Sequence
Step 1: Derive the State Transition Diagram
110
011
Count sequence: 000, 010, 011, 101, 110
000
010 101
33Dr. Mohammed Majid Al Khalidy

34. Step 2:State Transition Table
Note the Don't Care conditions
Present
State
Next
State
C B A C
+
B
+
A
+
0 0 0 0 1 0
0 0 1 X X X
0 1 0 0 1 1
0 1 1 1 0 1
1 0 0 X X X
1 0 1 1 1 0
1 1 0 0 0 0
1 1 1 X X X
34Dr. Mohammed Majid Al Khalidy

35. Step 3:K-Maps for Next State Functions
CB
00011110A
0
1
C+ = A
CB
00011110A
0
1
A+ = BC
CB
00011110A
0
1
B+ = B + AC
0 0 0 X
X 1 X 1
1 1 0 X
X 0 X 1
0 1 0 X
X 1 X 0
35Dr. Mohammed Majid Al Khalidy

36. C B A TC TB TA
0 0 0 0 1 0
0 0 1 X X X
0 1 0 0 0 1
0 1 1 1 1 0
1 0 0 X X X
1 0 1 0 1 1
1 1 0 1 1 0
1 1 1 X X X
Step 4:Choose FlipflopType for Implementation
Use Excitation Table to Remap Next State Functions
Toggle Excitation
Table
Remapped Next State
Functions
Present
State
Toggle
InputsQ Q
+
T
0 0 0
0 1 1
1 0 1
1 1 0
36Dr. Mohammed Majid Al Khalidy

37. Remapped K-Maps
CB
00011110A
0
1
TC
CB
00011110A
0
1
TA
CB
00011110A
0
1
TB
0 0 1 X
X 1 X 0
1 0 1 X
X 1 X 1
0 1 0 X
X 0 X 1
TC= A C + A C = A C
TB = A + B + C
TA= A B C + B C
37Dr. Mohammed Majid Al Khalidy

38. Resulting Logic:
5 Gates
13 Input Literals +
Flipflop connections
Note:
T-FFs are
implemented
using JK-FFs
38Dr. Mohammed Majid Al Khalidy

39. Timing Waveform:0
0
0
0
0
0
0
1
0
0
1
1
1
0
1
1
1
0
0
0
0
100
Count
\Reset
C
B
A
39Dr. Mohammed Majid Al Khalidy

40. Solution:
40Dr. Mohammed Majid Al Khalidy

41. 41Dr. Mohammed Majid Al Khalidy

42. 42Dr. Mohammed Majid Al Khalidy

43. 43Dr. Mohammed Majid Al Khalidy

44. 44
Controller Design
Using the process for designing a controller, convert the FSM of the figure
belowto acontroller, implementing the controller using a state register
and logic gates.
Step 1-Capture the FSM
The appropriate FSM is given here.
Step 2-Set up the architecture
Dr. Mohammed Majid Al Khalidy

45. Dr. Mohammed Majid Al Khalidy 45
Input Output
S1S0 a n1n0 y
A 0 B 0
A 1 A 0
B 0 B 1
B 1 C 1
C 0 D 1
C 1 D 1
D 0 A 0
D 1 A 0

46. 46
Step 3-Encode the states
A straightforward encoding is A=00, B=01, C=10, D=11.
Step 4-Fill in the truth table
Dr. Mohammed Majid Al Khalidy

47. 47
Step 5-Implement the combinational logic
n1 = s1’s0a + s1s0’a’ + s1s0’a = s1’s0a + s1s0’
n0 = s1’s0’a’ + s1’s0a’ + s1s0’a’ + s1s0’a = s1’a’ + s1s0’
y = s1’s0a’ + s1’s0a + s1s0’a’ + s1s0’a = s1’s0 + s1s0’ = s1 xors0
Dr. Mohammed Majid Al Khalidy

48. Dr. Mohammed Majid Al Khalidy 48
Bonus1: Design a Traffic Light Controller using Moore Machine.

49. 49
Example:
1) Draw a state diagram for an FSM with an input gcntand three
outputs, x, y and z.The xyzoutputs generate a sequence called a Gray
code in which exactly one of thethree outputs changes from 0 to 1 or
from 1 to 0. The Gray code sequence that theFSM should output is 000,
010, 011, 001, 101, 111, 110, 100, repeat. The outputshould change only
on a rising clock edge when the input gcnt= 1. Make the initial state
000.
2) Using the process for designing a controller, convert the FSM you
created for Example above to a controller, implementing the controller
using a state register andlogicgates.
Step 1-Capture the FSM
Dr. Mohammed Majid Al Khalidy

50. 50Dr. Mohammed Majid Al Khalidy

51. 51
Step 2 -Set up the architecture
Step 3-Encode the states
A straightforward encoding is A=000, B=001, C=010, D=011,
E=100, F=101,G=110, H=111.
Dr. Mohammed Majid Al Khalidy

52. 52
Step 4-Fill in the truth table
Dr. Mohammed Majid Al Khalidy

53. 53
Step 5-Implement the combinational logic
n2 = s2’s1s0gcnt + s2s1’ + s2s1s0’ + s2s1s0gcnt’
n1 = s2’s1’s0gcnt + s2’s1s0’ + s2’s1s0gcnt’ + s2s1’s0gcnt + s2s1s0’ + s2s1s0gcnt’
n0 = s2’s1’s0’gcnt + s2’s1’s0gcnt’ + s2’s1s0’gcnt + s2’s1s0gcnt’ + s2s1’s0’gcnt +
s2s1’s0gcnt’ + s2s1s0’gcnt + s2s1s0gcnt’
x = s2
y = s2’s1’s0 + s2’s1s0’ + s2s1’s0 + s2s1s0’
z = s2’s1 + s2s1’
Note: The above equations can be minimized further
Find the digital circuit?
Dr. Mohammed Majid Al Khalidy

54. 54
Example
Q Q+D
0 0 0
0 1 1
1 0 0
1 1 1
Dr. Mohammed Majid Al Khalidy

55. 55
Q3 Q2 Q1 D3 D2 D1 Q3+Q2+Q1+
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
Dr. Mohammed Majid Al Khalidy

56. 56
Example
Dr. Mohammed Majid Al Khalidy

57. 57Dr. Mohammed Majid Al Khalidy