Hardware Reference
In-Depth Information
Abfragereihenfolge:x
0
-x
1
-x
2
Abfragereihenfolge:x
2
-x
1
-x
0
y
y
y
≥
1
x
0
x
0
x
2
&
01
0
0
1
1
&
&
x
1
&
x
1
≥
1
1
0
1
x
2
&
0
x
1
x
2
x
0
x
0
x
0
1
0
1
0
x
1
0 1
0 1
x
1
x
2
x
2
Abb. 2.62. Schaltungsnachbildung der ROBDDs für den Ausdruck x
2
(x
1
_x
0
)
Mit der Abfragereihenfolge x
2
-x
1
-x
0
entsteht ein anderes ROBDD, in dem
der erste Abfrageknoten durch ein UND-Gatter mit einem invertierten Ein-
gang und der zweite durch ein ODER-Gatter nachzubilden sind. Das Ergeb-
nis ist dieselbe Schaltung, die sich auch aus dem Ausdruck ablesen lässt. Zur
Schaltungsoptimierung mit ROBDDs sind offensichtlich mehrere Abfragerei-
henfolgen durchzuprobieren.
2.3.4 Zusammenfassung und Übungsaufgaben
Ein binäres Entscheidungsdiagramm beschreibt eine logische Funktion durch
binäre Entscheidungen. Zur Anwendung der beiden Vereinfachungsregeln -
Verschmelzung und Knotenelimination - muss der Entscheidungsfluss geord-
net sein. Das bedeutet, die Eingabevariablen müssen auf allen Entscheidungs-
wegen in derselben Reihenfolge abgefragt werden. Ein reduziertes geordnetes
binäres Entscheidungsdiagramm (ROBDD) mit einer vorgegebenen Abfrage-
reihenfolge ist eine Normalform, d.h. eine eindeutige Darstellung einer logi-
schen Funktion und geeignet für den Test zweier Funktionen auf Gleichheit.
Die Verknüpfung logischer Funktionen, die durch ROBDDs dargestellt sind,
erfolgt mit Hilfe des Entwicklungssatzes. Dieser besagt, dass eine zweistellige
Operation zweier ROBBDs rekursiv eine Entscheidungsebene tiefer verschoben
werden darf.
Schaltungstechnisch werden Entscheidungsknoten durch Multiplexer nach-
gebildet. Multiplexer mit konstanten Eingabewerten vereinfachen sich zu
UND- oder ODER-Gattern mit zwei Eingabevariablen, einem Inverter oder
einer Identität mit einer Eingabevariablen oder einer Konstanten. Weiterfüh-
rende und ergänzende Literatur siehe [10, 15, 19, 24, 34].
