Digital Logic design. Chapter 3, Karnaugh maps

Include only Kmaps and related maths

1. LOGIC DESIGN
Ch 4
Karnaugh Maps

2. KARNAUGH MAPS
Introduction
Venn Diagrams
2-variable K-maps
3-variable K-maps
4-variable K-maps
5-variable and larger K-maps
Simplification using K-maps
2

3. KARNAUGH MAPS
Converting to Minterms Form
Simplest SOP Expressions
Getting POS Expressions
Don’t-care Conditions
Review
Examples
3

4. INTRODUCTION
Systematic method to obtain simplified sum-of-
products(SOPs) Boolean expressions.
Objective: Fewestpossible terms/literals.
Diagrammatic technique based on a special form of
Venn diagram.
Advantage: Easy with visual aid.
Disadvantage: Limited to 5 or 6 variables.
4

5. VENN DIAGRAMS
Venn diagram to represent the space of minterms.
Example of 2 variables (4 minterms):
5
ab' a'b
a'b'
ab
a
b

6. 2-VARIABLE K-MAPS
Karnaugh-map(K-map) is an abstract form of Venn
diagram, organised as a matrix of squares, where
each square represents a minterm
adjacent squares always differ by just one literal(so that the
unifying theorem may apply: a + a' = 1)
For 2-variable case (e.g.: variables a,b), the map can be
drawn as:
6

7. 2-VARIABLE K-MAPS
Alternative layouts of a 2-variable (a, b) K-map
7
a'b'ab'
a'bab
b
a
m0m2
m1m3
b
a
OR
Alternative 2:
a'b'a'b
ab'ab
a
b
m0m1
m2m3
a
b
Alternative 1:
OR
aba'b
ab'a'b'
b
a
m3m1
m2m0
b
a
OR
Alternative 3:
and others…

8. 2-VARIABLE K-MAPS
Equivalent labeling:
8
a
b
equivalent to:
a
b
0 1
0
1
b
a
equivalent to:
b
a
1 0
0
1

9. 2-VARIABLE K-MAPS
The K-map for a function is specified by putting
a ‘1’ in the square corresponding to a minterm
a ‘0’ otherwise
For example: Carry and Sum of a half adder.
9
0 0
0 1
a
b
0 1
1 0
a
b
C = ab S = ab' + a'b

10. 3-VARIABLE K-MAPS
There are 8 minterms for 3 variables (a, b, c). Therefore,
there are 8 cells in a 3-variable K-map.
10
ab'c'ab'ca
b
abc abc'
a'b'c'a'b'ca'bca'bc'0
1
00 01 11 10
c
a
bc
OR
m4m5a
b
m7m6
m0m1m3m20
1
00 01 11 10
c
a
bc
Note Gray codesequenceAbove arrangement ensures that minterms
of adjacent cells differ by only ONE literal.
(Other arrangements which satisfy this
criterion may also be used.)

11. 3-VARIABLE K-MAPS
There is wrap-aroundin the K-map:
a'b'c' (m0) is adjacent to a'bc' (m2)
ab'c' (m4) is adjacent to abc' (m6)
11
m4m5m7m6
m0m1m3m20
1
00 01 11 10
a
bc
Each cell in a 3-variable K-map has 3 adjacent neighbours.
In general, each cell in an n-variable K-map has nadjacent
neighbours. For example, m0has 3 adjacent neighbours:
m1, m2and m4.

12. SOLVE IT YOURSELF (EXERCISE
6.1)
1.The K-map of a 3-variable function Fis shown below.
What is the sum-of-minterms expression of F?
2.Draw the K-map for this function A:
A(x, y, z) = x.y + y.z’ + x’.y’.z
12
0 1
a
b
0 0
1 0 0 10
1
00 01 11 10
c
a
bc

13. 4-VARIABLE K-MAPS
There are 16 cells in a 4-variable (w, x, y, z) K-map.
13
m4m5
w
y
m7m6
m0m1m3m200
01
11
10
00 01 11 10
z
wx
yz
m12m13m15m14
m8m9m11m10
x

14. 4-VARIABLE K-MAPS
There are 2 wrap-arounds: a horizontal wrap-around and a
vertical wrap-around.
Every cell thus has 4 neighbours. For example, the cell
corresponding to minterm m0has neighbours m1, m2, m4
and m8.
14
m4m5
w
y
m7m6
m0m1m3m2
z
wx
yz
m12m13m15m14
m8m9m11m10
x

15. 5-VARIABLE K-MAPS
Maps of more than 4 variables are more difficult to
use because the geometry (hyper-cube
configurations) for combining adjacent squares
becomes more involved.
For 5 variables, e.g. vwxyz, need 2
5
= 32 squares.
15

16. 5-VARIABLE K-MAPS
Organised as two 4-variable K-maps:
16
Corresponding squares of each map are adjacent.
Can visualise this as being one 4-variable mapon TOP of the
other 4-variable map.
m20m21
w
y
m23m22
m16m17m19m1800
01
11
10
00 01 11 10
z
wx
yz
m28m29m31m30
m24m25m27m26
x
m4m5
w
y
m7m6
m0m1m3m200
01
11
10
00 01 11 10
z
wx
yz
m12m13m15m14
m8m9m11m10
x
v ' v

17. LARGER K-MAPS
6-variable K-map is pushing the limit of human
“pattern-recognition” capability.
K-maps larger than 6 variables are practically
unheard of!
Normally, a 6-variable K-map is organised as four 4-
variable K-maps, which are mirrored along two axes.
17

18. LARGER K-MAPS
Try stretch your recognition capability by finding simpliest
sum-of-products expression for Sm(6,8,14,18,23,25,27,29,41,45,57,61).
18
w
a'b'
m000
01
11
10
00 01 11 10cd
ef
m1m3m2
m4m5m7m6
m12m13m15m14
m8m9m11m10
m4010
11
01
00
00 01 11 10
cd
ef
m41m43m42
m44m45m47m46
m36m37m39m38
m32m33m35m34
m18
00
01
11
10
10 11 01 00
cd
ef
m19m17m16
m22m23m21m20
m30m31m29m28
m26m27m25m24
m58 10
11
01
00
10 11 01 00
cd
ef
m59m57m56
m62m63m61m60
m54m55m53m52
m50m51m49m48
a'b
ab' ab
a
b

19. SIMPLIFICATION USING K-MAPS
Based on the Unifying Theorem:
A + A' = 1
In a K-map, each cell containing a ‘1’ corresponds to a
minterm of a given function F.
Each group of adjacent cells containing ‘1’ (group must
have size in powersof twos: 1, 2, 4, 8, …) then corresponds
to a simpler product termof F.
Grouping 2 adjacent squares eliminates 1 variable, grouping 4
squares eliminates 2 variables, grouping 8 squares eliminates 3
variables, and so on. In general, grouping 2
n
squares eliminates n
variables.
19

20. SIMPLIFICATION USING K-MAPS
Group as many squares as possible.
The larger the group is, the fewer the number of literals in the
resulting product term.
Select as few groups as possible to cover all the squares
(minterms) of the function.
The fewer the groups, the fewer the number of product terms in
the minimized function.
20

21. SIMPLIFICATION USING K-MAPS
Example:
F(w,x,y,z) = w'xy'z' + w'xy'z + wx'yz'
+ wx'yz + wxyz' + wxyz
= Sm(4, 5, 10, 11, 14, 15)
21
z
1 1
w
y
00
01
11
10
00 01 11 10wx
yz
1 1
1 1
x(cells with ‘0’ are not
shown for clarity)

22. SIMPLIFICATION USING K-MAPS
Each group of adjacent minterms (group size in
powers of twos) corresponds to a possible product
termof the given function.
22
1 1
w
00
01
11
10
00 01 11 10
z
wx
yz
1 1
1 1
x
A
B
y

23. SIMPLIFICATION USING K-MAPS
There are 2 groups of minterms: A and B, where:
A= w'xy'z' + w'xy'z
= w'xy'(z' + z)
= w'xy'
B= wx'yz' + wx'yz + wxyz' + wxyz
= wx'y(z' + z) + wxy(z' + z)
= wx'y + wxy
= w(x'+x)y
= wy
23
1 1
w
00
01
11
10
00 01 11 10
z
wx
yz
1 1
1 1
x
A
B
y

24. SIMPLIFICATION USING K-MAPS
Each product term of a group, w'xy' and wy, represents the
sum of mintermsin that group.
Boolean function is therefore the sum of product terms
(SOP) which represent all groups of the minterms of the
function.
F(w,x,y,z) = A + B = w'xy' + wy
24

25. SIMPLIFICATION USING K-MAPS
Larger groups correspond to product terms of fewer literals.
In the case of a 4-variable K-map:
1 cell= 4 literals, e.g.: wxyz, w'xy'z
2 cells= 3 literals, e.g.: wxy, wy'z'
4 cells= 2 literals, e.g.: wx, x'y
8 cells= 1 literal, e.g.: w, y', z
16 cells= no literal, e.g.: 1
25

26. SIMPLIFICATION USING K-MAPS
Other possible valid groupings of a 4-variable K-map
include:
26
1
11
1
1
1
1
1
P
1
11
11
111
P
1
1
1
1
P

27. SIMPLIFICATION USING K-MAPS
Groups of minterms must be
(1) rectangular, and
(2) have size in powers of 2’s.
Otherwise they are invalidgroups. Some examples of
invalid groups:
27
1
11
1 1
111
1
1
O
1
1
1
1
1
1
O

28. CONVERTING TO MINTERMS FORM
The K-map of a function is easily drawn when the
function is given in canonical sum-of-products, or sum-
of-minterms form.
What if the function is not in sum-of-minterms?
Convert it to sum-of-products (SOP) form.
Expand the SOP expression into sum-of-minterms
expression, or fill in the K-map directly based on the SOP
expression.
28

29. CONVERTING TO MINTERMS FORM
Example:
f(A,B,C,D) = A(C+D)'(B'+D') + C(B+C'+A'D)
= A(C'D')(B'+D') + BC + CC' + A'CD
= AB'C'D' + AC'D' + BC + A'CD
29
11
C
A
00
01
11
10
00 01 11 10
B
CD
AB
D
11 1
1 1
AB'C'D' + AC'D'+ BC + A'CD
= AB'C'D' + AC'D'(B+B') + BC+ A'CD
= AB'C'D' + ABC'D' + AB'C'D' +
BC(A+A') + A'CD
= AB'C'D' + ABC'D' + ABC + A'BC +
A'CD
= AB'C'D' + ABC'D' + ABC(D+D') +
A'BC(D+D') + A'CD(B+B')
= AB'C'D' + ABC'D' + ABCD + ABCD' +
A'BCD + A'BCD' + A'B'CD

