Binäres Entscheidungsdiagramm

Ein Binäres Entscheidungsdiagramm (BED; engl. binary decision diagram, BDD) ist eine Datenstruktur zur Repräsentation Boolescher Funktionen. Binäre Entscheidungsdiagramme werden vor allem im Bereich der Hardwaresynthese und -verifikation eingesetzt.

Definition

Ein Binäres Entscheidungsdiagramm ist ein azyklischer, gerichteter Graph G = (V,E) mit einer Wurzel, so dass gilt

• Jeder Knoten v aus V ist entweder ein Blatt oder ein innerer Knoten.
• Blätter besitzen keine ausgehenden Kanten und sind mit einem Wert aus {0,1} beschriftet.
• Jeder innere Knoten v besitzt genau zwei ausgehende Kanten, die als niedrig- bzw. hoch-Kante bezeichnet werden. Die Endpunkte dieser Kanten werden mit niedrig(v) bzw. hoch(v) bezeichnet. Außerdem ist jeder innere Knoten mit einer Variablen x_i beschriftet.
• Auf allen Pfaden von der Wurzel zu einem Blatt sind die Variablen in einer festen, strikten Ordnung geordnet (Variablenordnung, OBDD).
• Alle isomorphen Teilgraphen sind verschmolzen und es existieren keine Knoten, deren Kinder identisch sind (Reduktion, ROBDD).

Durch die Shannon-Zerlegung kann die von einem Binären Entscheidungsdiagramm dargestellte Boolesche Funktion berechnet werden. Sei v aus V ein Knoten des Binären Entscheidungsdiagramms. Dann ist die von v dargestellte Funktion f_v definiert als

• falls v ein Blatt ist, dann ist die dargestellte Funktion f_v der Wert der Beschriftung von v
• falls v ein innerer Knoten mit Beschriftung x_i ist, dann ist $f_v(x) = x_i f_{hoch(v)}(x) + \overline{x_i} f_{niedrig(v)}(x)$.

Für jede Boolesche Funktion existiert (bei fester Variablenordnung) genau ein minimales OBDD, d. h. OBDDs sind eine kanonische Darstellung Boolescher Funktionen (Bryant, 1986).

Beispiel

Darstellung eines BDDs

Dieses Bild stellt ein freies, geordnetes und reduziertes Binäres Entscheidungsdiagramm dar. Dabei wird die niedrig-Kante eines Knotens gestrichelt und die hoch-Kante durchgezogen dargestellt. Die verwendete Variablenordnung ist x₁ < x₃ < x₂. Die dargestellte Funktion lässt sich folgendermaßen berechnen:

• x₂-Knoten:

$f_1(x_1,x_2,x_3) = 0\cdot x_2 + 1\cdot\overline{x_2} = \overline{x_2}$

• linker x₃-Knoten:

$f_2(x_1,x_2,x_3) = f_1\cdot x_3 + 1\cdot \overline{x_3} = \overline{x_2}x_3 + \overline{x_3}$

• rechter x₃-Knoten:

$f_3(x_1,x_2,x_3) = 0 \cdot x_3 + f_1\cdot\overline{x_3} = \overline{x_2}\,\overline{x_3}$

• x₁-Knoten:

$f_4(x_1,x_2,x_3) = f_2\cdot x_1 + f_3\cdot\overline{x_1} = x_1\overline{x_2}x_3 + x_1\overline{x_3} + \overline{x_1}\,\overline{x_2}\,\overline{x_3}$

Wir können die dargestellte Funktion auch direkt für eine gegebene Variablenbelegung auswerten. Dazu muss lediglich dem Pfad, der zu der Belegung gehört, gefolgt werden, bis man ein Blatt erreicht. Der Wert dieses Blattes ist der Funktionswert für die gegebene Variablenbelegung.

Nehmen wir an, wir wollen für obiges Beispiel den Funktionswert für (x₁,x₂,x₃) = (0,1,1) bestimmen. Wir beginnen an der Wurzel des Binären Entscheidungsdiagramms. Dieser Knoten ist mit x₁ beschriftet. Da in unserer Belegung x₁ = 0 ist, folgen wir der niedrig-Kante und erreichen einen Knoten, der mit x₃ beschriftet ist. Es gilt x₃ = 1, also folgen wir der hoch-Kante und erreichen das Blatt mit der Beschriftung 0. Folglich gilt f(0,1,1) = 0.

Variablenordnungen

Die Struktur und die Zahl der Knoten eines geordneten und reduzierten Binären Entscheidungsdiagramms hängen bei vielen Funktionen stark von der gewählten Variablenordnung ab. Als Beispiel betrachten wir die Boolesche Funktion $f(x_1,\ldots, x_{2n}) = x_1x_2 + x_3x_4 + \dots + x_{2n-1}x_{2n}$. Wählt man dafür die Variablenordnung $x_1 < x_3 < \dots < x_{2n-1} < x_2 < x_4 < \dots < x_{2n}$, so benötigt das Binäre Entscheidungsdiagramm mehr als 2ⁿ Knoten. Bei der Variablenordnung $x_1 < x_2 < x_3 < x_4 < \dots < x_{2n-1} < x_{2n}$ genügen hingegen 2n Knoten.

