Authors: Stojković, Suzana
Stanković, Milena
Stanković, Radomir 
Title: Transformation of BDD into heterogeneous MDD with minimal cost
Journal: IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Volume: E92-A
Issue: 10
First page: 2580
Last page: 2587
Issue Date: 1-Jan-2009
Rank: M23
ISSN: 0916-8508
DOI: 10.1587/transfun.E92.A.2580
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: Binary decision diagrams | Boolean functions | Heterogeneous decision diagrams | Multi-valued functions
Publisher: IEICE

Show full item record


checked on Jul 12, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.