Area-Time Complexities of Multi-Valued Decision Diagrams
Shinobu Nagayama, Tsutomu Sasao, Yukihiro Iguchi, Munehiro Matsuura · 2004
This paper considers Quasi-Reduced ordered Multivalued Decision Diagrams with k bits (QRMDD(k)s) to represent binary logic functions. Experimental results show relations between the values of k and the numbers of nodes, the memory sizes, the numbers of memory accesses, and area-time complexity for QRMDD(k). For many benchmark functions, the numbers of nodes and memory accesses for QRMDD(k)s are nearly equal to 1/k of the corresponding Quasi-Reduced ordered Binary Decision Diagrams (QRBDDs), and the memory sizes and the area-time complexities for QRMDD(k)s are minimum when k = 2 and k = 3--6, respectively