A Boolean factorization using an extended Boolean matrix

Abstract

A factorization, which provides a factored form, is an extremely important part of multi-level logic synthesis. The number of literals in a factored form is a good estimate of the complexity of a logic function, and can be translated directly into the number of transistors required for implementation. Factored Forms are described as either algebraic or Boolean, according to the trade-off between run-time and optimization. A Boolean factored form contains fewer number of literals than an algebraic factored form. In this paper, we present a new method for a Boolean factorization. The key idea is to build an extended Boolean matrix using cokernel/kernel pairs and kernel/kernel pairs together. The extended Boolean matrix makes it possible to yield a Boolean factored form. We also propose a heuristic method for covering of the extended Boolean matrix. Experimental results on various benchmark circuits show the improvements in literal counts over the algebraic factorization based on Brayton's Boolean matrix.