Efficient canonical form for Boolean matching of complex functions in large libraries

Author

Ciric, J. ; Sechen, C.

Author_Institution

Synplicity Inc., Sunnyvale, CA, USA

fYear

2001

fDate

4-8 Nov. 2001

Firstpage

610

Lastpage

617

Abstract

A new algorithm is developed which transforms the truth table or implicant table of a Boolean function into a canonical form under any permutation of inputs. The algorithm is used for Boolean matching for large libraries that contain cells with large numbers of inputs and implicants. The minimum cost canonical form is used as a unique identifier for searching for the cell in the library. The search time is nearly constant if a hash table is used for storing the cells´ canonical representations in the library. Experimental results on more than 100,000 gates confirm the validity and feasible run-time of the algorithm.

Keywords

Boolean algebra; cellular arrays; circuit CAD; formal verification; logic CAD; logic gates; software libraries; Boolean function; Boolean matching; canonical form; cell libraries; complex functions; feasible run-time; hash table; implicant table; logic gates; logic synthesis; logic verification; truth table; Binary decision diagrams; Boolean functions; Costs; Data structures; Input variables; Libraries; Logic testing; Network synthesis; Runtime; Sufficient conditions;

fLanguage

English

Publisher

ieee

Conference_Titel

Computer Aided Design, 2001. ICCAD 2001. IEEE/ACM International Conference on

Conference_Location

San Jose, CA, USA

ISSN

1092-3152

Print_ISBN

0-7803-7247-6

Type

conf

DOI

10.1109/ICCAD.2001.968724

Filename

968724