Page 178 - Engineering Digital Design

4.4 KARNAUGH MAP FUNCTION MINIMIZATION 149

with these problems, it will be helpful to identify the following three subsets of Pis:

• Essential Prime Implicants (EPIs): Single-way Pis that must be used to achieve
minimum cover
• Optional Prime Implicants (OPIs): Optional-way Pis that are used for alterna-
tive minimum cover
• Redundant Prime Implicants (RPIs): Superfluous Pis that cannot be used if mi-
nimum cover is to result.

Any grouping of 2" adjacencies is an implicant, including a single minterm or maxterm,
but it may not be a PI. For example, a solitary quad EPI contains eight RPIs, four monads,
and four dyads, none of which are Pis.
To illustrate a simple mapping problem with optional coverage, consider the function

Z(A, B,C, D) = ^m(2,4,6, 8,9, 10, 11, 15), (4.25)
which is mapped in Fig. 4.18a. Noting first the minterm adjacencies that form the three
dyads (no monads exist) and the single quad, there results the SOP minimum expression

_ _ \ACD\
ZSOP=ACD+ABD + { _ _ } +AB, (4.26)
I BCD I
which has three EPI p-terms (two dyads and one quad), and two OPI dyads indicated in
braces. The minterm m^ can be covered in two ways to form the OPI dyads m(2, 6) and
m(2, 10) shown with dashed loops in Fig. 4.18a. Remember that when one OPI is selected

A+B+C (EPI)
/ C
AB X 00 01 '1 1 10 ' AB X 00 / 01 • 11 10

00

io|X.
Z
\ I / POS
°_ V B+ C + D(EPI)
A+B+C (OPI)

FIGURE 4.18
K-maps showing EPIs and OPIs for the function Z in Eq. (4.25). (a) SOP minimum cover, (b) POS
minimum cover.