Page 205 - Engineering Digital Design

176 CHAPTER 4 / LOGIC FUNCTION REPRESENTATION AND MINIMIZATION

original optimized SOP expressions require a gate/input tally of 14/30, including three
inverters, and have a maximum fan-in requirement of 3.
The factorized expressions of Eqs. (4.63) are three-level functions, whereas the original
SOP expressions are two-level. This brings up other aspects of the optimization problem,
namely the design area (real estate usage) vs delay (performance), as discussed in Section
4.10.

4.9.2 Resubstitution Method

The Boolean resubstitution method possesses a close resemblance to polynomial division
and works to generate multilevel functions that have improved fan-in (hence improved area)
requirements. The process of resubstitution begins by finding a good, if not optimal, divisor
P in the expression

F = PQ + R, (4.64)
where F is the dividend, Q is the quotient, and R is the remainder. Heuristic algorithms
exist that can accomplish this, but they are complex and fall outside the scope of this text.
However, an attempt will be made to illustrate the resubstitution method with a simple
example. Consider the minimized SOP five-variable function
F = ABE + ABCD + CDE + ACE + ABCD + ABE + CDE. (4.65)

Noting the appearance ofAB, AB, CD, CD, E, and E in six of the seven p-terms, the divisor
is chosen to be P = AB + CD + E. The process continues by repeating three steps for each
of the seven p-terms:
Step 1. Select term ABE.
Step 2. AND (Boolean multiply) ABE • P = ABE + ABCDE + ABEE = ABE.
Step 3. Delete AB in ABE • P to yield term E • P.
Step 1. Select term ABCD.
Step 2. AND ABCD • P = ABCD + ABCDE = ABCD.
Step 3. Delete AB in ABCD • P to yield term CD • P.

Repeat Steps 1, 2, and 3 for the remaining five terms in the order given by Eq. (4.65):

CDE • P = ABCDE + CDE = CDE. Delete CD in CDE • P to yield E • P.
ACE • P = 0. Thus, no literals can be deleted in ACE • P.
ABCD • P = ABCD + ABCDE = ABCD. Delete CD in ABCD • P yield AB • P.
ABE • P = ABCDE + ABE = ABE. Delete E in ABE • P to yield AB • P.
CDE • P = ABCDE + CDE = CDE. Delete E in CDE • P to yield CD- P.
In the preceding set of steps it should be observed that the only literals that can be deleted
are those that appear as p-terms in the divisor P. Also, it should be noted that the choice
of divisor P is somewhat arbitrary, since there are other combination of terms that can be
used in the resubstitution process.
The final results of resubstitution are expressed by the partition

F = A BP + CDP + EP + A CE
= PQ + R, (4.66)