Page 247 - Engineering Digital Design

218 CHAPTER 5 / FUNCTION MINIMIZATION

POS expression, a conventional (1's and O's) K-map, or a truth table. The cell subfunctions
of the EV K-map become the // coefficients in the CRMT form of Eq. (5.16) or (5.19).
Thus, the entered variables make up the free set. As a caveat, try to avoid bond sets that
generate / coefficients like • • • Z(X + F) • • •, since such coefficients do not produce simple
g coefficients. Note that an EV truth table, such as that in Fig. 8.26, will also suffice for the
purpose of the CRMT minimization method if the table-heading variables are taken as the
bond set variables.
Step 2. For the choice of bond set used, obtain a set of minimum CRMT g, coefficients
from Eq. (5.18) or (5.21) by using the EV K-map cell entries as the /} coefficients and by
applying Eqs. (3.19). If alternative minimum expressions exist for a given g coefficient,
choose among these for the "best" one in consideration of steps 3 and 4 that follow. Thus,
if an exact minimum result is required for a given bond set, an exhaustive search for an
optimum g set must be carried out.
Step 3. Recast the function in positive or negative CRMT form by using the g set from
step 2 in Eq. (5.17) or (5.20).
Step 4. Reduce the results of STEP (3) by applying the laws and identities given by
Eqs. (3.19) and (3.27)-(3.33). Keep in mind that identical EXSOP terms in the form • • • ©
X © X © • • • or EQPOS terms in the form • • • O X O X O • • • can be excised immediately
in their respective CRMT expressions.
Step 5. If an exact minimum result is required, an exhaustive search must be carried
out by repeating Steps (1) through (4) for all possible bond sets. As a practical matter for
pencil-and-paper application of the CRMT method, the exhaustive search process should not
be conducted on functions exceeding five variables. For example, a five-variable function
would have to be partitioned into 10 two- or 10 three-variable bond sets in addition to the
partitioning for the remaining bond sets. Of course, if an exact minimum is not required,
most any choice of CRMT bond set will yield an acceptable minimum for many applica-
tions — one that may even be a near-exact minimum.
Step 6. Don't cares, if present, must be considered during the bond set selection process.
This is usually done with the intent of reducing the complexity of the CRMT g coefficients,
if not optimizing them. It is often the case that simple / coefficients (EV K-map cell entries
such as 0, 1, X, or X © F) yield simple g coefficients that lead to near-exact minimizations.
In any case, the presence of don't cares will complicate considerably an exhaustive search
process.
Step 7. If more than one function is to be optimized, the procedure is to set up the
CRMT forms separately as in steps 1-5 and then follow a systematic reduction process for
each, taking care to use shared terms in an optimal fashion.

5.9 INCOMPLETELY SPECIFIED FUNCTIONS

Consider the five- variable function

(l,3,4,6, 9, 10, 12,13, 18,21,23,25)
+ 0(0,8,11,14,15, 16,24,26,27,29,30,31), (5.46)

where 0 is the symbol representing don't cares (nonessential minterms). Shown in Fig. 5.6a
is the conventional K-map for this function and in Fig. 5.6b its second-order EV K-map