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

Author

Ciric, Jovanka ; Seche, Carl

Author_Institution

Univ. of Washington, Seattle, WA, USA

Volume

22

Issue

5

fYear

2003

fDate

5/1/2003 12:00:00 AM

Firstpage

535

Lastpage

544

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 100000 gates confirm the validity and feasible runtime of the algorithm.

Keywords

Boolean functions; logic CAD; symmetry; tree searching; Boolean function; Boolean matching; branch-and-bound algorithm; cell canonical representations; circuit design; circuit optimization; efficient canonical form; hash table; implicant table; large libraries; minimum cost canonical form; search time; technology mapping; tight bounding function; truth table; unique identifier; Binary decision diagrams; Boolean functions; Circuit optimization; Circuit synthesis; Costs; Data structures; Libraries; Logic testing; Network synthesis; Runtime;

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/TCAD.2003.810744

Filename

1196197