| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Generalized Reed-Muller Forms as a Tool to Detect Symmetries
January 1996 (vol. 45 no. 1)
pp. 33-40
Abstract—In this paper, we present a new method for detecting groups of symmetric variables of completely specified Boolean functions. The canonical Generalized Reed-Muller(GRM) forms are used as a powerful analysis tool. To reduce the search space we have developed a set of signatures that allow us to identify quickly sets of potentially symmetric variables. Our approach allows for detecting symmetries of any number of inputs simultaneously. Totally symmetric functions can be detected very quickly. The traditional definitions of symmetry have also been extended to include more types. This extension has the advantage of grouping input variables into more classes. Experiments have been performed on MCNC benchmark cases and the results verify the efficiency of our method.
[1] S.B. Akers,"Binary decision diagrams," IEEE Trans. Computers, vol. 27, no. 6, pp. 509-516, June 1978.
[2] P.W. Besslich,"Efficient computer method for ExOR logic design," IEE Proc., vol. 130, pt. E, no. 6, pp. 203-206, Nov. 1983.
[3] R.E. Bryant, "Graph-Based Algorithms for Boolean Function Manipulation," IEEE Trans. Computers, Vol. C-35, No. 8, Aug. 1986, pp. 667-690.
[4] D.I. Cheng and M. Sadowska, "Verifying Equivalence of Functions with Unknown Input Correspondence," Proc. EDAC, pp. 81-85, Feb. 1993.
[5] S.R. Das and C.L. Sheng,"On detecting total or partial symmetry of switching functions," IEEE Trans. Computers, vol. 20, no. 3, pp. 352-355, Mar. 1971.
[6] M. Davio,J.P. Deschamps, and A. Thayse,Discrete and Switching Functions. McGraw-Hill Int'l, 1978.
[7] D.L. Dietmeyer and P.R. Schneider,"Identification of symmetry, redundancy and equivalence of Boolean functions," IEEE Trans. Elec. Computers, vol. 16, no. 6, pp. 804-817, Dec. 1967.
[8] C.R. Edwards and S.L. Hurst,"A digital synthesis procedure under function symmetries and mapping methods," IEEE Trans. Computers, vol. 27, no. 11, pp. 985-997, Nov. 1978.
[9] M.A. Harrison,Introduction to Switching and Automata Theory. McGraw-Hill Int'l, 1965.
[10] V. Kebschull and W. Rosenstiel, "Efficient Graph-Based Computation and Manipulation of Functional Decision Diagrams," Proc. EDAC, pp. 278-282, 1993.
[11] D. Moller, J. Mohnke, and M. Weber, "Detection of Symmetry of Boolean Functions Represented by ROBDDs," Proc. ICCAD-93, pp. 680-684, 1993.
[12] A. Mukhopadhyay,"Detection of total or partial symmetry of a switching function with the use of decomposition charts," IEEE Trans. Elec. Computers, vol. 16, pp. 553-557, Oct. 1963.
[13] A. Mukhopadhyay and G. Schmitz,"Minimization of exclusive or and logical equivalence switching circuits," IEEE Trans. Computers, vol. 19, no. 2, pp. 132-140, Feb. 1970.
[14] C. Tsai and M. Marek-Sadowska,"Efficient minimization algorithms for fixed polarity AND/XOR canonical networks," Proc. Third Great Lakes Symp. VLSI 1993, pp. 76-79.
[15] C. Tsai and M. Marek-Sadowska,"Detecting symmetric variables in Boolean functions using generalized Reed-Muller forms," Proc. IEEE Int'l Symp. Circuits and Systems, pp. 287-290, May 1994.
[16] C. Tsai and M. Marek-Sadowska,"Boolean matching using generalized Reed-Muller forms," Proc. 31st ACM/IEEE Design Automation Conf., pp. 339-344, June 1994.
[17] X. Wu,X. Chen, and S.L. Hurst,"Mapping of Reed-Muller coefficients and the minimisation of exclusive OR-switching functions," IEE Proc., vol. 129, pt. E, no. 1, pp. 15-20, Jan. 1982.
Index Terms:
Boolean functions, generalized Reed-Muller forms, signatures, symmetry.
Citation:
Chien-Chung Tsai, Malgorzata Marek-Sadowska, "Generalized Reed-Muller Forms as a Tool to Detect Symmetries," IEEE Transactions on Computers, vol. 45, no. 1, pp. 33-40, Jan. 1996, doi:10.1109/12.481484
