Area-Time Complexities of Multi-Valued Decision Diagrams

• NAGAYAMA Shinobu

  Department of Computer Science and Electronics, Kyushu Institute of Technology

• SASAO Tsutomu

  Department of Computer Science and Electronics, Kyushu Institute of Technology

• IGUCHI Yukihiro

  Department of Computer Science, Meiji University

• MATSUURA Munehiro

  Department of Computer Science and Electronics, Kyushu Institute of Technology

抄録

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.

収録刊行物

• IEICE transactions on fundamentals of electronics, communications and computer sciences

  IEICE transactions on fundamentals of electronics, communications and computer sciences 87 (5), 1020-1028, 2004-05-01

  一般社団法人電子情報通信学会

キーワード

• decision diagrams
• the number of nodes
• area-time complexity
• randomly generated function
• representation of logic functions

詳細情報

• CRID: 1571980077395036928
• NII論文ID: 110003212997
• NII書誌ID: AA10826239
• ISSN: 09168508
• 本文言語コード: en
• データソース種別:
  • CiNii Articles