�ݺ�ߣ

KARNAUGH MAP METHOD
KARNAUGH MAP METHOD
‰The Karnaugh map is a graphical device used to simplify a logic
equation or to convert a truth table to its corresponding logic
circuit in a simple, orderly process.
‰Although a Karnaugh map (henceforth abbreviated K map) can
be used for problems involving any number of input variables,
its practical usefulness is limited to six variables.
‰The following discussion will be limited to problems with up to
four inputs, since even five-and six- input problems are too
involved and are best done by a computer program.

Karnaugh Map Format
Karnaugh Map Format
1. The truth table gives the value of output X for each
combination of input values. The K map gives the
same information in a different format. Each case in
the truth table corresponds to a square in the K
map.
2. The K map squares are labeled so that horizontally
adjacent square differs only in one variable.
3. In order for vertically and horizontally adjacent
squares to differ in only one variable, the top-to-
bottom labeling must be done in the order shown-.
The same is true of the left-to-right labeling.
4. Once a K map has been filled with 0s and 1s, the
sum-of-product expression for the output X can be
obtained by ORing together those squares that
contain a 1.
B
A
AB
B
A
B
A ,
,
,

‰The expression for output X can be simplified by
properly combining those squares in the K map
which contain 1s.
‰The process for combining these 1s is called
looping.
Looping
Looping

Looping Groups of Two (pairs)
0 0
1 0
1 0
0 0
C C
B
A
B
A
B
A
B
A
0 0
1 1
0 0
0 0
C C
B
A
B
A
B
A
B
A
C
B
Y =
B
A
Y =
(a)
(b)

Looping Groups of Two (pairs) (Continued)
1 0
0 0
0 0
1 0
C C
B
A
B
A
B
A
B
A
C
B
Y =
(c)
™
™Looping a pair of adjacent 1s in a K map eliminates the variable
Looping a pair of adjacent 1s in a K map eliminates the variable
that appears in complemented and uncomplemented form.
that appears in complemented and uncomplemented form.

Redundant Looping
Redundant Looping
0 0 1 1
0 0 0 0
0 0 0 0
1 0 0 1
B
A
B
A
B
A
B
A
D
C D
C D
C D
C
D
B
A
C
B
A
D
C
B Redundant Looping
D
B
A
C
B
A
Y +
=
D
C
B
D
B
A
C
B
A
Y +
+
=
NOT
NOT

Looping Groups of Four (Quads):
0 0 0 1
0 0 0 1
0 0 0 1
0 0 0 1
B
A
B
A
B
A
B
A
D
C D
C D
C D
C
0 0 0 0
0 0 0 0
1 1 1 1
0 0 0 0
B
A
B
A
B
A
B
A
D
C D
C D
C D
C
(a)
(b)
D
C
X =
AB
X =

Looping Groups of Four (Quads) (continued…)
0 0 0 0
0 1 1 0
0 1 1 0
0 0 0 0
B
A
B
A
B
A
B
A
D
C D
C D
C D
C
0 0 0 0
0 0 0 0
1 0 0 1
1 0 0 1
B
A
B
A
B
A
B
A
D
C D
C D
C D
C
(c) (d)
BD
=
X D
A
X =

Looping Groups of Four (Quads) (continued…)
1 0 0 1
0 0 0 0
0 0 0 0
1 0 0 1
B
A
B
A
B
A
B
A
D
C D
C D
C D
C
(e)
D
B
=
X
™
™ Looping a quad of 1s eliminates the two variables that appear i
Looping a quad of 1s eliminates the two variables that appear in
n
both complemented and uncomplemented form.
both complemented and uncomplemented form.

Looping Groups of Eight (octets):
0 0 0 0
1 1 1 1
1 1 1 1
0 0 0 0
B
A
B
A
B
A
B
A
D
C D
C D
C D
C
1 1 0 0
1 1 0 0
1 1 0 0
1 1 0 0
B
A
B
A
B
A
B
A
D
C D
C D
C D
C
B
X =
(a) (b)
C
X =

Looping Groups of Eight (Octets) (continued…)
1 1 1 1
0 0 0 0
0 0 0 0
1 1 1 1
B
A
B
A
B
A
B
A
D
C D
C D
C D
C
1 0 0 1
1 0 0 1
1 0 0 1
1 0 0 1
B
A
B
A
B
A
B
A
D
C D
C D
C D
C
(c) (d)
B
Y = D
Y =
™
™Looping an octet of 1s eliminates the three variables that appea
Looping an octet of 1s eliminates the three variables that appear
r
in both complemented and uncomplemented form.
in both complemented and uncomplemented form.

Rule for loops of any size
Rule for loops of any size
We can summarize the rule for loops of any size:
‰When a variable appears in both complemented and
uncomplemented form within a loop, that variable is eliminated
from the expression.
‰Variables that are the same for all squares of the loop must appear
in the final expression.
‰It should be clear that a larger loop of 1s eliminates more
variables. To be exact, a loop of two eliminates one variable, a loop
of four eliminates two, and a loop of eight eliminates three.

