Page 70 - DCAP108_DIGITAL_CIRCUITS_AND_LOGIC_DESIGNS

Unit 4: Minimization of Boolean Algebra

Notes
Figure 4.16: Karnaugh Maps and Truth Tables for (a) Two, (b) Three, and (c) Four Variables

A B X B B
0 0 1 AB A 1 0
0 1 0 x= AB +AB
1 0 0 A 0 1
1 1 1 AB
a
()
AB C X C C
0 0 0 1 ABC AB 1 1
0 0 1 1 ABC
0 1 0 1 ABC AB 1 0
0 1 1 0
1 0 0 0 X= ABC + ABC AB 1 0
1 0 1 0 + ABC + ABC
1 1 0 1 ABC AB 0 0
1 1 1 0
b
()
AB C D X
0 0 0 0 0 CD CD CD CD
0 0 0 1 1 ABCD
0 0 1 0 0 AB 0 1 0 0
0 0 1 1 0
0 1 0 0 0 X= ABCD + ABCD AB 0 1 0 0
0 1 0 1 1 ABCD + ABCD + ABCD
0 1 1 0 0 AB 0 1 1 0
0 1 1 1 0
1 0 0 0 0 0 0 0 0
1 0 0 1 0 AB
1 0 1 0 0
1 0 1 1 0
1 1 0 0 0
1 1 0 1 1 ABCD
1 1 1 0 0
1 1 1 1 1 ABCD
c
()
2. The K-map squares are labelled so that horizontally adjacent squares differ only in one
variable. For example, the upper left-hand square in the four-variable map is ABCD, while
the square immediately to its right is ABCD (only the D variable is different). Similarly,
vertically adjacent squares differ only in one variable. For example, the upper left-hand
square is ABCD while the square directly below it is ABCD (only the B variable is different).
Note that each square in the top row is considered to be adjacent to a corresponding square
in the bottom row. For example, the ABCD square in the top row is adjacent to the ABCD
square in the bottom row, since they differ only in the A variable. The top of the map as
being wrapped around to touch the bottom of the map. Similarly, squares in the leftmost
column are adjacent to corresponding squares in the rightmost column.
3. In order for vertically and horizontally adjacent squares to differ in only one variable, the
top-to-bottom labelling must be done in the order shown- AB AB AB AB, , , . 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-products expression for the
output X can be obtained by 0Ring together those squares that contain a 1. In the three-
variable map of Figure 4.17(b), the ABCABC ABC, , and ABC squares contain a 1, so that
X = ABC + ABC + ABC + ABC.
The magnificence of the Karnaugh map is that it has been cleverly designed so that any
two adjacent cells in the map differ by a change in one variable. It is always a change of
one variable any time you cross a horizontal or vertical cell boundaries. (It is not fair to go
through the corners!)

LOVELY PROFESSIONAL UNIVERSITY 65