On Properties of Kleene TDDs

• IGUCHI Yukihiro

  the Department of Computer Science, Meiji University

• SASAO Tsutomu

  the Department of Computer Science and Electronics, Kyushu Institute of Technology

• NATSUURA Munehiro

  the Department of Computer Science and Electronics, Kyushu Institute of Technology

抄録

Three types of ternary decision diagrams(TDDs)are considered:AND_TDDs, EXOR_TDDs, and Kleene_TDDs. Kleene_TDDs are useful for logic simulation in the presence of unknown inputs. Let N(BDD:f), N(AND_TDD:f), and N(EXOR_TDD:f)be the number of non-terminal nodes in the BDD, the AND_TDD, and the EXOR_TDD for f, respectively. Let N(Kleene_TDD:F)be the number of non-terminal nodes in the Kleene_TDD for F, where F is the regular ternary function corresponding to f. Then N(BDD:f)≦N(TDD:f). For parity functions, N(BDD:f)=N(AND_TDD:f)=N(EXOR_TDD:f)=N(Kleene_TDD:F). For unate functions, N(BDD:f)=N(AND_TDD:f). The sizes of Kleene_TDDs are O(3^n/n), and O(n^3)for arbitrary functions, and symmetric functions, respectively. There exist a 2n-variable function, where Kleene_TDDs require O(n)nodes with the best order, while O(3^n)nodes in the worst order.

収録刊行物

• IEICE transactions on information and systems

  IEICE transactions on information and systems 81 (7), 716-723, 1998-07-25

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

キーワード

• binary decision diagram
• ternary decision diagram
• logic simulation
• ternary logic

詳細情報

• CRID: 1570854177489035904
• NII論文ID: 110003219785
• NII書誌ID: AA10826272
• ISSN: 09168532
• 本文言語コード: en
• データソース種別:
  • CiNii Articles