Page 210 - Engineering Digital Design

4.12 WORKED EV K-MAP EXAMPLES 181

Here, tree configuration (III) is expected to show the least delay, but at the cost of greater
design area. Tree configuration (II) would seem to have the most favorable area/delay trade-
off, while gate (I) and cascade configuration (IV) are expected to have the least favorable
trade-off. A dual set of ANDing operations would show the same area/delay trade-offs.

4.11 PERSPECTIVE ON LOGIC MINIMIZATION AND OPTIMIZATION

The EV mapping methods described in Sections 4.6 and 4.7 are useful up to three or
four orders of map compression. However, with increasing compression order beyond
third order, the gap usually widens between the reduced forms obtained and the absolute
minimum result. This is especially true if reduced or minimized subfunctions are used to
extract cover from such EV K-maps. For this reason a practical limit of four orders of K-map
compression (eight variables) is set, and use of reduced or minimum subfunctions is highly
recommended. The use of submaps can narrow the gap between a reduced result and one
that is an absolute or exact minimum. This fact is implied by the simple examples given in
the sections on EV mapping methods.
Beyond four orders of compression in fourth-order K-maps, the use of computer algorith-
mic methods for logic minimization becomes necessary. But even these computer programs
have their limitations, particularly with regard to multiple output systems having a large
number of input variables. It is an established fact that the generalized optimal solution for an
n-variable function is impossible. The reason for this is that 2" minterms must be dealt with
in some manner or another. Minimization problems in the class referred to as P are called
tractable problems — those for which an optimum or near-optimum solution is possible.
Those that are intractable belong to the class of problems referred to as A/^P-complete. The
search for faster, more robust algorithms to optimize very large multiple output systems
continues. These algorithms are most likely to be of the heuristic type. Though the Q-M
linear tabular method is useful in introducing readers to the subject of logic minimization,
it is of little practical importance given the much-improved heuristic methods now in use.
Finally, it must be said that the SOP (or POS) minimization of a function may not be an end
in itself. Section 4.9 demonstrates that optimization may continue beyond minimization by
techniques such as factorization and resubstitution that generate multilevel functions. To do
this, however, brings into play other factors such as area/delay trade-offs. Thus, there emerge
two approaches to function optimization from which the designer must choose: Optimize
design area under delay constraints or optimize delay under design area constraints. It is
unlikely that a system can be optimized with respect to both design area and delay, although
it may be possible to come close to this for some systems.

4.12 WORKED EV K-MAP EXAMPLES

EXAMPLE 4.1 Compress the following four-variable function into a third-order K-map
and extract minimum SOP and minimum POS cover from it.

f(A, B, C, S) = ^m(2, 3, 5, 6, 7, 10, 12, 13, 15)
= ]~[Af(0, 1,4, 8,9, 11,14). (4.72)