arXiv:1710.06500v1 [cs.DS] 17 Oct 2017

Chain Reduction for
Binary and Zero-Suppressed Decision Diagrams
Randal E. Bryant
Computer Science Department
Carnegie Mellon University
Randy.Bryant@cs.cmu.edu
October 19, 2017

Abstract
Chain reduction enables reduced ordered binary decision diagrams (BDDs) and zero-suppressed
binary decision diagrams (ZDDs) to each take advantage of the others’ ability to symbolically represent Boolean functions in compact form. For any Boolean function, its chain-reduced ZDD (CZDD)
representation will be no larger than its ZDD representation, and at most twice the size of its BDD representation. The chain-reduced BDD (CBDD) of a function will be no larger than its BDD representation,
and at most three times the size of its CZDD representation. Extensions to the standard algorithms for
operating on BDDs and ZDDs enable them to operate on the chain-reduced versions. Experimental
evaluations on representative benchmarks for encoding word lists, solving combinatorial problems, and
operating on digital circuits indicate that chain reduction can provide significant benefits in terms of both
memory and execution time.

1

Introduction

Decision diagrams (DDs) encode sets of values in compact forms, such that operations on the sets can
be performed on the encoded representation, without expanding the sets into their individual elements.
In this paper, we consider two classes of decision diagrams: reduced ordered binary decision diagrams
(BDDs) [4] and zero-suppressed binary decision diagrams (ZDDs) [12, 13]. These two representations
are closely related to each other, with each achieving more compact representations for different classes
of applications. We present extensions to both representations, such that BDDs can take advantage of the
source of compaction provided by ZDDs, and vice-versa.
Both BDDs and ZDDs encode sets of binary sequences of some fixed length n, defining a Boolean function
over n variables. We can bound their relative sizes as follows. Suppose for some function, we encode it
according to the different DD types. For function f , let T (f ) indicate the number of nodes (including leaf
nodes) in the representation of type T . Let Rf (T1 , T2 ) denote the relative sizes when representing f using
types T1 and T2 :
(f )
Rf (T1 , T2 ) = TT21 (f
)

1

n/2
BDD

ZDD
n/2

1

2

1

CBDD

CZDD
3

Figure 1: Size bound relations between different representations
Comparing BDDs and ZDDs, Knuth [9] has shown that for any function f :
Rf (BDD, ZDD) ≤ n/2 + o(n)

(1)

Rf (ZDD, BDD) ≤ n/2 + o(n)

(2)

These bound improve on the size ratios of n derived by Wegener [17].
As these bounds show, ZDDs may be significantly (a factor of n/2) more compact than BDDs, or vice-versa.
Hence, it can be critical to choose one representation over another in a given application. Indeed, users of
DDs often switch between the two representations during a sequence of operations in order take advantage
of their different characteristics.
In this paper, we introduce two new representations: chain-reduced ordered binary decision diagrams (CBDDs), and chain-reduced zero-suppressed binary decision diagrams (CZDDs). The key idea is to associate
two levels with each node and to use such nodes to encode particular classes of linear chains found in BDDs
and ZDDs. Chain reduction can be defined in terms of a set of reduction rules applied to BDDs and ZDDs,
giving bounds for any function f
Rf (CBDD, BDD) ≤ 1

(3)

Rf (CZDD, ZDD) ≤ 1

(4)

In terms of graph sizes, using chain reduction can only lead to more compact representations.
We show bounds on the relative sizes of the representations as:
Rf (CBDD, CZDD) ≤ 3 + o(1)

(5)

Rf (CZDD, BDD) ≤ 2 + o(1)

(6)

These relations are summarized in the diagram of Figure 1. In this figure, each arc from type T1 to type T2
labeled by an expression E indicates that Rf (T1 , T2 ) ≤ E + o(E). These arcs define a transitive relation,
2

and so we can also infer that
Rf (CBDD, ZDD) ≤ 3 + o(1)

(7)

These results indicate that the two compressed representations will always be within a small constant factor
(2 for CZDDs and 3 for CBDDs) of either a BDD or a ZDD representation. While one representation may
be more slightly compact than the other, the relative advantage is bounded by a constant factor, and hence
choosing between them is less critical.
This paper defines the two compressed representations, derives the bounds indicated in Equations 5–6 and
presents extensions of the core BDD and ZDD algorithms to their chained versions. It describes an implementation based on modifications of the CUDD BDD package [16]. It presents some experimental results
and concludes with a discussion of the merits of chaining and possible extensions.

2

BDDs and ZDDs

Both BDDs and ZDDs encode sets of binary sequences of length n as directed acyclic graphs with two leaf
nodes, labeled with values 0 and 1, which we refer to as “leaf 0” and “leaf 1,” respectively. Each nonleaf
node v has an associated level l, such that 1 ≤ l ≤ n, and two outgoing edges, labeled lo and hi to either a
leaf node or a nonleaf node. By convention, leaf nodes have level n + 1. An edge from v to node u having
level l0 must have l < l0 .
Figure 2 shows three decision-diagram representations of the set S, defined as:
S = {0001, 0011, 0101, 0111, 1000}

(8)