30. SIMPLEST SOP EXPRESSIONS
To find the simplest possible sum of products(SOP)
expression from a K-map, you need to obtain:
minimum number of literals per product term; and
minimum number of product terms
This is achieved in K-map using
bigger groupingsof minterms (prime implicants) where
possible; and
no redundant groupings (look foressential prime implicants)
Implicant:a product term that could be used
to cover minterms of the function.
30

31. SIMPLEST SOP EXPRESSIONS
A prime implicantis a product term obtained by
combining the maximum possible number of
minterms from adjacentsquares in the map.
Use bigger groupings (prime implicants) where
possible.
31
111
11
1
O
111
111
P

32. SIMPLEST SOP EXPRESSIONS
No redundant groups:
An essential prime implicantis a prime implicant that
includes at least one minterm that is not covered by
any other prime implicant.
32
1
1
1
11
1
P
1
1
1
1
1
11
1
O
1
1
Essential prime implicants

33. SOLVE IT YOURSELF (EXERCISE 6.2)
Q.Identify the prime implicants and the essential
prime implicants of the two K-maps below.
33
0 1
a
b
0 0
1 1 0 10
1
00 01 11 10
c
a
bc
11
C
A
00
01
11
10
00 01 11 10
B
CD
AB
D
11 1
1 1
1
11
1

