Combinational Logic-Level Verification using Boolean Expression Diagrams

Henrik Hulgaard, Poul Frederick Williams, Henrik Reif Andersen

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

    Abstract

    Boolean Expression Diagrams (BEDs) is a new data structure for representing and manipulating Boolean functions. BEDs are a generalization of Binary Decision Diagrams (BDDs) that are capable of representing any Boolean circuit in linear space and still maintain many of the desirable properties of BDDs. This paper demonstrates that BEDs are well suited for solving the combinational logic-level verification problem which is, given two combinational circuits, to determine whether they implement the same Boolean functions. Based on all combinational circuits in the ISCAS 85 and LGSynth 91 benchmarks, we demonstrate that BEDs outperform both standard BDD approaches and the techniques specifically developed to exploit structural similarities for efficiently solving the problem.
    Original languageEnglish
    Title of host publicationCombinational Logic-Level Verification using Boolean Expression Diagrams
    Publication date1997
    Publication statusPublished - 1997
    Event3rd International Workshop on Applications of the Reed-Muller Expansion in Circuit Design - Oxford, United Kingdom
    Duration: 19 Sep 199720 Sep 1997
    Conference number: 3

    Conference

    Conference3rd International Workshop on Applications of the Reed-Muller Expansion in Circuit Design
    Number3
    CountryUnited Kingdom
    CityOxford
    Period19/09/199720/09/1997

    Cite this

    Hulgaard, H., Williams, P. F., & Andersen, H. R. (1997). Combinational Logic-Level Verification using Boolean Expression Diagrams. In Combinational Logic-Level Verification using Boolean Expression Diagrams
    Hulgaard, Henrik ; Williams, Poul Frederick ; Andersen, Henrik Reif. / Combinational Logic-Level Verification using Boolean Expression Diagrams. Combinational Logic-Level Verification using Boolean Expression Diagrams. 1997.
    @inproceedings{3a08d9b00102449a8de83c405a8418ee,
    title = "Combinational Logic-Level Verification using Boolean Expression Diagrams",
    abstract = "Boolean Expression Diagrams (BEDs) is a new data structure for representing and manipulating Boolean functions. BEDs are a generalization of Binary Decision Diagrams (BDDs) that are capable of representing any Boolean circuit in linear space and still maintain many of the desirable properties of BDDs. This paper demonstrates that BEDs are well suited for solving the combinational logic-level verification problem which is, given two combinational circuits, to determine whether they implement the same Boolean functions. Based on all combinational circuits in the ISCAS 85 and LGSynth 91 benchmarks, we demonstrate that BEDs outperform both standard BDD approaches and the techniques specifically developed to exploit structural similarities for efficiently solving the problem.",
    author = "Henrik Hulgaard and Williams, {Poul Frederick} and Andersen, {Henrik Reif}",
    year = "1997",
    language = "English",
    booktitle = "Combinational Logic-Level Verification using Boolean Expression Diagrams",

    }

    Hulgaard, H, Williams, PF & Andersen, HR 1997, Combinational Logic-Level Verification using Boolean Expression Diagrams. in Combinational Logic-Level Verification using Boolean Expression Diagrams. 3rd International Workshop on Applications of the Reed-Muller Expansion in Circuit Design, Oxford, United Kingdom, 19/09/1997.

    Combinational Logic-Level Verification using Boolean Expression Diagrams. / Hulgaard, Henrik; Williams, Poul Frederick; Andersen, Henrik Reif.

    Combinational Logic-Level Verification using Boolean Expression Diagrams. 1997.

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

    TY - GEN

    T1 - Combinational Logic-Level Verification using Boolean Expression Diagrams

    AU - Hulgaard, Henrik

    AU - Williams, Poul Frederick

    AU - Andersen, Henrik Reif

    PY - 1997

    Y1 - 1997

    N2 - Boolean Expression Diagrams (BEDs) is a new data structure for representing and manipulating Boolean functions. BEDs are a generalization of Binary Decision Diagrams (BDDs) that are capable of representing any Boolean circuit in linear space and still maintain many of the desirable properties of BDDs. This paper demonstrates that BEDs are well suited for solving the combinational logic-level verification problem which is, given two combinational circuits, to determine whether they implement the same Boolean functions. Based on all combinational circuits in the ISCAS 85 and LGSynth 91 benchmarks, we demonstrate that BEDs outperform both standard BDD approaches and the techniques specifically developed to exploit structural similarities for efficiently solving the problem.

    AB - Boolean Expression Diagrams (BEDs) is a new data structure for representing and manipulating Boolean functions. BEDs are a generalization of Binary Decision Diagrams (BDDs) that are capable of representing any Boolean circuit in linear space and still maintain many of the desirable properties of BDDs. This paper demonstrates that BEDs are well suited for solving the combinational logic-level verification problem which is, given two combinational circuits, to determine whether they implement the same Boolean functions. Based on all combinational circuits in the ISCAS 85 and LGSynth 91 benchmarks, we demonstrate that BEDs outperform both standard BDD approaches and the techniques specifically developed to exploit structural similarities for efficiently solving the problem.

    M3 - Article in proceedings

    BT - Combinational Logic-Level Verification using Boolean Expression Diagrams

    ER -

    Hulgaard H, Williams PF, Andersen HR. Combinational Logic-Level Verification using Boolean Expression Diagrams. In Combinational Logic-Level Verification using Boolean Expression Diagrams. 1997