An efficient cost-based canonical form for Boolean matching

ABSTRACT

In this paper, we present new canonical forms for P, NP and NPN equivalence relations on boolean functions. The canonical forms are based on the minimization of a cost function. With respect to previous approaches based on cost minimization, our function allows the minimization algorithm to explore a reduced solution space. This reduction is obtained by partitioning the columns of the boolean function through an equivalence relation. NP and NPN canonical forms are obtained by means of a preprocessing step of negligible computational overhead.

REFERENCES

• 1: Afshin Abdollahi , Massoud Pedram, A new canonical form for fast boolean matching in logic synthesis and verification, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA [doi>10.1145/1065579.1065681]
• 2: K. Beauchamp. Applications of Walsh and Related Functions. Academic Press, 1984.
• 3: Luca Benini , Giovanni De Micheli, A survey of Boolean matching techniques for library binding, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.2 n.3, p.193-226, July 1997 [doi>10.1145/264995.264996]
• 4: Jerry R. Burch , David E. Long, Efficient Boolean function matching, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.408-411, November 1992, Santa Clara, California, United States
• 5: Jovanka Ciric and Carl Sechen. Efficient canonical form for boolean matching of complex functions in large libraries. Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, 22(5):535--544, May 2003.
• 6: Janett Mohnke , Paul Molitor , Sharad Malik, Limits of using signatures for permutation independent Boolean comparison, Proceedings of the 1995 conference on Asia Pacific design automation (CD-ROM), p.74-es, August 29-September 01, 1995, Makuhari, Massa, Chiba, Japan [doi>10.1145/224818.224955]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.m Miscellaneous

General Terms:
Design

Keywords:
boolean matching, logic sinthesys, technology mapping