34. SIMPLEST SOP EXPRESSIONS
Algorithm 1 (non optimal):
1. Count the number of adjacencies for each minterm on the
K-map.
2. Select an uncovered minterm with the fewest number of
adjacencies. Make an arbitrary choice if more than one
choice is possible.
3. Generate a prime implicant for this minterm and put it in the
cover. If this minterm is covered by more than one prime
implicant, select the one that covers the most uncovered
minterms.
4. Repeat steps 2 and 3 until all the minterms have been
covered.
34

35. SIMPLEST SOP EXPRESSIONS
Algorithm 2 (non optimal):
1. Circle all prime implicants on the K-map.
2. Identify and select all essential prime implicants for the
cover.
3. Select a minimum subset of the remaining prime implicants
to complete the cover, that is, to cover those minterms not
covered by the essential prime implicants.
35

36. SIMPLEST SOP EXPRESSIONS
Example:
f(A,B,C,D) = m(2,3,4,5,7,8,10,13,15)
36
All prime implicants
1
1
C
A
00
01
11
10
00 01 11 10
B
CD
AB
1
1
1
1
D
1
1
1

37. SIMPLEST SOP EXPRESSIONS
37
B
1
1
C
A
00
01
11
10
00 01 1110CD
AB
1
1
1
1
D
1
1
1
1
1
C
A
00
01
11
10
00 01 11 10
B
CD
AB
1
1
1
1
D
1
1
1
Essential prime
implicants
1
1
C
A
00
01
11
10
00 01 11 10
B
CD
AB
1
1
1
1
D
1
1
1
Minimum cover

