Binary Decision Diagram

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 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 &amp;amp;lt; x_3 &amp;amp;lt; \dots &amp;amp;lt; x_{2n-1} &amp;amp;lt; x_2 &amp;amp;lt; x_4 &amp;amp;lt; \dots &amp;amp;lt; x_{2n}, so benötigt das Binäre Entscheidungsdiagramm mehr als 2n Knoten. Bei der Variablenordnung x_1 &amp;amp;lt; x_2 &amp;amp;lt; x_3 &amp;amp;lt; x_4 &amp;amp;lt; \dots &amp;amp;lt; x_{2n-1} &amp;amp;lt; 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 exponenziell 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 C++ Bibliothek, Universität Bonn.


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-5190-2149-8

Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

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

  • Binary decision diagram — In the field of computer science, a binary decision diagram (BDD) or branching program, like a negation normal form (NNF) or a propositional directed acyclic graph (PDAG), is a data structure that is used to represent a Boolean function. On a… …   Wikipedia

  • Binary moment diagram — A binary moment diagram (BMD) is a generalization of the binary decision diagram (BDD) to linear functions over domains such as booleans (like BDDs), but also to integers or to real numbers.They can deal with boolean functions with complexity… …   Wikipedia

  • Zero suppressed decision diagram — A zero suppressed decision diagram (ZSDD or ZDD) is a version of binary decision diagram (BDD) where instead of nodes being introduced when the positive and the negative part are different, they are introduced when negative part is different from …   Wikipedia

  • Decision tree learning — This article is about decision trees in machine learning. For the use of the term in decision analysis, see Decision tree. Decision tree learning, used in statistics, data mining and machine learning, uses a decision tree as a predictive model… …   Wikipedia

  • Decision tree — This article is about decision trees in decision analysis. For the use of the term in machine learning, see Decision tree learning. A decision tree is a decision support tool that uses a tree like graph or model of decisions and their possible… …   Wikipedia

  • Diagramme de decision binaire — Diagramme de décision binaire Pour les articles homonymes, voir BDD. Un diagramme de décision binaire (BDD pour Binary Decision Diagram en anglais), comme une forme normale niée ou un graphe orienté acyclique propositionnel, est une structure de… …   Wikipédia en Français

  • Diagramme de décision binaire — Pour les articles homonymes, voir BDD. Exemple de diagramme de décision binaire Un diagramme de décision binaire (BDD pour Binary Decision Diagram en anglais) est une structure de données utilisée pour repr …   Wikipédia en Français

  • Warnier/Orr diagram — A Warnier/Orr diagram (also known as a logical construction of a program/system) is a kind of hierarchical flowchart that allow the description of the organization of data and procedures. They were initially developed in France by Jean Dominique… …   Wikipedia

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

  • Список терминов, относящихся к алгоритмам и структурам данных —   Это служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавливается на информационные списки и глоссарии …   Википедия

Share the article and excerpts

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