The lo edge from each node is shown as a dashed line, and the hi edge is shown as a solid line. As a
shorthand, we omit leaf 0 and all branches to it.
Graph A represents S as a levelized binary decision diagram, where an edge from a node with level l must
connect to either leaf 0 or to a node with level l + 1. (This is similar to the quasi-reduced form described by
Knuth [9], except that he only allows edges to leaf 0 from nodes at level n.) Each path from the root to leaf
1 encodes an element of set S. For a given path, the represented sequence has value 0 at position l when the
path follows the lo edge from the node with level l and value 1 when the path follows the hi edge.
Graph A has nodes forming two linear chains: a DON ’ T- CARE chain, consisting of nodes a and b, and an OR
chain, consisting of nodes d, e, and f . A DON ’ T- CARE chain is a series of DON ’ T- CARE nodes, each having
its two outgoing edges directed to the same next node. In terms of the set of represented binary sequences, a
DON ’ T- CARE node with level l allows both values 0 and 1 at sequence position l. An OR chain consists of a
sequence where the outgoing hi edges for the nodes all go the same node—in this case, leaf 0. An OR chain
where all hi edges lead to value 0 has only a single path, assigning value 0 to the corresponding positions in
the represented sequence. We will refer to this special class of OR chain as a ZERO chain.
BDDs and ZDDs differ from each other in the interpretations they assign to a level-skipping edge, when
a node with level l has an edge to a node with level l0 such that l + 1 < l0 . For BDDs, such an edge is
considered to encode a DON ’ T- CARE chain. Thus, graph B in Figure 2 shows an BDD encoding set S. The
edge on the left from level 1 to level 4 is equivalent to the DON ’ T- CARE chain formed by nodes a and b of
graph A. For ZDDs, a level skipping edge encodes a ZERO chain. Thus, graph C shows a ZDD encoding
3

(A) Levelized BDD

(B) BDD

(C) ZDD

1

a

b

c

1

2

2

3

3

4

4

1

f

1

d

2

3

e

4

4

1

f

d

a

e

b

c

2

3

4

1

Figure 2: Reductions in BDDs and ZDDs. Each reduces the representation size with with edges between
nonconsecutive levels.
set S. The edge on the right from level 1 to the leaf encodes the ZERO chain formed by nodes d, e, and f
of graph A. Whether the set is encoded as a BDD or a ZDD, one type of linear chains remains. Introducing
chain reduction enables BDDs and ZDDs to exploit both DON ’ T- CARE and OR (and therefore ZERO) chains
to compress their representations.

3

Chain Patterns and Reductions

Figure 3 shows the general form of OR and DON ’ T- CARE chains, as were illustrated in the examples of
Figure 2. These chains have levels ranging from t to b, such that 1 ≤ t < b ≤ n. Each form consists of a
linear chain of nodes followed by two nodes f and g with levels greater than b. Nodes f and g are drawn
as triangles to indicate that they are the roots of two subgraphs in the representation. In an OR chain, the lo
edge from each node is directed to the next node in the chain, and the hi edge is directed to node g. The
chains eliminated by ZDDs are a special case where g = 0. In a DON ’ T- CARE chain, both the lo and the hi
edges are directed toward the next node in the chain.
As was illustrated in Figure 2, having edges that skip levels allows BDDs to compactly represent DON ’ TCARE chains and ZDDs to eliminate OR chains when g = 0. The goal of chain reduction is to allow both
forms to compactly represent both types of chains. They do so by associating two levels with each node,
as indicated in Figure 3(C). That is, every nonleaf node has an associated pair of levels t : b, such that
1 ≤ t ≤ b ≤ n. In a chain-reduced ordered binary decision diagram (CBDD), such a node encodes the
4

(A) OR chain

(B) DON ’ T- CARE chain
t

(C) Compressed representation

t

t+1

t+1

t:b

b–1

b–1

b

f

b

g

f

g

f

g

Figure 3: Chain patterns. These patterns remain after BDD reduction (A), and ZDD reduction (B), but can
be represented in compressed form (C).

5

(A) Levelized BDD

(B) CBDD

(C) CZDD
1:1

1

a

b

c

2

2

3

3

4

4

1

f

1:1

d

2:4

e

f’

c’

2 3: 4

4:4

1

1

Figure 4: Chain Reduction Examples. Each now reduces both chain types.
OR chain pattern shown in Figure 3(A), while in a chain-reduced zero-suppressed binary decision diagram
(CZDD), such a node encodes the DON ’ T- CARE chain pattern shown in Figure 3(B). A node with levels t
and b such that t = b encodes a standard node with respect to the indicated variable.

Figure 4 shows the effect of chain reduction, starting with the levelized graph A. In the CBDD (B), a single
node f 0 replaces the OR chain consisting of nodes d, e, and f . In the CZDD (C), the DON ’ T- CARE chain
consisting of nodes a and b is incorporated into node c to form node c0 . These new nodes are drawn in
elongated form to emphasize that they span a range of levels, but it should be emphasized that all nodes in
a chained representation have an associated pair of levels.

4

Generating CBDDs and CZDDs

As notation, let us denote a node of the form illustrated in Figure 3(C) with the modified if-then-else notation
ht : b → g, f i. That is, the node has a range of levels from t to b, an outgoing hi edge to node g, and an
outgoing lo edge to node f .
A BDD representation of a function can be transformed into a CBDD as follows. The process starts by
labeling each node having level l in the BDD with the pair t : b, such that t = b = l. Then, we repeatedly
apply a reduction rule, replacing any pair of nodes u and v of the form u = ht : m → g, vi and v =
hm + 1 : b → g, f i (illustrated in Figure 5(A)) by the single node ht : b → g, f i (illustrated in Figure 5(C)).
A similar process can transfrom any ZDD representation of a function into a CZDD, using the reduction

6

(A) BDD chain reduction

(B) ZDD chain reduction

t:m

(C) Compressed representation

t:m
t:b

m+1 : b

f

m+1 : b

g

f

g

f

g

