BDD, binary decision diagram, Datenstruktur für Boolesche Funktionen.

Ein BDD über den Booleschen Variablenx₁,…,x_n ist ein azyklischer, zusammenhängender, gerichteter Graph G = (V, E), dem eine Abbildung index : V → {x₁,…,x_n} U {0, 1} zugeordnet ist.

Die Menge V der Knoten enthält genau einen Knoten, in den keine Kante aus der Kantenmenge E einläuft, die Wurzel des BDD. Ein Knoten, aus dem keine Kante herausläuft, wird Blatt des BDD genannt. Ein Knoten aus V, der kein Blatt ist, heißt innerer Knoten des BDD.

Jedem inneren Knoten v ist eine Boolesche Variable index(v) ∈ {x_l,…,x_n} als Markierung zugeordnet. Zudem besitzt jeder innere Knoten genau zwei Nachfolgerknoten: low(v), der low-Nach- folgerknoten von v, und high(v), der high-Nach-folgerknoten von v. Die Kante (v, low(v)) wird mit low-Kante von v und die Kante (v, high(v)) mit high-Kante von v bezeichnet. Jedes Blatt ist mit einem Wert index(v) ∈ {0,1} markiert. Ist ein binärer Entscheidungsgraph ein gerichteter binärer Baum, so spricht man auch von einem binären Entscheidungsbaum.

BDDs dienen zur Darstellung Boolescher Funktionen. Ein BDD \({\mathfrak{b}}\) mit Wurzel \(W\), der über der n-elementigen Variablenmenge {x_l,…,x_n} definiert ist, beschreibt die Boolesche Funktion f_w : {0, l}ⁿ → {0,1}, definiert durch:

1. Ist w ein Blatt und index(w) = 0, so ist f_w die konstante Abbildung 0 : {0, l}ⁿ → {0,1} mit 0(α) = 0 für alle \(\alpha \in {\{\bar{0},1\}}^{n}\)
2. Ist w ein Blatt und index(w) = 1, so ist f_w die konstante Abbildung 1 : {0, l}ⁿ → {0,1} mit 1(α) = 1 für alle \(\alpha \in {\{\bar{0},1\}}^{n}\)
3. Ist w ein innerer Knoten und index(w) = x_i, so gilt

   \begin{eqnarray}{f}_{w}(\alpha )=(\bar{{\alpha }_{i}}\wedge {f}_{low}{}_{(w)}(\alpha ))\vee ({\alpha }_{i}\wedge {f}_{high(w)}(\alpha ))\end{eqnarray}

Verwendet wird in diesem Zusammenhang die Sprechweise „\({\mathfrak{b}}\) ist ein BDD der Booleschen Funktion f_w“ und „f_w ist die durch den binären Entscheidungsgraphen \({\mathfrak{b}}\) dargestellte Boolesche Funktion“. Sind zwei BDDs binäre Entscheidungsgraphen der gleichen Booleschen Funktion f, so spricht man von äquivalenten binären Entscheidungsgraphen. Ein Verfahren, das entscheidet, ob zwei gegebene BDDs äquivalent sind, wird auch Äquivalenztest genannt.

Jedem BDD kann in einfacher Weise ein kombinatorischer logischer Schaltkreis zugeordnet werden, der die zu dem BDD gehörige Boolesche Funktion realisiert. Jeder innere Knoten v des BDD wird durch einen Multiplexer mit einem Steuereingang s und zwei Dateneingängen a₀ und a₁ ersetzt. Der Dateneingang a₀ wird verbunden mit dem Ausgang des zu dem low-Nachfolger-knoten von v gehörigen Multiplexers, der Dateneingang a₁ mit dem Ausgang des zu dem high-Nach-folgerknoten von v gehörigen Multiplexers.

Der Steuereingang s des Multiplexers wird mit dem primären Eingang x_iverbunden, wenn x_i = index(v) gilt. Der Multiplexer berechnet an seinem Ausgang den Wert \(({a}_{0}\wedge \bar{{x}_{i}})\vee ({a}_{1}\wedge {x}_{i})\). Jedes 0-Blatt (1-Blatt) ersetzt man durch ein Signal, das konstant auf dem Wert 0 (1) gehalten wird. Die Anzahl der inneren Knoten des BDD bestimmt damit die Komplexität des so konstruierten logischen Schaltkreises. Sie wird Kosten des BDD genannt.

Eine kanonische Darstellung Boolescher Funktionen erhält man mit BDDs durch Einschränkung auf eine feste Variablenordnung, nach der auf jedem Pfad von der Wurzel zu einem Blatt die Variablen abgefragt werden (geordneter binärer Entscheidungsgraph) und durch Reduktion der binären Entscheidungsgraphen (reduzierter geordneter binärer Entscheidungsgraph).

[1] Drechsler, R.; Becker, B.: Graphenbasierte Funktionsdarstellung. B.G. Teubner Stuttgart, 1998.