K-disjointness paradigm with application to symmetry detection for incompletely specified functions

ABSTRACT

In this paper, we propose a K-disjointness paradigm that can effectively search all pairs of minterms with Hamming distance K between two Boolean functions. By this paradigm, we correlate it with symmetry detection problem and propose an efficient symmetry detection algorithm for Boolean functions. Our algorithm can not only handle completely specified functions but also incompletely specified functions. Experimental results on a set of MCNC and ISCAS benchmarking circuits show that our algorithm is indeed very effective and efficient for detecting symmetries of large Boolean functions.

REFERENCES

• 1: B. G. Kim and D. L. Dietmeyer, "Multilevel logic synthesis of symmetric switching functions," IEEE Trans. on Computer-Aided Design, vol. 10, pp. 436--446, April 1991.
• 2: Victor N. Kravets , Karem A. Sakallah, Constructive library-aware synthesis using symmetries, Proceedings of the conference on Design, automation and test in Europe, p.208-215, March 27-30, 2000, Paris, France [doi>10.1145/343647.343734]
• 3: Chien-Chung Tsai , Malgorzata Marek-Sadowska, Boolean matching using generalized Reed-Muller forms, Proceedings of the 31st annual conference on Design automation, p.339-344, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196404]
• 4: B. J. Falkowski and S. Kannurao, "Skew symmetry detection using the Walsh Spectral Coefficients,"in Proc. International Symposium on Circuit and System, 2000, vol. 2, pp. 321--324.
• 5: Fadi A. Aloul , Arathi Ramani , Igor L. Markov , Karem A. Sakallah, Solving difficult SAT instances in the presence of symmetry, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514102]
• 6: Randal E. Bryant, Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, Aug. 1986 [doi>10.1109/TC.1986.1676819]
• 7: C. Scholl , S. Melchior , G. Hotz , P. Molitor, Minimizing ROBDD Sizes of Incompletely Specified Boolean Functions by Exploiting Strong Symmetries, Proceedings of the 1997 European conference on Design and Test, p.229, March 17-20, 1997
• 8: Dirk Möller , Janett Mohnke , Michael Weber, Detection of symmetry of Boolean functions represented by ROBDDs, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.680-684, November 07-11, 1993, Santa Clara, California, United States
• 9: Alan Mishchenko, "Fast Computation of Symmetries in Boolean Functions,"IEEE Trans. Computer-Aided-Design, vol. 18, pp. 1588--1593, Nov. 2003.
• 10: C. Scholl, D. Moller, P. Molitor, and R. Drechsler, "BDD minimization using symmetries" IEEE Trans. Computer-Aided-Design, vol. 18, pp. 81--100, Feb. 1999.
• 11: S. Rahardja, B. J. Falkowski, "Symmetry conditions of Boolean functions in complex Hadamard transform," Electronics Letters, vol. 34, pp. 1634--1635, Aug. 1998.
• 12: Chien-Chung Tsai , Malgorzata Marek-Sadowska, Generalized Reed-Muller Forms as a Tool to Detect Symmetries, IEEE Transactions on Computers, v.45 n.1, p.33-40, January 1996 [doi>10.1109/12.481484]
• 13: Kuo-Hua Wang , Jia-Hung Chen, Symmetry detection for incompletely specified functions, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996690]
• 14: F. Somenzi, CUDD Package, Release 2.3.1. {Online} Availabe: http://vlsi/Colorado.EDU/ fabio/CUDD/cuddIntro.html
• 15: Shin-ichi Minato, Zero-suppressed BDDs for set manipulation in combinatorial problems, Proceedings of the 30th international conference on Design automation, p.272-277, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164890]
• 16: A. Mishchenko. EXTRA library of DD procedures. {Online}. Available: http://www.ee.pdx.edu/ alanmi/research/extra.htm
• 17: E. M. Sentovich, K. J. Singh, L. Lavagno, C. Moon, R. Murgai, A. Saldanha, H. Savoj, P. R. Stephan, R. K. Brayton, A. Sangiovanni-Vincentelli, "SIS: A System for Sequential Circuit Synthesis", Electronics Research Laboratory, Memorandum No. UCB/ERL M92/41, 4 May 1992.