Multi-terminal Multi-valued Decision Diagrams for Characteristic Function Representing Cluster Decomposition

Binary decision diagrams representing complex logic circuits require a large number of nodes. This paper shows a new method to represent logic circuits using multiple decision diagrams. First, a given logic circuit is converted into a direct acyclic graph (DAG). Then, the DAG is decomposed into clusters. Next, clusters are represented by multi-terminal binary decision diagrams for characteristic function (decomposed MTBDDs for CF). It represents a logic circuit more compactly than the conventional MTBDD for CF. Finally, the decomposed MTBDDs for CF are converted into the multi-terminal multi-valued decision diagrams for CF (decomposed MTMDDs for CF) to be stored in the given memory size. Also, the decomposed MTMDDs for CF is faster to evaluate than the conventional MTMDD for CF using the same memory size on a BDD machine.