The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Les diagrammes de décision binaire (BDD) sont une représentation graphique des fonctions booléennes. En particulier, les BDD ordonnés (OBDD) sont utiles dans de nombreuses situations, car ils fournissent une représentation canonique et sont manipulés efficacement. Des packages BDD qui génèrent automatiquement des OBDD ont été développés et sont désormais largement utilisés dans le domaine de la conception logique, notamment la vérification formelle et la synthèse logique. La synthèse de circuits à transistors passe-bas est l'une des applications réussies de tels packages BDD. Les circuits à transistors passants sont générés à partir de BDD en mappant chaque nœud sur un sélecteur composé de deux ou quatre transistors passants. Si les circuits sont générés à partir de BDD plus petits, les circuits générés comportent un plus petit nombre de transistors et permettent ainsi d'économiser de la surface sur la puce et de la consommation d'énergie. Dans cet article, des BDD plus génériques qui n'ont aucune restriction dans l'ordre des variables et le nombre d'apparences variables sur leurs chemins sont appelés BDD génériques (GBDD), et un algorithme de génération de GBDD est proposé à des fins de synthèse de circuits à transistors passe-bas. L'algorithme proposé se compose de deux étapes. Lors de la première étape, des arbres d'analyse (PT) pour des formules booléennes données sont générés, où un PT est une représentation arborescente orientée de formules booléennes et se compose de nœuds littéraux et de nœuds d'opération. Dans cette étape, notre algorithme tente de réduire le nombre de nœuds littéraux des PT. Lors de la deuxième étape, un GBDD est généré pour les PT à l'aide de la méthode de concaténation, où la méthode de concaténation génère un GBDD en connectant les GBDD verticalement. Dans cette étape, notre algorithme tente de partager des sous-graphes isomorphes. Lors d'expériences sur des circuits de référence ISCAS'89 et MCNC, notre programme a généré avec succès 32 GBDD sur 680 fonctions à sortie unique et 4 GBDD sur 49 fonctions multi-sorties dont les tailles sont inférieures à celles des OBDD. La taille du GBDD est réduite de 23.1 % dans le meilleur des cas par rapport à l'OBDD.
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.
Copier
Tetsushi KATAYAMA, Hiroyuki OCHI, Takao TSUDA, "An Algorithm for Generating Generic BDDs" in IEICE TRANSACTIONS on Fundamentals,
vol. E83-A, no. 12, pp. 2505-2512, December 2000, doi: .
Abstract: Binary Decision Diagrams (BDDs) are graph representation of Boolean functions. In particular, Ordered BDDs (OBDDs) are useful in many situations, because they provide canonical representation and they are manipulated efficiently. BDD packages which automatically generate OBDDs have been developed, and they are now widely used in logic design area, including formal verification and logic synthesis. Synthesis of pass-transistor circuits is one of successful applications of such BDD packages. Pass-transistor circuits are generated from BDDs by mapping each node to a selector which consists of two or four pass transistors. If circuits are generated from smaller BDDs, generated circuits have smaller number of transistors and hence save chip area and power consumption. In this paper, more generic BDDs which have no restrictions in variable ordering and variable appearance count on its paths are called Generic BDDs (GBDDs), and an algorithm for generating GBDDs is proposed for the purpose of synthesis of pass-transistor circuits. The proposed algorithm consists of two steps. At the first step, parse trees (PTs) for given Boolean formulas are generated, where a PT is a directed tree representation of Boolean formula(s) and it consists of literal nodes and operation nodes. In this step, our algorithm attempts to reduce the number of literal nodes of PTs. At the second step, a GBDD is generated for the PTs using Concatenation Method, where Concatenation Method generates a GBDD by connecting GBDDs vertically. In this step, our algorithm attempts to share isomorphic subgraphs. In experiments on ISCAS'89 and MCNC benchmark circuits, our program successfully generated 32 GBDDs out of 680 single-output functions and 4 GBDDs out of 49 multi-output functions whose sizes are smaller than OBDDs. GBDD size is reduced by 23.1% in the best case compared with OBDD.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e83-a_12_2505/_p
Copier
@ARTICLE{e83-a_12_2505,
author={Tetsushi KATAYAMA, Hiroyuki OCHI, Takao TSUDA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={An Algorithm for Generating Generic BDDs},
year={2000},
volume={E83-A},
number={12},
pages={2505-2512},
abstract={Binary Decision Diagrams (BDDs) are graph representation of Boolean functions. In particular, Ordered BDDs (OBDDs) are useful in many situations, because they provide canonical representation and they are manipulated efficiently. BDD packages which automatically generate OBDDs have been developed, and they are now widely used in logic design area, including formal verification and logic synthesis. Synthesis of pass-transistor circuits is one of successful applications of such BDD packages. Pass-transistor circuits are generated from BDDs by mapping each node to a selector which consists of two or four pass transistors. If circuits are generated from smaller BDDs, generated circuits have smaller number of transistors and hence save chip area and power consumption. In this paper, more generic BDDs which have no restrictions in variable ordering and variable appearance count on its paths are called Generic BDDs (GBDDs), and an algorithm for generating GBDDs is proposed for the purpose of synthesis of pass-transistor circuits. The proposed algorithm consists of two steps. At the first step, parse trees (PTs) for given Boolean formulas are generated, where a PT is a directed tree representation of Boolean formula(s) and it consists of literal nodes and operation nodes. In this step, our algorithm attempts to reduce the number of literal nodes of PTs. At the second step, a GBDD is generated for the PTs using Concatenation Method, where Concatenation Method generates a GBDD by connecting GBDDs vertically. In this step, our algorithm attempts to share isomorphic subgraphs. In experiments on ISCAS'89 and MCNC benchmark circuits, our program successfully generated 32 GBDDs out of 680 single-output functions and 4 GBDDs out of 49 multi-output functions whose sizes are smaller than OBDDs. GBDD size is reduced by 23.1% in the best case compared with OBDD.},
keywords={},
doi={},
ISSN={},
month={December},}
Copier
TY - JOUR
TI - An Algorithm for Generating Generic BDDs
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2505
EP - 2512
AU - Tetsushi KATAYAMA
AU - Hiroyuki OCHI
AU - Takao TSUDA
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E83-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 2000
AB - Binary Decision Diagrams (BDDs) are graph representation of Boolean functions. In particular, Ordered BDDs (OBDDs) are useful in many situations, because they provide canonical representation and they are manipulated efficiently. BDD packages which automatically generate OBDDs have been developed, and they are now widely used in logic design area, including formal verification and logic synthesis. Synthesis of pass-transistor circuits is one of successful applications of such BDD packages. Pass-transistor circuits are generated from BDDs by mapping each node to a selector which consists of two or four pass transistors. If circuits are generated from smaller BDDs, generated circuits have smaller number of transistors and hence save chip area and power consumption. In this paper, more generic BDDs which have no restrictions in variable ordering and variable appearance count on its paths are called Generic BDDs (GBDDs), and an algorithm for generating GBDDs is proposed for the purpose of synthesis of pass-transistor circuits. The proposed algorithm consists of two steps. At the first step, parse trees (PTs) for given Boolean formulas are generated, where a PT is a directed tree representation of Boolean formula(s) and it consists of literal nodes and operation nodes. In this step, our algorithm attempts to reduce the number of literal nodes of PTs. At the second step, a GBDD is generated for the PTs using Concatenation Method, where Concatenation Method generates a GBDD by connecting GBDDs vertically. In this step, our algorithm attempts to share isomorphic subgraphs. In experiments on ISCAS'89 and MCNC benchmark circuits, our program successfully generated 32 GBDDs out of 680 single-output functions and 4 GBDDs out of 49 multi-output functions whose sizes are smaller than OBDDs. GBDD size is reduced by 23.1% in the best case compared with OBDD.
ER -