Bi-Partition of Shared Binary Decision Diagrams

• MATSUURA Munehiro

  Department of Computer Science and Electronics, Kyushu Institute of Technology

• SASAO Tsutomu

  Department of Computer Science and Electronics, and Center for Microelectronic Systems, Kyushu Institute of Technology

• BUTLER Jon T.

  Department of Electrical and Computer Engineering, Naval Postgraduate School

• IGUCHI Yukihiro

  Department of Computer Science, Meiji University

Abstract

A shared binary decision diagram (SBDD) represents a multiple-output function, where nodes are shared among BDDs representing the various outputs. A partitioned SBDD consists of two or more SBDDs that share nodes. The separate SBDDs are optimized independently, often resulting in a reduction in the number of nodes over a single SBDD. We show a method for partitioning a single SBDD into two parts that reduces the node count. Among the benchmark functions tested, a node reduction of up to 23% is realized.

Journal

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

  IEICE transactions on fundamentals of electronics, communications and computer sciences 85 (12), 2693-2700, 2002-12-01

  The Institute of Electronics, Information and Communication Engineers

Keywords

• shared binary decision diagram
• SBDD
• bi-partition
• multiple-output function
• decomposition

Details

• CRID: 1571417127441643008
• NII Article ID: 110003212440
• NII Book ID: AA10826239
• ISSN: 09168508
• Text Lang: en
• Data Source:
  • CiNii Articles