### CS 140 Lecture 3

```CSE20 Lecture 15
Karnaugh Maps
Professor CK Cheng
CSE Dept.
UC San Diego
1
Example
Given F = Sm (3, 5), D = Sm (0, 4)
b
0
2
1
c
6
0
3
0
4
0
7
1
5
0
1
a
Primes: Sm (3), Sm (4, 5)
Essential Primes: Sm (3), Sm (4, 5)
Min exp: f(a,b,c) = a’bc + ab’
2
Boolean Expression
K-Map
Variable xi and its
compliment xi’

Two half planes Rxi,
and Rxi’
Product term P
(Pxi* e.g. b’c’)
 Intersect of Rxi* for all i
in P e.g. Rb’ intersect Rc’
Each minterm
 One element cell
Two minterms are adjacent
iff they differ by one and
only one variable, eg:

abc’d, abc’d’
The two cells are
neighbors
Each minterm has n
Each cell has n
neighbors

3
Procedure Input: Two sets of F R D
1) Draw K-map.
2) Expand all terms in F to their largest
sizes (prime implicants).
3) Choose the essential prime
implicants.
4) Try all combinations to find the
minimal sum of products. (This is the
most difficult step)
4
Example
Given F = Sm (0, 1, 2, 8, 14)
D = Sm (9, 10)
1. Draw K-map
b
0
4
1
1
0
5
1
3
c
12
0
2
1
13
0
6
1
0
0
7
8
9
0
15
0
14
0
11
d
0
10
1
a
5
2. Prime Implicants: Largest rectangles that intersect On Set but
not Off Set that correspond to product terms.
Sm (0, 1, 8, 9), Sm (0, 2, 8, 10), Sm (10, 14)
3. Essential Primes: Prime implicants covering elements in F that
are not covered by any other primes.
Sm (0, 1, 8, 9), Sm (0, 2, 8, 10), Sm (10, 14)
4. Min exp: Sm (0, 1, 8, 9) + Sm (0, 2, 8, 10) + Sm (10, 14)
f(a,b,c,d) = b’c’ + b’d’+ acd’
6
Another example
Given F = Sm (0, 3, 4, 14, 15)
D = Sm (1, 11, 13)
1. Draw K-map
b
0
4
1
1
1
5
3
c
2
12
1
0
0
6
0
13
0
7
8
0
0
9
15
14
1
1
0
11
10
a
d
0
7
2. Prime Implicants: Largest rectangles that intersect On Set but
not Off Set that correspond to product terms.
E.g. Sm (0, 4), Sm (0, 1), Sm (1, 3), Sm (3, 11), Sm (14, 15),
Sm (11, 15), Sm (13, 15)
3. Essential Primes: Prime implicants covering elements in F that
are not covered by any other primes.
E.g. Sm (0, 4), Sm (14, 15)
4. Min exp: Sm (0, 4), Sm (14, 15), ( Sm (3, 11) or Sm (1,3) )
f(a,b,c,d) = a’c’d’+ abc+ b’cd (or a’b’d)
8
Five variable K-map
c
d
c
0
4
12
8
16
20
28
24
1
5
13
9
17
21
29
25
3
7
15
11
19
23
31
27
2
6
14
10
18
22
30
26
e
d
b
e
b
a
Neighbors of m5 are: minterms 1, 4, 7, 13, and 21
Neighbors of m10 are: minterms 2, 8, 11, 14, and 26
9
Six variable K-map
d
e
d
0
4
12
8
16
20
28
24
1
5
13
9
17
21
29
25
3
7
15
11
19
23
31
27
2
6
14
10
18
22
30
26
e
c
d
e
f
c
d
32
36
44
40
48
52
60
56
33
37
45
41
49
53
61
57
35
39
47
43
51
55
63
59
34
38
46
42
50
54
62
58
f
e
c
f
f
a
c
b
10
Implicant: A product term that has non-empty intersection with
on-setF and does not intersect with off-set R .
Prime Implicant: An implicant that is not covered by any other
implicant.
Essential Prime Implicant: A prime implicant that has an element
in on-set F but this element is not covered by any other prime
implicants.
Implicate: A sum term that has non-empty intersection with off-set
R and does not intersect with on-set F.
Prime Implicate: An implicate that is not covered by any other
implicate.
Essential Prime Implicate: A prime implicate that has an element in
off-set R but this element is not covered by any other prime
implicates.
11
Min product of sums
Given F = Sm (3, 5), D = Sm (0, 4)
b
0
-
1
c
2
0
3
0
6
0
7
1
4
-
5
0
1
a
Prime Implicates: PM (0,1), PM (0,2,4,6), PM (6,7)
Essential Primes Implicates: PM (0,1), PM (0,2,4,6), PM (6,7)
Min exp: f(a,b,c) = (a+b)(c )(a’+b’)
12
Corresponding Circuit
a
b
f(a,b,c,d)
a’
b’
c
13
Quiz
Given F = Sm (0, 6), D = Sm (2, 7),
1. Fill the Karnaugh map.
2. Identify all prime implicates
3. Identify all essential primes.
4. Find a minimal expression in
product of sums format.
14
Another min product of sums example
Given R = Sm (3, 11, 12, 13, 14)
D = Sm (4, 8, 10)
b
K-map
0
4
1
1
5
1
3
c
2
12
0
1
0
6
-
13
1
7
8
1
1
9
0
15
14
1
11
1
10
0
a
d
0
15
Prime Implicates: PM (3,11), PM (12,13), PM(10,11),
PM (4,12), PM (8,10,12,14)
Essential Primes: PM (8,10,12,14), PM (3,11),
PM(12,13)
Exercise: Derive f(a,b,c,d) in minimal product of sums
expression.
16
Summary
•Karnaugh Maps: Two dimensional truth
table which mimics an n-variable cube