Boolean division and factorization using binary decision diagrams

Author

Stanion, Ted ; Sechen, Carl

Author_Institution

Dept. of Electr. Eng., Washington Univ., Seattle, WA, USA

Volume

13

Issue

9

fYear

1994

fDate

9/1/1994 12:00:00 AM

Firstpage

1179

Lastpage

1184

Abstract

A method for performing Boolean division and factorization using a new cofactor operation, the interval cofactor, is proposed. This method Is efficiently implemented using BDD´s and allows for the use of external and internal don´t care sets. As well as generating a normal factored form, the method also generates an extended factored form that allows for the use of the exclusive-OR function in the expression. Using this extended form, much better factorizations may sometimes be found. The method was implemented in Catamount, a logic synthesis system currently under development. The method compares favorably to existing algebraic methods

Keywords

Boolean functions; CMOS integrated circuits; integrated logic circuits; logic CAD; many-valued logics; Boolean division; Boolean factorization; Catamount; binary decision diagrams; cofactor operation; don´t care sets; exclusive-OR function; extended factored form; interval cofactor; logic synthesis system; Binary decision diagrams; Boolean algebra; Boolean functions; CMOS logic circuits; CMOS technology; Data mining; Data structures; Kernel; Logic functions; Polynomials;

fLanguage

English

Journal_Title

Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on

Publisher

ieee

ISSN

0278-0070

Type

jour

DOI

10.1109/43.310907

Filename

310907