Page 199 - Engineering Digital Design

170 CHAPTER 4 / LOGIC FUNCTION REPRESENTATION AND MINIMIZATION

Adjacent minterm
code numbers
Positional weight of variable
removed (6- 2 = 4 or B)

-- i
Dash indicates variable
(B) removed

Logically adjacent minterms in minterm
code
Boundary line
FIGURE 4.41
Quine-McCluskey (Q-M) notation for PI determination.

that follow. Notice that the Q-M notation uses minterm code, minterm code numbers, and
positional weights for PI determination.
EXAMPLE 1 Consider the minimization of the incompletely specified function

Y(A, B, C,D) = Y^ m(0, 1, 4, 6, 8, 14, 15) + 0(2, 3, 9). (4.55)
In the Q-M algorithm the 0's are treated as essential minterms, and minterm sets k are
compared with sets (k + 1) in a linear and exhaustive manner. The first step in the application
of the Q-M algorithm is presented in Fig. 4.42. Here, a check mark (^/) indicates that an
implicant is covered by a PI in the column to the right and, therefore, cannot itself be a PI.
Thus, unchecked terms in columns 4 and 6 are the indicated Pis and those that are lined out
are redundant.
The second step in the application of the Q-M method is the identification of the essential
prime implicants (EPIs). Presented in Fig. 4.43 is a table of the Pis (taken from Fig. 4.42)
vs the essential minterms in Eq. (4.55). The check mark (^/) within the table indicates that
a given minterm is covered by a PI. The EPIs are selected from a minimum set of Pis that
cover all of the essential minterms of the function Y in Eq. (4.55) and are presented in
Eq. (4.56):
Y=ABC + BC + AD. (4.56)

This result can be easily verified by the conventional K-map extraction method described
in Section 4.4.
EXAMPLE 2 In this example a minimum POS result is required for the incompletely
specified function
F(W, X, Y, Z) = £m(0, 1, 4, 5, 11, 12, 13, 14, 15) + 0(2, 7, 9) (4.57)

= J~jM(3, 6, 8, 10)-0(2, 7, 9). (4.58)