IEICE TRANSACTIONS on Fundamentals
Transformation of BDD into Heterogeneous MDD with Minimal Cost
Suzana STOJKOVI
, Milena STANKOVI, Radomir S. STANKOVI
Summary :
Decision diagrams (DDs) are data structures commonly used for representation of discrete functions with large number of variables. Binary DDs (BDDs) are used for representation and manipulation with Boolean functions. Complexity of a BDD is usually measured by its size, that is defined as the number of non-terminal nodes in the BDD. Minimization of the sizes of DDs is a problem greatly considered in literature and many related algorithms (exact and heuristic) have been proposed. However, there are many functions for which BDDs when minimized are still large and can have even an exponential size in the number of variables. An approach to derive compact decision diagram representations for such functions is transformation of BDDs into Multi-valued DDs (MDDs) and Heterogeneous MDDs (HMDDs). Complexity of MDDs and HMDDs is measured by the cost which is a generalization of the notion of the size by taking into account complexity of nodes in MDDs and HMDDs. This paper presents a method for transformation of BDD into HMDD with minimal cost. The proposed method reduces the time for determination of the type of nodes in HMDDs by introducing a matrix expressing dependency (interconnections) among nodes at different levels. Comparing to other methods for conversion of BDDs into HMDDs, the method reduces the number of traverses of a BDD necessary for collecting enough information to construct an equivalent HMDD. For an experimental verification of its efficiency, the method is applied to construction of HMDDs for some benchmark functions and their arithmetic and Walsh spectra.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E92-A No.10 pp.2580-2587
- Publication Date
- 2009/10/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E92.A.2580
- Type of Manuscript
- PAPER
- Category
- VLSI Design Technology and CAD
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
Suzana STOJKOVI, Milena STANKOVI, Radomir S. STANKOVI, "Transformation of BDD into Heterogeneous MDD with Minimal Cost" in IEICE TRANSACTIONS on Fundamentals,
vol. E92-A, no. 10, pp. 2580-2587, October 2009, doi: 10.1587/transfun.E92.A.2580.
Abstract: Decision diagrams (DDs) are data structures commonly used for representation of discrete functions with large number of variables. Binary DDs (BDDs) are used for representation and manipulation with Boolean functions. Complexity of a BDD is usually measured by its size, that is defined as the number of non-terminal nodes in the BDD. Minimization of the sizes of DDs is a problem greatly considered in literature and many related algorithms (exact and heuristic) have been proposed. However, there are many functions for which BDDs when minimized are still large and can have even an exponential size in the number of variables. An approach to derive compact decision diagram representations for such functions is transformation of BDDs into Multi-valued DDs (MDDs) and Heterogeneous MDDs (HMDDs). Complexity of MDDs and HMDDs is measured by the cost which is a generalization of the notion of the size by taking into account complexity of nodes in MDDs and HMDDs. This paper presents a method for transformation of BDD into HMDD with minimal cost. The proposed method reduces the time for determination of the type of nodes in HMDDs by introducing a matrix expressing dependency (interconnections) among nodes at different levels. Comparing to other methods for conversion of BDDs into HMDDs, the method reduces the number of traverses of a BDD necessary for collecting enough information to construct an equivalent HMDD. For an experimental verification of its efficiency, the method is applied to construction of HMDDs for some benchmark functions and their arithmetic and Walsh spectra.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E92.A.2580/_p
Copy
@ARTICLE{e92-a_10_2580,
author={Suzana STOJKOVI, Milena STANKOVI, Radomir S. STANKOVI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Transformation of BDD into Heterogeneous MDD with Minimal Cost},
year={2009},
volume={E92-A},
number={10},
pages={2580-2587},
abstract={Decision diagrams (DDs) are data structures commonly used for representation of discrete functions with large number of variables. Binary DDs (BDDs) are used for representation and manipulation with Boolean functions. Complexity of a BDD is usually measured by its size, that is defined as the number of non-terminal nodes in the BDD. Minimization of the sizes of DDs is a problem greatly considered in literature and many related algorithms (exact and heuristic) have been proposed. However, there are many functions for which BDDs when minimized are still large and can have even an exponential size in the number of variables. An approach to derive compact decision diagram representations for such functions is transformation of BDDs into Multi-valued DDs (MDDs) and Heterogeneous MDDs (HMDDs). Complexity of MDDs and HMDDs is measured by the cost which is a generalization of the notion of the size by taking into account complexity of nodes in MDDs and HMDDs. This paper presents a method for transformation of BDD into HMDD with minimal cost. The proposed method reduces the time for determination of the type of nodes in HMDDs by introducing a matrix expressing dependency (interconnections) among nodes at different levels. Comparing to other methods for conversion of BDDs into HMDDs, the method reduces the number of traverses of a BDD necessary for collecting enough information to construct an equivalent HMDD. For an experimental verification of its efficiency, the method is applied to construction of HMDDs for some benchmark functions and their arithmetic and Walsh spectra.},
keywords={},
doi={10.1587/transfun.E92.A.2580},
ISSN={1745-1337},
month={October},}
Copy
TY - JOUR
TI - Transformation of BDD into Heterogeneous MDD with Minimal Cost
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2580
EP - 2587
AU - Suzana STOJKOVI
AU - Milena STANKOVI
AU - Radomir S. STANKOVI
PY - 2009
DO - 10.1587/transfun.E92.A.2580
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E92-A
IS - 10
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - October 2009
AB - Decision diagrams (DDs) are data structures commonly used for representation of discrete functions with large number of variables. Binary DDs (BDDs) are used for representation and manipulation with Boolean functions. Complexity of a BDD is usually measured by its size, that is defined as the number of non-terminal nodes in the BDD. Minimization of the sizes of DDs is a problem greatly considered in literature and many related algorithms (exact and heuristic) have been proposed. However, there are many functions for which BDDs when minimized are still large and can have even an exponential size in the number of variables. An approach to derive compact decision diagram representations for such functions is transformation of BDDs into Multi-valued DDs (MDDs) and Heterogeneous MDDs (HMDDs). Complexity of MDDs and HMDDs is measured by the cost which is a generalization of the notion of the size by taking into account complexity of nodes in MDDs and HMDDs. This paper presents a method for transformation of BDD into HMDD with minimal cost. The proposed method reduces the time for determination of the type of nodes in HMDDs by introducing a matrix expressing dependency (interconnections) among nodes at different levels. Comparing to other methods for conversion of BDDs into HMDDs, the method reduces the number of traverses of a BDD necessary for collecting enough information to construct an equivalent HMDD. For an experimental verification of its efficiency, the method is applied to construction of HMDDs for some benchmark functions and their arithmetic and Walsh spectra.
ER -
English
