Page 230 - Engineering Digital Design

5.2 XOR-TYPE PATTERNS 201

and is seen to be a two-level function. Here, according to step III of the extraction procedure,
the associative XOR pattern is extracted in minterm code in SOP form with X located in
the A domain, hence A • X . The EXOR/SOP form can be converted to the E EQ V/ POS form by
double complementation as required by Eqs. (3.24), or can be read in maxterm code directly
from the K-map.
The function F in the second-order K-map of Fig. 5. Ic is read in maxterm code, accord-
ing to step III and is given by

FEQV/POS = [(B + f) 0 X] • A, (5.2)

which is a three-level function. In this case the EQV connective associates the Y in cells
0 and 2 (hence B + Y in maxterm code) with the X in all four cells. The remaining POS
cover in cell 0 is extracted with the don't care (</>) in cell 1 by ANDing the previous result
with A as required by step IV in the extraction procedure.
The function G in the third-order EV K-map, shown in Fig. 5. Id, is also read in maxterm
code. Here, the EQV connective associates the X's in cells 0, 1,4, and 5 (thus, B + X in
maxterm code) with the F's in cells 5 and 7 (hence, A + C + F), giving the result

GEQV/POS = [(B + X)Q(A+C + Y)](A + C + X), (5.3)

which is also a three-level function. The term (A + C + X) removes the remaining POS
cover in cells 4 and 6, as required by step IV.
For comparison purposes the two-level minimum results for ESOP> FPQ$, and GPOS are

(5.4)
Y)(B + X + Y)(B + X)A (5.5)

X + Y)(A + C + X + Y)(A + C + X)
B+X + Y). (5.6)

The use of associative patterns often leads to significant reduction in hardware compared
to the two-level SOP and POS forms. For example, function EXOR/SOP has a minimum
gate/input tally of 2/4 compared to 4/10 for ESOP, the two-level SOP minimum form. The
gate/input tally for FEQV/POS is 3/6 compared to 4/11 for the FPOS expression, and function
GEQV/POS has a minimum gate/input tally of 4/12 compared to 6/22 for GPOS, the two-level
POS minimum result, all excluding inverters.
XOR patterns may be combined very effectively to yield gate-minimum results. Shown
in Fig. 5.2a is a second-order compression where diagonal, adjacent, and offset patterns are
associated in minterm code by the XOR operator in cell 1. Here, the defining relation for
XOR, given in Eqs. (3.4), is applied to the diagonal pattern (cells 1 and 4) in the B domain
for all that is X to yield BX(A © C). This pattern is then associated with the intersection
(ANDing) of the adjacent pattern (A O Y) and the offset pattern (B © C) in cells 1, 2, 5,
and 6 to give the gate-minimum, three-level result

HXOR/SOP = [BX(A © C)] © [(A O Y)(B © C)] (5.7)

with a gate/input tally of 6/13. The defining relation for EQV, given in Eqs. (3.5), is used