Title :
New multivalued functional decomposition algorithms based on MDDs
Author :
Files, Craig M. ; Perkowski, Marek A.
Author_Institution :
Dept. of Electr. Eng., Portland State Univ., OR, USA
fDate :
9/1/2000 12:00:00 AM
Abstract :
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
Keywords :
data mining; decision diagrams; logic CAD; unsupervised learning; EVAL algorithm; PARTITION algorithm; data mining; knowledge discovery; logic synthesis; machine learning; multivalued decision diagrams; multivalued functional decomposition algorithms; Boolean functions; Data mining; Data structures; Databases; Logic design; Machine learning; Machine learning algorithms; Multivalued logic; Partitioning algorithms; Runtime;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
