EDA Tech Forum publishes the second of the two 'best of' papers from the 2005 Design Automation Conference. The contributors this quarter are Afshin Abdollahi and Massoud Pedram from the University of Southern California.
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.
are required.