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

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.