Page 258 - Engineering Digital Design

FURTHER READING 229

5.12 PERSPECTIVE ON THE CRMT AND CRMT/TWO-LEVEL
MINIMIZATION METHODS

The main advantage of the CRMT method of function minimization lies in the fact that
it breaks up the minimization process into tractable parts that are amenable to pencil-
and-paper or classroom application. The CRMT minimization process can be thought of
as consisting of three stages: the selection of a suitable bond set, the optimization of the
CRMT g coefficients (for the chosen bond set), and the final minimization stage once
the g coefficients have been introduced into the CRMT form. If an exact minimum is
not required, a suitable bond set can be easily found, permitting the CRMT method to be
applied to functions of as many as eight variables or more. Knowledge of the use of EV
K-maps and familiarity with XOR algebra are skills essential to this process. A properly
conducted CRMT minimization can yield results competitive with or more optimum than
those obtained by other means.
It has been shown that minimization by the CRMT method yields results that are often
similar to those obtained by the EV K-map method described in Section 5.4. This is partic-
ularly true when the EV K-map subfunctions are partitioned so as to take advantage of both
the CRMT and two-level (SOP or POS) minimization methods. In fact, when subfunction
partitioning is carried out in agreement with the minimum K-map cover (as indicated by
loopings), the CRMT/two-level result is often the same as that obtained from the K-map.
It is also true that when a function is partitioned for CRMT and two-level minimizations,
an extra level results because of the OR (or AND) operator(s) that must be present in the
resulting expression. Thus, a CRMT/two-level (mixed) result can be more optimum than
the CRMT method (alone) only if the reduction in the gate/input tally of the CRMT portion
of the mixed result more than compensates for the addition of the two-level part. At this
point, this can be known only by a trial-and-error-method that is tantamount to an exhaustive
search.
If an exact or absolute minimum CRMT result is sought, an exhaustive search must
be undertaken for an optimum bond set. Without computer assistance this can be a te-
dious task even for functions of four variables, particularly if the function contains don't
cares. Multiple-output systems further complicate the exhaustive search process and make
computer assistance all the more necessary. One advantage of the mixed CRMT/two-level
approach to function minimization is that each method can be carried out independently on
more tractable parts.

FURTHER READING

Additional information on XOR algebra, XOR function extraction from K-maps, and logic
synthesis with XOR and EQV gates can be found in the texts of Roth, Sasao (Ed.), and
Tinder.

[1] C. H. Roth, Fundamentals of Logic Design, 4th ed. West, St. Paul, MN 1992 (Chapter 3).
[2] T. Sasao, "Logic Synthesis with XOR Gates," in Logic Synthesis and Optimization (T. Sasao,
Ed). Kluwer, 1993 (see, e.g., Chapter 12).
[3] R. F. Tinder, Digital Engineering Design: A Modern Approach. Prentice Hall, 1991 (see, e.g.,
Chapter 3).