Page 246 - Engineering Digital Design

5.8 HEURISTICS FOR CRMT MINIMIZATION 217

and

G K. map YZ = [W + (Y Q Z)] Q(X® Z)] (5.44)

with gate/input tallies of 5/10 and 4/8, respectively. Note that reading a K-map in maxterm
code requires that the domains (not the entered variables) be complemented, since the
K-maps are minterm-code based [3]. In comparison, the two-level minimum result from
Fig. 5.5ais

G = (W + X + Y)(W + X + Y)(W + X + Z)(W + X + Z), (5.45)

which has a gate/input tally of 5/16 excluding possible inverters.
Notice that all CRMT minimization results, the canonical R-M minimization result, and
one EV K-map result for G all represent three-level functions with minimum gate/input
tallies of 4/8 (excluding possible inverters). In comparison, the best two-level result that can
be obtained for G yields a gate/input tally of 5/16, again excluding inverters. Notice also
that the two-level result requires that four s-terms be ANDed in the output stage, whereas
all other results mentioned earlier have a fan-in limit of two. Increased fan-in can slow the
throughput of a circuit, particularly in CMOS, as was discussed in Subsections 3.6.2 and
3.6.3, and in Section 4.10.

5.8 HEURISTICS FOR CRMT MINIMIZATION

A given minimization method can yield a guaranteed exact minimum for a function if, and
only if, an exhaustive search is carried out. Applied to the CRMT method this involves
finding the optimum (bond set)/(free set) combination for the optimal reduction process
of minimization required by the CRMT method. As the number of inputs to a function
increases, the task of performing an exhaustive search becomes more difficult, eventually
requiring computer algorithmic means. Even then, an intractable problem eventually ensues
when the number of inputs becomes excessively large for the minimization algorithm used.
When this happens, the minimization problem is known to be A/^P-complete (see Section
4.11).
Fortunately, variation in the choice of bond set for CRMT minimization often results in
little or no difference in minimum gate/input tally for a minimized function. However, the
effort required to achieve a minimum result may vary considerably with bond set choice.
Thus, if a guaranteed absolute minimum is not required, alternative choices of bond set
should yield an acceptable minimum, but with some limits placed on the number of bond set
variables. By the pencil-and-paper method this means that for practical reasons the number
of bond set variables should not exceed four for most applications of the CRMT method.
The limit on the total number of variables is placed between eight and twelve depending on
one's ability to use entered variables. In any case, experience in the application of the laws
and identities of XOR algebra is an invaluable asset in achieving a minimized result.
Given these preliminary comments, the following procedure should be helpful in apply-
ing the CRMT "hand" minimization method to functions of 12 variables or less:
Step 1. Choose a bond set and construct an entered variable (EV) K-map with the K-
map axes as the bond set. The starting point in this process can be a canonical SOP or