Figure 5: Chain reduction cases. These cases define how chain reduction can be applied to BDDs (A) and
ZDDs to obtain the single chain node (C).
rule that a pair of nodes u and v of the form u = ht : m → v, vi and v = hm + 1 : b → g, f i (illustrated
in Figure 5(B)) is replaced by the single node ht : b → g, f i (illustrated in Figure 5(C)). In practice, most
algorithms for constructing decision diagrams operate from the bottom up. The reduction rules are applied
as nodes are created, and so unreduced nodes are never actually generated.

5

Size Ratio Bounds

These reduction rules allows us to bound the relative sizes of the different representations, as given by
Equations 5 and 6.
First, let us consider Equation 5, bounding the relative sizes of the CBDD and CZDD representations of a
function. Consider a graph G representing function f as a CZDD. We can generate a CBDD representation
G0 as follows. G0 contains a node v 0 for each node v in G. However, if v has levels t : b, then v 0 has levels
b : b, because any DON ’ T- CARE chain encoded explicitly in the CZDD is encoded implicitly in a CBDD.
Consider an edge from node u to node v in G, where the nodes have levels tu : bu and tv : bv , respectively.
If tv = bu + 1, then there can be an edge directly from u0 to v 0 . If tv < bu + 1, then we introduce a new
node to encode the implicit zero chain in G from u to v. This node has the form hbu + 1 : tv − 1 → 0, v 0 i
and has an edge from u0 to it.
The size of G0 is bounded by the number of nodes plus the number of edges in G. Since each node in G has
at most two outgoing edges, we can see that G0 has at most three times the number of nodes as G. Graph G0
may not be reduced, but it provides an upper bound on the size of a CBDD relative to that of a CZDD.
This bound it tight—Figure 6 illustrates the representations for a family of functions, parameterized by a
7

(A) ZDD/CZDD representation

(B) CBDD representation

Level

Level

1

1

2

2

3

3

4

4

5

5

6

6

7

7

8

8

9

9

10

10

11

11

1

1

Figure 6: Worst case example for effectiveness of CBDD compression. The implicit ZERO chains in the
ZDD (A) must be explicitly encoded in the CBDD (B), increasing its size by a factor of 3.

8

(A) BDD representation

(B) CZDD representation

Level

Level

1

1

2

2

3

3

4

4

5

5

6

6

7

7

1

1

Figure 7: Worst case example for effectiveness of CZDD compression. The nodes in the BDD (A) must
be duplicated to encode the incoming DON ’ T- CARE chains (B), increasing the size by a factor of 2.
value k (k = 3 in the example), such that the function is defined over 3k + 2 variables. The ZDD and CZDD
representations are identical (A), having 2k+3 nodes (including both leaf nodes.) The CBDD representation
has 6k + 2 nodes (B). We can see in this example that the CBDD requires nodes (shown in gray) to encode
the ZERO chains that are implicit in the ZDD. To construct the graphs for different values of k, the graph
pattern enclosed in the diagonal boxes can be replicated as many times as are needed.
Second, let us consider Equation 6, bounding the relative sizes of the CZDD and BDD representations of a
function. Consider a graph G representing function f as a BDD. We can construct its representation G0 as
a CZDD. Consider each edge G from node u, having level lu to node v, having level lv . Let r = lo(v) and
s = hi(v). G0 has a node wuv of the form hlu + 1 : lv → wvs , wvr i. That is, wuv encodes any DON ’ T- CARE
chain between u and v, and it has edges to the nodes generated to encode the edges between v and its two
children. The size of G0 is bounded by the number of edges in G, which is at most twice the number of
nodes.
This bound it also tight—Figure 7 illustrates the representations for a family of functions, parameterized
by a value k (k = 3 in the example), such that the function is defined over 2k + 1 variables. The BDD
representations (A) has 2k + 3 nodes (including both leaf nodes.) The CZDD representation has 4k + 3
nodes (B). We can see that most of the nodes in the BDD must be duplicated: once with no incoming
DON ’ T- CARE chain, and once with a chain of length one. To construct the graphs for different values of k,
the graph pattern enclosed in the diagonal boxes can be replicated as many times as are needed.
As can be seen in Figure 1, these bounds contain an asymmetry between BDDs and ZDDs and their compressed forms. The bound of 3 holds between CBDDs and CZDDs, and hence by transitivity between

9

CBDDs and ZDDs, while the bound of 2 holds only between CZDDs and BDDs. The general form of the
OR chain (Figure 3(A)), where g is something other than 0, cannot be directly encoded with CZDD nodes.

6

Operating on CBDDs and CZDDs

The APPLY algorithms for decision diagrams operate by recursively expanding a set of argument decision
diagrams according to a Shannon expansion of the represented functions [4, 6]. These algorithms allow
functions to be combined according to standard binary Boolean operations, such as AND, OR, and XOR, as
well as by the if-then-else operation ITE.
As notation, consider a step that expands k argument nodes {vi |1 ≤ i ≤ k} where vi = hti : bi → gi , fi i.
For example, operations AND, OR, and XOR use the APPLY algorithm with k = 2, while ternary operations,
such as ITE use k = 3. A step can be summarized as follows:
1. If one of the terminal cases apply, then return the result.
2. If the computed cache contains an entry for this combination of operation and arguments, then return
the previously computed result.
3. Recursively compute the result:
(a) Choose splitting level(s) based on the levels of the arguments.
(b) Generate hi and lo cofactors for each argument.
(c) Recursively compute the hi and lo values of the result using the APPLY algorithm with the hi
cofactors and the lo cofactors, respectively.
(d) Determine the result node parameters based on the computed hi and lo cofactors and the splitting
level(s).
(e) Either reuse an existing node or create a new one with the desired level(s) and hi and lo children.
4. Store an entry in the computed cache.
5. Return the computed value.
In generalizing from conventional BDDs and ZDDs to their chained versions, we need only modify 3(a)
(splitting), 3(b) (cofactoring), and 3(d) (combining) in this sequence, considering the two levels for each
node.
For CBDDs, we define the splitting levels t and b as:
t =

