Binary Decision Diagrams (BDDs)

Concept

Binary Decision Diagrams (BDDs) are canonical, directed-acyclic-graph representations of Boolean functions that serve as a foundational data structure in formal hardware verification and reactive synthesis. They underpin techniques such as Polynomial Formal Verification (PFV), which exploit structural properties of BDD-based and tree-like circuits to achieve polynomial-time, polynomial-space verification, in contrast to the exponential worst-case complexity of generic formal approaches. Although BDDs face scalability challenges in large reactive synthesis problems, they remain widely used for verifying combinational and sequential logic, including multi-cycle RISC-V processor cores.

First seen 6/6/2026

Last seen 6/6/2026

Evidence 3 chunks

Wiki v1

WIKI

Overview

Binary Decision Diagrams (BDDs) are compact, canonical graph-based encodings of Boolean functions that have become a cornerstone of formal hardware verification and logic synthesis. A BDD represents a Boolean function by recursively Shannon-expanding over its input variables and sharing isomorphic sub-graphs, yielding a reduced ordered binary decision diagram (ROBDD) that is canonical for a given variable ordering. This canonicality enables efficient equivalence checking, model checking, and satisfiability analysis of combinational and sequential circuits.

Use in Circuit Verification

READ FULL ARTICLE →

NEIGHBORHOOD

No graph connections found for this entity yet. It may appear in future ingestion runs.

explore full graph →

RELATIONSHIPS

1 connections

Polynomial Formal Verification (PFV) ← uses 95% 2e

PFV uses Binary Decision Diagrams and related structures for formal verification.

LINKED ENTITIES

1 links

Polynomial Formal Verification (PFV) USES Extracted graph relationship

CITATIONS

5 sources

5 citations — click to expand

[1] PFV uses Binary Decision Diagrams (BDDs) and related structures to bound verification complexity and has been demonstrated on multi-cycle RISC-V cores covering both combinational and sequential logic. Towards Reliable and Secure RISC-V Systems: Survey of Testability ...

[2] PFV is characterized in the RISC-V co-verification taxonomy as 'Polynomial formal verification using BDD-based techniques'. Towards Reliable and Secure RISC-V Systems: Survey of Testability ...

[3] For circuits with specific structural properties (tree-like circuits, multiplexer-based circuits derived from BDDs) complete formal verification can be carried out in polynomial time and space using BDDs, despite most verification approaches having exponential worst-case behavior. Polynomial Circuit Verification using BDDs

[4] Existing reactive synthesis approaches mostly rely on BDDs and inherit their scalability issues, motivating SAT/QBF/EPR-based alternatives that have been shown to outperform BDD-based tools on safety specifications. Satisfiability-Based Methods for Reactive Synthesis from Safety Specifications

[5] The RISC-V verification ecosystem combines PFV (BDD-based) with complementary techniques including symbolic co-simulation, FERIVer (FPGA-assisted), and the open-source riscv-formal framework using RVFI. Towards Reliable and Secure RISC-V Systems: Survey of Testability ...