IEICE TRANSACTIONS on Information
A New Algorithm for Boolean Matching Utilizing Structural Information
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E78-D No.3 pp.219-223
- Publication Date
- 1995/03/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Issue on Synthesis and Verification of Hardware Design)
- Category
- Logic Synthesis
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Yusuke MATSUNAGA, "A New Algorithm for Boolean Matching Utilizing Structural Information" in IEICE TRANSACTIONS on Information,
vol. E78-D, no. 3, pp. 219-223, March 1995, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/e78-d_3_219/_p
Copy
@ARTICLE{e78-d_3_219,
author={Yusuke MATSUNAGA, },
journal={IEICE TRANSACTIONS on Information},
title={A New Algorithm for Boolean Matching Utilizing Structural Information},
year={1995},
volume={E78-D},
number={3},
pages={219-223},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={March},}
Copy
TY - JOUR
TI - A New Algorithm for Boolean Matching Utilizing Structural Information
T2 - IEICE TRANSACTIONS on Information
SP - 219
EP - 223
AU - Yusuke MATSUNAGA
PY - 1995
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E78-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 1995
AB - 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.
ER -
English