b =

min ti

(9)

1≤i≤k



 bi ,

ti = t
ti ,
ti = n + 1

1≤i≤k 
ti − 1, else
min

We then define the two cofactors for each argument node vi , denoted lo(vi , b : t) and hi(vi , b : t), according
to the following table:
10

Case
1
2
3

Condition
b < ti
b = bi
ti ≤ b < bi

lo(vi , b : t)
vi
fi
hb + 1 : bi → gi , fi i

hi(vi , b : t)
vi
gi
gi

These three cases can be explained as follows:
Case 1: Splitting spans levels less than the top level of vi . Since level-skipping edges encode DON ’ T- CARE
chains, both cofactors equal the original node.
Case 2: Splitting spans the same levels as node vi . The cofactors are therefore the nodes given by the
outgoing edges.
Case 3: Splitting spans a subset of the levels covered by node vi . We construct a new node spanning the
remaining part of the encoded OR chain for the lo cofactor and have gi as the hi cofactor.
Recursive application of the APPLY operation on the cofactors generates a pair of nodes u0 and u1 . Using
the variable levels t and b defined in Equation 9, these are combined to form a result node u, defined as
follows:

u =



 u0 ,

u0 = u1
Case 1
ht : b0 → u1 , w0 i , u0 = hb + 1, b0 : → u1 , w0 i Case 2


ht : b → u1 , u0 i , else
Case 3

(10)

These three cases can be explained as follows:
Case 1: The hi and lo cofactors are identical, and so the don’t-care reduction rule can be applied.
Case 2: Chain compression can be applied to create a node that absorbs the lo cofactor.
Case 3: No special rules apply.
Similar rules hold for applying operations to CZDDs, although there are important differences, due to the
different interpretations of level-skipping edges.
We define the splitting levels t and b as:
t =

b =

min ti

(11)

1≤i≤k



 bi ,

ti = t
n + 1, vi = 0

1≤i≤k 
t,
else
min

The cofactors for argument node vi are defined according to the following table:
Case
1
2
3

Condition
b < ti
b = bi
ti ≤ b < bi

lo(vi , b : t)
vi
fi
hb + 1 : bi → gi , fi i
11

hi(vi , b : t)
0
gi
hb + 1 : bi → gi , fi i

These three cases can be explained as follows:
Case 1: The splitting spans levels less than the top level of vi . Since level-skipping edges encode ZERO
chains, the lo cofactor equals the original node and the hi cofactor equals leaf 0.
Case 2: The splitting spans the same levels as node vi . The cofactors are therefore the nodes given by the
outgoing edges.
Case 3: The splitting spans a subset of the levels covered by node vi . We construct a new node spanning
the remaining part of the encoded DON ’ T- CARE chain for both cofactors.
Recursive application of the APPLY operation on the cofactors generates a pair of nodes u0 and u1 . Using
the variable ranges t and b defined in Equation 11, these are combined to form a result node u, defined as
follows:

u =



u0 ,
u1 = 0 and t = b
Case 1


 ht : b − 1 → u , u i , u = 0 and t < b
Case 2
0 0
1
0 → w ,w i,
0 : → w , w i Case 3

ht
:
b
u
=
u
=
hb
+
1,
b
1
0
0
1
1
0




ht : b → u1 , u0 i ,

else

(12)

Case 4

These four cases can be explained as follows:
Case 1: The zero-suppression rule can be applied to return a direct pointer to u0
Case 2: The zero-suppression rule can be applied, but we must construct a node encoding the DON ’ T- CARE
chain between levels t and b − 1.
Case 3: Chain compression can be applied to create a node that absorbs the lo cofactor.
Case 4: No special rule applies.

7

Implementation

We implemented both CBDDs and CZDDs by modifying version 3.0.0 of the CUDD BDD package [16].
When compiled for 64-bit execution, CUDD stores a 32-bit field index in each node, where this index is
translated into a level according to the variable ordering. For our implementation, we split this field into two
16-bit fields index and bindex to (indirectly) encode the top and bottom levels of the node. Thus, there
was no storage penalty for the generalization to a chained form.
Incorporating chaining required modifications to many parts of the code, including how node keys are generated for the unique table and computed cache, how reductions are performed, and how Boolean operations
are applied to functions. In addition, many of the commonly used functions, such as computing the number
of satisfying solutions to a function, computing its support, and enumerating a minterm representation of a
function required modifications.

12

Compact word list
ASCII word list
Compact password list
ASCII password list

Words
235,886
235,886
979,247
979,247

Radix
54
129
80
129

Length
24
24
32
32

One-hot variables
1,296
3,096
2,560
4,128

Binary variables
144
192
192
256

Figure 8: Characteristics of Dictionary Benchmarks
CUDD uses complement edges when representing BDDs [2, 14]. Complement edges can potentially reduce
the size of a BDD by a factor of two, invalidating the size ratio bounds derived in Equations 1–2 and 5–
6. For the experimental results presented in the following section, we therefore use a representation based
on CUDD’s support for Algebraic Decision Diagrams (ADDs) [1]. ADDs generalize BDDs by allowing
arbitrary leaf values. Restricting the leaf values to 0 and 1 yields conventional BDDs without complement
edges. We revisit the use of complement edges in Section 9.

