Karnaugh Maps
Karnaugh Maps
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
Karnaugh Maps
a'b'
ab' ab a'b
a
b
Venn Diagrams
Each set of minterms represents a Boolean function.
Examples:
Alternative 3:
a a
OR
b ab a'b b m3 m1 and others…
ab' a m2 m0
'b'
2-variable K-maps
Equivalent labeling:
b b
a 0 1
0
equivalent to:
a
1
a a
b 1 0
equivalent to: 0
b
1
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
0 0 0 1
a 0 1 a 1 0
C = ab S = ab' + a'b
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.
b
b
bc
bc
a a 00 01 11 10
00 01 11 10
0 m0 m1 m3 m2
0 a'b'c a'b'c a'bc a'bc'
' OR
a m4 m5 m7 m6
a
1 ab'c' ab'c abc abc' 1
c
c
bc
a
00 01 11 10
0 m0 m1 m3 m2
m4 m5 m7 m6
1
a 0 1 0 0
1
y
yz
wx 00 01 11 10
00 m0 m1 m3 m2
m4 m5 m7 m6
01
x
m1 m1 m1 m1
11 2 3 5 4
w
m8 m9 m1 m1
10 1 0
z
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 m0 has neighbours
m1, m2, m4 and m8.
yz y
wx
m0 m1 m3 m2
m4 m5 m7 m6
x
m1 m1 m1 m1
w 2 3 5 4
m8 m9 m1 m1
1 0
z
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 25 = 32 squares.
5-variable K-maps
Organised as two 4-variable K-maps:
v' v
y y
yz yz
wx 00 01 11 10 wx 00 01 11 10
00 m0 m1 m3 m2 00 m1 m1 m1 m1
6 7 9 8
m4 m5 m7 m6 m2 m2 m2 m2
01 01
x 0 1 3 2 x
m1 m1 m1 m1 m2 m2 m3 m3
11 2 3 5 4 11 8 9 1 0
w w
m8 m9 m1 m1 m2 m2 m2 m2
10 1 0 10 4 5 7 6
z z
ef a'b' a'b ef
cd 00 01 11 10 10 11 01 00 cd
00 m0 m1 m3 m2 m1 m1 m1 m1 00
8 9 7 6
m4 m5 m7 m6 m2 m2 m2 m2
2 3 1 0
01 m1 m1 m1 m1 m3 m3 m2 m2 01
2 3 5 4 0 1 9 8
m8 m9 m1 m1 m2 m2 m2 m2 11
11 1 0 6 7 5 4
10 10
10 m4 m4 m4 m4 m5 m5 m5 m5 10
0 1 3 2 8 9 7 6
m4 m4 m4 m4 m6 m6 m6 m6
a 4 5 7 6 2 3 1 0
m3 m3 m3 m3 m5 m5 m5 m5
11 6 7 9 8 4 5 3 2
11
m3 m3 m3 m3 m5 m5 m4 m4
01 2 3 5 4 0 1 9 8 01
cd cd
00 01 11 10 10 11 01 00 ef
00ef ab' ab 00
01 1 1
x (cells with ‘0’ are not
1 1
w
11 shown for clarity)
1 1
10
z
Simplification Using K-maps
Each group of adjacent minterms (group size in
powers of twos) corresponds to a possible product
term of the given function.
y
yz
wx 00 01 11 10
00
A
01 1 1
x
11 1 1
w
10 1 1 B
z
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'
z
Simplification Using K-maps
Each product term of a group, w'xy' and wy,
represents the sum of minterms in 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
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
Simplification Using K-maps
Other possible valid groupings of a 4-variable K-map
include:
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1 1 1
1
Simplification Using K-maps
Groups of minterms must be
(1) rectangular, and
(2) have size in powers of 2’s.
Otherwise they are invalid groups. Some examples
of invalid groups:
1 1 1 1
1 1 1 1
1 1 1
1 1 1 1 1
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.
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
A
AB'C'D' + AC'D' + BC + A'CD AB
CD 00 01 11 10
= AB'C'D' + AC'D'(B+B') + BC + A'CD
00 1 1
= AB'C'D' + ABC'D' + AB'C'D' +
BC(A+A') + A'CD 01
D
= AB'C'D' + ABC'D' + ABC + A'BC + 11 1 1 1
A'CD C
10 1 1
= AB'C'D' + ABC'D' + ABC(D+D') +
A'BC(D+D') + A'CD(B+B') B
1 1 1 1 1 1
1 1 1 1 1 1
Simplest SOP Expressions
No redundant groups:
1 1 1 1
1 1 1 1
1 1
1 1
1 1 1 1
b
A
bc
a AB
00 01 11 10 CD 00 01 11 10
0 1 1 0 1 00 1 1 1
a 0 1 0 0 01 1 1
1 D
11 1 1 1
c C
10 1 1 1
B
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.
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.
Simplest SOP Expressions
Example:
f(A,B,C,D) = ∑ m(2,3,4,5,7,8,10,13,15)
A
AB
CD 00 01 11 10
00 1 1
All prime implicants
01 1 1
D
11 1 1 1
C
10 1 1
B
Simplest SOP Expressions
A
AB A
CD 00 01 11 10 AB
00 CD 00 01 11 10
1 1
01
1 1 D
00 1 1 Essential prime
C
11 1 1 1 01 1 1 implicants
10 1 1 D
11 1 1 1
B C
10 1 1
B
A
AB
CD 00 01 11 10
00 1 1 Minimum cover
01 1 1
D
11 1 1 1
C
10 1 1
B
Simplest SOP Expressions
A
AB
CD 00 01 11 10
A'BC'
00 1 1 AB'D'
01 1 1
D
11 1 1 1
C
10 1 1 BD
B
A'B'C
00 1
01 1 1 1
D
11 1 1 1
C
10 1
B
Getting POS Expressions
Simplified POS expression can 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:
A
AB
CD 00 01 11 10
00 1 0 0 1
01 1 1 0 1
D
11 1 1 0 1
C
10 1 0 0 1
B
Getting POS Expressions
A A
AB AB
CD 00 01 11 10 CD 00 01 11 10
K-map 00 1 0 0 1 00 0 1 1 0 K-map
of F 01 1 1 0 1 01 0 0 1 0 of F'
D D
11 1 1 0 1 11 0 0 1 0
C C
10 1 0 0 1 10 0 1 1 0
B B
WITH Don’t-cares: CD
C
AB 00 01 11 10
P = A'B'C'D' + B'CD + BC'D 00 1 1
+ BCD' + AD 01 1 1
B
11 X X X X
A
10 1 X X
D
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.
a a'b m0 m1
'b' OR
a ab' ab a m2 m3
Review – K-maps
b b
bc bc
a a
00 01 11 10 00 01 11 10
0 a'b'c a'b'c a'bc a'bc' 0 m0 m1 m3 m2
'
a ab'c' ab'c abc abc' a m4 m5 m7 m6
1 1
c c
y
yz
wx 00 01 11 10
00 m0 m1 m3 m2
m4 m5 m7 m6
x
01 m1 m1 m1 m1
w 2 3 5 4
11 m8 m9 m1 m1
1 0
10 z
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
00 1 1
Fill in the 1’s.
01 1 1
D
11 1 1 1
C
10 1 1
B
Examples
Example #1:
f(A,B,C,D) = ∑ m(2,3,4,5,7,8,10,13,15)
A
AB
CD 00 01 11 10
These are all the
00 1 1 prime implicants; but
01 1 1 do we need them
D
11 1 1 1
all?
C
10 1 1
B
Examples
Example #1:
f(A,B,C,D) = ∑ m(2,3,4,5,7,8,10,13,15)
A
AB
CD 00 01 11 10
00 1 1
Essential prime implicants:
01 1 1
D
11 1 1 1
B.D
C
10 1 1 A'.B.C'
B A.B'.D'
Examples
Example #1:
f(A,B,C,D) = ∑ m(2,3,4,5,7,8,10,13,15)
A
AB
CD 00 01 11 10
00 1 1
Minimum cover.
01 1 1
D EPIs: B.D, A'.B.C', A.B'.D'
11 1 1 1
C
1 1
+
10
B A'.B'.C
B
SUMMARY
A
AB
CD 00 01 11 10
00 1 1
Minimum cover
01 1 1
D
11 1 1 1
C
10 1 1
f(A,B,C,D) = BD + A'B'C + AB'D' + A'B.C'
B
Examples
Example #2:
f(A,B,C,D) = A.B.C + B'.C.D' + A.D + B'.C'.D'
A
AB
CD 00 01 11 10
00 1 1
Fill in the 1’s.
01 1 1
D
11 1 1
C
10 1 1 1
B
Examples
Example #2:
f(A,B,C,D) = A.B.C + B'.C.D' + A.D + B'.C'.D'
A
AB
CD 00 01 11 10
00 1 1
Find all PIs:
01 1 1
D
11 1 1 A.D
C
10 1 1 1 A.C
B B'.D'
00 X 1
Fill in the 1’s and X’s.
01 X
D
11 X X 1
C
10 1 1
B
Examples
Example #3 (with don’t cares):
f(A,B,C,D) = ∑ m(2,8,10,15) + ∑ d(0,1,3,7)
A
AB
CD 00 01 11 10 Do we need to have an
00 X 1 additional term A'.B' to
01 X cover the 2 remaining x’s?
D
11 X X 1 No, because all the 1’s
C
1 1 (minterms) have been
10
covered.
B
CD
AB
00 01 11 10
From K-map,
00 X 1 1 f ' = B.C' + B.D' + B'.D
01 X 1 1 1
D
Using DeMorgan’s theorem,
11 X X 1
C f = (B.C' + B.D' + B'.D)'
10 1 1
= (B'+C).(B'+D).(B+D')
B