The search functionality is under construction.

The search functionality is under construction.

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 (adr*n*). 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 adr*n* 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.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E82-A No.11 pp.2398-2406

- Publication Date
- 1999/11/25

- Publicized

- Online ISSN

- DOI

- Type of Manuscript
- Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)

- Category

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Hafiz Md. HASAN BABU, Tsutomu SASAO, "Representations of Multiple-Output Functions Using Binary Decision Diagrams for Characteristic Functions" in IEICE TRANSACTIONS on Fundamentals,
vol. E82-A, no. 11, pp. 2398-2406, November 1999, doi: .

Abstract: 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 (adr*n*). 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 adr*n* 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.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e82-a_11_2398/_p

Copy

@ARTICLE{e82-a_11_2398,

author={Hafiz Md. HASAN BABU, Tsutomu SASAO, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={Representations of Multiple-Output Functions Using Binary Decision Diagrams for Characteristic Functions},

year={1999},

volume={E82-A},

number={11},

pages={2398-2406},

abstract={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 (adr*n*). 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 adr*n* 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.},

keywords={},

doi={},

ISSN={},

month={November},}

Copy

TY - JOUR

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

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 2398

EP - 2406

AU - Hafiz Md. HASAN BABU

AU - Tsutomu SASAO

PY - 1999

DO -

JO - IEICE TRANSACTIONS on Fundamentals

SN -

VL - E82-A

IS - 11

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - November 1999

AB - 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 (adr*n*). 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 adr*n* 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.

ER -