8

Experimental Results

We chose three different categories of benchmarks to compare the performance of BDDs, ZDDs, and their
chained versions. One set of benchmarks evaluated the ability of DDs to represent information in compact
form, a second to evaluate their ability to solve combinatorial problems, and a third to represent typical
digital logic functions. All experiments were performed on a 4.2 GHz Intel Core i7 processor with 32 GB
of memory running the OS X operating system.

8.1

Encoding a Dictionary

As others have observed [9], a list of words can be encoded as a function mapping strings in some alphabet
to either 1 (included in list) or 0 (not included in list.) Strings can further be encoded as binary sequences by
encoding each symbol as a sequence of bits, allowing the list to be represented as a Boolean function. We
consider two possible encodings of the symbols, defining the radix r to be the number of possible symbols.
A one-hot encoding (also referred to as a “1-of-N” encoding) requires r bits per symbol. Each symbol is
assigned a unique position, and the symbol is represented with a one in this position and zeros in the rest.
A binary encoding requires dlog2 re bits per symbol. Each symbol is assigned a unique binary pattern, and
the symbol is represented by this pattern. Lists consisting of words with multiple lengths can be encoded by
introducing a special “null” symbol to terminate each word.
Figure 8 shows the characteristics of eight benchmarks derived from two word lists to allow comparisons of
different encoding techniques and representations. The first list is the file /usr/share/dict/words
found on Macintosh systems. It is derived from the word list used by the original Unix spell checker.
It contains 235,886 words with lengths ranging from one to 24 symbols, and where the symbols consist
of lower- and upper-case letters plus hyphen. We consider two resulting symbol sets: a compact form,
consisting of just the symbols found in the words plus a null symbol (54 total), and an ASCII form, consisting
of all 128 ASCII characters plus a null symbol.

13

One-hot
Compact word list
ASCII word list
Compact password list
ASCII password list

BDD
9,701,439
23,161,501
49,231,085
79,014,931

Node counts
CBDD
(C)ZDD
626,070
297,681
626,071
297,681
2,321,572 1,130,729
2,321,792 1,130,729

Ratios
BDD:CBDD CBDD:CZDD
15.50
2.10
37.00
2.10
21.21
2.05
34.03
2.05

BDD
1,117,454
1,464,773
4,422,292
4,943,940

Node counts
CBDD
(C)ZDD
1,007,868
723,542
1,277,640
851,580
3,597,474 2,506,088
4,307,614 2,875,612

Ratios
BDD:CBDD CBDD:CZDD
1.11
1.39
1.15
1.50
1.23
1.44
1.15
1.50

Binary
Compact word list
ASCII word list
Compact password list
ASCII password list

Figure 9: Node counts and ratios of node counts for dictionary benchmarks
The second word list is from an online list of words employed by password crackers. It consists of 979,247
words ranging in length from one to 32 symbols, and where the symbols include 79 possible characters.
Again, we consider both a compact form and an ASCII form.
As Figure 8 shows, the choice of one-hot vs. binary encoding has a major effect on the number of Boolean
variables required to encode the words. With a one-hot encoding, the number of variables ranges between
1,296 and 4,128, while it ranges between 144 and 256 with a binary representation.
To generate DD encodings of a word list, we first constructed a trie representation the words and then
generated Boolean formulas via a depth-first traversal of the trie.
Figure 9 shows the number of nodes required to represent word lists as Boolean functions, according to
the different lists, encodings, and DD types. The entry labeled “(C)ZDD” gives the node counts for both
ZDDs and CZDDs. These are identical, because there were no DON ’ T- CARE chains for these functions. The
two columns on the right show the ratios between the different DD types. Concentrating first on one-hot
encodings, we see that the chain compression of CBDDs reduces the size compared to BDDs by large factors
(15.50–34.03). Compared to ZDDs, representing the lists by CBDDs incurs some penalty (2.05–2.10), but
less than the worst-case penalty of 3. Increasing the radix from a compact form to the full ASCII character
set causes a significant increase in BDD size, but this effect is eliminated by using the zero suppression
capabilities of CBDDs, ZDDs, and CZDDs.
Using a binary encoding of the symbols reduces the variances between the different encodings and DD
types. CBDDs provide only a small benefit (1.11–1.23) over BDDs, and CBDDs are within a factor of
1.50 of ZDDs. Again, chaining of ZDDs provides no benefit. Observe that for both lists, the most efficient
representation is to use either ZDDs or CZDDs with a one-hot encoding. The next best is to use CBDDs
with a one-hot encoding, and all three of these are insensitive to changes in radix. These cases demonstrate
the ability of ZDDS (and CZDDs) to use very large, sparse encodings of values. By using chaining, CBDDs
can also take advantage of this property.
Although the final node counts for the benchmarks indicate no advantage of chaining for ZDDs, statistics

14

One-hot
Compact word list
ASCII word list
Compact password list
ASCII password list

Operations
ZDD
CZDD
142,227,877
12,097,435
375,195,184
28,574,814
806,017,001
62,785,274
1,383,534,557 104,059,626

Binary
Compact word list
ASCII word list
Compact password list
ASCII password list

Operations
ZDD
CZDD
15,701,738
1,826,171
20,921,746
2,139,574
66,489,058
7,499,615
75,556,080
7,936,321

Ratio
1.38
13.13
12.84
13.30

Time (secs.)
ZDD CZDD Ratio
48.78
15.04
3.24
173.56
21.84
7.95
713.15
46.73 15.26
658.21
57.81 11.39

Ratio
8.60
9.78
8.87
9.52

