Hardware Reference
In-Depth Information
2.3.1 Vereinfachung binärer Entscheidungsdiagramme
Ein unreduziertes binäres Entscheidungsdiagramm bildet einen Baum mit 2
n
Blättern und 2
n
1 Entscheidungen (n - Stelligkeit der Funktion). Es ist direkt
aus der Wertetabelle ablesbar (Abb. 2.54).
x
0
0 1
x
2
x
1
x
0
y
0
0
0
0
1
1
1
1
0
0
1
x
1
x
2
0
1
1
1
1
0
1
1
0
0 0
1
1
1
1
0
0
0
0
x
2
x
2
x
1
x
1
0
0
0
0 10 10 10 1
1
1
1
1 0 0 1 0 1 1 0
Abb. 2.54. Unreduziertes ungeordnetes binäres Entscheidungsdiagramm mit der
zugehörigen Wertetabelle
Zur Schaltungsminimierung ist die Anzahl der Entscheidungen zu mini-
mieren. Dafür gibt es zwei Vereinfachungsregeln:
• Verschmelzung gleicher Teilgraphen und
• Löschen von Knoten mit zwei gleichen Nachfolgern (Abb. 2.55).
x
i
x
j
x
i
x
j
0 1
10
0
1
0 1
≡
a)
Entscheidungs-
knoten
x
i
0
1
Teilbaum
b)
Abb. 2.55. Vereinfachungsregeln a) Verschmelzung gleicher Teilgraphen b) Lö-
schen von Knoten mit gleichen Nachfolgern
Die offensichtliche Optimierungsvoraussetzung ist, dass die Eingabevariablen
auf allen Entscheidungswegen in derselben Reihenfolge abgefragt werden. Das
führt auf ein geordnetes binäres Entscheidungsdiagramm (OBDD -
rdered
binary decision diagram). Abbildung 2.56 zeigt ein OBDD für die Funktion
aus Abb. 2.54 mit der Abfragereihenfolge x
0
-x
1
-x
2
.
Die Suche nach Verschmelzungsmöglichkeiten beginnt an den Blättern. Es
gibt nur die zwei Blatttypen »0« und »1«, die durch zwei Symbole ersetzt
werden (Abb. 2.57). Dann werden auf der untersten Entscheidungsebene die
o
