Page 218 - Engineering Digital Design

PROBLEMS 189

cited in countless publications. A few representative sources of these methods are presented
here. Included are some of the original references as well as some of the more current ones,
which often provide useful summaries of the methods.

[8] E. J. McCluskey, Logic Design Principles. Prentice-Hall, Englewood Cliffs, NJ, 1986.
[9] E. J. McCluskey, "Minimization of Boolean Functions," Bell Syst. Tech. J. 35(5), 1417-1444
(1956).
[10] W. V. Quine, "The Problem of Simplifying Truth Functions," Am. Math Monthly 59(8), 521-531
(1952).
[11] R. K. Brayton, G. Hachtel, C. McMullen, and A. Sangiovanni-Vincentelli, Logic Minimization
Algorithms for VLSI Synthesis. Kluwer Academic Publishers, Boston, 1984.
[12] R. Rudell and A. Sangiovanni-Vincentelli, "Multiple-valued Minimization for PLA Optimiza-
tion," IEEE Transactions on CAD/CAS CAD-6(5), 727-750 (1987).
[13] R. K. Brayton, P. C. McGeer, J. V. Sanghavi, and A. L. Sangiovanni-Vincentelli, "A New Exact
Minimizer for Two-Level Logic Synthesis," in Logic Synthesis and Optimization (T. Sasao, Ed.).
Kluwer Academic Publishers, Boston, 1993.
References on the factorization, resubstitution, and decomposition methods of optimiza-
tion of multilevel circuits are fairly numerous but are set in fairly advanced notation. Perhaps
the most useful are those found in texts by De Micheli, Kohavi, and Dietmeyer, and in the
reference book edited by Sasao. Advanced preparation by the reader is recommended for
use of these references. The text of De Micheli also has useful discussions of the area/delay
trade-off factors.

[14] G. De Micheli, Synthesis and Optimization of Digital Circuits. McGraw-Hill, New York, 1994.
[15] D. L. Dietmeyer, Logic Design of Digital Systems, 2nd ed., Allyn and Bacon, Boston, 1971.
[16] M. Fujita, Y. Matsunaga, Y. Tamiya, and K.-C. Chen, "Multi-Level Logic Minimization of Large
Combinational Circuits by Partitioning," in Logic Synthesis and Optimization (T. Sasao, Ed.).
Kluwer Academic Publishers, Boston, 1993.
[17] Z. Kohavi, Switching and Finite Automata Theory. McGraw-Hill, New York, 1978.

PROBLEMS

4.1 Expand each of the following expressions into canonical (literal) form by using the
appropriate Boolean laws:
(a) e(a,b) = a + b
(b) f(x,y ) = x+xy
(c) g(A,B, C) = ABC+ABC+AB+BC + ABC
(d) h(X, Y, Z) = (X + Y)(X + Y + Z)(F + Z)(X + Y + Z)
(e) E(A, B, C, D) = (A + BQ(B + D)(A +C + D)(A + B + C + D)(B + D}
(f) F(w, x, y, z) = wxyz + wxz + xyz + wxyz + xz + wxyz + wxyz
(g) G(a, b, c, d,) = (a + b + c + d)(b + c + d)(d + b)(b + d)(d + c + d}
(h) H(V, W, X, Y) = VWXY + XY + WXY + VWXY + VXY+ VWXY + WXY
4.2 Place each of the three-variable functions below in a canonical truth table and in a
conventional (1 's and O's) K-map. Place the variables on the K-map axes in alphabetical