ECE 376 Worked Karnaugh-Map Example

c Eric Benedict
15 November 1997

1 Introduction
This document provides a numerically worked Karnaugh-map (K-map) example problem in order to
illustrate the design procedure using a K-map. Simpli ed realizations using both sum-of-products
(SOP) and product-of-sums (POS) are developed and compared.

2 K-map Design Procedure

Combination digital circuit design and simpli cation is often performed using the graphical Karnaugh-
map technique. This technique allows for a systematic determination of minimal boolean expressions
and the corresponding two-level digital circuits. The Sum-of-Products (SOP) form is found directly
and the Product-of-Sums (POS) is found after applying DeMorgan's Theorem.
The design procedure typically consists of the following steps:
1. From the problem description (circuit design) or existing expression (simpli cation), complete
a truth-table.
2. Using the truth-table values, ll in the corresponding cells of the K-map.
3. Circle the K-map cells using the fewest number of and largest regular rectangles possible.
Each circle must contain a power of two (1, 2, 4, 8 or 16) cells.
 Circle 1's for Sum-of-Products (SOP) realization.

 Circle 0's for Product-of-Sums (POS) realization.

4. Write the corresponding minimized function

SOP Write the sum of the minterms represented by each circle.
POS Write the sum of the minterms represented by each circle to form the complement of the
function. Next, apply DeMorgan's theorem to obtain actual function in POS form.
5. Realize the corresponding circuit if required.

3 Problem Statement
Given the truth table of Table 1, nd the minimum Sum-of-Products (SOP) and Product-of-
Sums (POS) realization using two-level logic. You may assume that both complemented and
non-complemented literals (input variables) are available.
1
 Table 1: Example Truth Table
A B C D F
0 0 0 0 0
0 0 0 1 0
0 0 1 0 0
0 0 1 1 1
0 1 0 0 0
0 1 0 1 0
0 1 1 0 1
0 1 1 1 1
1 0 0 0 1
1 0 0 1 1
1 0 1 0 0
1 0 1 1 1
1 1 0 0 0
1 1 0 1 0
1 1 1 0 0
1 1 1 1 1

4 Problem Solution
A minimum Sum-of-Products (SOP) form will be found and realized rst. Then, a minimum
Product-of-Sums (POS) form will be found and realized.
Step 1: Form the truth-table. It is assumed that in this example, the truth-table has already been
found and is provided in Table 1.
Step 2: Filling in the K-map. The corresponding truth table entries are lled in the K-map as shown
in Figure 1.
Each truth table entry corresponds to one cell in the K-map. For example, the upper left
most cell in the map holds the truth table entry for ABCD=0000, while the lower right most
cell in the map holds the truth table entry for ABCD=1100.
Step 3a: Since we are implementing an SOP form, we want to circle the 1's which are present in the
map shown in Figure 1. A possible circling is shown in Figure 2. Each circle will correspond
to one minterm or rst-level logic gate, so fewer circles will result in a simpler expression or
circuit. Because we must assure that all cells containing a 1 are covered, larger circles are
desirable over smaller circles.
The four 1's in the center form an obvious group to circle and represent the minterm CD since
those are the variables which do not change for all of the cells contained in the circle. The
minterm ABC includes the 1 just to the left of the square, while the minterm AB C includes
2
 A A
0 0 1 1 C
B
0 1 1 0
1 1 1 0
C
B
0 0 0 0 C
D D D
Figure 1: Filled-in K-map
ABC
A A
B
0 0 1 1 C
0 1 1 0
1 1 1 0
C
B CD
0 0 0 0 C
ABC
D D D
Figure 2: Sum of Products K-map

the 1's above the square. Note that the minterm ABD does not include any new 1's and
therefore including it in the solution will not result in a minimal form. Its inclusion will,
however, provide a hazard-free design. Since we are to provide a minimal design, it will not
be included.
Step 4b: Now, we can realize the function as an SOP expression. The expression is simply the sum of
each minterm circle, or
F = CD + ABC + AB C :

Step 5a: This expression is then implemented using two-level logic as shown in Figure 3. This completes
the SOP design.
Step 3b: Now, we are designing a POS circuit, so we will circle the 0's from Figure 1. The map showing
a possible set of circles is shown in Figure 4. The minterms ABD and BC are clear; however, the
minterms BCD and A C are not as obvious. Because the K-map can be visualized as a attened
sphere, much like a world-map, the outside edges are actually adjacent to their opposite side!

3
 C C
D D
A F A F
B B
C C
A A
B B
C C
AND-OR Implementation NAND-NAND Implementation
Figure 3: Sum of Products Circuit Realizations
AC A A
0 0 1 1 C
B
BCD 0 1 1 0 BCD
1 1 1 0
C
B ABD
0 0 0 0 C
D D D
AC BC
Figure 4: Product of Sums K-map
Step 4b: The circled minterms will realize the complement of the desired function or
F = ABD + BC + BCD + A C :

Applying DeMorgan's Theorem, we can obtain F in a POS form. Basically, we will complement
all of the literals and then swap AND's and OR's to obtain
F = (A + B + D)
(B + C)
(B + C + D)
(A + C)
:

Step 5b: This expression is then implemented using two-level logic as shown in Figure 5. This completes
the POS design.
Comments: Neither of the SOP or POS circuits implemented in this example are unique since there are
other ways that the circles could have been drawn which would have resulted in equally simple
circuits. In this example, the SOP circuit realization is considered to be simpler than the POS
circuit since the SOP form has both fewer rst level logic gates and those gates also have fewer
inputs.

4
 A A
B B
D D
B B
F C F
C
B B
C C
D D
A A
C C
OR-AND Implementation NOR-NOR Implementation
Figure 5: Product of Sums Circuit Realizations