Page 227 - Engineering Digital Design

198 CHAPTER 5 / FUNCTION MINIMIZATION

device, meaning two units of path delay as implied by the defining relations for XOR and
EQV given by Eqs. (3.4) and (3.5). But the emergence of CMOS 1C technology has moved
the XOR and EQV gates close to single-level gates with respect to compactness and speed,
as is evident from Figs. 3.26 and 3.27. The term multilevel, as used in this text, means the
use of XOR and/or EQV gates together with two-level logic to form multiple levels of path
delay as measured from input to output.
The concept of minimization, as used in this text, is presented in terms of three degrees.
A minimum result is one that yields the lowest gate/input tally for a particular method used,
for example, a two-level minimum result, but may not be the lowest possible. An exact
minimization designates a result that has the fewest p-terms possible in an expression or
the fewest s-terms possible in an expression. An absolute minimum expression is one that
has the lowest possible gate/input tally considering all possible methods of minimization.
Thus, an absolute minimum is a gate/input-tally minimum (or simply gate-minimum) and
is usually the result of a specific or unique method of minimization. As a reminder, the
gate/input tally (defined in Subsection 4.4.3) will usually be given exclusive of possible
inverters. Only when the input activation levels are known can the gate/input tally include
the inverter count.
Where appropriate to do so, reference will be made to the defining relations for XOR
and EQV given by Eqs. (3.4) and (3.5) and to the XOR and EQV laws, corollaries, and
identities presented in Section 3.10. Reference will also be made to minterm code (logic 0 for
a complemented variable and logic 1 for an uncomplemented variable), and to maxterm code
which is the dual of minterm code as discussed in Section 4.2. The EV K-map methods used
in this chapter may be considered as an extension of the conventional methods discussed in
Sections 4.6 and 4.7.

5.2 XOR-TYPE PATTERNS AND EXTRACTION OF GATE-MINIMUM COVER
FROM EV K-MAPS

There are four types of XOR patterns that can be easily identified in EV K-maps:

1. Diagonal patterns
2. Adjacent patterns
3. Offset patterns
4. Associative patterns

References will frequently be made to the so-called XOR-type patterns in EV K-maps.
These are references to the diagonal, adjacent, offset, and associative patterns listed above
and are found only in compressed K-maps. A Mi-order K-map compression results when
an W-variable function is represented in an nth-order K-map — that is, k = N — n. Of the
XOR-type patterns, only the offset pattern requires third and higher order K-maps for its
appearance. K-maps used in the following discussions are all minterm code based, but are
used to extract gate-minimum functions in both minterm code and maxterm code.
Simple examples of the first three patterns are shown in Fig. 5. la, where a six-variable
function has been compressed into a third-order EV K-map. Empty cells 0 and 2 in Fig. 5. la
are to be disregarded so as to focus attention on the patterns: The diagonal pattern formed by
cells 1 and 4 is read in minterm code as BX(A © C) or in maxterm code asB + X + AQC.