Page 234 - Engineering Digital Design

5.4 K-MAP PLOTTING AND ENTERED VARIABLE XOR PATTERNS 205

As a second example, consider function / in Fig. 5.2b, which has been extracted in
maxterm code. Verification of this function is also accomplished in six steps:

I = (A + B + XQ Y)(A + B + X O Z)(A + B + Y O Z) (1) From K-map
== (A + B + X O Y) O (A + B + X O Z) O (A + B + Y O Z) (2) By Eq. (3.26)
= (A + B + X) O (A + B + 7) O (A + B + X) 0 (A + 5 + Z)
O (A + B + Y) O (A + B + Z) (3) By Eqs. (3.19)
= [B + (A + X) O (A + X)] O [Y + (A + B) O (A + B)]
O [A + Z + (B O B)] (4) By Eqs. (3.19)
= [B + (A + X)(A + X)] O [7 + (A + B)(A + B)] O [A + Z] (5) By Eq. (3.26)
= [B + (A © X)] O [Y + (A © 5)] O [A + Z] (6) By Eqs. (3.4)

In going from step 3 to step 4, commutivity was applied before application of Eqs. (3.19).
Also, in step 4, B Q B = 0.

5.4 K-MAP PLOTTING AND ENTERED VARIABLE XOR PATTERNS

At the onset let it be understood that one does not usually hunt for applications of the
XOR pattern minimization methods described here. It is possible to do this, as the example
in this section illustrates, but it is more likely that such methods would be applied to
EV XOR patterns that occur naturally in the design of a variety of combinational logic
devices. Examples of these include a 2 x 2 bit "fast" multiplier, comparator design, Gray-
to-binary code conversion, XS3-to-BCD code conversion, dedicated ALU design, binary-
to-2's complement conversion, and BCD to 84-2-1 code conversion, to name but a few, most
covered in later chapters. EV XOR patterns may also occur quite naturally in the design of
some state machines as, for example, the linear feedback shift register counters discussed
in Subsection 12.4.3.
EV K-map plotting for the purpose of extracting a gate-minimum cover by using XOR
patterns is not an exact science, and it is often difficult to find the optimum K-map com-
pression involving specific EVs, hence specific K-map axis variables. However, for some
functions it is possible to plot the map directly from the canonical form, as illustrated by
the example that follows. For some relatively simple functions, the K-map plotting process
can be deduced directly from the canonical expression. Consider the simple function given
in canonical code form:

f(W, X, Y, Z) = Em(l, 2, 3, 6, 7, 8, 11, 12, 13). (5.13)

Shown in Fig. 5.3 are the conventional (1's and O's) K-map and the second-order compres-
sion (two EVs) K-map derived directly from the conventional K-map. The two-level SOP
minimum and the multilevel XOR/SOP gate-minimum forms are

f SOP = WXZ + WXY + WYZ + XYZ + WY (5.14)