An Introduction to Binary Decision Diagrams

Henrik Reif Andersen

October 1997 (minor revisions April 1998)

Abstract

This note is a short introduction to Binary Decision Diagrams (BDDs). It provides some background knowledge and describes the core algorithms. It is used in the course "49285 Advanced Algorithms" at the Technical University of Denmark.

The 1997 version is a major revision of earlier versions. The presentation of the algorithms is based on a global table of nodes, making the presentation simpler and more in line with state-of-the-art BDD packages.

In teaching, the tool BED for constructing and manipulating BDDs interactively might be useful. It is available upon request (by e-mail). There is more information on BEDs on the BED homepage.

Earlier versions of the lecture notes from 1995 and 1996 are available upon request (by e-mail).

Available as PostScript, PostScript (gzip'ed).

[List of Publications] [Home Page]