Page 232 - Engineering Digital Design

5.2 XOR-TYPE PATTERNS 203

which has a gate/input tally of 7/14. Extraction involves the association of an adjacent
pattern and a diagonal pattern with the three EQV connectives. The adjacent pattern in
domain B (cells 0 and 2) requires the use of Eqs. (3.5) to give [B + (A 0 X)]. This is
associated with the diagonal pattern in cells 0 and 3, by using Eqs. (3.5), "for all that is
Y" to give [Y + (A 0 #)], but is also associated with the cell 3 connective in domain A
for all that is Z. Notice that the terms in square brackets are commutative. For comparison
purposes the two-level POS result for function / is given by

I POS = (A + B + X + f)(A + B + X + Y}(A +B + X + Z)(A + B + X + Z)
x(A + B + Y + Z)(A + B + Y + Z) (5.10)

and has a gate/input tally of 7/30.
The function J in Fig. 5.2c is extracted in minterm code, giving the four-level, gate-
minimum result

JXOR/SOP = [D(B O Z)(A O C)] 0 [B(A 0 X)(C O D)] 0 [C(D O Y)(A O B)] (5.11)
with a gate/input tally of 11/25. This function is extracted as three sets of two intersecting
patterns, all associated by the three XOR connectives. The "Z" set consists of adjacent and
diagonal patterns where application of Eqs. (3.5) yields (B O Z) and (A O C), respectively,
which intersect (AND) in the D domain. The "X" set consists of adjacent and offset patterns
that are read as (A 0X) and (C O D), by application of Eqs. (3.4) and (3.5), and that intersect
in the B domain. Here, as in Fig 5.2a, the O's (now in cells 5 and 13) are disregarded in
the development of the offset/adjacent pattern. Finally, the "7" set also consists of adjacent
and offset patterns such that the application of Eqs. (3.5) yields (D O Y) and (A O B),
respectively, which intersect in the C domain. As in the previous example, the terms in
square brackets of Eq. (5.11) are commutative. In comparison, the two-level SOP minimum
for function J is given by

JSOP = ABCDXY + ABCDYZ + ABCDZ + ABCDY + ABCDY + ABCDX + ABCDX
+ AB CDZ + A CDXZ + BCDXZ + BCDXY + ACD YZ (5.12)

and has a gate/input tally of 13/74. Again, the gate/minimum advantage of the multilevel
function over its two-level counterpart in Eq. (5.12) is evident.
Both four-level functions, IEQV/POS and JXOR/SOP, ar e easily verified by introducing in
turn the coordinates for each cell into the particular expression. For example, if one sets
ABCD = 1111 in Eq. (5.11), the subfuction X 0 Y is generated for cell 15 as required by
Fig. 5.2c. Generation of the subfunctions in each cell validates the extraction process.
The gate/input tallies for all six functions represented previously are given exclusive
of inverters. When account is taken of the inverters required for inputs assumed to arrive
active high, the gate/input tally differentials between the multilevel results and the two-
level results increases significantly. These gate/input tallies from previous examples are
compared in Table 5.1, where all inputs are assumed to arrive active high.
There are other factors that may significantly increase the gate/input tally and throughput
time differentials between multilevel and standard two-level SOP and POS minimum forms.
These include gate fan-in restrictions and static hazard cover considerations. Static hazards