Page 229 - Engineering Digital Design

200 CHAPTER 5 / FUNCTION MINIMIZATION

5.2.1 Extraction Procedure and Examples
Before illustrating the extraction process by example, it will be instructive to outline the
extraction procedure. In this procedure, reference will be made to minterm and maxterm
codes for clarification purposes. Since all K-maps are minterm code based, extraction of
EQV/POS cover from them requires that the K-map domains be complemented, but not
the entered variables. Extraction of XOR/SOP cover follows conventional procedure. The
following six-step extraction procedure applies generally to all four types of XOR-type
patterns.

Extraction Procedure
Step I. Identify the type of EV XOR pattern that exists in the K-map. A diagonal pat-
tern requires identical K-map cell entries in diagonally located cells. An adjacent pattern
requires complementary K-map cell entries in logically adjacent cells. An offset pattern
requires identical cell entries in cells whose coordinates differ by two bits (a Hamming
distance of 2). Associative patterns require terms associated by an XOR or EQV connective
in at least one cell.
Step II. Write down the K-map domains in which the XOR pattern exists and any
subfunctions that are the same in the pattern. Remember that in maxterm code the domains
are complemented, whereas in minterm code they are not.
Step III. Extract the XOR pattern of type 1, 2, or 3 that exists by using the defining SOP
or POS relations for XOR and EQV given by Eqs. (3.4) and (3.5). Associative patterns,
of type 4, are extracted in a manner similar to the extraction of EV s- and p-terms as
discussed in Section 4.6. Thus, associative patterns with XOR connectives are extracted in
minterm code while those with EQV connectives are extracted in maxterm code. Compound
associative patterns involve some combination of associative pattern with one or more of
the other three patterns. They may also include the intersection (ANDing) of patterns or
the union (ORing) of patterns. In all cases involving an associative pattern, the associating
connective must be preserved in the resulting expression.
Step IV. Extract any remaining two-level SOP or POS cover that may exist.
Step V. Combine into SOP or POS form the results of steps I through IV. The resulting
expression may be altered as follows: Single complementation of an XOR/EQV-associated
term complements the XOR or EQV connective while double complementation of the asso-
ciated terms retains the original connective.
Step VI. If necessary, test the validity of the extraction process. This can be done by
introducing the K-map cell coordinates into the resulting expression. Generation of each
cell subfunction of the K-map validates the extraction procedure.

Examples The simplest associative patterns are formed between XOR-associated or EQV-
associated variables and like variables in adjacent cells. Three examples are presented in
Figs. 5.1b, 5.1c, and 5. Id, all representing second-order K-map compressions (two EVs).
For the first-order EV K-map, shown in Fig. 5.1b, the function E is read in minterm
code as

EXOVSOP = (A-X)®Y = (A + X)QY (5.1)