Area-Time Complexities of Multi-Valued Decision Diagrams

Shinobu NAGAYAMA  Tsutomu SASAO  Yukihiro IGUCHI  Munehiro MATSUURA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E87-A   No.5   pp.1020-1028
Publication Date: 2004/05/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
decision diagrams,  the number of nodes,  area-time complexity,  randomly generated function,  representation of logic functions,  

Full Text: PDF(307.2KB)>>
Buy this Article




Summary: 
This paper considers Quasi-Reduced ordered Multi-valued 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 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.