A Boolean Factorization Using an Extended Boolean Matrix

Oh-Hyeong KWON; Sung Je HONG; Jong KIM

A Boolean Factorization Using an Extended Boolean Matrix

Oh-Hyeong KWON, Sung Je HONG, Jong KIM

Full Text Views

0

Share
Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Information Vol.E81-D No.12 pp.1466-1472

Publication Date: 1998/12/25

Publicized

Online ISSN

DOI

Type of Manuscript

Category: Computer Hardware and Design

Cite this

Copy

Oh-Hyeong KWON, Sung Je HONG, Jong KIM, "A Boolean Factorization Using an Extended Boolean Matrix" in IEICE TRANSACTIONS on Information, vol. E81-D, no. 12, pp. 1466-1472, December 1998, doi: .
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.
URL: https://globals.ieice.org/en_transactions/information/10.1587/e81-d_12_1466/_p

Copy

@ARTICLE{e81-d_12_1466,
author={Oh-Hyeong KWON, Sung Je HONG, Jong KIM, },
journal={IEICE TRANSACTIONS on Information},
title={A Boolean Factorization Using an Extended Boolean Matrix},
year={1998},
volume={E81-D},
number={12},
pages={1466-1472},
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.},
keywords={},
doi={},
ISSN={},
month={December},}

Copy

TY - JOUR
TI - A Boolean Factorization Using an Extended Boolean Matrix
T2 - IEICE TRANSACTIONS on Information
SP - 1466
EP - 1472
AU - Oh-Hyeong KWON
AU - Sung Je HONG
AU - Jong KIM
PY - 1998
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E81-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 1998
AB - 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.
ER -