Time (secs.)
ZDD CZDD Ratio
13.11
9.70
1.35
14.40
10.20
1.41
52.52
30.62
1.72
50.77
30.33
1.67

Figure 10: Impact of chaining on effort required to generate DD representations of word lists.
characterizing the effort required to derive the functions show a significant benefit. Figure 10 indicates the
total number of operations and the total time required for generating ZDD and CZDD representations of
the benchmarks. The operations are computed as the number of times the program checks for an entry in
the operation cache (step 2 in the description of the APPLY algorithm). There are many operational factors
that can affect the number of operations, including the program’s policies for operation caching and garbage
collection. Nevertheless, it is some indication of the amount of activity required to generate the DDs. We
can see that chaining reduces the number of operations by factors of 8.87–13.30. The time required depends
on many attributes of the DD package and the system hardware and software. Here we see that chaining
improves the execution time by factors of 1.35–15.26.
With unchained ZDDs, many of the intermediate functions have large DON ’ T- CARE chains. For example,
the ZDD representation of the function x, for variable x, requires n + 2 nodes—one for the variable, n − 1
for the DON ’ T- CARE chains before and after the variable, and two leaf nodes. With chaining, this function
reduces to just four nodes: the upper DON ’ T- CARE chain is incorporated into the node for the variable, and
a second node encodes the lower chain. Our dictionary benchmarks have as many as 4,000 variables, and
so some of the intermediate DDs can be 1,000 times more compact due to chaining.

8.2

The 15-Queens Problem

A second set of benchmarks involved encoding all possible solutions to the n-queens problem. This problem
attempts to place n queens on a n × n chessboard in such a way that no two queens can attack each other.
For our benchmark we chose n = 15 to stay within the memory limit of the processor being used. Once a
DD representation has been generated for all possible solutions, it is easy to then compute useful properties,
such as the number of solutions.
Once again, there are two choices for encoding the positions of queens on the board. A one-hot encoding
uses a Boolean variable for each square. A binary encoding uses dlog2 ne = 4 variables for each row,
encoding the position of the queen within the row.
15

One-hot
Ordering
Top-down
Top-down
Center-first
Center-first
Binary
Ordering
Top-down
Top-down
Center-first
Center-first

Graph(s)
Final
Peak
Final
Peak

Graph(s)
Final
Peak
Final
Peak

BDD
51,889,029
165,977,497
65,104,658
175,907,712

Node counts
CBDD
10,529,738
39,591,936
12,628,086
42,045,602

BDD
13,683,076
43,954,472
17,121,947
46,618,943

Node counts
CBDD
11,431,403
38,898,146
14,185,276
41,362,659

CZDD
4,796,504
18,625,659
5,749,613
19,434,105

Ratios
BDD:CBDD CBDD:CZDD
4.93
2.20
4.19
2.13
5.16
2.20
4.18
2.16

CZDD
7,383,739
26,682,980
9,054,115
28,195,596

Ratios
BDD:CBDD CBDD:CZDD
1.20
1.55
1.13
1.46
1.21
1.57
1.13
1.47

Figure 11: Node counts and ratios of node counts for 15-queens benchmarks
The Boolean formulas must then impose the following constraints:
ROW: No two squares in the same row are occupied. There are n such constraints. A binary encoding
already imposes this constraint.
COL: No two squares in the same column are occupied. There are n such constraints.
DIAG: No two squares in the same diagonal from upper left to lower right are occupied. There are 2n − 1
such constraints.
OFF-DIAG: No two squares in the same diagonal from upper right to lower left are occupied. There are
2n − 1 such constraints.
Our most successful approach worked from the bottom row to the top. At each level, it generated formulas
for each column, diagonal, and off-diagonal expressing whether it was occupied in the rows at or below this
one, based on the formulas for the level below and the variables for the present row.
We considered two ways of ordering the variables for the different rows. The top-down ordering listed the
variables according to the row numbers 1 through 15. The center-first ordering listed variables according to
the row number sequence 8, 9, 7, 10, 6, 11, 5, 12, 4, 13, 3, 14, 2, 15, 1. Our hope in using this sequence was
that ordering the center rows first would reduce the DD representation size. This proved not to be the case,
but the resulting node counts are instructive.
Figure 11 shows the node counts for the different benchmarks. It shows both the size of the final function
representing all solutions to the 15-queens problem, as well as the peak size, computed as the maximum
across all rows of the combined size of the functions that are maintained to express the constraints imposed
by the row and those below it. For both the top-down and the center-first benchmarks, this maximum was
reached after completing row 3. Typically the peak size was around three times larger than the final size.
For a one-hot encoding, we can see that CBDDs achieve factors of 4.18–5.16 compaction over BDDs, and
they come within a factor of 2.20 of CZDDs. For a binary encoding, the levels of compaction are much less
16

One-hot
Ordering
Top-down
Top-down
Center-first
Center-first
Binary
Ordering
Top-down
Top-down
Center-first
Center-first

Graph(s)
Final
Peak
Final
Peak

Node counts
ZDD
CZDD
4,796,504
4,796,504
18,632,019 18,625,659
5,749,613
5,749,613
73,975,637 19,434,105

Ratios
ZDD:CZDD
1.00
1.00
1.00
3.81

Graph(s)
Final
Peak
Final
Peak

Node counts
ZDD
CZDD
7,383,739
7,383,739
26,684,315 26,682,980
9,054,115
9,054,115
33,739,362 28,195,596

Ratios
ZDD:CZDD
1.00
1.00
1.00
1.20

