3,EEng k-map.pdf

K-Map

1. 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 li mited to problems with up to
four inputs, since even five-a nd six- input problems are too
involved and are best done by a computer program.

2. 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.
BA AB BA BA, , ,

3. ‰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

4. Looping Groups of Two (pairs)
00
10
10
00
C
C
BABABABA
00
11
00
00
C
C
BABABABA
CB Y=
BA Y
=
(a)
(b)

5. Looping Groups of Two (pairs)
(Continued)
10
00
00
10
C
C
BABABABA
CB 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.

6. Redundant Looping Redundant Looping
0011
0000
0000
1001
BABA BABA
DC
DC
DC
DC
DBA
CBA DCB
Redundant Looping
DBA CBA Y+ =
DCB DBA CBA Y+ + =
NOTNOT

7. Looping Groups of Four (Quads)
:
0001
0001
0001
0001
BABA BABA
DC
DC
DC
DC
0000
0000
1111
0000
BABA BABA
DC
DC
DC
DC
(a)
(b)
DC X=
AB X=

8. Looping Groups of Four (Quads)
(continued…)
0000
0110
0110
0000
BABA BABA
DC
DC
DC
DC
0000
0000
1001
1001
BABA BABA
DC
DC
DC
DC
(c)
(d)
BD=X
DA X
=

9. Looping Groups of Four (Quads)
(continued…)
1001
0000
0000
1001
BABA BABA
DC
DC
DC
DC
(e)
DB
=
X
™™Looping a quad of 1s eliminates the two variables that appear i Looping a quad of 1s eliminates the two variables that appear i n n
both complemented and uncomplemented form. both complemented and uncomplemented form.

10. Looping Groups of Eight (octets)
:
0000
1111
1111
0000
BABA BABA
DC
DC
DC
DC
1100
1100
1100
1100
BABA BABA
DC
DC
DC
DC
B X
=
(a) (b)
C X
=

11. Looping Groups of Eight (Octets)
(continued…)
1111
0000
0000
1111
BABA BABA
DC
DC
DC
DC
1001
1001
1001
1001
BABA BABA
DC
DC
DC
DC
(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 appea r r
in both complemented and uncomplemented form. in both complemented and uncomplemented form.

12. 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, aloop
of four eliminates two, and a loop of eight eliminates three.

13. 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.

14. Example#1
0001
0110
0110
0010
BABA BABA
DC
DC
DC
DC
(a)
ACD
BD
DCBA
BD ACD DCBA X
+
+
=

15. Example#2
0100
0111
0001
1101
BABA BABA
DC
DC
DC
DC
DCA
BCA DAC
CBA
CBA DAC BCA DCA X+ + + =
Option #1 Option #1

16. Example#
0100
0111
0001
1101
BABA BABA
DC
DC
DC
DC
DCB
BDA
DBC
DBA
DBA DBC BDA DCB X+ + + =
Option # 2 Option # 2

17. 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 M
0
, M
l, M
2
and M
3
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.

18. Minimization of POS Expressions
‰To obtain the minimal expressi on 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 non ­complemented
variable if its value remains co nstant 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
+

19. 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
(2
5) 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
0000 0 0 10000 0
0000 1 1 10001 1
0001 0 0 10010 0
0001 1 0 10011 0
0010 0 0 10100 1
0010 1 1 10101 0
0011 0 0 10110 0
0011 1 0 10111 0
0100 0 1 11000 0
0100 1 0 11001 0
0101 0 0 11010 0
0101 1 0 11011 0
0110 0 1 11100 1
0110 1 0 11101 1
0111 0 0 11110 0
0111 1 0 11111 0

20. ABCDE⋅⋅⋅⋅
AD
⋅
INPUTS
OUTPUT
INPUTS
OUTPUT
E
D
C
B
A
Y
E
D
C
B
A
Y
0000 0 0 10000 0
0000 1 1 10001 1
0001 0 0 10010 0
0001 1 0 10011 0
0010 0 0 10100 1
0010 1 1 10101 0
0011 0 0 10110 0
0011 1 0 10111 0
0100 0 1 11000 0
0100 1 0 11001 0
0101 0 0 11010 0
0101 1 0 11011 0
0110 0 1 11100 1
0110 1 0 11101 1
0111 0 0 11110 0
0111 1 0 11111 0

21. 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
ACDE ACE BCD Y⋅⋅⋅ +⋅⋅ +⋅⋅ =
BCD
AEC
DCA E
(a)
(b)

22. ““DonDon’’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).
AABBCCZZ 000 0
001 0
010 0
011 X
100 X
101 1
110 1
111 1

23. 0000
0000
1111
1111
BABA
AB
BA
C
C
0000
00xx
1111
xx11
BABA
AB
BA
C
C
(b)(c)
Z=AZ=A
™Whenever ‘’don’t care’’ condition s 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.

24. BABA
AB
BA
DC
DC
CD
DC

25. 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 th e algebraic method because it requires
a thorough knowledge of Boolean algebra and is not simply a mechanical
procedure. Each method has its advan tages, and though most logicdesigners
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 transl ated into a computer program, which will
perform the minimization from inpu t data that supply the truth table or
unsimplified expression.
Summary Summary