Handbook of Data Structures and Applications, 2nd Edition

32

Binary Decision Diagrams

Shin-ichi Minato

Hokkaido University

32.1Introduction

32.2Basic Concepts

32.3Data Structure

32.4Construction of BDDs from Boolean Expressions

Binary Logic Operation•Complement Edges

32.5Variable Ordering for BDDs

32.6Zero-Suppressed BDDs

32.7Related Research Activities

Acknowledgments

References

32.1Introduction

Binary decision diagrams (BDDs) are a powerful means for computer processing of Boolean functions because in many cases, with BDDs, smaller memory space is required for storing Boolean functions, and values of functions can be calculated faster than with truth tables or logic expressions. The BDD-based techniques are now used in many application areas in computer science, for example, hardware/software system ...