A New Algorithm for Boolean Matching Utilizing Structural Information

Yusuke MATSUNAGA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E78-D   No.3   pp.219-223
Publication Date: 1995/03/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Issue on Synthesis and Verification of Hardware Design)
Category: Logic Synthesis
Keyword: 
logic synthesis,  technology mapping,  Boolean matching,  binary decision diagrams,  

Full Text: PDF>>
Buy this Article




Summary: 
The paper describes a new algorithm for Boolean matching, which is based on BDD structure manipulation. Pruning of the search space takes place after partial assignments if certain subgraphs of two BDD's become inequivalent. This pruning is different from existing techniques, so that the search space is further reduced. Another feature of this algorithm is topological filtering. Usually, many functions have no matchings and this is easily found by only counting the number of minterms. To check it quickly, upper and lower bounds of minterm count are calculated from topological information. Using these bounds, functions that have no matchings are discarded without building their BDD's.