Karnaugh Graph or K-Map

Each fact and details of K-Map

1. KARNAU
GH
MAP

2. CONTENTS
Introduction.
Advantages of Karnaugh Maps.
SOP & POS.
Properties.
Simplification Process
Different Types of K-maps
Simplyfing logic expression by different types of K-Map
Don’t care conditions
Prime Implicants
References.

3. Also known as Veitch diagram or K-Map.
Invented in 1953 by
Maurice Karnaugh.
 A graphical way of
minimizing Boolean
expressions.
It consists tables of rows
and columns with entries
represent 1`s or 0`s.
Introduction

4. Advantages of Karnaugh Maps
Data representation’s simplicity.
Changes in neighboring variables are easily displayed
Changes Easy and Convenient to implement.
Reduces the cost and quantity of logical gates.

5. SOP & POS
The SOP (Sum of Product) expression represents
1’s .
SOP form such as (A.B)+(B.C).
The POS (Product of Sum) expression represents the
low (0) values in the K-Map.
POS form like (A+B).(C+D)

6. Properties
An n-variable K-map has 2
n
cells with n-variable truth
table value.
Adjacent cells differ
in only one bit .
Each cell refers to a
minterm or maxterm.
For minterm m
i
,
maxterm M
i
and
don’t care of f we
place 1 , 0 , x .

7. Simplification Process
No diagonals.
Only 2^n cells in each group.
Groups should be as large as possible.
A group can be combined if all cells of the group have
same set of variable.
Overlapping allowed.
Fewest number of groups possible.

8. Different Types
of
K-maps

9. Two Variable K-map(continued)
The K-Map is just a different form of the truth table.
V
WXF
WX
Minterm – 0001
Minterm – 1010
Minterm – 2101
Minterm – 3110
V
0 1
2 3
X
W
W
X
10
10

10. Two Variable K-map Grouping
V
0 0
0 0
B
A
A
Groups of One – 4
1
A B
B

11. Groups of Two – 2
Two Variable K-Map Groupings
Group of Four
V
0 0
0 0
B
A
A
B
1
B
1
V
1 1
1 1
B
A
A
1
B

12. Three Variable K-map (continued)
K-map from truth table.
WXYF
WXY
Minterm – 0000 1
Minterm – 1001 0
Minterm – 2010 0
Minterm – 3011 0
Minterm – 4100 0
Minterm – 5101 1
Minterm – 6110 1
Minterm – 7111 0
V
0 1
2 3
6 7
4 5
Y
X W
Y
1
X W
X W
X W
0
00
01
10
Only one
variable changes
for every row
cnge
12

13. Three Variable K-Map Groupings
V
0 0
0 0
0 0
0 0
C C
B A
B A
BA
BA
B A
1 1
B A
1 1
B A
1 1
B A
1 1
1
C A
1
1
C A
1
1
C A
1
1
C B
1
1
C B
1
1
C A
11
C B
1
1
C B
1
Groups of One – 8 (not shown)
Groups of Two – 12

14. Three Variable K-Map Groupings
Groups of Four – 6 Group of Eight - 1
V
1 1
1 1
1 1
1 1
C C
B A
B A
BA
BA
1
V
0 0
0 0
0 0
0 0
C C
B A
B A
BA
BA
1
C
1
1
1
1
C
1
1
1
A
1 1
1 1
B
1 1
1 1
A
1 1
1 1
B
1 1
1 1

15. Truth Table to K-Map Mapping
Four Variable K-Map
W X Y Z F
WXYZ
Minterm – 0 0 0 0 0 0
Minterm – 1 0 0 0 1 1
Minterm – 2 0 0 1 0 1
Minterm – 3 0 0 1 1 0
Minterm – 4 0 1 0 0 1
Minterm – 5 0 1 0 1 1
Minterm – 6 0 1 1 0 0
Minterm – 7 0 1 1 1 1
Minterm – 8 1 0 0 0 0
Minterm – 9 1 0 0 1 0
Minterm –
10
1 0 1 0 1
Minterm –
11
1 0 1 1 0
Minterm –
12
1 1 0 0 1
Minterm –
13
1 1 0 1 0
Minterm –
14
1 1 1 0 1
Minterm –
15
1 1 1 1 1
V
0 1 3 2
4 5 7 6
12 13 15 14
8 9 11 10
X W
X W
X W
X W
Z Y Z Y
ZY Z Y
1 011
1
101
0 100
0 1
10

16. FOUR VARIABLE K-MAP
GROUPINGS
V
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
B A
B A
BA
BA
D C D C D C D C
C B
1 1
1 1
D B
1 1
1 1
D A
1
1
1
1
C B
1 1
1 1
D B
1
1
1
1
D A
1
1
1
1 D B
11
11

