Computer Graphics & Decision of the Node Decomposition Type for the Minimization of OPKFDDs


The KIPS Transactions:PartA, Vol. 9, No. 3, pp. 363-370, Sep. 2002
10.3745/KIPSTA.2002.9.3.363,   PDF Download:

Abstract

OPKFDD (Ordered Pseudo-Kronecker Functional Decision Diagram) is one of ordered-DDs (Decision Diagrams) in which each node can take one of three decomposition types : Shannon, positive Davio and negative Davio decompositions. Whereas OBDD (Ordered Binary Decision Diagram) uses only the Shannon decomposition in each node, OPKFDD uses the three decompositions and generates representations of functions with smaller number of nodes than other DDs. However, this leads to the extreme difficulty of getting an optimal solution for the minimization of OPKFDD. Since an appropriate decomposition type has to be chosen for each node, the size of the representation is decided by the selection of the decomposition type. We propose a heuristic method to generate OPKFDD efficiently from the OBDD of the given function and the algorithm of the decision of decomposition type for a given variable ordering. Experimental results demonstrate the performance of the algorithm.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
M. G. Jung, M. Hwang, G. S. Lee, Y. C. Kim, "Computer Graphics & Decision of the Node Decomposition Type for the Minimization of OPKFDDs," The KIPS Transactions:PartA, vol. 9, no. 3, pp. 363-370, 2002. DOI: 10.3745/KIPSTA.2002.9.3.363.

[ACM Style]
Mi Gyoung Jung, Min Hwang, Guee Sang Lee, and Young Chul Kim. 2002. Computer Graphics & Decision of the Node Decomposition Type for the Minimization of OPKFDDs. The KIPS Transactions:PartA, 9, 3, (2002), 363-370. DOI: 10.3745/KIPSTA.2002.9.3.363.