Page 259 - Engineering Digital Design

230 CHAPTER 5 / FUNCTION MINIMIZATION

[4] R. F. Tinder, "Multilevel Logic Minimization by Using K-map XOR Patterns," IEEE Trans, on
Ed. 38(4), 370-375 (1995).

Earlier work on Reed-Muller expansions and the use of conventional K-map methods
to obtain Reed-Muller coefficient values can be found in the work of Dietmeyer and Wu
et al.

[5] D. L. Dietmeyer, Logic Design of Digital Systems. Allyn and Bacon, 1978 (Chapter 2).
[6] X. Wu, X. Chen, and S. L. Hurst, "Mapping of Reed-Muller Coefficients and the Minimization
of Exclusive-OR Switching Functions," Proc. IEE, Part E, 129, 15-20 (1982).
An excellent experimental study of the various XOR and EQV (XNOR) CMOS gate
configurations can be found in the work of Wang, Fang, and Feng.

[7] J. Wang, S. Fang, and W. Feng, "New Efficient Designs for XOR and XNOR Functions on the
Transistor Level," IEEE Journal of Solid-State Circuits 29(7), 780-786 (1994).

Many approaches to the decomposition and minimization of multilevel (Reed-Muller)
forms can be found in literature. A few representative works are cited below:

[8] D. Bochman, F. Dresig, and B. Steinbach, "A New Decomposition Method for Multilevel Circuit
Design," The European Conference on Design Automation, Amsterdam, The Netherlands, 25-28
Feb. 1991, pp. 374-377.
[9] H. M. Fleisher and J. Yeager, "A Computer Algorithm for Minimizing Reed-Muller Canonical
Forms," IEEE Trans. Comput. 36(2), 247-250 (1987).
[10] J. M. Saul, "An Algorithm for the Multi-level Minimization of Reed-Muller Representations,"
IEEE Int. Conf.on Computer Design:VLSlin ComputersandProcessors (Cat. No. 91CH3040-3),
pp. 634-637. IEEE Computer Soc. Press, Los Alamitos, CA, 1991.
[11] T. Sasao, "Logic Synthesis with XOR Gates," in Logic Synthesis and Optimization (T. Sasao,
Ed.), Kluwer, 1993, pp. 259-285.
[12] N. Song and M. A. Perkowski, "EXORCISM-MV-2: Minimization of Exclusive Sum of Products
Expressions for Multiple-valued Input Incompletely Specified Functions," Proc. of the 23rd
International Symposium on Multiple-Valued Logic, ISMVL '93, Sacramento, CA, May 24—27,
1993, pp. 132-137.
[13] W. Wan and M. A. Perkowski, "A New Approach to the Decomposition of Incompletely Spe-
cified Functions Based on Graph-Coloring and Local Transformations and its Application to
FPGA Mapping," Proc. of the IEEE EURO-DAC '92 European Design Automation Conference,
Hamburg, Sept. 7-10, Hamburg, 1992, pp. 230-235.

PROBLEMS

Note: Most K-map minimization results of problems that follow can be verified by intro-
ducing the binary coordinates of each K-map cell into the resulting expression. Generation
of each cell sub/unction by this means validates the extraction results. In some cases, it
may be necessary to construct a suitable EV K-map for this purpose. Also, to obtain correct
answers for these problems, the reader will be required to make frequent use of the laws,
corollaries, and identities of XOR algebra given in Section 3.11.