Complete Simplification Process
Complete Simplification Process
1. Construct the K map and place 1s in those squares corresponding to
the 1s in the truth table. Place 0s in the other squares.
2. Examine the map for adjacent 1s and loop those 1s, which are not
adjacent to any other 1s. These are called isolated 1s.
3. Next, look for those 1s, which are adjacent to only one other 1. Loop
any pair containing such a 1.
4. Loop any octet even it contains some 1s that have already been
looped.
5. Loop any quad that contains one or more 1s, which have not already
been looped, is making sure to use the minimum number of loops.
6. Loop any pairs necessary to include any 1s that have not yet been
looped, making sure to use the minimum number of loops.
7. Form the OR sum of all the terms generated by each loop.

Example#1
0 0 0 1
0 1 1 0
0 1 1 0
0 0 1 0
B
A
B
A
B
A
B
A
D
C D
C D
C D
C
(a)
ACD
BD
D
C
B
A
BD
ACD
D
C
B
A
X +
+
=

Example#2
0 1 0 0
0 1 1 1
0 0 0 1
1 1 0 1
B
A
B
A
B
A
B
A
D
C D
C D
C D
C
D
C
A
BC
A
D
AC
C
B
A
C
B
A
D
AC
BC
A
D
C
A
X +
+
+
=
Option #1
Option #1

Example#
0 1 0 0
0 1 1 1
0 0 0 1
1 1 0 1
B
A
B
A
B
A
B
A
D
C D
C D
C D
C
D
C
B
BD
A
D
BC
D
B
A
D
B
A
D
BC
BD
A
D
C
B
X +
+
+
=
Option # 2
Option # 2

Mapping of POS Expressions
Mapping of POS Expressions
‰ Each sum term in the standard POS expression is called a
maxterm. A function in two variables (A, B) has four
possible maxterms, and .
‰ They are represented as M0, Ml, M2 and M3 respectively.
‰ The upper case letter M stands for maxterm and its
subscript denotes the decimal designation of that
maxterm obtained by treating the non-complemented
variable as a 0 and the complemented variable as a 1 and
putting them side by side for reading the decimal
equivalent of the binary number so formed.
‰ For mapping a POS expression on to the K-map, 0s are
placed in the squares corresponding to the maxterms
which are present in the expression and 1 s are placed
(or no entries are made) in the squares corresponding to
the maxterms which are not present in the expression.
‰ The decimal designation of the squares for maxterms is
the same as that for the minterms
,
B
A
,
B
A
,
B
A +
+
+ B
A +
A
B
A
B
B
A + B
A +
B
A + B
A +
B
A +
B
A +
B
A +
B
A +
C
C
C
B
A +
+
C
B
A +
+
C
B
A +
+
C
B
A +
+
C
B
A +
+
C
B
A +
+
C
B
A +
+
C
B
A +
+
B
A +
B
A +
B
A +
B
A +
D
C + D
C + D
C +
D
C +
D
C
B
A +
+
+ D
C
B
A +
+
+ D
C
B
A +
+
+ D
C
B
A +
+
+
D
C
B
A +
+
+ D
C
B
A +
+
+ D
C
B
A +
+
+ D
C
B
A +
+
+
D
C
B
A +
+
+ D
C
B
A +
+
+
D
C
B
A +
+
+
D
C
B
A +
+
+
D
C
B
A +
+
+ D
C
B
A +
+
+ D
C
B
A +
+
+
D
C
B
A +
+
+
(a) two-variable k-map
(b) three-variable K-map
(c) four-variable K-map.

