Definition

A Binary Decision Diagram (BDD) represents a Boolean function as a directed acyclic graph. In the SCV constraint-solving paper, each BDD node carries out a Shannon decomposition of a Boolean function (f : B^n \rightarrow B) ^[1]. In the RISC-V verification survey, BDDs used for verification are described as directed graphs with no cycles, with each node having two edges representing 0 and 1 ^[2].

Ordered, reduced, and canonical form

A BDD is ordered when each variable is encountered at most once on any path from the root to a terminal node and variables are encountered in the same order on all such paths. A BDD is reduced when it contains neither isomorphic subgraphs nor redundant nodes. Reduced and ordered BDDs are canonical: for each Boolean function, the BDD is uniquely specified. The SCV paper states that it uses the term “BDD” as shorthand for reduced and ordered BDDs ^[3].

Complement edges

The SCV paper illustrates BDDs with complement edges. A complement edge allows a BDD to represent both a function and its complement using the same node by modifying the edge that points to the node; in the example, this means the BDD contains only the 1-terminal ^[3].

Use in the SystemC Verification Library

The SystemC Verification Library (SCV) includes constraint-based stimulus generation for SystemC and C++, and its listed features include an integrated constraint solver based on BDDs ^[1]. Internally, an SCV constraint is represented by its characteristic function: the function is true for all solutions of the constraint. This characteristic function is represented as a BDD, and the SCV library uses the CUDD BDD package ^[3].

In SCV constraint solving, the solver works on individual bits. It computes a BDD representation of the constraint, then generates a solution by traversing the BDD from the root to the 1-terminal. A root-to-1-terminal path determines values of the variables along the path, and these values correspond to a solution because the BDD is the characteristic function of the constraint ^[4].

BDD synthesis in scv_expression

The SCV improvements paper describes the class scv_expression as the internal representation of constraint expressions in expression-tree form, with variables or constants as leaves and operators as non-terminal nodes ^[3]. It also states that scv_expr is used to store the BDD representation of an SCV expression, and that each bit operator must be mapped to corresponding BDD synthesis operations; for example, a bitwise AND is computed by the BDD-AND operation for each bit of the two input vectors ^[5].

The same paper reports added support for bit operators in SCV constraints, including bitwise AND, bitwise OR, bitwise NOT, bit-select, and slice-select ^[3].

Uniform distribution and BDD weighting

Uniform distribution of constraint solutions is important for the quality of a constraint solver, but the SCV paper observed that solutions were not always uniformly distributed when variables were fixed and disabled for randomization ^[5]. The paper explains why a naive 50/50 choice between 0- and 1-edges does not guarantee uniformity: different sub-BDDs may contain different numbers of paths to the 1-terminal, so selecting a sub-BDD with fewer paths can overweight the solutions represented there ^[4].

SCV therefore uses a special weighting algorithm. In preprocessing, the BDD of the initial constraints is traversed, weights of else- and then-children are computed while accounting for nodes removed by BDD reduction rules, and probabilities are assigned to BDD nodes. During value generation, these probabilities guide BDD traversal so that one constraint solution is selected uniformly across all solutions ^[5].

The paper also identifies a limitation in the original SCV behavior: the weighting algorithm was called only once for the initial BDD, so later simplifications such as fixing variables changed the BDD without updating probabilities, causing non-uniform constraint solutions ^[5]. The proposed redesign tightly integrated the weighting algorithm with BDD synthesis operations, made constraint objects capable of returning a pointer to their BDD representation via getBddNodeP, and recomputed weights and probabilities after simplification, producing a uniform distribution in the reported experiment ^[6][7].

Use in processor formal verification

In a RISC-V processor verification survey, BDD-based verification is discussed as a way to specify space and time complexity for polynomial formal verification. The survey notes two BDD-related challenges: BDD size can grow beyond polynomial, and a golden-reference BDD model can be hard to obtain ^[2].

For a 32-bit single-cycle RISC-V RV32I processor, the cited method mitigated BDD size using divide-and-conquer: partially simulate the RISC-V RTL, produce instruction hardware, and run symbolic simulation to obtain an output BDD. For the reference-model challenge, a reference BDD was generated piece by piece for each instruction; after equivalence checking between the two BDDs, polynomial formal verification was performed. The survey reports a verification time of 16 minutes with less memory use ^[2].

For the multi-cycle MicroRV32 processor, the survey reports that BDDs generated using the SYMSIM tool were used to verify extracted processor functionalities after preprocessing to generate an AIG and using partial simulation to extract functionalities. Results covered Fetch, Control, Execute/ALU, and Decode and Extension Unit stages, and the reported total verification time for the ALU was 200 ms ^[2].

Use in knowledge compilation

In knowledge compilation, Ordered BDDs (OBDDs) have been extended with AND-vertices and OR-vertices for conjunctive and disjunctive decomposition of propositional knowledge bases. The resulting language is Ordered {AND, OR}-decomposition and binary-Decision Diagram (OAODD). The public abstract states that OBDD, AOBDD, OBDD-L, and MLDD can be viewed as special types of OAODD, and that the paper presents conversion algorithms, polynomial-time logical-operation algorithms, and a compilation algorithm from negative normal form formulas into OAODD [url:https://arxiv.org/abs/1208.2852v2].

Use in logic minimization

BDDs have also been applied to two-level logic minimization for Boolean sum-of-products functions and Disjoint Sums-of-Products (DSOPs). The public abstract reports that BDDs provide an implicit representation of terms, allowing the method to handle large circuits faster than techniques based on explicit representations, while the quality of the result depends strongly on the variable ordering of the underlying BDD [url:https://arxiv.org/abs/1203.2505v1].

Key challenges