Hardware Reference
In-Depth Information
Aufgabe 2.12
Gegeben ist die Menge der Minterme einer sechsstelligen logischen Funktion:
K 2f100000; 100100; 101010; 101110; 111110; 110000;
011000; 101011; 101111; 101000; 101001g
für die der Funktionswert »1« sein soll. Bestimmen Sie mit Hilfe des Verfahrens
von Quine und McCluskey einen minimierten logischen Ausdruck.
2.3 Binäre Entscheidungsdiagramme
Ein binäres Entscheidungsdiagramm (BDD -
iagram) setzt
eine logische Funktion aus binären Entscheidungen zusammen. Die Definition
ist rekursiv. Das Ergebnis einer Entscheidung ist entweder konstant (»0« oder
»1«) oder eine durch eine binäre Variable getroffene Entscheidung zwischen
zwei Alternativen. Beide Alternativen sind die Ergebnisse zuvor getroffener
Entscheidungen. Alle Entscheidungen zusammen bilden ein binäres Entschei-
dungsdiagramm mit konstanten Werten als Blätter und dem Entscheidungs-
ergebnis als Wurzel (Abb. 2.52).
b
inary
d
ecision
d
bin¨areEntscheidung
Entscheidunganhand
einerbin¨arenVariablen
Konstante
0
1
x
i
0 1
Abb. 2.52. Definition eines binären Entscheidungsdiagramms
Zur Bestimmung der Wertetabelle aus einem Entscheidungsdiagramm wer-
den nacheinander alle Kanten des Graphen durchlaufen. Die Kantenbeschrif-
tungen bilden die abhängigen Größen. Der Funktionswert ist die Blattkon-
stante, die über die Kantenfolge erreicht wird (Abb. 2.53).
x
1
x
0
y
x
0
x
1
x
1
0
1
00
01
0
0
1
1
0
0
0 1 1 0
1 1
0
1
11
Abb. 2.53. Wertetabelle und binäres Entscheidungsdiagramm
