Bi-Partition of Shared Binary Decision Diagrams

Munehiro MATSUURA  Tsutomu SASAO  Jon T. BUTLER  Yukihiro IGUCHI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E85-A   No.12   pp.2693-2700
Publication Date: 2002/12/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
Category: Logic Synthesis
Keyword: 
shared binary decision diagram,  SBDD,  bi-partition,  multiple-output function,  decomposition,  

Full Text: PDF(555.1KB)>>
Buy this Article




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