New multivalued functional decomposition algorithms based on MDDs
New multivalued functional decomposition algorithms based on MDDs
复制标题
DOI：
10.1109/43.863648
复制
发表时间：
2000-09
期刊：
影响因子：
--
通讯作者：
C. Files;M. Perkowski
中科院分区：
文献类型：
--
作者：
C. Files;M. Perkowski
本文提出了两种使用多值决策图（MDD）的新的函数分解划分算法。MDD是广义分解的一种非常好的表示形式，因为它们是规范的，并且能够表示非常大的函数。本文所开发的算法适用于布尔/多值输入和输出、完全/不完全指定的函数，可应用于逻辑综合、机器学习、数据挖掘以及数据库中的知识发现。我们将我们算法的运行时间和决策图大小与现有的基于决策图的分解划分算法进行了比较。比较结果表明，我们的算法速度更快，并且在分解具有小边界集的函数时不会导致指数级的图大小。
This paper presents two new functional decomposition partitioning algorithms that use multivalued decision diagrams (MDDs). MDDs are an exceptionally good representation for generalized decomposition because they are canonical and they can represent very large functions. Algorithms developed in this paper are for Boolean/multivalued input and output, completely/incompletely specified functions with application to logic synthesis, machine learning, data mining and knowledge discovery in databases. We compare the run-times and decision diagram sizes of our algorithms to existing decomposition partitioning algorithms based on decision diagrams. The comparisons show that our algorithms are faster and do not result in exponential diagram sizes when decomposing functions with small bound sets.