Hardware Reference
In-Depth Information
die sich nur in einer Invertierung unterscheiden, basiert:
n
:::K
100
; K
101
; :::
o
n
o
)
:::; K
10 -
; :::
Im Vergleich zur Minimierung mit KV-Diagrammen ist dieses Verfahren auch
für Ausdrücke mit weit mehr als vier binären Eingabevariablen geeignet.
Ausgangspunkt ist eine Liste der Minterme, für die der Funktionswert »1«,
bzw. bei einer Entwicklung nach den Nullen, für die er »0« ist. Die Berechnung
teilt sich in zwei Teile. Zuerst werden mit Hilfe der sog. Quine'schen Tabellen
die Primterme bestimmt. Das sind minimierte Konjunktionen, die von keiner
Konjunktion mit einer größeren Anzahl von Don't-Care-Stellen vollständig
abgedeckt werden. Im zweiten Teil wird aus allen gefundenen Primtermen
eine minimierte Teilmenge ausgewählt, die alle Minterme abdeckt.
Zur Bestimmung der Primterme wird zuerst die Quine'sche Tabelle nullter
Ordnung aufgestellt. Das ist eine Tabelle mit allen Mintermen, in der die-
se aufsteigend nach der Anzahl der Einsen im Konjunktionsindex einsortiert
sind (Abb. 2.47). Die Konjunktionsnummern vor den Tabellenzeilen in der
Abbildung sind die Dezimalwerte der Konjunktionsindizes in der Tabelle. In
dieser Tabelle wird für alle Konjunktionspaare, deren Anzahl von Einsen sich
um eins unterscheidet, getestet, ob sie zu einer Konjunktion mit einer Don't-
Care-Stelle zusammengefasst werden können. Falls das möglich ist, werden
die resultierenden Konjunktionen mit der Don't-Care-Stelle nach der Anzahl
der Einsen in die Quine'sche Tabelle erster Ordnung einsortiert und die abge-
deckten Konjunktionen in der Quine'sche Tabelle nullter Ordnung abgehakt.
Mit der vollständigen Quine'schen Tabelle erster und später allgemein n-ter
Ordnung wird genauso verfahren, um jeweils die Quine'sche Tabelle n + 1-ter
VisualisierungderBlock-
bildungsm¨oglichkeiten
miteinemKV-Diagramm
Quine'scheTabelle
Quine'scheTabellen
nullterOrdnung
ersterundzweiterOrdnung
x
3
x
0
x
2
x
1
x
3
x
0
x
2
x
1
x
2
√
√
2 0
0
8 1000
3 11
0
1
2,3
00 -
1
P
2
P
3
1
0
1
3
2
4
5
7
6
12
13
8
9
2,10 - 0
0
1
√
√
8,10
10 0
-
7
0
5 1 1
0
√
√
6
8,121 00
-
x
0
0
10 1 10 0
12 1100
7 111
0
5
√
15
11
3,7
0-
11
P
6
P
5
P
4
4
x
1
√
2
5,7
0 -
1 1
14
10
3
3
√
5,13
- 0
1 1
0
13 11 1
1
√
√
10,14
1 10
-
x
3
0
14 1110
√
12,13
110-
P
7
√
m¨oglicheZweierbl¨ocke
12,14
11 0
-
i
i
m¨oglicherVierererblock
iPrimtermnummer
Mintermnummer
x
3
x
0
x
2
x
1
P
i
Primterm
8,10,12,14
1- 0
-
P
1
√
Konjunktionabgedeckt
Abb. 2.47. Berechnung der Quine'schen Tabellen
