L4: Binary Decision Diagrams

Reading material
• de Micheli pp. 75 - 85
• R. Bryant, “Graph-based algorithms for Boolean
function manipulation”, IEEE Transactions on
computers, C-35, No 8, August 1986; can be
downloaded from
– http://www.cs.cmu.edu/~bryant/

• CUDD-package manual
– http://vlsi.colorado.edu/~fabio/

p. 2 - Advanced Logic Design – L4 - Elena Dubrova

Binary Decision Diagram
• Graph-based representation for Boolean
functions f: Bn → Bm
– directed acyclic graph
– one root node, terminal nodes 0, 1
– each non-terminal node has two children and is labeled by a
variable

a b f
00
01
10
11

0
1
1
0

a
b
0

1

b
1

0

p. 3 - Advanced Logic Design – L4 - Elena Dubrova

Binary Decision Diagram
• Mathematical foundation for BDDs is the
Shannon decomposition theorem:
f(x1,x2, ...,xn) = x'1·f|x1=0 + x1· f|x1=1

where
f|x1=0 := f(0,x2, ...,xn), f|x1=1 := f(1,x2, ...,xn)

are subfunctions of f, called co-factors

p. 4 - Advanced Logic Design – L4 - Elena Dubrova

Binary Decision Diagram
• Let v be a node of a ROBDD labeled by some
variable xi, then
– low(v) is the subghraph pointed by the edge
corresponding to xi = 0
• this subgraph represents f|x

1=0

– high(v) is the subghraph pointed by the edge
corresponding to xi = 1
• this subgraph represents f|x

1=1

– index(v) = i

p. 5 - Advanced Logic Design – L4 - Elena Dubrova

Binary Decision Diagram

p. 6 - Advanced Logic Design – L4 - Elena Dubrova

Ordering rules
• no variable appears more than once along a path
• in all paths variables appear in the same order

a
c

ordered
order = a,c,b
c

b

b
0

c
b

c
1

not
ordered

a

0

1

p. 7 - Advanced Logic Design – L4 - Elena Dubrova

Reduction rules
1) no vertex v with low(v) = high(v)

2) no distinct vertices v and u such that the subgraphs
rooted by v and u are isomorphic
• these two rules guarantee that each node represents a
distinct logic function
p. 8 - Advanced Logic Design – L4 - Elena Dubrova

Reduced Ordered Binary Decision
Diagram (ROBDD)
a b f
00
01
10
11

a

0
1
1
0

b
0

b
1

• canonical representation (fixed ordering)
• easy manipulation algorithms
• compact for many practical functions
p. 9 - Advanced Logic Design – L4 - Elena Dubrova

Properties of ROBDD
• function is given by tracing all the paths to 1
terminal node: f = b’+a’c’ = ab’+a’cb’+a’c’
a
0
fa = cb’+c’

c

1
1

fa= b’

b

0
1
0

f

0
1

•cubes given by paths are pair-wise disjoint
p. 10 - Advanced Logic Design – L4 - Elena Dubrova

Advantages of ROBDDs
• The number of cubes we represent might be
exponential
• But the size of a ROBDD is measured by its
nodes, not by its paths
• a ROBDD can represent an exponential number
of paths with a linear number of nodes

p. 11 - Advanced Logic Design – L4 - Elena Dubrova

Problems with ROBDDs
• Some functions have exponential-size ROBDDs
– multipliers, HWB

• size of a ROBDD depends critically on variable
ordering
– adders - exponential for bad orderings, linear for good
orderings

• finding a best variable ordering requires
exponential time

p. 12 - Advanced Logic Design – L4 - Elena Dubrova

Example
root
node
c+bd

c

b
c+d

c

f = ab+a’c+bc’d

a
b

a
c+bd

b

d+b

c

d

b

c

d

b

d

0

1

0

1

Two different orderings, same function
p. 13 - Advanced Logic Design – L4 - Elena Dubrova

Algorithms for BDD manipulation
• Basic algorithms for BDD manipulation:
– Reduce : BDD G reduced to canonical form,
complexity O(|G|log |G|)
– Apply : performes f1 • f2 for some operation “•“,
complexity O(|G1|⋅|G2|)
– Compose : substitues f2 in a variable x of f1,
complexity O(|G1|2⋅|G2|)
– Satisfy-one: checkes whether f(x1,.., xn)=1 for some
assignment x1,.., xn, O(n)

p. 14 - Advanced Logic Design – L4 - Elena Dubrova

