Lexikon der Mathematik: binärer Entscheidungsgraph
BDD, binary decision diagram, Datenstruktur für Boolesche Funktionen.
Ein BDD über den Booleschen Variablen x1,…,xn ist ein azyklischer, zusammenhängender, gerichteter Graph G = (V, E), dem eine Abbildung index : V → {x1,…,xn} 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) ∈ {xl,…,xn} 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 {xl,…,xn} definiert ist, beschreibt die Boolesche Funktion fw : {0, l}n → {0,1}, definiert durch:
- Ist w ein Blatt und index(w) = 0, so ist fw die konstante Abbildung 0 : {0, l}n → {0,1} mit 0(α) = 0 für alle \(\alpha \in {\{\bar{0},1\}}^{n}\)
- Ist w ein Blatt und index(w) = 1, so ist fw die konstante Abbildung 1 : {0, l}n → {0,1} mit 1(α) = 1 für alle \(\alpha \in {\{\bar{0},1\}}^{n}\)
- Ist w ein innerer Knoten und index(w) = xi, 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 fw“ und „fw 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.
Binärer Entscheidungsgraph der Booleschen Funktion \({X}_{2}\vee ({X}_{1}\wedge \bar{{X}_{2}}\wedge {X}_{3}\wedge {X}_{4})\). Die low-Kanten sind durch gestrichelte Linien, die high-Kanten durch durchgezogene Linien gekennzeichnet.
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 a0 und a1 ersetzt. Der Dateneingang a0 wird verbunden mit dem Ausgang des zu dem low-Nachfolger-knoten von v gehörigen Multiplexers, der Dateneingang a1 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 xiverbunden, wenn xi = 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.
Schreiben Sie uns!