Page 254 - Engineering Digital Design

5.11 K-MAP SUBFUNCTION PARTITIONING FOR COMBINED CRMT 225

for function F and

AD0Ce S (5.63)

for function H. Then, combining an optimum set of shared EXSOP terms results in the
expressions

F = [B ©AD] 0 AB ©ACD ®BCD\

This is a four-level system having a total gate/input tally of 9/20, including shared term
50 AD.
Comparing results in Eqs. (5.60), (5.61), and (5.64) with those for the minimized CRMT
forms in Eqs. (5.59) clearly shows that the CRMT method is competitive with the K-map and
two-level minimization methods and illustrates the advantage of simplicity that the CRMT
minimization approach has over that of the EXSOP minimization as a pencil-and-paper
method.

5.11 K-MAP SUBFUNCTION PARTITIONING FOR COMBINED CRMT
AND TWO-LEVEL MINIMIZATION

Any function can be partitioned in a manner that permits it to be minimized by a combination
of the CRMT and two-level methods. Function partitioning for this purpose is best carried out
within an EV K-map, hence subfunction partitioning. This partitioning process is significant
because with K-map assistance it makes possible the selection of the most tractable (if not
optimal) parts of a function for the combined two methods of minimization. This can be
of great advantage for a multioutput function where shared term usage is important. There
still remains the problem of knowing what is the "best" choice of function partitioning for
optimal results. An absolute minimum result in the CRMT approach not only would require
an exhaustive search of the best CRMT bond set minimum, but must be accompanied by
an exhaustive two-level search. This is no easy task except for, perhaps, relatively simple
functions. However, if an absolute minimum result is not sought, there may exist a variety
of ways in which a given function can be partitioned without significant change in the
cost (complexity) of the resulting minimized function. In any case, the combined minimum
forms are classified as partitioned EXSOP/SOP forms or their dual EQPOS/POS.
As a simple example of K-map function partitioning, consider function ZAC in Fig. 5.4c.
Here, the literal D in cell 1 (see dashed loop in domain AC) is separated out to be later
ORed to the CRMT solution as the EPI ACD. After removal of the literal D, the CRMT g
coefficients become

= B® D 2 = B ®B®D = D

Introducing these coefficients into Eq. (5.29) and adding the two level result ACD yields