A Boolean Factorization Using an Extended Boolean Matrix

Oh-Hyeong KWON  Sung Je HONG  Jong KIM  

IEICE TRANSACTIONS on Information and Systems   Vol.E81-D   No.12   pp.1466-1472
Publication Date: 1998/12/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Computer Hardware and Design
factored form,  kernel,  cokernel,  Boolean matrix,  rectangle covering,  

Full Text: PDF>>
Buy this Article

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.