Minimization of POS Expressions
‰ To obtain the minimal expression in the POS form, map the
given POS expression on to the K-map and combine the
adjacent 0s into as large squares as possible.
‰ Read the squares putting the complemented variable if its
value remains constant as a 1 and the noncomplemented
variable if its value remains constant as a 0 along the entire
square (ignoring the variables which do not remain constant
throughout the square) and then write them as a sum term.
‰ Various maxterm combinations and the corresponding
reduced expressions are shown in Figure 4.13.
A
B
A
B
A
B
A
B
B
A +
B
A +
B
A +
B
A +
C
C
B
Y =
A
Y =
A
)
C
B
(
Y +
= A
C
B +

A Five Variable Karnaugh Map
‰ The Karnaugh map becomes three
dimensional when solving logic
problems with more than four variables.
A three-dimensional Karnaugh map will
be used in this section.
‰ Consider the truth table shown in Figure
below (a). The truth table must have 32
(25) rows to show all the combinations
for five variables.
‰ The unsimplified Boolean expression for
the truth table can be written as
A
B
C
D
E
A
B
C
D
E
A
B
C
D
E
A
B
C
D
E
A
B
C
D
E
A
B
C
D
E
A
B
C
D
E
A
B
C
D
E
A
B
C
D
E
Y
⋅
⋅
⋅
⋅
+
⋅
⋅
⋅
⋅
+
⋅
⋅
⋅
⋅
+
⋅
⋅
⋅
⋅
+
⋅
⋅
⋅
⋅
+
⋅
⋅
⋅
⋅
+
⋅
⋅
⋅
⋅
+
⋅
⋅
⋅
⋅
+
⋅
⋅
⋅
⋅
=
INPUTS OUTPUT INPUTS OUTPUT
E D C B A Y E D C B A Y
0 0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0 1 1
0 0 0 1 0 0 1 0 0 1 0 0
0 0 0 1 1 0 1 0 0 1 1 0
0 0 1 0 0 0 1 0 1 0 0 1
0 0 1 0 1 1 1 0 1 0 1 0
0 0 1 1 0 0 1 0 1 1 0 0
0 0 1 1 1 0 1 0 1 1 1 0
0 1 0 0 0 1 1 1 0 0 0 0
0 1 0 0 1 0 1 1 0 0 1 0
0 1 0 1 0 0 1 1 0 1 0 0
0 1 0 1 1 0 1 1 0 1 1 0
0 1 1 0 0 1 1 1 1 0 0 1
0 1 1 0 1 0 1 1 1 0 1 1
0 1 1 1 0 0 1 1 1 1 0 0
0 1 1 1 1 0 1 1 1 1 1 0

A
B
C
D
E ⋅
⋅
⋅
⋅
A
D⋅
INPUTS OUTPUT INPUTS OUTPUT
E D C B A Y E D C B A Y
0 0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0 1 1
0 0 0 1 0 0 1 0 0 1 0 0
0 0 0 1 1 0 1 0 0 1 1 0
0 0 1 0 0 0 1 0 1 0 0 1
0 0 1 0 1 1 1 0 1 0 1 0
0 0 1 1 0 0 1 0 1 1 0 0
0 0 1 1 1 0 1 0 1 1 1 0
0 1 0 0 0 1 1 1 0 0 0 0
0 1 0 0 1 0 1 1 0 0 1 0
0 1 0 1 0 0 1 1 0 1 0 0
0 1 0 1 1 0 1 1 0 1 1 0
0 1 1 0 0 1 1 1 1 0 0 1
0 1 1 0 1 0 1 1 1 0 1 1
0 1 1 1 0 0 1 1 1 1 0 0
0 1 1 1 1 0 1 1 1 1 1 0

Example
Example
‰ Simplify the following 5-input variables k-map
shown in Figure (a).
‰ The simplified expression taken from the map of
Figure (a) is developed and shown in Figure (b).
‰ Combining these AND terms using OR gate yields
A
C
D
E
A
C
E
B
C
D
Y ⋅
⋅
⋅
+
⋅
⋅
+
⋅
⋅
=
B
C
D
A
EC
DCA
E
(a)
(b)

“
“Don
Don’
’t Care
t Care”
” Conditions
Conditions
‰ Some logic circuits can be
designed so that there are certain
input conditions for which there
are no specified output levels,
usually because these input
conditions will never occur.
‰ In other words, there will be
certain combinations of input
levels where we ‘’don’t care’’
whether the output is HIGH or
LOW.
‰ This is illustrated in the truth table
of figure (a).
A
A B
B C
C Z
Z
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 X
1 0 0 X
1 0 1 1
1 1 0 1
1 1 1 1

0
0 0
0
0
0 0
0
1
1 1
1
1
1 1
1
B
A
B
A
AB
B
A
C C
0
0 0
0
0
0 x
x
1
1 1
1
x
x 1
1
B
A
B
A
AB
B
A
C C
(b) (c)
Z=A
Z=A
™Whenever ‘’don’t care’’ conditions occur, we have to decide
which ones to change to 0 and which to 1 to produce the best K-
map looping (i.e., the simplest expression).
™This decision is not always an easy one.

The K-map process has several advantages over the algebraic method.
™ K mapping is a more orderly process with well-defined steps as compared with
the trial- and error process sometimes used in algebraic simplification.
™ K mapping usually requires fewer steps, especially for expressions containing
many terms, and it always produces a minimum expression.
™ Nevertheless, some instructors prefer the algebraic method because it requires
a thorough knowledge of Boolean algebra and is not simply a mechanical
procedure. Each method has its advantages, and though most logic designers
are adept at both, being proficient in one method is all that is necessary to
produce acceptable results.
™ There are other more complex techniques that designers use to minimize logic
circuits. These techniques are especially suited for circuits with large numbers
of inputs where algebraic and k-mapping methods are not feasible.
™ Most of these techniques can be translated into a computer program, which will
perform the minimization from input data that supply the truth table or
unsimplified expression.
Summary
Summary

�ݺ�ߣ

3,EEng k-map.pdf

Recommended

More Related Content

Similar to 3,EEng k-map.pdf (20)

Recently uploaded (20)

3,EEng k-map.pdf