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

Volume

19

Issue

9

fYear

2000

fDate

9/1/2000 12:00:00 AM

Firstpage

1081

Lastpage

1086

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;

fLanguage

English

Journal_Title

Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on

Publisher

ieee

ISSN

0278-0070

Type

jour

DOI

10.1109/43.863648

Filename

863648