Page 206 - Engineering Digital Design

4.9 FACTORIZATION, RESUBSTITUTION, AND DECOMPOSITION METHODS 177

A(H)
B(H)
C(H) —
D(H) —
E(H)

FIGURE 4.47
NAND/NOR/INV realization of the partitioned function given by Eq. (4.66).

where P = AB + CD + E, Q = AB + CD + E and R = ACE. Function F, expressed by
Eqs. (4.66), represents four levels of path delay, as shown implemented by NAND/NOR/INV
logic in Fig. 4.47 where it is assumed that all inputs arrive active high. Notice that the
gate/input tally is now 11/25, including three inverters, and that only one gate has a fan-in
of 4. If a fan-in limitation of 4 is also applied to the original two-level SOP expression in
Eq. (4.65), a three-level circuit results having a gate/input tally of 14/35, including five
inverters, and four gates with a fan-in of 4. Thus, the partitioned function of Fig. 4.47 has
an improved design area factor but not necessarily an improved performance. A discussion
of the design area vs performance factors is given in Section 4.10.
The resubstitution method just described bears similarity to portions of some heuristic
two-level minimization algorithms such as Espresso II, qualitatively described in Subsection
4.8.3. In particular, the introduction of a new literal, divisor term P in step 2 and the subse-
quent deletion of literals in step 3 of resubstitution is a generalization of the REDUCE and
EXPAND processes in Espresso II. In these processes, Espresso seeks to add literals existing
in one product term of the original expression to other candidate terms so that implicants
covered by a given expanded implicant can be deleted. Thus, by repeated introduction of
divisor P followed by deletions of redundant terms, the resubstitution process seeks a more
optimum result, not unlike the heuristic processes in Espresso.

4.9.3 Decomposition by Using Shannon's Expansion Theorem
Shannon' s expansion theorem states that any Boolean function of n variables f(x n-\ , . . . X2,
X\,XQ) can be decomposed into the SOP form

/-l , ...,X 2,Xi,XQ)
(4.67)