Figure 12: Effect of chaining for ZDD representations of 15-queens benchmarks
compelling (1.13–1.20), as is the advantage of CZDDs over BDDs. It is worth noting that the combination
of a one-hot encoding and chaining gives lower peak and final sizes than BDDs with a binary encoding.
Figure 12 compares the sizes of the ZDD and CZDD representations of the 15-queens functions. We can
see that the final sizes are identical—there are no DON ’ T- CARE chains in the functions encoding problem
solutions. For the top-down ordering, CZDDs also offer only a small advantage for the peak requirement.
For the center-first ordering, especially with a one-hot encoding, however, we can see that CZDDs are
significantly (3.81×) more compact. As the construction for row 3 completes, the variables that will encode
the constraints for rows 2 and 5 remain unconstrained, yielding many DON ’ T- CARE chains. Once again,
this phenomenon is much smaller with a binary encoding. In the end, the center-first variable ordering does
not outperform the more obvious, top-down ordering, but it was beneficial to be able to test it. By using
chaining, CZDDs can mitigate the risk of trying a nonoptimal variable order.
By way of comparison, Kunkle, Slavici, and Cooperman [10] also used the n-queens problem to test their
BDD implementation performed on a cluster of 64 machines. They used a one-hot encoding, but generated
the formula by forming a conjunction of all of the constraints on each single position on the board, requiring
n2 constraints, each with up to 4n−4 terms, requiring a total of θ(n3 ) Boolean operations. In constructing a
representation of the 15-queens problem, their program reached a peak of 917,859,646 nodes, a factor of 5.5
times greater than our peak. Our row-by-row constraint generation requires only θ(n2 ) Boolean operations,
and it significantly reduces the peak memory requirement. Minato described a third approach for generating
constraints for the n-queens problem, but his method also requires θ(n3 ) operations [13].

8.3

Digital Circuits

BDDs are commonly used in digital circuit design automation, for such tasks as verification, test generation,
and circuit synthesis. There ability to represent functions typically found in digital circuits has been widely
studied. It is natural to study the suitability of ZDDs, as well as chained versions of BDDs and ZDDs for
these applications.
17

Circuit
c432
c499
c880
c1908
c2670
c3540
c5315
c6288
c7552

BDD
31,321
49,061
23,221
17,391
67,832
3,345,341
636,305
48,181,908
4,537

Node counts
ZDD
CZDD
48,224
41,637
49,983
48,878
52,436
32,075
18,292
17,017
261,736
85,900
4,181,847
3,538,982
898,912
681,440
48,331,495 48,329,117
37,689
4,774

Ratios
ZDD:BDD CZDD:BDD
1.54
1.33
1.02
1.00
2.26
1.38
1.05
0.98
3.86
1.27
1.25
1.06
1.41
1.07
1.00
1.00
8.31
1.05

Figure 13: Node counts and ratios of node counts for digital circuit benchmarks
We selected the circuits from the ISCAS ’85 benchmark suite [3]. These were originally developed as
benchmarks for test generation, but they have also been widely used as benchmarks for BDDs [7, 11]. We
generated variable orderings for all but last two benchmarks by traversing the circuit graphs, using the fanin
heuristic of [11]. Circuit c6288 implements a 16×16 multiplier. For this circuit, the ordering of inputs listed
in the file provided a feasible variable ordering, while the one generated by traversing the circuit exceeded
the memory limits of our machine. For c7552, neither the ordering in the file, nor that provided by traversing
the graph, generated a feasible order. Instead, we manually generated an ordering based on our analysis of
a reverse-engineered version of the circuit described in [8].
Figure 13 presents data on the sizes of the DDs to represent all of the circuit outputs. We do not present any
data for CBDDs, since these were all close in size to BDDs. We can see that the ZDD representations for
these circuits are always larger than the BDD representations, by factors ranging up to 8.31. Using CZDDs
mitigates that effect, yielding a maximum size ratio of 1.38.
Circuit c6288 has historical interest. Integer multiplication is known to be intractable for BDDs regardless
of variable ordering [5]. As a result, this benchmark was long considered out of reach for a BDD representation and therefore typically omitted from many benchmark comparisons. With a modern machine, the
benchmark is achievable, requiring a peak of around 16 GB to represent the data structures. On the other
hand, we see that these functions contain very few DON ’ T- CARE or OR chains, and hence all four DD types
require around 48 million nodes to represent them.

8.4

Observations

These experiments, while not comprehensive, demonstrate that chaining can allow BDDs to make use of
large, sparse encodings, one of the main strengths of ZDDs. They also indicate that CZDDs may be the best
choice overall. They have all of the advantages of ZDDs, while avoiding the risk of intermediate functions
growing excessively large due to DON ’ T- CARE chains. They are guaranteed to stay within a factor of 2× of
BDDs. Even for digital circuit functions, we found this bound to be conservative—all of the benchmarks
stayed within a factor of 1.4×.
Experienced ZDD users take steps to avoid DON ’ T- CARE chains, for example, by implementing special
18

Metric
Final size
Operations
Time (secs.)

Complement edges
No
Yes
48,177,349
41,417,996
675,645,812 272,783,843
1757
280

Ratio
1.16
2.48
6.27

Figure 14: Benefits of complement edges for CBDD representations of c6288 benchmark.
algorithms that operate directly on ZDDs, rather than expressing a computation as a sequence of Boolean
operations [9, 18]. By using chaining, CZDDs reduce the cost of these chains, enabling users to express
their computations at the more abstract level of Boolean expressions, rather than implementing special
algorithms.

9

Complement Edges

