Digital Logic Design Start from Zero to Hero 2

Digital Logic Design 2

1. Gate-Level Minimization 1
DIGITAL LOGIC DESIGN
by
Dr. Fenghui Yao
Tennessee State University
Department of Computer Science
Nashville, TN

2. Gate-Level Minimization 2
What is minimization?What is minimization?
Simplifying boolean expressionsSimplifying boolean expressions
Algebraic manipulations is hard since Algebraic manipulations is hard since
there is not a uniform way of doing itthere is not a uniform way of doing it
Karnaugh map or K-map techniques is Karnaugh map or K-map techniques is
very commonly usedvery commonly used

3. Gate-Level Minimization 3
Two-Variable K-MapTwo-Variable K-Map

4. Gate-Level Minimization 4
ExampleExample
BBAABF  '

5. Gate-Level Minimization 5
ExampleExampleExampleExample
BABABAABF  ''''

6. Gate-Level Minimization 6
Three-Variable K-MapThree-Variable K-Map

7. Gate-Level Minimization 7
Three-Variable K-MapThree-Variable K-Map

8. Gate-Level Minimization 8
ExampleExample
'''
'''''
CBAACAB
ABCCABCBAABCF



9. Gate-Level Minimization 9
NoteNote
In K-maps, you can have groups of 2, 4, In K-maps, you can have groups of 2, 4,
8, or 168, or 16
You cannot have groups of other You cannot have groups of other
combinations such as a group of 6combinations such as a group of 6

10. Gate-Level Minimization 10
ExercisesExercises
''''
''''''
'''''
3
2
1
CBCABAF
ABCCABCACAF
ABCABCABBCAF




11. Gate-Level Minimization 11
ExampleExample
Represent Represent F F in the minimal format and in the minimal format and
draw the network diagramdraw the network diagram

12. Gate-Level Minimization 12
ExampleExample
Represent Represent F F in the minimal format and in the minimal format and
draw the network diagramdraw the network diagram

13. Gate-Level Minimization 13
ExampleExample
  7,5,4,3,2,0F
Represent Represent F F in the minimal format and in the minimal format and
draw the network diagramdraw the network diagram

14. Gate-Level Minimization 14
Four-Variable K-MapFour-Variable K-Map

15. Gate-Level Minimization 15
Four-Variable K-MapFour-Variable K-Map

16. Gate-Level Minimization 16
ExampleExample
'''''''),,,( ABCDCDACADCBAF 
  13,12,8,6,5,4,2,1,0),,,( DCBAF
Represent Represent
F F in the in the
minimal minimal
format and format and
draw the draw the
network network
diagramdiagram

17. Gate-Level Minimization 17
ExampleExample
  15,13,12,11,10,8,6,5,3),,,( DCBAF
Represent Represent F F in the minimal format and in the minimal format and
draw the network diagramdraw the network diagram

18. Gate-Level Minimization 18
ExampleExample
Represent Represent F F in the minimal format and in the minimal format and
draw the network diagramdraw the network diagram

19. Gate-Level Minimization 19
Prime ImplicantsPrime Implicants
You must cover all of the mintermsYou must cover all of the minterms
You must avoid redundancyYou must avoid redundancy
You must follow some rulesYou must follow some rules
Prime ImplicantPrime Implicant
A product term that is generated by combining A product term that is generated by combining
the maximum number of adjacent squares in the the maximum number of adjacent squares in the
mapmap
Essential Prime ImplicantEssential Prime Implicant

A minterm that is covered by only one prime A minterm that is covered by only one prime
implicant implicant

20. Gate-Level Minimization 20
Maxterm SimplificationMaxterm Simplification

RememberRemember
)''(FF

21. Gate-Level Minimization 21
ExampleExample

Simplify Simplify F F in product of sumsin product of sums
  12,11,10,8,6,5,3,2,1),,,( DCBAF

22. Gate-Level Minimization 22
Example (cont)Example (cont)
Step – 1Step – 1

Fill the K-map for Fill the K-map for FF

23. Gate-Level Minimization 23
Example (cont)Example (cont)
Step – 1Step – 1

Fill the K-map for Fill the K-map for FF

24. Gate-Level Minimization 24
Example (cont)Example (cont)
Step – 2Step – 2
Fill zeros in the rest of the squaresFill zeros in the rest of the squares

25. Gate-Level Minimization 25
Example (cont)Example (cont)

Step – 3 Step – 3
Cover zeros. This is your Cover zeros. This is your F’F’
)''')(''')('')((),,,(
'''')',,,(
CBADCBDCADCADCBAF
ABCBCDDACDCADCBAF




26. Gate-Level Minimization 26
ImportantImportant
'')'(
'')'(
BAAB
BABA



27. Gate-Level Minimization 27
Don’t Care ConditionsDon’t Care Conditions
A network is usually composed of sub-A network is usually composed of sub-
networksnetworks
Net-1 may not produce all Net-1 may not produce all
combinations of A,B, and Ccombinations of A,B, and C
In this case, F don’t care about those In this case, F don’t care about those
combinationscombinations
A
B
C
FNet-1 Net-2

28. Gate-Level Minimization 28
Don’t Care ConditionsDon’t Care Conditions
FCBA
0 0 0 1

0 0 1 x

0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 x
1 1 1 1
ABBCBAABCABCCBABCACBAF
BCBAABCCBABCACBAF
ABCBCACBAF



'''''''''
''''''''
''''
X can be
considered
as 0 or 1,
whichever
is more
convenient

29. Gate-Level Minimization 29
NAND/NOR NAND/NOR
ImplementationsImplementations
AND, OR, and NOT gates can be used AND, OR, and NOT gates can be used
to construct the digital systemsto construct the digital systems
However, it is easier to fabricate NAND However, it is easier to fabricate NAND
and NOR gatesand NOR gates
So try to replace AND, OR, and NOT So try to replace AND, OR, and NOT
gates with NAND or NOR gatesgates with NAND or NOR gates

30. Gate-Level Minimization 30
NAND ImplementationNAND Implementation
First implement with AND-ORFirst implement with AND-OR
Put bubble at the output of each AND Put bubble at the output of each AND
gategate
Put bubbles at the inputs of each OR Put bubbles at the inputs of each OR
gategate
Place necessary inverters Place necessary inverters

31. Gate-Level Minimization 31
ExampleExample
ECDABBAF ),(

32. Gate-Level Minimization 32
ExampleExample
ABDBCABAF  )('),(

33. Gate-Level Minimization 33
ExampleExample
ABDBCABAF  )('),(

34. Gate-Level Minimization 34
NOR ImplementationNOR Implementation
First implement with AND-ORFirst implement with AND-OR
Put bubble at the inputs of each AND Put bubble at the inputs of each AND
gategate
Put bubbles at the output of each OR Put bubbles at the output of each OR
gategate
Place necessary inverters Place necessary inverters

35. Gate-Level Minimization 35
ExampleExample
)()(),( EDCBABAF 

36. Gate-Level Minimization 36
Study ProblemsStudy Problems
Course Book Chapter – 3 ProblemsCourse Book Chapter – 3 Problems
3– 13– 1

3 – 33 – 3

3 – 53 – 5

3 – 73 – 7

3 – 123 – 12

3 – 153 – 15

3 – 183 – 18

37. Gate-Level Minimization 37
QuestionsQuestions