Combinational Logic-Level Verification using Boolean
                Expression Diagrams

Henrik Hulgaard; Poul Frederick Williams; Henrik Reif Andersen

Combinational Logic-Level Verification using Boolean Expression Diagrams

Henrik Hulgaard, Poul Frederick Williams, Henrik Reif Andersen

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-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 language	English
Title of host publication	Combinational Logic-Level Verification using Boolean Expression Diagrams
Publication date	1997
Publication status	Published - 1997
Event	3rd International Workshop on Applications of the Reed-Muller Expansion in Circuit Design - Oxford, United Kingdom Duration: 19 Sept 1997 → 20 Sept 1997 Conference number: 3

Conference

Conference	3rd International Workshop on Applications of the Reed-Muller Expansion in Circuit Design
Number	3
Country/Territory	United Kingdom
City	Oxford
Period	19/09/1997 → 20/09/1997

OpenUrl availability

Full text

Cite this

@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",

note = "3rd International Workshop on Applications of the Reed-Muller Expansion in Circuit Design, Reed-Muller 97 ; Conference date: 19-09-1997 Through 20-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 proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Combinational Logic-Level Verification using Boolean Expression Diagrams

AU - Hulgaard, Henrik

AU - Williams, Poul Frederick

AU - Andersen, Henrik Reif

N1 - Conference code: 3

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

T2 - 3rd International Workshop on Applications of the Reed-Muller Expansion in Circuit Design

Y2 - 19 September 1997 through 20 September 1997

ER -