Hardware Reference
In-Depth Information
auf dem Rechner kaum noch darstellbar und verarbeitbar. Die Auflistung der
Minterme für alle Einsen bzw. Nullen ist meist auch nicht signifikant kleiner,
ein ROBBD in der Regel schon.
2.3.2 Zweistellige Operationen mit ROBDDs
Ein ROBDD kann nicht nur aus der Wertetabelle, sondern auch aus einem lo-
gischen Ausdruck berechnet werden. Die Grundlage hierfür bildet der folgende
Entwicklungssatz:
• Für zwei beliebige Teilbäume, bei denen im obersten Knoten dieselbe Va-
riable ausgewertet wird, kann die Operation eine Entscheidungsebene tiefer
verschoben werden (Abb. 2.58 a).
• Fehlende Entscheidungsknoten sind wie Entscheidungsknoten mit gleichen
Nachfolgern zu behandeln (Abb. 2.58 b).
x
i
x
i
x
i
0
1
10
0 1
⋄
⋄ ⋄
Υ
1
Υ
2
Υ
1
Υ
3
Υ
4
Υ
3
Υ
4
Υ
2
a)
x
i
x
i
x
i
0
1
0
1
0 1
⋄
⋄
⋄
Υ
1
Υ
2
Υ
3
Υ
1
Υ
2
Υ
3
Υ
3
b)
beliebigezweistelligebin¨areOperation
⋄
Abb. 2.58. Entwicklungssatz für die Verknüpfung zweier ROBDDs mit einer zwei-
stelligen binären Operation a) Verschiebung der Operation eine Entscheidungsebene
tiefer b) Einfügen eines gelöschten Entscheidungsknotens, um den Entwicklungssatz
anwenden zu können
In Abb. 2.59 wird das ROBDD für den Ausdruck x
1
_x
0
entwickelt. Die Ab-
fragereihenfolge sei x
0
-x
1
. Zur Anwendung des Entwicklungssatzes muss in
der ROBDD-Darstellung der Variablen x
1
der eliminierbare Entscheidungs-
knoten für x
0
ergänzt werden. Auf der Ebene tiefer wird jeweils eine Konstan-
te mit einem Teilbaum ODER-verknüpft. Eine ODER-Verknüpfung mit »0«
hat keinen Einfluss auf das Ergebnis und damit auf den Teilbaum und eine
ODER-Verknüpfung mit »1« ist »1«.
In Abb. 2.60 wird das ROBDD für den Ausdruck x
1
_x
0
weiter mit dem
ROBDD für den Ausdruck x
2
UND-verknüpft. Die Abfragereihenfolge des ge-
samten ROBDDs sei x
0
-x
1
-x
2
. In dem ROBDD für x
2
müssen gedanklich die
gelöschten Knoten für die Abfrage von x
0
und x
1
ergänzt werden bzw. die
Operation kann gleich zwei Entscheidungsebenen tiefer verlagert werden. In
