Afshin Abdollahi
Massoud Pedram
ABSTRACT
An efficient and compact canonical form is proposed for the Boolean matching problem under permutation and complementation of variables. In addition an efficient algorithm for computing the proposed canonical form is provided. The efficiency of the algorithm allows it to be applicable to large complex Boolean functions with no limitation on the number of input variables as apposed to previous approaches, which are not capable of handling functions with more than seven inputs. Generalized signatures are used to define and compute the canonical form while symmetry of variables is used to minimize the computational complexity of the algorithm. Experimental results demonstrate the efficiency and applicability of the proposed canonical form.
- G. De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill, 1994. Google Scholar
Digital Library
- L. Benini and G. De Micheli, "A survey of Boolean matching techniques for library binding," ACM Trans. Design Automation of Electronic Systems, vol. 2, no. 3, pp. 193--226, July 1997. Google ScholarDigital Library
- M. A. Harrison, Introduction to Switching and Automata Theory, McGraw-Hill, 1965.Google Scholar
- J. Mohnke, P. Molitor, and S. Malik, "Limits of using signatures for permutation independent Boolean comparison," Proc. of ASP Design Automation Conf., pp. 459--464, 1995. Google ScholarDigital Library
- J. R. Burch and D. E. Long, "Efficient Boolean function matching," in Proc. Int. Conf. on Computer-Aided Design, pp. 408--411, Nov. 1992. Google ScholarDigital Library
- Q. Wu, C. Y. R. Chen, and J. M. Acken, "Efficient Boolean matching algorithm for cell libraries," Proc. IEEE Int. Conf. on Computer Design, pp. 36--39, Oct. 1994. Google ScholarDigital Library
- U. Hinsberger and R. Kolla, "Boolean matching for large libraries," Proc. of Design Automation Conf., pp. 206--211, June 1998. Google ScholarDigital Library
- D. Debnath and T. Sasao, "Fast Boolean matching under permutation using representative," Proc. ASP Design Automation Conf., pp. 359--362, Jan. 1999.Google Scholar
- J. Ciric and C. Sechen, "Efficient canonical form for Boolean matching of complex functions in large libraries," IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, vol. 22, no. 5, pp. 535--544, May 2003. Google ScholarDigital Library
- D. Debnath and T. Sasao, "Efficient computation of canonical form for Boolean matching in large libraries," Proc. ASP Design Automation Conf., pp. 591--596, Jan. 2004. Google ScholarDigital Library
- C. R. Edwards and S. L. Hurst, "A digital synthesis procedure under function symmetries and mapping methods", IEEE Trans. Comp., Vol. C-27, No. 11, pp. 985--997, NOV. 1978.Google Scholar
Index Terms
- A new canonical form for fast boolean matching in logic synthesis and verification
Recommendations
An efficient cost-based canonical form for Boolean matching
GLSVLSI '07: Proceedings of the 17th ACM Great Lakes symposium on VLSIIn 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 ...
Efficient canonical form for boolean matching of complex functions in large libraries
ICCAD '01: Proceedings of the 2001 IEEE/ACM international conference on Computer-aided designA new algorithm is developed which transforms the truth table or implicant table of a Boolean function into a canonical form under any permutation of inputs. The algorithm is used for Boolean matching for large libraries that contain cells with large ...
Comments