A
binary decision diagram (or
BDD) is a
decision diagram representing a
boolean function :
Bn ->
B.
The
values of the
sinks are {0,1}, the are exactly two outgoing
edges at every non-sink
node, marked with 0 or 1.
A BDD is called
ordered if one every
path from the
source to the sink the
variables turn up in the same fixed
order and every variable turns up at most once.
A BDD is called
reduced if it is ordered and there are no
isomorphic sub
graphs in the BDD. They are often called
ROBDDs or
OBDDs (the second is a little bit confusing, but standard nowadays).
Why are they important ?
In automatic digital circuit designs you have to deal with extremely large boolean functions. Think of a 32 bit multiplier. So you need a handy representation for them. Boolean formulas are often large and most important not canonical. If they are restricted to SOPs or the like, they usually get much too large to handle. Function tables are too large anyway. So you have of problem. OBDD are really small representations for some functions (often used functions !), canonical (for a fixed order of variables) and there are fast algorithms for them. So they play an important role in automatic digital circuit design, in fact they are very often used. Howevery, some problems remain: there are functions for which you can prove that all representing OBDDs have at least expotential size (in respect to the number of variables). A multiplier contains such functions. Note that there must be such functions, unless P=NP. (A OBDD is a satisfiability test !)