Page 202 - Engineering Digital Design

4.8 MINIMIZATION ALGORITHMS AND APPLICATION, 173

4.8.2 Cube Representation and Function Reduction

The cube notation is commonly used in CAD programs and, in fact, is the notation that is
used in the computer implementation of the Q-M algorithm described in Subsection 4.8.1.
In this notation an n-dimensional cube has 2" vertices formed by the intersection of n
dimensional lines. Most commonly one thinks of a cube as three-dimensional (a 3-cube)
3
having 2 = 8 vertices. But the concept is much more general, extending to n dimensions
that generally cannot be easily visualized by a geometrical figure.
Cube representation is usually based on minterm code. Thus, the minterms of a switching
function can be mapped onto the 2" vertices of an n-dimensional cube such that each pair
of adjacent vertices differ by exactly one bit position. As an example, consider implicants
(2, 3) and (6, 7) listed in the Q-M example of Fig. 4.44. In minterm code cube notation, these
implicants would be represented as (0010, 001 1) and (01 10, 01 1 1), respectively. Reduction
of these implicants to PI (r-cube) form occurs between adjacencies (adjacent vertices) as
follows:

0010 + 0011 =001- = WXY and 0110 + 0111 = Oil- = WXY

or, finally,

-) = 0- l- = WY,

where 0 represents the complemented variable, 1 is the uncomplemented variable, and the
"— " symbol represents an irrelevant input variable (representing both 1 and 0). Thus, in gen-
r
eral, an r-cube of an n-variable function is produced by combining 2 adjacent minterms,
thereby eliminating r variables in a function reduction process.

4.8.3 Qualitative Description of the Espresso Algorithm
The two-level minimization algorithm called Espresso belongs to a class of minimization
algorithms that use heuristic logic methods as opposed to the linear exhaustive PI search
of the Q-M method. In effect, all heuristic methods group, expand and regroup adjacent
minterms over a number of iterations until an optimal or near-optimal grouping, called the
irredundant set, is found. The exact strategies used and the order in which they are used
depends on the particular algorithm.
Though a detailed description of the Espresso algorithm is beyond the scope of this text,
the principal steps involved can be qualitatively understood by the K-maps in Fig. 4.46. Here,
the four basic steps of the Espresso algorithm are represented by four fourth-order K-maps
labeled ORIGINAL, REDUCE, EXPAND and IRREDUNDANT. The ORIGINAL function,
plotted in Figure 4.46a, is the graphical equivalent to the PI table of the Q-M method since
it represents the largest number of prime implicants, that is, six Pis. The original function
is then regrouped to form a smaller (REDUCED) number of prime implicants (four Pis)
in Fig. 4.46b and then EXPANDED (RESHAPED) to form four Pis by eliminating two
Pis. Notice that the cardinality is preserved in the REDUCE-to-EXPAND step. Finally, an
IRREDUNDANT set is found by regrouping and eliminating yet another PI, resulting in only
three EPIs. This irredundant set is said to have minimum cardinality, that is, minimum cover.
The Espresso algorithm just described qualitatively is usually called Espresso-II. Since its
inception, various improvements have been made, adding to the speed and multiple-output