Fast Boolean matching for field-programmable gate arrays

Kai Zhu, D.F. Wong

Research output: Chapter in book/report/conference proceedingConference proceeding

8 Citations (Scopus)


A key step in technology mapping for non-lookup-table (such as multiplexer) based FPGAs (field programmable gate arrays) 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. When compared to the matching algorithm by searching for isomorphism on all different BDDs (binary decision diagrams), the new algorithm is much faster with a modest increase of memory requirement. For example, the experimental results showed that in matching all three-input Boolean function against Actel's ACT1 logic module, the new algorithm is 634 times faster by using 19.9% more memory.
Original languageEnglish
Title of host publicationProceedings of EURO-DAC 93 and EURO-VHDL 93- European Design Automation Conference
Number of pages6
ISBN (Print)0818643501
Publication statusPublished - 24 Sept 1993
EventEURO-DAC 93 and EURO-VHDL 93- European Design Automation Conference - Hamburg, Germany
Duration: 20 Sept 199324 Sept 1993

Publication series

NameEuropean Design Automation Conference


ConferenceEURO-DAC 93 and EURO-VHDL 93- European Design Automation Conference
Internet address

User-Defined Keywords

  • Field programmable gate arrays
  • Boolean functions
  • Data structures
  • Clustering algorithms
  • Logic arrays
  • Libraries
  • Logic functions
  • Boolean algebra
  • Pins
  • Logic gates


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

Cite this