Fast Boolean matching for field-programmable gate arrays

Kai Zhu, D. F. Wong

Research output: Chapter in Book/Report/Conference proceedingConference contribution


A key step in technology mapping for non lookup-table (such as multiplexor) based FPGAs is to determine whether a given function can be implemented by the logic module. A new algorithm is presented for solving this problem. The algorithm is based on a character string representation of binary decision diagrams. Such representation leads to a matching algorithm which requires only a few string comparisons for each matching operation. Comparing to the matching algorithm by searching for isomorphism on all different BDDs, the new algorithm is much faster with a modest increase of memory requirement.

Original languageEnglish (US)
Title of host publicationEuropean Design Automation Conference - Proceedings
Editors Anon
PublisherPubl by IEEE
Number of pages6
ISBN (Print)0818643528
StatePublished - 1993
Externally publishedYes

Publication series

NameEuropean Design Automation Conference - Proceedings

ASJC Scopus subject areas

  • Control and Systems Engineering


Dive into the research topics of 'Fast Boolean matching for field-programmable gate arrays'. Together they form a unique fingerprint.

Cite this