A

**binary decision diagram** (or

**BDD**) is a

decision diagram representing a

boolean function :

**B**^{n} ->

**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

**ROBDD**s or

**OBDD**s (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 !)