38. SIMPLEST SOP EXPRESSIONS
38
1
1
C
A
00
01
11
10
00 01 11 10
B
CD
AB
1
1
1
1
D
1
1
1
BD
AB'D'
A'BC'
A'B'C
f(A,B,C,D) = BD + A'B'C + AB'D' + A'BC'

39. SOLVE IT YOURSELF (EXERCISE 6.3)
Q.Find the simplified expression for G(A,B,C,D).
39
1
C
A
00
01
11
10
00 01 11 10
B
CD
AB
D
111
1
1
11

40. GETTING POS EXPRESSIONS
Simplified POS expressioncan be obtained by grouping the
maxterms (i.e. 0s) of given function.
Example:
Given F=m(0,1,2,3,5,7,8,9,10,11), we first draw the
K-map, then group the maxterms together:
40
1
1
C
A
00
01
11
10
00 01 11 10
B
CD
AB
1
0
1
1
D
1
1
1 1
10
00
00

41. GETTING POS EXPRESSIONS
This gives the SOP of F' to be:
F' = BD' + AB
To get POS of F, we have:
F = (BD' + AB)'
= (BD')'(AB)' DeMorgan
= (B'+D)(A'+B')DeMorgan
41
0
0
C
A
00
01
11
10
00 01 11 10
B
CD
AB
0
1
0
0
D
0
0
0 0
01
11
11
1
1
C
A
00
01
11
10
00 01 11 10
B
CD
AB
1
0
1
1
D
1
1
1 1
10
00
00
K-map
of F
K-map
of F'

42. DON’T-CARE CONDITIONS
In certain problems, some
outputs are not specified.
These outputs can be either ‘1’ or
‘0’.
They are called don’t-care
conditions, denoted by X (or
sometimes, d).
Example: An odd parity generator
for BCD code which has 6 unused
combinations.
42No.ABCDP
000001
100010
200100
300111
401000
501011
601101
701110
810000
910011
101010X
111011X
121100X
131101X
141110X
151111X

43. DON’T-CARE CONDITIONS
Don’t-care conditions can be used to help simplify
Boolean expression further in K-maps.
They could be chosen to be either ‘1’ or ‘0’, depending
on which gives the simpler expression.
43

44. DON’T-CARE CONDITIONS
For comparison:
WITHOUT Don’t-cares:
P = A'B'C'D’ + A'B'CD + A'BC'D
+ A'BCD' + AB'C'D
WITH Don’t-cares:
P = A'B'C'D' + B'CD + BC'D
+ BCD' + AD
44
1
A
C
00
01
11
10
00 01 11 10
D
AB
CD
1
B
1
1
1
1
A
C
00
01
11
10
00 01 11 10
D
AB
CD
1
B
1
1
1
XX
XXXX

45. REVIEW –THE TECHNIQUES
Algebraic Simplification.
requires skill but extremely open-ended.
Karnaugh Maps.
can obtain simplified standard forms.
easy for humans (pattern-matching skills).
limited to not more than 6 variables.
Other computer-aided techniques such as Quine-
McCluskey method
45

46. REVIEW –K-MAPS
Characteristics of K-map layouts:
(i) each minterm in one square/cell
(ii) adjacent/neighbouring minterms differ by only 1 literal
(iii) n-literal minterm has nneighbours/adjacent cells
Valid 2-, 3-, 4-variable K-maps
46
a'b'a'b
ab'ab
a
b
m0m1
m2m3
a
b
OR

47. REVIEW –K-MAPS
47
ab'c'ab'ca
b
abc abc'
a'b'c'a'b'ca'bca'bc'0
1
00 01 11 10
c
a
bc
m4m5a
b
m7m6
m0m1m3m20
1
00 01 11 10
c
a
bc
m4m5
w
y
m7m6
m0m1m3m200
01
11
10
00 01 11 10
z
wx
yz
m12m13m15m14
m8m9m11m10
x

48. REVIEW –K-MAPS
Groupings to select product-terms must be:
(i) rectangular in shape
(ii) in powers of twos (1, 2, 4, 8, etc.)
(iii) always select largest possible groupings of minterms
(i.e. prime implicants)
(iv) eliminate redundant groupings
Sum-of-products (SOP) form obtained by selecting
groupings of minterms (corresponding to product
terms).
48

49. REVIEW –K-MAPS
Product-of-sums (POS) form obtained by selecting
groupings of maxterms (corresponding to sum terms) and
by applying DeMorgan’s theorem.
Don’t cares, marked by X (or d), can denote either 1 or 0.
They could therefore be selected as 1 or 0 to further
simplify expressions.
49

50. EXAMPLES
Example #1:
f(A,B,C,D) = m(2,3,4,5,7,8,10,13,15)
50
Fill in the 1’s.
1
1
C
A
00
01
11
10
00 01 11 10
B
CD
AB
1
1
1
1
D
1
1
1

51. EXAMPLES
Example #1:
f(A,B,C,D) = m(2,3,4,5,7,8,10,13,15)
51
These are all the
prime implicants; but
do we need them
all?
1
1
C
A
00
01
11
10
00 01 11 10
B
CD
AB
1
1
1
1
D
1
1
1

52. EXAMPLES
Example #1:
f(A,B,C,D) = m(2,3,4,5,7,8,10,13,15)
52
Essential prime implicants:
B.D
A'.B.C'
A.B'.D'
1
1
C
A
00
01
11
10
00 01 11 10
B
CD
AB
1
1
1
1
D
1
1
1

53. EXAMPLES
Example #1:
f(A,B,C,D) = m(2,3,4,5,7,8,10,13,15)
53
Minimum cover.
EPIs: B.D, A'.B.C', A.B'.D'
+
A'.B'.C
1
1
C
A
00
01
11
10
00 01 11 10
B
CD
AB
1
1
1
1
D
1
1
1
f(A,B,C,D) = B.D + A'.B.C' + A.B'.D' + A'.B'.C

54. EXAMPLES
54
1
1
C
A
00
01
11
10
00 01 11 10
B
CD
AB
1
1
1
1
D
1
1
1
1
1
C
A
00
01
11
10
00 01 11 10
B
CD
AB
1
1
1
1
D
1
1
1
B
1
1
C
A
00
01
11
10
00 01 1110CD
AB
1
1
1
1
D
1
1
1
Essential prime
implicants
Minimum cover
SUMMARY
f(A,B,C,D) = BD + A'B'C + AB'D' + A'B.C'

55. EXAMPLES
Example #2:
f(A,B,C,D) = A.B.C + B'.C.D' + A.D + B'.C'.D'
55
Fill in the 1’s.
1
1
C
A
00
01
11
10
00 01 11 10
B
CD
AB
1
1
1
D
1
1
11

56. EXAMPLES
Example #2:
f(A,B,C,D) = A.B.C + B'.C.D' + A.D + B'.C'.D'
56
Find all PIs:
A.D
A.C
B'.D'
1
1
C
A
00
01
11
10
00 01 11 10
B
CD
AB
1
1
1
D
1
1
11
Are all ‘1’s covered by the PIs? Yes, so the
answer is: f(A,B,C,D) = A.D + A.C + B'.D'

57. EXAMPLES
Example #3 (with don’t cares):
f(A,B,C,D) = m(2,8,10,15) + d(0,1,3,7)
57
Fill in the 1’s and X’s.
1X
C
A
00
01
11
10
00 01 11 10
B
CD
AB
X1
X
D
11
X

58. EXAMPLES
Example #3 (with don’t cares):
f(A,B,C,D) = m(2,8,10,15) + d(0,1,3,7)
58
1X
C
A
00
01
11
10
00 01 11 10
B
CD
AB
X1
X
D
11
X
f(A,B,C,D) = B'.D' + B.C.D
Do we need to have an
additional term A'.B' to
cover the 2 remaining x’s?
No, because all the 1’s
(minterms) have been
covered.

59. EXAMPLES
To find simplest POS expression for example #2:
f(A,B,C,D) = A.B.C + B'.C.D' + A.D + B'.C'.D'
Draw the K-map of the complement of f, f '.
59
1
1
C
A
00
01
11
10
00 01 11 10
B
CD
AB
1
1
D
11
1
From K-map,
f ' = A'.B + A'.D + B.C'.D'
Using DeMorgan’s theorem,
f = (A'.B + A'.D + B.C'.D')'
= (A+B').(A+D').(B'+C+D)

60. EXAMPLES
•To find simplest POS expression for example #3:
f(A,B,C,D) = m(2,8,10,15) + d(0,1,3,7)
•Draw the K-map of the complement of f, f '.
f '(A,B,C,D) = m(4,5,6,9,11,12,13,14) + d(0,1,3,7)
60
From K-map,
f ' = B.C' + B.D' + B'.D
Using DeMorgan’s theorem,
f = (B.C' + B.D' + B'.D)'
= (B'+C).(B'+D).(B+D')
1
1
C
A
00
01
11
10
00 01 11 10
B
CD
AB
1
1
D
11
1
X
X
X
X
1

61. END OF SEGMENT
61