Page 69 - DCAP108_DIGITAL_CIRCUITS_AND_LOGIC_DESIGNS

Digital Circuits and Logic Design

Notes 4.3 Karnaugh Maps

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.
What Does a Karnaugh Map Look Like?

A Karnaugh map is a grid-like representation of a truth table. It is really just another way of
presenting a truth table, but the mode of presentation gives more insight. A Karnaugh map has
zero and one entries at different positions. Each position in a grid corresponds to a truth table
entry. Here’s an example taken from the voting circuit presented on Minterms. The truth table is
shown first. The Karnaugh Map for this truth table is shown after the truth table.
Table 4.3: Karnaugh Map for Truth Table

A B C V
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1

BC
00 01 11 10
0 0 0 1 0
A
1 0 1 1 1

A Boolean algebra is called representable when it is isomorphic to a concrete
Boolean algebra.
4.3.1 Karnaugh Map Format

The K-map, like a truth table, is a means for showing the relationship between logic inputs and
the desired output. Figure 4.16 shows three examples of K-maps for two, three, and four variables,
together with the corresponding truth tables. These examples illustrate the following important
points:
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. For example, in Figure 4.16 (a), the A = 0, B = 0 condition in the truth
table corresponds to the AB square in the K map. Since the truth table shows X = 1 for this
case, a 1 is placed in the AB square in the K-map. Similarly, the A = 1, B = 1 condition in
the truth table corresponds to the AB square of the K-map. Since X = 1 for this case, a 1 is
placed in the AB square. All other squares are filled with Os. This same idea is used in the
three- and four-variable maps shown in the Figure 4.16.

64 LOVELY PROFESSIONAL UNIVERSITY