Boolean factoring with kernels and rectangle covering

Abstract

A technique for factoring Boolean expressions which extends standard factorization algorithms by utilizing Boolean and topological information directly during the factorization process is presented. A representation for Boolean functions is introduced, and efficient algorithms for constructing this representation are given. Examples of the techniques are given, and the results of experiments using these methods to factor functions from the MCNC logic synthesis benchmark set are reported. Preliminary experimental results show improvements of up to 20% in literal count compared to MISII algebraic factoring.