Hardware Reference
In-Depth Information
Knoten gleiche Nachfolger und kann eliminiert werden. Abschließend sind die
beiden Blätter mit dem Wert »0« zusammenzufassen.
2.3.3 Umsetzung von ROBDDs in minimierte Schaltungen
Zur Umsetzung eines ROBDDs in eine Schaltung werden die Entscheidungs-
knoten durch Multiplexer ersetzt. Ein Multiplexer bildet eine dreistellige logi-
sche Funktion nach, die minimiert mit einem KV-Diagramm durch folgenden
logischen Ausdruck dargestellt werden kann (Abb. 2.61):
y = x
1
s_x
2
s
(2.1)
x
1
y
a:x
1
¯s
b:x
2
s
x
1
0
0
01
11 0
1
0
1
y
a
s
x
2
s
y=x
1
¯s
∨
x
2
s
0 1
b
x
1
x
2
s
x
2
Abb. 2.61. Minimierung des logischen Ausdrucks für einen Multiplexer
Wenn die Auswahl zwischen einer Konstanten und einer Variablen erfolgt,
realisiert ein Multiplexer eine zweistellige Funktion. Je nach dem konstanten
Wert und dem Eingang, an dem er anliegt, ist das eine der nachfolgenden
UND- oder ODER-Verknüpfungen:
x
1
= 0 : y = (0 ^ s) _x
2
s = x
2
s
x
1
= 1 : y = (1 ^ s) _x
2
s = s_x
2
s = s_x
2
x
2
= 0 : y = x
1
s_ (0 ^s) = x
1
s
x
2
= 1 : y = x
1
s_ (1 ^s) = x
1
s_s = x
1
_s
Bei der Auswahl zwischen zwei unterschiedlichen konstanten Werten bildet der
Multiplexer eine einstellige Funktion nach, eine Identität oder eine Negation:
x
1
= 0; x
2
= 1 : y = (0 ^ s) _ (1 ^s) = s
x
1
= 1; x
2
= 0 : y = (1 ^ s) _ (0 ^s) = s
In dem in Abb. 2.60 entwickelten ROBDD für die Funktion (x
1
_x
0
) ^ x
2
kann der Entscheidungsknoten für x
0
durch einen Multiplexer, der Entschei-
dungsknoten für x
1
durch ein UND-Gatter und der Entscheidungsknoten für
x
2
durch einen Inverter nachgebildet werden. Der Multiplexer kann nach Glei-
chung 2.1 weiter durch eine Schaltung aus einem ODER-Gatter, zwei UND-
Gattern und einem Inverter ersetzt werden. Die resultierende Schaltung ist
wesentlich aufwändiger, als wenn der Ausdruck direkt in eine Schaltung aus
einem ODER- und einem UND-Gatter übersetzt wird (Abb. 2.62).
