Page 242 - Engineering Digital Design

5.7 EXAMPLES OF MINIMUM FUNCTION EXTRACTION 213

Then from Eq. (5.16) the R-M g/ coefficients are evaluated as follows:

So = /o = 0 g 8 =e/(8,0)=l
gi = e/d, o) = i g9 = e/(9, s, i, o) - i
= e/(2, 0) = 1 = e/(io, 8, 2, o) = i
§2 glo
g 3 = 0/(3, 2, 1, 0) = 0 gn = ©/(1 1 - 8, 3 - 0) = 1
g 4 = 0/(4, 0) =1 g n = ©/(12, 8, 4, 0) = 0

g5 = 0/(5, 4, 1, 0) = 0 gi 3 = 0/(13, 12, 9, 8, 5, 4, 1, 0) = 0
g6 = 0/(6, 4, 2, 0) = 1 g, 4 = 0/(14, 12, 10, 8, 6, 4, 2, 0) = 1
gi = ®/(7 - o) - i g = e/d5 - o) = i.
15
Note that the g { coefficients are immediately realized by counting 1 's within the domains
of the conventional K-map shown in Fig. 5.4a. Thus, g 13 = 0 since an even number of 1's
exist in the C domain (determined from 1101), or #9 = 1 because an odd number of 1's
exist in the BC domain (from 1001). Disregarding the g = 0 coefficients, there results the
positive polarity R-M expression and its simplified mixed polarity form

Z 4 = Dgi © Cg 2 © Bg 4 © BCg 6 © BCD gl © Ag & © ADg 9 © ACg ]Q © ACDg } ,
©AflCg,4©AflCDg, 5
=D©C©fl©flC © BCD © A © AD © AC © ACD © ABC © ABCD
= D © C © B © BCD © AD © ACD © AflCD
= #©C©D©ACD©AflCD, (5.31)

which is a three-level function having a gate/input tally of 6/ 1 5 excluding possible inverters.
The function in Eq. (5.31) is seen to be the same as that in Eq. (5.28), but it is not an exact
minimum. Here, multiple applications of the XOR identities in Eqs. (3.30) have been applied
to excise terms.
Other comparisons are now made between the CRMT method and the EV K-map and
conventional K-map methods presented in Sections 4.6 and 4.4. From Figs. 5.4b and 5.4c,
the minimum cover extraction by using XOR type patterns (shown by loops) gives

Z K-map AB = B(C © D) + D(A © fl) + .BCD (5.32)

and

© (AD) + C(B © D) (5.33)

representing three-level functions with gate/input tallies of 6/14 and 6/12, respectively,
excluding possible inverters. The function Z K-map AC is a gate/input-tally minimum for
function Z. The results in Eqs. (5.32) and (5.33) are hybrid forms classified as mixed
AND/OR/EXSOP expressions. The two-level SOP minimum, obtained from Fig. 5.4a,