Boolean Expression Diagrams

Henrik Reif Andersen, Henrik Hulgaard

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

    974 Downloads (Pure)

    Abstract

    This paper presents a new data structure called Boolean Expression Diagrams (BEDs) for representing and manipulating Boolean functions. BEDs are a generalization of Binary Decision Diagrams (BDDs) which can represent any Boolean circuit in linear space and still maintain many of the desirable properties of BDDs. Two algorithms are described for transforming a BED into a reduced ordered BDD. One closely mimics the BDD apply-operator while the other can exploit the structural information of the Boolean expression. The efficacy of the BED representation is demonstrated by verifying that the redundant and non-redundant versions of the ISCAS 85 benchmark circuits are identical. In particular, it is verified that the two 16-bit multiplication circuits (c6288 and c6288nr) implement the same Boolean functions. Using BEDs, this verification problem is solved in less than a second, while using standard BDD techniques this problem is infeasible. BEDs are useful in applications where the end-result as a reduced ordered BDD is small, for example for tautology checking
    Original languageEnglish
    Title of host publicationProceedings, Twelfth Annual IEEE Symposium on Logic in Computer Science, Warsaw, Poland
    PublisherIEEE Computer Society Press
    Publication date1997
    Pages88-98
    ISBN (Print)0-8186-7925-5
    DOIs
    Publication statusPublished - 1997
    EventTwelfth Annual IEEE Symposium on Logic in Computer Science - Warsaw, Poland
    Duration: 29 Jun 19972 Jul 1997
    Conference number: 12

    Conference

    ConferenceTwelfth Annual IEEE Symposium on Logic in Computer Science
    Number12
    CountryPoland
    CityWarsaw
    Period29/06/199702/07/1997

    Bibliographical note

    Copyright: 1997 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE

    Fingerprint Dive into the research topics of 'Boolean Expression Diagrams'. Together they form a unique fingerprint.

    Cite this