Symmetry detection for incompletely specified functions

ABSTRACT

In this paper, we formulate symmetry detection for incompletely specified functions as an equation without using cofactor computation and equivalence checking. Based on this equation, a symmetry detection algorithm is proposed. This algorithm can simultaneously find non-equivalence and equivalence symmetries. Experimental results on a set of benchmarks show that our algorithm is indeed very effective in solving symmetry detection problem for incompletely specified functions.

REFERENCES

• 1: A. Mukhopadhyay, "Detection of total or partial symmetry of a switching function with the use of decomposition charts," IEEE Trans. Electron. Comput., vol. EC-12, pp. 535--557, Oct. 1963.
• 2: D.L. Dietmeyer and P.R. Schneider, "Identification of symmetry, redundancy, and equivalence of Boolean functions," IEEE Trans. Electron. Comput. vol. 16, pp. 804--817, Dec. 1967.
• 3: 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.
• 4: R. Drechsler and B. Becker, "Sympathy: fast exact minimization of fixed polarity Reed-Muller expressions for symmetric functions," IEEE Trans. on Computer-Aided Design, Vol. 16, pp. 1--5, Jan. 1997.
• 5: 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]
• 6: 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]
• 7: 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]
• 8: C. Chang , B. Hu , M. Marek-Sadowska, In-place delay constrained power optimization using functional symmetries, Proceedings of the conference on Design, automation and test in Europe, p.377-382, March 2001, Munich, Germany
• 9: S. Chakrabarti, S. Das, D.K. Das, and B.B. Bhattacharya, "Synthesis of symmetric functions for path-delay fault testability," IEEE Trans. Computer-Aided Design, vol. 9, pp. 1076--1081, Sept. 2000.
• 10: 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
• 11: 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]
• 12: 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.
• 13: Alan Mishchenko, "Fast computation of symmetries in Boolean functions," IEEE Trans. Computer-Aided-Design, vol. 18, pp. 1588--1593, Nov. 2003.
• 14: S. Rahardja, B.J. Falkowski, "Symmetry conditions of Boolean functions in complex Hadamard transform," Electronics Letters, vol. 34, pp. 1634--1635, Aug. 1998.
• 15: 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]
• 16: B.J. Falkowski and S. Kannurao, "Skew symmetry detection using the Walsh spectral coefficients," in Proc. International Symposium on Cirucuit and System, 2000, vol. 2, pp. 321--324.
• 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.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Automatic synthesis

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Switching theory

General Terms:
Design, Theory

Keywords:
equivalence symmetry, non-equivalence symmetry