Page 238 - Engineering Digital Design

5.7 EXAMPLES OF MINIMUM FUNCTION EXTRACTION 209

where the 2"M, in Eq. (5.19) represent maxterms read in maxterm code, and the f { repre-
sent their respective coefficients whose values derive from the binary set {0, 1}. The 2"M,
maxterms are mutually disjoint since only one maxterm can be inactive (logic 0) for the
same values of inputs. For this reason it is permissible to interchange the AND and EQV
operators in Eq. (5.19). Thus, Eq. (5.19) expresses the transformation of a POS expres-
sion to an EQV-product-of-sums (EQPOS) expression. Note that if all f f are logic 0, then
F n = 0.
Setting Xj=Xi 00 eliminates all Jt, from Eq. (5.19), resulting in a negative polarity
expression for the function F n , which is simplified by multiple applications of the EQV
form of the distributive law given by Eqs. (3.19). The result is the Reed-Muller expansion
in the EQPOS form

F n(XQ,Xi,X 2, • ..,*n-l) = goO(g l + *K-l)O (
O(g4 +^-3)O •• • O(g2"-l
(5.20)

where the g, are now the R-M coefficients for an EQPOS (negative polarity) R-M expansion.
Each EQPOS R-M coefficient is the set

8, = Qfj (5-21)

m
obtained from the subnumbers of / by replacing m 1's with O's in 2 possible ways in the
binary number corresponding to decimal i, as in Eq. (5.18). Thus, the array of g, for an
EQPOS expansion is the same as that for an EXSOP expansion except that the © operator
is replaced by the O operator. In Eq. (5.21) any g,- is 0 if an odd number of / coefficients are
logic 0, but is 1 otherwise. Again, the use of a K-map can be helpful in obtaining the values
by counting the O's within a given domain similar to the procedure explained earlier for the
case of the EXSOP expansion. Thus, any g/ is 0 if an odd number of O's exist within a given
domain defined by the O's in the binary number. All terms in the R-M EQPOS expansion
whose g coefficients are logic 1 are ignored.

5.7 EXAMPLES OF MINIMUM FUNCTION EXTRACTION

In this section two examples of minimum function extraction are presented that bear the
same relationship to each other as do the conventional and EV K-map methods — that is,
one is based on canonical forms (conventional method) while the other is equivalent to the
use of entered variables in K-maps (called the CRMT method).

A SIMPLE EXSOP EXAMPLE Consider the function

F 3 = ABC + AB + AC = £m(3, 4, 5, 6)

= £fW3,4,5,6), (5.22)