Area-Time Complexities of Multi-Valued Decision Diagrams

Search this Article

Author(s)

    • NAGAYAMA Shinobu
    • Department of Computer Science and Electronics, Kyushu Institute of Technology
    • SASAO Tsutomu
    • Department of Computer Science and Electronics, Kyushu Institute of Technology
    • MATSUURA Munehiro
    • Department of Computer Science and Electronics, Kyushu Institute of Technology

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 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.

Journal

  • IEICE Transactions on Foundamentals of Electronics, A

    IEICE Transactions on Foundamentals of Electronics, A 87(5), 1020-1028, 2004-05-01

    The Institute of Electronics, Information and Communication Engineers

References:  36

Cited by:  9

Codes

  • NII Article ID (NAID)
    110003212997
  • NII NACSIS-CAT ID (NCID)
    AA10826239
  • Text Lang
    ENG
  • Article Type
    Journal Article
  • ISSN
    09168508
  • Data Source
    CJP  CJPref  NII-ELS 
Page Top