A new canonical form for fast Boolean matching in logic synthesis and verification

Topics/Categories: Best of DAC 2005

• Print This Article
• Share This Article

• Issue: December 2005
• Download this issue

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. Previous approaches were 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.

Introduction

Boolean matching is the problem of determining whether one Boolean function can be functionally equivalent to another under a permutation of its inputs and complementation of some of its inputs. Boolean matching algorithms have many applications in logic synthesis including cell-library binding where it is necessary to repeatedly determine whether some part (cluster) of a Boolean network can be realized by any of the cells in a library.

Download article

This article is available as a PDF download (246 KB, Adobe Acrobat Reader required.)