Representations of Multiple-Output Functions Using Binary Decision Diagrams for Characteristic Functions

Hafiz Md. HASAN BABU  Tsutomu SASAO  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E82-A   No.11   pp.2398-2406
Publication Date: 1999/11/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
Category: 
Keyword: 
binary decision diagram (BDD),  characteristic function (CF),  multiple-output function,  variable ordering,  logic simulation,  adder,  bit-counting function,  multiplier,  

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




Summary: 
This paper proposes a method to construct smaller binary decision diagrams for characteristic functions (BDDs for CFs). A BDD for CF represents an n-input m-output function, and evaluates all the outputs in O(n+m) time. We derive an upper bound on the number of nodes of the BDD for CF of n-bit adders (adrn). We also compare complexities of BDDs for CFs with those of shared binary decision diagrams (SBDDs) and multi-terminal binary decision diagrams (MTBDDs). Our experimental results show: 1) BDDs for CFs are usually much smaller than MTBDDs; 2) for adrn and for some benchmark circuits, BDDs for CFs are the smallest among the three types of BDDs; and 3) the proposed method often produces smaller BDDs for CFs than an existing method.