Area-Time Complexities of Multi-Valued Decision Diagrams

Shinobu NAGAYAMA; Tsutomu SASAO; Yukihiro IGUCHI; Munehiro MATSUURA

Area-Time Complexities of Multi-Valued Decision Diagrams

Shinobu NAGAYAMA, Tsutomu SASAO, Yukihiro IGUCHI, Munehiro MATSUURA

Full Text Views

0

Share
Cite this

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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E87-A No.5 pp.1020-1028

Publication Date: 2004/05/01

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Shinobu NAGAYAMA, Tsutomu SASAO, Yukihiro IGUCHI, Munehiro MATSUURA, "Area-Time Complexities of Multi-Valued Decision Diagrams" in IEICE TRANSACTIONS on Fundamentals, vol. E87-A, no. 5, pp. 1020-1028, May 2004, doi: .
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/e87-a_5_1020/_p

Copy

@ARTICLE{e87-a_5_1020,
author={Shinobu NAGAYAMA, Tsutomu SASAO, Yukihiro IGUCHI, Munehiro MATSUURA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Area-Time Complexities of Multi-Valued Decision Diagrams},
year={2004},
volume={E87-A},
number={5},
pages={1020-1028},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={May},}

Copy

TY - JOUR
TI - Area-Time Complexities of Multi-Valued Decision Diagrams
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1020
EP - 1028
AU - Shinobu NAGAYAMA
AU - Tsutomu SASAO
AU - Yukihiro IGUCHI
AU - Munehiro MATSUURA
PY - 2004
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E87-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2004
AB - 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.
ER -