A simple reduction algorithm:
1) Merge all identical terminal nodes and appropriately
redirect their incoming edges
2) Proceeding from bottom to top:
• if a node v is found such that low(v) = high(v), remove v and
redirect its incoming edges to low(v) (reduction rule 1)
• if two nodes v and u with index(v) = index(u) are found such
that low(v) = low(u) and high(v) = high(u), remove v and redirect its incoming edges to u (reduction rule 2)

p. 15 - Advanced Logic Design – L4 - Elena Dubrova

Apply
• The procedure Apply provides the basic method
for creating the BDD representation of a function
given by a Boolean expression
• It takes BDDs for functions f1, f2 and a binary
operation •, and produces a BDD for the function
f1 • f2 defined as
[f1 • f2 ] (x1,...,xn)= f1 (x1,...,xn) • f2 (x1,...,xn)

p. 16 - Advanced Logic Design – L4 - Elena Dubrova

Apply
• Apply can be used to complement a function
(compute f ⊕ 1)
• to compute intersection (• = ⋅)
• to compute union (• = +)
• Note: in cube representations we needed 3
different procedures for that

p. 17 - Advanced Logic Design – L4 - Elena Dubrova

ITE operator
• If-then-else: ite(f,g,h) equals to g when f is 1 and equals to
h otherwise:
ite(f,g,h) = f ⋅ g + f' ⋅h
• Each node is written as a triple: f = (v,g,h) where
g = fv
and h = fv , where v is the root node of f
• We read this triple as:
f = if v then g else h = ite (v,g,h) = vg+v ’ h

v

1

f
0

g

h

v
mux

0
h

f
1
g

p. 18 - Advanced Logic Design – L4 - Elena Dubrova

ITE operator
• Ite can be used to implement any binary
operation, like AND, OR
f ⋅ g = ite(f,g,0)
f + g = ite(f,1,g)

• Ite can be implemented by extending Apply
procedure to ternary operations

p. 19 - Advanced Logic Design – L4 - Elena Dubrova

ITE operator
Table
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

Subset
0
AND(f, g)
f>g
f
f<g
g
XOR(f, g)
OR(f, g)
NOR(f, g)
XNOR(f, g)
NOT(g)
f≥g
NOT(f)
f≤g
NAND(f, g)
1

Expression
0
fg
fg
f
fg
g
f⊕g
f+g
f+g
f⊕g
g
f + g
f
f + g
fg
1

Equivalent Form
0
ite(f, g, 0)
ite(f,g, 0)
f
ite(f, 0, g)
g
ite(f,g, g)
ite(f, 1, g)
ite(f, 0,g)
ite(f, g,g)
ite(g, 0, 1)
ite(f, 1, g)
ite(f, 0, 1)
ite(f, g, 1)
ite(f, g, 1)
1

p. 20 - Advanced Logic Design – L4 - Elena Dubrova

Variable ordering problem
• Exact algorithms are intractable
• Heuristics are used:
– static: use properties to group the variables together
(e.g. keep symmetric variable together)
– dynamic sifting: use the property that exchanging
adjacent variables has only a local effect on the BDD;
the variables are sifted from top to bottom one by one
and the best position is remembered

p. 21 - Advanced Logic Design – L4 - Elena Dubrova

Static variable ordering
• variable ordering is computed up-front based on
the problem structure
• works very well for many combinational functions
that come from circuits we actually build
– general scheme: control variables first

• works bad for unstructured problems
– e.g. using BDDs to represent arbitrary sets

• lots of research in ordering algorithms
– simulated annealing, genetic algorithms
– give better results but extremely costly
p. 22 - Advanced Logic Design – L4 - Elena Dubrova

Dynamic variable ordering
Theorem (Friedman): Permuting any top part of the variable
order has no effect on the nodes labeled by variables in
the bottom part. Permuting any bottom part of the variable
order has no effect on the nodes labeled by variables in
the top part.
mem1

f

f0

f0
mem2

a
mem3

mem1

f1

b

b

mem3

c

c

f01 f10

c

f1 mem2

b

b
a a

b

f00

f

c

c

c

f11

f00

f01 f10

c

c

Two adjacent variable
layers can be
exchanged by without
changing the rest of
BDD

f11

p. 23 - Advanced Logic Design – L4 - Elena Dubrova

Dynamic variable ordering
• Dynamic variable ordering is done as follows:
– shift a BDD variable to the top and then to the bottom
and see which position had minimal number of BDD
nodes
– fix the variable to this position
– repeat for all variables

p. 24 - Advanced Logic Design – L4 - Elena Dubrova

BDD package (CUDD)
• A BDD package is a software program that can
manipulate ROBDDs:
– It can store multiple Boolean functions, sharing all
vertices that can be shared.
– It can create new functions by combining existing ones
(e.g. f = g⋅ h)
– It can convert the internal representation back to an
external one