Binäres Entscheidungsdiagramm für die Funktion f(x1, ..., x8) = x1x2 + x3x4 + x5x6 + x7x8 mit schlechter Variablenordnung

Gute Variablenordnung

Es gibt auch Funktionen, die unabhängig von der Variablenordnung exponentiell in Zahl der Variablen viele Knoten benötigen. Dazu gehören auch so wichtige Funktionen wie die Multiplikation. Deshalb wurden im Laufe der Jahre zahlreiche Varianten von Binären Entscheidungsdiagrammen entwickelt, wie beispielsweise Kronecker Functional Decision Diagrams, Binary Moment Diagrams, Edge-valued Binary Decision Diagrams und zahlreiche andere.

Operationen auf Binären Entscheidungsdiagrammen

Die Operationen, die normalerweise von allen Implementierungen zur Verfügung gestellt werden, sind zumindest die Booleschen Verknüpfungen Konjunktion (AND), Disjunktion (OR) und die Negation (NOT).

Die Negation kann durchgeführt werden, indem man das 0- und das 1-Blatt des Binären Entscheidungsdiagramms vertauscht. Die übrigen zweistelligen Booleschen Operationen werden normalerweise auf einen speziellen ternären Operator, den sogenannten ITE-Operator zurückgeführt:

$ITE(f,g,h) = (f\wedge g) \vee (\neg f\wedge h)$

Der Name ITE kommt von if-then-else: Wenn das Argument f gleich 1 ist, dann ist der Funktionswert von ITE gleich dem Funktionswert von g, ansonsten gleich dem von h.

Mit Hilfe von ITE können wir schreiben:

$f\wedge g = ITE(f,g,0)$

$f\vee g = ITE(f,1,g)$

$\neg f = ITE(f,0,1)$

Man kann sich leicht davon überzeugen, dass sich alle 16 binären Booleschen Operationen mit Hilfe des ITE-Operators ausdrücken lassen. Es genügt folglich, eine Implementierung des ITE-Operators anzugeben.

Weitere wichtige Operationen sind beispielsweise:

• Test von zwei dargestellten Funktionen auf Gleichheit. Die meisten verfügbaren Implementierungen sorgen dafür, dass Knoten, die dieselbe Funktion darstellen, nur einmal angelegt werden. Dann können einfach die Zeiger auf die Knoten der Binären Entscheidungsdiagramms verglichen werden: sind sie gleich, so auch die dargestellten Funktionen und umgekehrt. Damit ist die Laufzeit konstant (d. h. O(1)).
• Test auf Erfüllbarkeit der dargestellten Funktion, also Beantwortung der Frage, ob es eine Belegung der Variablen gibt, so dass die Funktion den Wert 1 annimmt. Dazu muss das Binäre Entscheidungsdiagramm lediglich mit dem 0-Blatt verglichen werden.
• Berechnung der Anzahl der erfüllenden Belegungen: kann durch Traversieren des Binären Entscheidungsdiagramms in Linearzeit geschehen. Für Details siehe [1].

Implementierungen

• CMU BDD, BDD-Paket, Carnegie Mellon University, Pittsburgh
• CUDD: BDD-Paket, University of Colorado, Boulder
• CrocoPat: BDD-Paket mit Interpreter für Relationales Programmieren, University of California, Berkeley
• JINC: Eine parallele (multi-threading) C++ Bibliothek, Universität Bonn.
• BuDDy : libbdd, eine sehr effiziente BDD Library, geschrieben in C, mit C++ Interface

Literatur

• C. Y. Lee. Representation of Switching Circuits by Binary-Decision Programs. Bell Systems Technical Journal, 38:985–999, 1959.
• Sheldon B. Akers: Binary Decision Diagrams, IEEE Transactions on Computers, C-27(6):509–516, Juni 1978.
• Randal E. Bryant: Graph-Based Algorithms for Boolean Function Manipulation, IEEE Trans. Computers, Vol. C-35, No. 8 (August, 1986), 677-691.
• Ingo Wegener: Branching Programs and Binary Decision Diagrams, SIAM Monographs on Discrete Mathematics and Applications 4, ISBN 0-89871-458-3
• Rolf Drechsler, Bernd Becker: Graphenbasierte Funktionsdarstellung. Boolesche und Pseudo-Boolesche Funktionen, Teubner Verlag 1998, ISBN 3-519-02149-8
• Donald E. Knuth: The Art of Computer Programming - Combinatorial Algorithms, Part 1, Addison-Wesley 2011, 202-280, ISBN 0-201-03804-8