As mentioned earlier, CUDD uses complement edges in its representation of BDDs, and hence our experiments showed the results for ADDs. We also implemented CBDDs with complement edges by modifying
CUDD’s implementation of BDDs. The standard rules for deciding how to canonicalize complement edges
[2] can be used without modification with CBDDs. Interestingly, these rules imply that there are no ZERO
chains in our CBDDs, because the canonicalization forbids having a hi pointer to leaf 0. Instead, such
chains are represented by chain nodes with the hi edges pointing to leaf 1, and with their incoming edges
complemented. Although Minato’s original paper on ZDDs [14] includes a set of conventions for using
complement edges with ZDDs, these are not implemented in CUDD. Thus, we did not attempt this feature
in our implementation.
Figure 14 illustrates the impact of complement edges for CBDDs, based on the c6288 benchmark. Similar
results hold without chaining. As can be seen, although complement edges can potentially yield a 2×
reduction in the number of nodes, the actual reduction is much smaller (1.16). However, it can greatly affect
the number of operations required (2.48×), since complement edges enable complementing a function in
a single step, rather than traversing the graph. (The circuit consists mostly of NOR gates, each requiring a
complement operation.) The impact on time (6.27×) is even greater, since the large number of complement
operations pollutes the operation cache.

10

Further Work

Our modifications to CUDD to support chaining were only sufficient to evaluate the basic concepts. Fully
integrating these changes into such a complex software would require significantly more effort. Perhaps
the most challenging would be to implement dynamic variable ordering [15]. The same basic principles
of dynamic variable ordering hold for both CBDDs and CZDDs. An exchange of variables at levels l and
l + 1 could be performed without modifying any of the nodes with levels less than l and without modifying
any external node pointers. Special consideration must be given to nodes with levels t : b, such that either
t = l + 1 or b = l. Many low-level details and heuristics of the implementation would need to be altered to
19

enable dynamic variable ordering to work well.

11

Acknowledgements

This work has benefitted from conversations with Shin-Ichi Minato and Ofer Strichman.

References
[1] R. Iris Bahar, E. A. Frohm, C. M. Gaona, Gary D. Hachtel, Enrico Macii, Abelardo Pardo, and Fabio
Somenzi. Algebraic decision diagrams and their applications. In Proceedings of the International
Conference on Computer-Aided Design, pages 188–191, November 1993.
[2] Karl S. Brace, Richard L. Rudell, and Randal E. Bryant. Efficient implementation of a BDD package.
In Proceedings of the 27th ACM/IEEE Design Automation Conference, pages 40–45, June 1990.
[3] F. Brglez and H. Fujiwara. A neutral netlist of 10 combinational benchmark circuits and a target
translator in Fortran. In 1985 International Symposium on Circuits And Systems, 1985.
[4] Randal E. Bryant. Graph-based algorithms for Boolean function manipulation. IEEE Transactions on
Computers, C-35(8):677–691, August 1986.
[5] Randal E. Bryant. On the complexity of VLSI implementations and graph representations of Boolean
functions with application to integer multiplication. IEEE Transactions on Computers, 40(2):205–213,
Feb 1991.
[6] Randal E. Bryant. Binary decision diagrams. In E. M. Clarke, T. A. Henzinger, H. Veith, and R. Bloem,
editors, Handbook of Model Checking. Springer Verlag, 2017.
[7] Masahiro Fujita, H. Fujisawa, and N. Kawato. Evaluation and improvements of Boolean comparison method based on binary decision diagrams. In Proceedings of the International Conference on
Computer-Aided Design, pages 2–5, November 1988.
[8] M. Hansen, H. Yalcin, and J. P. Hayes. Unveiling the ISCAS-85 benchmarks: A case study in reverse
engineering. IEEE Design and Test, 16(3):72–80, July-September 1999.
[9] Donald S. Knuth. The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part I.
Addison Wesley, 2011.
[10] D. Kunkle, V. Slavici, and G. Cooperman. Parallel disk-based computation for large, monolithic binary
decision diagrams. In International Workshop on Parallel and Symbolic Computation, pages 63–72.
ACM, July 2010.
[11] Sharad Malik, Albert Wang, Robert K. Brayton, and Alberto L. Sangiovanni-Vincentelli. Logic verification using binary decision diagrams in a logic synthesis environment. In Proceedings of the International Conference on Computer-Aided Design, pages 6–9, November 1988.

20

[12] Shin-ichi Minato. Zero-suppressed BDDs for set manipulation in combinatorial problems. In Proceedings of the 30th ACM/IEEE Design Automation Conference, pages 272–277, June 1993.
[13] Shin-ichi Minato. Binary Decision Diagrams and Applications for VLSI CAD. Kluwer Academic
Publishers, 1995.
[14] Shin-ichi Minato, Nagisa Ishiura, and Shuzo Yajima. Shared binary decision diagrams with attributed
edges for efficient Boolean function manipulation. In Proceedings of the 27th ACM/IEEE Design
Automation Conference, pages 52–57, June 1990.
[15] Richard L. Rudell. Dynamic variable ordering for ordered binary decision diagrams. In Proceedings
of the International Conference on Computer-Aided Design, pages 139–144, November 1993.
[16] Fabio Somenzi. Efficient manipulation of decision diagrams. International Journal on Software Tools
for Technology Transfer, 3(2):171–181, 2001.
[17] Ingo Wegener. Branching Programs and Binary Decision Diagrams: Theory and Applications. SIAM,
2000.
[18] Tomohiro Yoneda, Hideyuki Hatori, Atsushi Takahara, and Shin-ichi Minato. BDDs vs. zerosuppressed BDDs for CTL symbolic model checking of Petri nets. In Formal Methods in ComputerAided Design, volume 1166 of Lecture Notes in Computer Science, pages 435–449, 1996.

21