17. FOUR VARIABLE K-MAP
GROUPINGS
Groups of Eight – 8 (two shown)
V
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
B A
B A
BA
BA
D C D C D C D C
B
1 1 1 1
1 1 1 1
D
1
1
1
1
1
1
1
1
Group of Sixteen – 1
V
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
B A
B A
BA
BA
D C D C D C D C
1

18. Simplyfing Logic
Expression
by
Different types of K-Map

19. TWO VARIABLE K-MAP
Differ in the value of y in
m0 and m1.
Differ in the value of x in
m0 and m2.
y = 0 y = 1
x = 0
m
0
= m
1
=
x = 1
m
2
=

m
3
=

yx yx
yx
yx

20. Two Variable K-Map
Simplified sum-of-products (SOP) logic expression for the logic
function F
1
.
V
1 1
0 0
K
J
J
K
J
JF=
1
JKF
1
001
011
100
110
20

21. Three Variable Maps

A three variable K-map :
yz=00 yz=01 yz=11 yz=10
x=0 m
0
m
1 m
3
m
2

x=1 m
4
m
5
m
7
m
6

Where each minterm corresponds to the product terms:
yz=00 yz=01 yz=11 yz=10
x=0
x=1
zyx zyx zyx zyx
zyx zyx zyx zyx

22. Four Variable K-Map
Simplified sum-of-products (SOP) logic expression for the logic
function F
3
.
T SU RU T SU S RF +++=
3
R S T U F
3
0 0 0 0 0
0 0 0 1 1
0 0 1 0 0
0 0 1 1 1
0 1 0 0 0
0 1 0 1 1
0 1 1 0 1
0 1 1 1 1
1 0 0 0 0
1 0 0 1 1
1 0 1 0 0
1 0 1 1 0
1 1 0 0 1
1 1 0 1 0
1 1 1 0 1
1 1 1 1 1
V
0 1 1 0
0 1 1 1
1 0 1 1
0 1 0 0
S R
S R
S R
S R
U T U T U T U T
U R
T S
U S R
U T S

23. Five variable K-map is formed using two connected 4-
variable maps:
Chapter 2 - Part 2 23
23
0
1 5
4
VWX
YZ
V
Z
000001
00
13

12
011
9
8
010
X
3
2 6
7
14
15
10
11
01
11
10
Y
16
17 21
20
29

28
25
24
19
18 22
23
30
31
26
27
100101111110
W W
X
Five Variable K-Map

24. Don’t-care condition
Minterms that may produce either
0 or 1 for the function.
Marked with an ‘x’
in the K-map.
These don’t-care conditions can
be used to provide further simplification.

25. SOME YOU GROUP, SOME YOU
DON’T
V
X 0
1 0
0 0
X 0
C C
B A
B A
BA
BA
C A
This don’t care condition was treated as a
(1).
There was no advantage in treating
this don’t care condition as a (1),
thus it was treated as a (0) and not
grouped.

26. Don’t Care Conditions
Simplified sum-of-products (SOP) logic expression for the logic
function F
4
.
S RT RF +=
4
R S T U F
4
0 0 0 0 X
0 0 0 1 0
0 0 1 0 1
0 0 1 1 X
0 1 0 0 0
0 1 0 1 X
0 1 1 0 X
0 1 1 1 1
1 0 0 0 1
1 0 0 1 1
1 0 1 0 1
1 0 1 1 X
1 1 0 0 X
1 1 0 1 0
1 1 1 0 0
1 1 1 1 0
V
X 0 X 1
0 X 1 X
X 0 0 0
1 1 X 1
S R
S R
S R
S R
U T U T U T U T
T R
S R

27. Implicants
The group of 1s is called implicants.
Two types of Implicants:
Prime Implicants.
Essential Prime Implicants.

28. Prime and Essential Prime
Implicants
Chapter 2 - Part 2 28
DB
CB
11
1 1
1 1
B

D
A
11
11
1
ESSENTIAL Prime
Implicants

C

BD
CD
BD
Minterms covered by single prime implicant
DB

11
1 1
1 1
B
C
D
A
11
11
1
AD

BA

29. Example with don’t Care
Chapter 2 - Part 2 29
x
x
1
11
1
1
B
D
A
C
1
1
1
x
x
1
11
1
1
B
D
A
C
1
1
EssentialSelected

30. Besides some disadvantages like usage of
limited variables K-Map is very efficient
to simplify logic expression.
Conclusion

31. References
Wikipedia.com.
Digital Design by Morris Mano

32. Thank
You