For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Boolean Factorization Using an Extended Boolean Matrix
Oh-Hyeong KWON Sung Je HONG Jong KIM
IEICE TRANSACTIONS on Information and Systems
Publication Date: 1998/12/25
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Computer Hardware and Design
factored form, kernel, cokernel, Boolean matrix, rectangle covering,
Full Text: PDF>>
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.