Page 181 - Engineering Digital Design

152 CHAPTER 4/LOGIC FUNCTION REPRESENTATION AND MINIMIZATION

, -A+D _ _
CD / C \ CD C
00 / 01 ^ 11 10 ' AB \ 00 01 '1 1 10 '
i ] — ABD
0
0
0
U
00 0 0 0 0 00
0 1 3 2
01 0 1 1 0 0 0
4 5 7 6
0
11 1 0 1
A 12 13 15 14 14
(b
10 J0 n 0 0 0 "7| 10
(b
f 8 9 11 10 _M/
Hi C
\l ' POS \ I I SOP
D
Wc+5 V A5 D
(a) (b)
FIGURE 4.20
K-maps for Eq. (4.30) containing don't cares showing (a) minimum POS cover and (b) minimum
SOP cover containing OPIs for minterms in cells 7 and 13 but not shown.

(connections) to gates. Gate tallies are weighted more heavily than input tallies. Inverters
can be included in the gate/input tally of a given function only if the activation levels of the
inputs are known. Unless otherwise stated, the gate/input tallies will be given exclusive of
inverters. An inverter is considered to be a gate with one input.
The number of p-terms or s-terms representing a function is called the cardinality of
the function. Thus, the cardinality of a cover represents the number of prime implicants of
the function, and a minimum cardinality (or cover) consists only of EPIs. When significant
numbers of don't cares are present in a function, there may exist several alternative covers
of minimum cardinality that may differ in gate/input tally.
As an example of the use of the gate/input tally and cardinality, consider the minimized
expressions in Eqs. (4.29). Here, F SOp has a gate/input tally of 2/4, whereas the gate/input
tally for F POs is 3/6, both exclusive of inverters and both with a minimum cardinality of 2.
Thus, the SOP expression is the simpler of the two. However, this may not always be true.
Taking a gate and input count of Eqs. (4.31) reveals that the gate/input tally for Y POs is 3/8
while that for Y SOp is 4/11, again both exclusive of possible inverters. Thus, in this case,
the POS expression is the simpler hardware-wise, but both expressions have a minimum
cardinality of 3. Notice that a single variable EPI contributes to the cardinality count of the
function but not to the gate tally.

4.5 MULTIPLE OUTPUT OPTIMIZATION

Frequently, logic system design problems require optimization of multiple output functions,
all of which are functions of the same input variables. For complex systems this is generally
regarded as a tedious task to accomplish without the aid of a computer, and for this reason
computer programs have been written to obtain the optimum cover for multioutput functions
of many variables. Examples of such computer programs are discussed in Appendix B.I.
In this section a simple approach to this process will be presented but limited to two or