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
Dans plusieurs méthodes de conception de circuits Pass-Transistor Logic (PTL), les fonctions booléennes sont exprimées sous forme d'OBDD sous forme décomposée, puis les composants OBDD sont directement mappés sur les cellules PTL. La taille totale des OBDD (nombre de nœuds) correspond à la taille du circuit. Dans cet article, nous étudions une méthode de synthèse PTL basée sur la minimisation exacte des BDD libres (FBDD). Les FBDD sont une extension bien étudiée des OBDD avec un ordre de variables libre sur chaque chemin. Nous présentons des statistiques montrant que plus de 56 % des 616126 5 classes d’équivalence NPN de fonctions booléennes à 5 variables ont des FBDD minimum de taille inférieure à leurs OBDD. Ce résultat peut être utilisé pour la synthèse PTL en tant que bibliothèques. Nous avons également appliqué l'algorithme de minimisation exacte des FBDD à la minimisation des sous-circuits dans la synthèse des benchmarks MCNC et avons constaté une réduction de taille allant jusqu'à XNUMX %.
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
Kazuyoshi TAKAGI, Hiroshi HATAKEDA, Shinji KIMURA, Katsumasa WATANABE, "Exact Minimization of Free BDDs and Its Application to Pass-Transistor Logic Optimization" in IEICE TRANSACTIONS on Fundamentals,
vol. E82-A, no. 11, pp. 2407-2413, November 1999, doi: .
Abstract: In several design methods for Pass-transistor Logic (PTL) circuits, Boolean functions are expressed as OBDDs in decomposed form and then the component OBDDs are directly mapped to PTL cells. The total size of OBDDs (number of nodes) corresponds to the circuit size. In this paper, we investigate a method for PTL synthesis based on exact minimization of Free BDDs (FBDDs). FBDDs are well-studied extension of OBDDs with free variable ordering on each path. We present statistics showing that more than 56% of 616126 NPN-equivalence classes of 5-variable Boolean functions have minimum FBDDs with less size than their OBDDs. This result can be used for PTL synthesis as libraries. We also applied the exact minimization algorithm of FBDDs to the minimization of subcircuits in the synthesis for MCNC benchmarks and found up to 5% size reduction.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e82-a_11_2407/_p
Copier
@ARTICLE{e82-a_11_2407,
author={Kazuyoshi TAKAGI, Hiroshi HATAKEDA, Shinji KIMURA, Katsumasa WATANABE, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Exact Minimization of Free BDDs and Its Application to Pass-Transistor Logic Optimization},
year={1999},
volume={E82-A},
number={11},
pages={2407-2413},
abstract={In several design methods for Pass-transistor Logic (PTL) circuits, Boolean functions are expressed as OBDDs in decomposed form and then the component OBDDs are directly mapped to PTL cells. The total size of OBDDs (number of nodes) corresponds to the circuit size. In this paper, we investigate a method for PTL synthesis based on exact minimization of Free BDDs (FBDDs). FBDDs are well-studied extension of OBDDs with free variable ordering on each path. We present statistics showing that more than 56% of 616126 NPN-equivalence classes of 5-variable Boolean functions have minimum FBDDs with less size than their OBDDs. This result can be used for PTL synthesis as libraries. We also applied the exact minimization algorithm of FBDDs to the minimization of subcircuits in the synthesis for MCNC benchmarks and found up to 5% size reduction.},
keywords={},
doi={},
ISSN={},
month={November},}
Copier
TY - JOUR
TI - Exact Minimization of Free BDDs and Its Application to Pass-Transistor Logic Optimization
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2407
EP - 2413
AU - Kazuyoshi TAKAGI
AU - Hiroshi HATAKEDA
AU - Shinji KIMURA
AU - Katsumasa WATANABE
PY - 1999
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E82-A
IS - 11
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - November 1999
AB - In several design methods for Pass-transistor Logic (PTL) circuits, Boolean functions are expressed as OBDDs in decomposed form and then the component OBDDs are directly mapped to PTL cells. The total size of OBDDs (number of nodes) corresponds to the circuit size. In this paper, we investigate a method for PTL synthesis based on exact minimization of Free BDDs (FBDDs). FBDDs are well-studied extension of OBDDs with free variable ordering on each path. We present statistics showing that more than 56% of 616126 NPN-equivalence classes of 5-variable Boolean functions have minimum FBDDs with less size than their OBDDs. This result can be used for PTL synthesis as libraries. We also applied the exact minimization algorithm of FBDDs to the minimization of subcircuits in the synthesis for MCNC benchmarks and found up to 5% size reduction.
ER -