p. 25 - Advanced Logic Design – L4 - Elena Dubrova

Basic data structures
• The basic component is DdNode, which is a
structure with several fields
typedef struct DdNode {
struct DdNode *low, *high; /* pt to low, high child */
int index;
/* index of the variable that */
/* labels the node, in 0...n */
char value;
/* range in {0,1} of terminal nodes */
/* x for non-terminal nodes */
int id;
/* reference count - identifier */
...
/* unique to that node */
}

p. 26 - Advanced Logic Design – L4 - Elena Dubrova

Efficient Implementation
Unique Table:
•

avoids duplication of existing nodes
– Implemented by a hash-table
hash value
of key

collision
chain

Computed Table:
•

avoids re-computation of existing results
• Implemented by a software cache
p. 27 - Advanced Logic Design – L4 - Elena Dubrova

Building a BDD
• It is normally more efficient to build BDDs
“bottom-up”
• ITE-procedure Cudd_bddIteVar can be used
• Other procedures for binary operations, like
Cudd_bddAnd or Cudd_bddOr can also be used

p. 28 - Advanced Logic Design – L4 - Elena Dubrova

Example of building a BDD using
CUDD package
• Building BDD for f = x'0 x'1 x'2 x'3:
DdManager *manager;
DdNode *f, *var, *tmp;
int i;
f = Cudd_readOne(manager); /* start from const 1*/
Cudd_ref(f);
/* referencing f */
for(i=3; i >= 0; i--) {
/* building bottom-up */
var = Cudd_bddIthVar(manager,i);
tmp = Cudd_bddAnd(manager, Cudd_Not(var),f); /*assigning to a
tmp variable, old f should be kept to free its nodes */
Cudd_ref(tmp);
Cudd_recursiveDeref(manager,f);
f = tmp; }
p. 29 - Advanced Logic Design – L4 - Elena Dubrova

Garbage Collection
•
•

It is very important to free and reuse memory of unused
BDD nodes. This is done by garbage collection.
Timing is very crucial because garbage collection is
expensive. There are two approaches:
1. do immediately when a node gets freed
– bad because dead nodes get often reincarnated in next
operation

2. regular garbage collections based on statistics
collected during BDD operations
– better

p. 30 - Advanced Logic Design – L4 - Elena Dubrova

Extension - complemented edges
• Complemented edge indicates that the function
associated with it is the complement of the
function being pointed by the edge
– reduces memory requirements
– BUT MORE IMPORTANT:
• makes some operations more efficient (NOT, ITE)
G

G

G

G

two different
BDDs
0

1

0

1

0

only one BDD
using complement
pointer

1

p. 31 - Advanced Logic Design – L4 - Elena Dubrova

Extension - complement edges
• To maintain strong canonical form, need to
resolve 4 equivalences:

Solution: Always choose one on left, i.e. the “then”
edge must have no complement edge.
p. 32 - Advanced Logic Design – L4 - Elena Dubrova

Other extensions
• Many different extentions of BDDs are possible
– algebraic DDs: for Bn → M functions
•
•
•
•

multi-terminal BDDs
decision tree is binary
multiple leafs, including real numbers, sets or arbitrary objects
efficient for matrix computations and other non-integer applications

– MDDs: for Mn → M functions
• can be implemented using a regular BDD package with binary
encoding
• advantage that binary BDD variables for one MV variable do not have
to stay together -> potentially better ordering
– FDDs: Free Bdds
• variable ordering differs; not canonical anymore

p. 33 - Advanced Logic Design – L4 - Elena Dubrova

Zero Suppressed BDD’s - ZBDD’s
ZBDD’s were invented by Minato to efficiently represent
sparse sets. They have turned out to be useful in implicit
methods for representing primes (which usually are a
sparse subset of all cubes).
Different reduction rules:
•
•
•

BDD: eliminate all nodes where dotted edge and solid edge point to
the same node.
ZBDD: eliminate all nodes where the solid edge points to 0. Connect
incoming edges to node pointed by dotted edge.
For both: share equivalent nodes.

BDD:

0

1

ZBDD:

0

1
0

0

1

0

1

0

1

p. 34 - Advanced Logic Design – L4 - Elena Dubrova

0

1

Summary of BDDs
• BDDs give a compact representation for many
practical functions as well as fast manipulation
algorithms
– widely used in CAD-tools nowadays

• They are very convenient for formal verification
(equivalence checking)
– comparing of two functions is done by comparing two
pointers to the root nodes (constant-time operation)

p. 35 - Advanced Logic Design – L4 - Elena Dubrova