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.

Inhaltsverzeichnis

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 xi 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 fv definiert als

  • falls v ein Blatt ist, dann ist die dargestellte Funktion fv der Wert der Beschriftung von v
  • falls v ein innerer Knoten mit Beschriftung xi 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 x1 < x3 < x2. Die dargestellte Funktion lässt sich folgendermaßen berechnen:

  • x2-Knoten:
f_1(x_1,x_2,x_3) = 0\cdot x_2 + 1\cdot\overline{x_2} = \overline{x_2}
  • linker x3-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 x3-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}
  • x1-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 (x1,x2,x3) = (0,1,1) bestimmen. Wir beginnen an der Wurzel des Binären Entscheidungsdiagramms. Dieser Knoten ist mit x1 beschriftet. Da in unserer Belegung x1 = 0 ist, folgen wir der niedrig-Kante und erreichen einen Knoten, der mit x3 beschriftet ist. Es gilt x3 = 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 2n 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

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Binary Decision Diagram — 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… …   Deutsch Wikipedia

  • OBDD — 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… …   Deutsch Wikipedia

  • ROBDD — 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… …   Deutsch Wikipedia

  • BdD — Die Abkürzung BDD steht für: Buddhistischer Dachverband Diamantweg Bund der Deutschen Demokraten (DDD) Bundesverband Deutscher Detektive. Bundesverband Direktvertrieb Deutschland. Bundesverband der Dienstleistungsunternehmen. Body Dysmorphic… …   Deutsch Wikipedia

  • Bdd — Die Abkürzung BDD steht für: Buddhistischer Dachverband Diamantweg Bund der Deutschen Demokraten (DDD) Bundesverband Deutscher Detektive. Bundesverband Direktvertrieb Deutschland. Bundesverband der Dienstleistungsunternehmen. Body Dysmorphic… …   Deutsch Wikipedia

  • Modelchecking — Model Checking (deutsch auch Modellprüfung) ist ein Verfahren zur vollautomatischen Verifikation einer Systembeschreibung (Modell) gegen eine Spezifikation (Formel). Der Begriff ist motiviert durch die mathematische Formulierung des Problems: Für …   Deutsch Wikipedia

  • Modellprüfer — Model Checking (deutsch auch Modellprüfung) ist ein Verfahren zur vollautomatischen Verifikation einer Systembeschreibung (Modell) gegen eine Spezifikation (Formel). Der Begriff ist motiviert durch die mathematische Formulierung des Problems: Für …   Deutsch Wikipedia

  • Modellprüfung — Model Checking (deutsch auch Modellprüfung) ist ein Verfahren zur vollautomatischen Verifikation einer Systembeschreibung (Modell) gegen eine Spezifikation (Formel). Der Begriff ist motiviert durch die mathematische Formulierung des Problems: Für …   Deutsch Wikipedia

  • Modellprüfverfahren — Model Checking (deutsch auch Modellprüfung) ist ein Verfahren zur vollautomatischen Verifikation einer Systembeschreibung (Modell) gegen eine Spezifikation (Formel). Der Begriff ist motiviert durch die mathematische Formulierung des Problems: Für …   Deutsch Wikipedia

  • BDD — Die Abkürzung BDD steht für: Buddhistischer Dachverband Diamantweg Bund der Deutschen Demokraten (DDD) Bundesverband Deutscher Detektive. Bundesverband Direktvertrieb Deutschland. Bundesverband der Dienstleistungsunternehmen. Body Dysmorphic… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”