Technische Informatik II
(für Bachelor)
Vorlesung 3: Kombinatorische Schaltungen
21.04.2008 , v16
Themen:
1.
2.
Beschreibung kombinatorischer Logik
Minimierung von Schaltfunktionen
Quellen:
Zum Teil aus den Unterlagen „Digitale Systeme“, Prof. Schimmler, Prof. Loogen
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
Seite 1
Schaltnetze
Definition:
Ein Schaltnetz ist eine technische Realisierung einer
Boole‘schen Funktion. Schaltnetze können durch
Zusammenschalten von Gattern und Leitungen aufgebaut
werden.
Schaltnetz mit einem Ausgang:
x1
x2
.
.
Schaltfunktion
.
.
y
y = f(X)
xn
Anz. Funktionen = 2
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
2n
Seite 2
Schaltfunktion
Eingangswerte
Ausgangswerte
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
Seite 3
Schaltfunktionen
m
n
x
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
f(X)
f
Seite 4
Beispiel des Schaltnetzes:
x0
x1
≠
&
x2
&
x3
1
IDA, Technische Universität Braunschweig
≥1
Technische Informatik II (INF 1211)
y0
Seite 5
Logische Funktionen von einer Variablen
1
1
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
Seite 6
Logische Funktionen von zwei Variablen(1)
Anz. Funktionen = 2
22
=16
f
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
Seite 7
Logische Funktionen von zwei Variablen(2)
Anz. Funktionen = 2
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
22
=16
Seite 8
Verbreiteten Funktionen bis zwei Variablen
grafische Darstellung der
verschalteten Logik
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
Seite 9
Rechengesetze der Schaltalgebra
Grafische Darstellung der
verschalteten Logik
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
Seite 10
Rechengesetze der Schaltalgebra
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
Seite 11
Definition:
Ein Produktterm ist eine UND-Verknüpfung von
Eingabevariablen, wobei jede Eingabevariable
höchstens einmal in invertierter oder in nichtinvertierter Form vorkommen kann.
Beispiele für Produktterme:
x 0  x1  x 2
x0
x0  x2  x3
x4 x2
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
Seite 12
Definition:
Eine Boole‘sche Funktion ist in Disjunktiver
Normalform (DNF), wenn sie aus einer ODERVerknüpfung von Produkttermen besteht.
(Sum Of Products: SOP)
Beispiele für Funktionen in DNF:
( x 0  x1  x 2 )  ( x 0  x1  x 2 )  ( x 0  x1  x 2 )
x0
x0  x2  x0
x 4 x 2  x1  x 3 x 2  x 0 x 4
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
Seite 13
Definition:
Ein Minterm (Vollkonjunktion, minimaler Produktterm)
ist ein Produktterm, bei dem alle Eingabevariablen
entweder in invertierter oder in nicht-invertierter Form
vorkommen. Ein Minterm entspricht einer Zeile in der
Wertetabelle der Funktion.
Beispiele für Minterme:
x 0  x1  x 2
( x0 x1 x2 sind alle Eingangsvariablen)
x0
( x0 ist die einzige Eingangsvariable)
x0  x2
hingegen ist kein Minterm, wenn es auch noch
eine Eingabevariable x1 gibt.
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
Seite 14
Definition:
Die Kanonische Disjunktive Normalform (KDNF)
einer Boole‘schen Funktion ist eine ODERVerknüpfung aller Minterme, für die die Funktion
den Wert 1 annimmt.
Beispiele für Funktionen in KDNF:
( x 0  x1  x 2 )  ( x 0  x1  x 2 )  ( x 0  x1  x 2 )
x0
Die folgende Funktion ist nicht in KDNF;
( x 0  x1  x 2 )  ( x 0  x 2 )  ( x 0  x1  x 2 )
im zweiten Produktterm taucht das x1 nicht auf, daher ist es kein Minterm.
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
Seite 15
Beispiel einer Wertetabelle einer Funktion y1:
x0
0
1
0
1
0
1
0
1
y1 =
x1
0
0
1
1
0
0
1
1
x2
0
0
0
0
1
1
1
1
x 0 x 1 x 2 + x 0 x1 x 2
IDA, Technische Universität Braunschweig
y1
0
0
0
1
0
1
1
1
Minterm
x 0 x1 x 2
x 0 x1 x 2
x 0 x1 x 2
x 0 x1 x 2
x 0 x1 x 2
x 0 x1 x 2
x 0 x1 x 2
x 0 x1 x 2
+ x 0 x 1 x 2 + x 0 x1 x 2
Technische Informatik II (INF 1211)
Seite 16
Beispiel des Schaltbildes einer Funktion in KDNF:
y1 =
x1
x0
1
x 0 x 1 x 2 + x 0 x1 x 2
+ x 0 x 1 x 2 + x 0 x1 x 2
x2
1
1
&
&
≥1
y1
&
&
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
Seite 17
Definition:
Ein Summenterm ist eine ODER-Verknüpfung
von Eingabevariablen, wobei jede
Eingabevariable höchstens einmal in invertierter
oder in nicht-invertierter Form vorkommen kann.
Beispiele für Summenterme:
x 0  x1  x 2
x0
x0  x2
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
Seite 18
Definition:
Eine Boole‘sche Funktion ist in Konjunktiver
Normalform (KNF), wenn sie aus einer UNDVerknüpfung von Summentermen besteht.
(Product Of Sums: POS )
Beispiele für Funktionen in KNF:
( x 0  x1  x 2 )  ( x 0  x1  x 2 )  ( x 0  x1  x 2 )
x0
x0  ( x2  x0 )
( x 4  x 2 ) x1 ( x 3  x 2 )( x 0  x 4 )
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
Seite 19
Definition:
Ein Maxterm (Volldisjunktion) ist ein
Summenterm, bei dem alle Eingabevariablen
entweder in invertierter oder in nicht-invertierter
Form vorkommen. Es gibt für jede Zeile i in einer
Wertetabelle der Funktion einen Maxterm, der
der Menge aller Zeilen außer seiner Zeile i
entspricht.
Beispiele für Maxterme:
x 0  x1  x 2
x0
x0  x2
hingegen ist kein Maxterm, wenn es auch
noch eine Eingabevariable x1 gibt.
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
Seite 20
Definition:
Die Kanonische Konjunktive Normalform (KKNF)
einer Boole‘schen Funktion ist eine UND-Verknüpfung
aller Maxterme, für deren Zeile die Funktion den Wert
0 annimmt.
Beispiele für Funktionen in KKNF:
( x 0  x1  x 2 )  ( x 0  x1  x 2 )  ( x 0  x1  x 2 )
x0
Die folgende Funktion ist nicht in KKNF;
x 0  ( x 0  x1  x 2 )
im ersten Summenterm tauchen x1 und x2 nicht auf, daher ist es
kein Maxterm.
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
Seite 21
Beispiel einer Wertetabelle einer Funktion:
x0
0
1
0
1
0
1
0
1
x1
0
0
1
1
0
0
1
1
y1 =
x0 x1 x2
y1 =
x 0  x1  x 2
x2
0
0
0
0
1
1
1
1
y1
0
0
0
1
0
1
1
1
Maxterm
x 0  x1  x 2
x 0  x1  x 2
x 0  x1  x 2
x 0  x1  x 2
x 0  x1  x 2
x 0  x1  x 2
x 0  x1  x 2
x 0  x1  x 2
+ x0 x1 x2
+ x0 x1 x2
.
.
IDA, Technische Universität Braunschweig
x 0  x1  x 2
Einzelvariablen
werden invertiert
im Maxterme!
x 0  x1  x 2
Technische Informatik II (INF 1211)
+ x0 x1 x2
.
x 0  x1  x 2
Seite 22
Beispiel des Schaltbildes einer Funktion in KKNF:
y1 =
x 0  x1  x 2
.
x1
x2
x0
1
1
x 0  x1  x 2
.
x 0  x1  x 2
.
x 0  x1  x 2
1
≥1
≥1
≥1
&
y1
≥1
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
Seite 23
Beispiel einer Funktion im Auto:
Zündung:
Z=1 : Zündung an
Hitze:
H=1 : Temperatur>95o
Pegel:
P=1 : ausreichend Wasser
Ausgangsfunktion Warnleuchte W
Z
0
0
0
0
1
1
1
1
H
0
0
1
1
0
0
1
1
IDA, Technische Universität Braunschweig
P
0
1
0
1
0
1
0
1
W
0
0
0
0
1
0
1
1
Minterm
Technische Informatik II (INF 1211)
ZHP
ZH P
ZHP
Seite 24
Warnleuchten-Funktion in KDNF:
H
Z
1
W  Z H P  ZH P  ZHP
P
1
1
&
&
≥1
W
&
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
Seite 25
Minimierung durch Hilfe der Schaltalgebra
W  Z H P  ZH P  ZHP
 Z H P  ZH P  ZH P  ZHP
 Z P H  Z P H  ZH P  ZHP
 ( Z P  H  Z P  H )  ( ZH  P  ZH  P )
 Z P ( H  H )  ZH ( P  P )
 Z P (1)  ZH (1)
 Z P  ZH
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
Seite 26
Warnleuchten-Funktion in DMF:
Z
H
P
W  Z P  ZH
1
&
≥1
W
&
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
Seite 27
Hintergrund der logischen Minimierung
„ Unit Distance Code“
Schlüsseloperation:
A (B + B)
AB +AB
A
Beispiel: Darstellung der Funktion f (x1, x2) =  m(1, 2, 3)
x1 x 2  x1 x 2
f  x1  x 2
 x 2 ( x1  x1 )  x 2
1
2
3
x1 x2
f
0
0
1
1
0
1
1
1
0
1
0
1
Brawn Figure 4.33. Ref. Brown
IDA, Technische Universität Braunschweig
01
-1
11
x1 x 2  x1 x 2
 x1 ( x 2  x 2 )  x1
x2
1x1
00
Technische Informatik II (INF 1211)
10
Die Stelle des
Bitwechsels
wird gekürzt
Seite 28
Hintergrund „ Unit Distance Code“
Darstellung der 3-Variablen Funktion f (x1, x2, x3) =  m(0, 2, 4, 5, 6)
(2)
(6)
--0
(5)
10(0)
(4)
f (x1, x2, x3) = x3 + x1 x2
Ref.: Brawn Figure 4.33.
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
Seite 29
Hintergrund „ Unit Distance Code“
Darstellung der 4-Variablen Funktion f (x1, x2, x3 , x4)
f (x1, x2, x3 , x4) = x2 x4 + x1 x3 + x2 x3 x4
Brawn Figure 4.33.
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
Seite 30
Karnaugh-Vieth KV-Diagramm:
• Rechteckiges Schema
• bei n Eingabevariablen 2n innere Felder.
• Ränder so beschriften, dass jede Variable
genau die Hälfte des Diagramms abdeckt.
• Jede Variable deckt genau den halben
Bereich jeder anderen Variablen ab.
• Jeder Minterm ist eindeutig durch ein inneres
Feld repräsentiert.
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
Seite 31
Karnaugh-Veith KV-Diagramm:
Beispiele:
b
Unit-Distance Kodierung
für benachbarte Felder!
b
Gray Code Zähler:
00 → 01 →11 →10
(Nur ein Bit wechselt!)
a ab a b
a
ab a b
b
Für Funktionen
mit 2 Variablen
a
a bc
abc
ab c
a bc
abc
abc
c
Für Funktionen
mit 3 Variablen
ab c d abc d a bc d a b c d
ab c d abcd
ab c abc
a bcd a b c d
d
a b c d abcd a bcd a b c d
ab c d abc d a bc d a b c d
Minimierungsregel
c
xy  x y  x
Für Funktionen
mit 4 Variablen
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
Seite 32
Beispiele:
B
CA
A
A
A
1
B
1
BA
1
1
1
1
1
C
ABC
2 Variablen
A
3 Variablen
B
CB
AB
1
1
1
1
1 1
1 1
1
1 1
C
A
D
CB
DB
B
CB
CD
4 Variablen
IDA, Technische Universität Braunschweig
BC
AB
1
1
1
1
1 1
1 1
1
1 1
D
CB
C
4 Variablen-Alternativ
Technische Informatik II (INF 1211)
Seite 33
Beispiel für ein KV-Diagramm mit 3 Variablen
xy  x y  x
Beispiel: Warnleuchte:
Z
0
0
0
0
1
1
1
1
H
0
0
1
1
0
0
1
1
P
0
1
0
1
0
1
0
1
IDA, Technische Universität Braunschweig
W
0
0
0
0
1
0
1
1
ZPH+ZPH = ZH
ZPH+ZPH= ZP
P
Z
0
1
1
1
0
0
0
0
Technische Informatik II (INF 1211)
H
W  Z P  ZH
Seite 34
Zusammenfassung:
Die Einsen im KV-Diagramm werden zu Blöcken maximaler Größe
zusammengefasst. Dabei müssen die Blöcke immer im Raster der
Zweierpotenzen beginnen und enden. Eine Zusammenfassung von zwei Blöcken
zu einem Block doppelter Größe entspricht einer Anwendung der
Vereinfachungsregel: Wenn ein Block (x0x1) und ein zweiter Block (x0x1) beide
nur aus Einsen bestehen, liegen diese beiden Blöcke im KV-Diagramm
nebeneinander und können zu einem doppelt so großen Block x0
zusammengefasst werden. Die gegenüberliegenden Ränder eines KVDiagramms sind zu identifizieren. Man kann sich das Diagramm als Torus
vorstellen.
Wenn mehr als 4 Eingabevariablen vorliegen, muss ein 2-dimensionales KVDiagramm so dargestellt werden, dass einzelne Variablen Bereiche überdecken,
die nicht zusammenhängend in der Ebene sind. Dabei sind aber die zueinander
zeigenden Ränder dieser Bereiche als identisch anzusehen.
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
Seite 35
Einträge in KV-Diagrammen können Nullen und Einsen sein. In diesem Fall kann
man durch Zusammenfassen aller Einsen zu maximalen Blöcken eine DMF
ablesen. (Leider ist sie nicht eindeutig). In solchen Fällen schreibt man meist nur
die Einsen in das Diagramm und lässt die Nullen weg. Zusammenfassen der
Nullen und benutzen der Komplemente der Variablen führt zur KMF.
Wenn einzelne Elemente in der Wertetabelle don‘t cares sind, können diese in
den Blöcken der Einsen bei der DMF (oder Nullen bei der KMF) mit auftauchen.
Sie schaden nichts. Aber es müssen durchaus nicht alle don‘t cares (dargestellt
durch den Buchstaben X oder d) mit in Blöcke aufgenommen werden.
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
Seite 36
n1
Beispiel: 2-Bit Multiplizierer:
n1
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
n0
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
m1 m0
0 0
0 1
1 0
1 1
0 0
0 1
1 0
1 1
0 0
0 1
1 0
1 1
0 0
0 1
1 0
1 1
p3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
IDA, Technische Universität Braunschweig
p2
0
0
0
0
0
0
0
0
0
0
1
1
0
0
1
0
p1
0
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
p0
0
0
0
0
0
1
0
1
0
0
0
0
0
1
0
1
Technische Informatik II (INF 1211)
n0
p0
1 1 1 1
n1
n0
m1
1 1
1 1
1 1
n1 m1
n0
m0
1
1
1
m1
p1
m0
p2
m0
Seite 37
n1
p0
n0
1 1 1 1 m0
p0  n0  m 0
m1
n1
p1
n0
1 1
1 1
1 1
m0
p 1  n 0  m 0  m 1  n 0  n1  m 0  n1  m 0  m 1  n 0  n1  m 1
m1
n1
p2
n0
1
1
1
m1
IDA, Technische Universität Braunschweig
p 2  n 0  n1  m 1  n1  m 0  m 1
m0
p3
p 3  n 0  n1  m 0  m1
Technische Informatik II (INF 1211)
Seite 38
m1
m0
1
2-Bit-Multiplizierer
n0
n1
1
1
1
p0
&
&
&
&
≥1
p1
≥1
p2
&
&
&
&
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
p3
Seite 39
Don’t Care Behandlung
Don’t Care
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
Seite 40
4-Bit Codewandler: Dezimal -> Aiken
x3
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
x2
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
x1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
x0
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
IDA, Technische Universität Braunschweig
y3
0
0
0
0
0
1
1
1
1
1
X
X
X
X
X
X
y2
0
0
0
0
1
0
1
1
1
1
X
X
X
X
X
X
y1
0
0
1
1
0
1
0
0
1
1
X
X
X
X
X
X
y0
0
1
0
1
0
1
0
1
0
1
X
X
X
X
X
X
Technische Informatik II (INF 1211)
Don’t Care
Seite 41
KV Minimierung für Disjunktive Minimalform DMF:
Zusammenfassung
1. Aufstellen der Wertetabelle
2. Eintragen der Terme „mit 1“ in KV-Diagramm
3. Zusammenfassen von benachbarten Einsen zu
Blöcken maximaler Größe
4. Ablesen der DMF
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
Seite 42
KV Minimierung für konjunktive Minimalform KMF:
Zusammenfassung:
1. Aufstellen der Wertetabelle
2. Eintragen der Werte „mit 0“ in KV-Diagramm
3. Zusammenfassen von benachbarten Nullen zu
Blöcken maximaler Größe
4. Ablesen der KMF, indem die Summenterme
gebildet werden, die diese Blöcke von Nullen
nicht abdecken. Zu diesem Zweck oder‘t man
die invertierten Eingabevariablen, die diese
Blöcke von Nullen überdecken.
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
Seite 43
KV-Diagramme mit mehr als 4 Variablen
(sehr Arbeitsaufwendig)
x2
x3
x3
x4
x5
x0
x0
x2
x1
x5
x1
x1
x4
5 - Variablen
IDA, Technische Universität Braunschweig
x4
6 - Variablen
Technische Informatik II (INF 1211)
Seite 44
Das Verfahren von Quine und McCluskey
(Rechnergestützte Verfahren)
Mit KV-Diagrammen kommen wir nicht weiter, wenn die Anzahl der
Eingabevariablen größer als 6 wird. In diesem Fall empfiehlt sich das Verfahren
von Quine und McCluskey. Es beginnt mit der KDMF und besteht aus zwei
Schritten:
Erstens: Das Verfahren von McCluskey erzeugt durch systematische Anwendung
der Vereinfachungsregeln alle Primterme einer Funktion.
Zweitens: Das Verfahren von Quine wählt aus dieser Menge aller Primterme eine
minimale Teilmenge aus, deren Oder-Verknüpfung die gesamte Funktion
repräsentiert.
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
Seite 45
Das Verfahren von Quine und McCluskey
1. McCluskey:
Systematische Anwendung der Regel
xy  x y  x
Konstruktion aller Primterme
Edward J. McCluskey
Stanford University
Computer Science
2. Quine
Treffen einer minimalen Auswahl von Primtermen,
deren Disjunktion die Funktion realisiert.
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
Seite 46
Einleitendes Beispiel
1
2
3
4
5
6
f  abcd  a b cd  a bcd  abc d  a b cd  a bc d
1,2
1,3
1,4
2,5
3,5
3,6
4,6
acd  bcd  abc  b cd  a cd  a bc  bc d
A
B
C
D
E
F
G
A,E
B,D
B,G C,F
cd  cd  bc  bc
IDA, Technische Universität Braunschweig
 cd  bc
Technische Informatik II (INF 1211)
Seite 47
Das Verfahren von McCluskey
Begonnen wird mit der Funktion in DNF
1. Für jedes Paar von Produkttermen wird geprüft, ob
die Regel
xy  x y  x
anwendbar ist. Wenn ja, wird in der nächsten Zeile
der Produktterm x aufgenommen. Alle Terme, die
nicht zu einem solchen Produktterm beigetragen
haben, werden unverändert in die nächste Zeile
übernommen.
2. Wenn keine neuen Produktterme in der neuen Zeile
entstehen, ist man fertig. Sonst wird bei 1.
weitergemacht. Am Ende stehen in der letzten Zeile
alle Primterme.
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
Seite 48
Zweites Beispiel
I
II
III
IV
f  ab c  abc  a bc  a b c
I,II
II,III
III,IV
ab  bc  a c
3 Primterme sind generiert
bc ist ein redundanter Term, wie man am KV-Diagramm
leicht sehen kann. Daher benötigen wir das Verfahren von
Quine.
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
Seite 49
Das Verfahren von Quine
Eine Primterm-Minterm-Tabelle wird aufgestellt: Die
Minterme in der Zeile und die Primterme in der
Spalte.
1. Alle Spalten, in denen eine 1 aus einer dominanten
Zeile (Zeile mit nur einer 1) steht, werden markiert.
Alle Zeilen, in denen 1en aus markierten Spalten
stehen, werden gestrichen.
2. Wenn keine ungestrichene Zeile mehr vorhanden ist,
wird das Verfahren beendet. Die markierten Spalten
bilden die Minterme der DMF.
3. Wenn keine dominante Zeile mehr vorhanden ist,
aber noch ungestrichene Zeilen existieren, wird eine
beliebige Spalte markiert und bei 1. fortgefahren.
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
Seite 50
Quine Verfahren, minimaler Abdeckung
1. Primterme horizontal, Minterme vertikal einsetzen
2. 1 setzen für alle Minterme die einen Primterm enthalten
Minterme
ab
ab c
1
abc
1
a bc
bc
ac
Primterme
1
1
ab c
1
1
bc ist nicht nötig da die Primterme ab, ac alle Minterme abdecken!
Also f =( ab + ac ) ist die Minimale Implementierung
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
Seite 51
Beispiel zum Verfahren von Quine McCluskey
10 beteiligte Minterme in Gruppen sortiert
nach Anz. von Einsen (Gewicht) (oder
Nullen) inklusive den „don‘t cares“ (-)
Gewicht=0
Gewicht=1
Gewicht=2
Gewicht=3
Gewicht=4
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
Seite 52
Primterme generieren
Jede Gruppe mit der folgenden Gruppe testen!
Primterme
Alle nicht markierte Terme
werden als Primterme
für die weitere Bearbeitung
ausgewählt!
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
Seite 53
Primimplikanten-Tabelle und minimale Funktionsauswahl
Nur Minterme mit 1 (nur 6)
Primterme
x 3 x 2 x1
x 3 x1 x 0
y 
x 3 x1 x 0

x2 x0

x
3
x1
Eine andere Lösung ist auch möglich!
IDA, Technische Universität Braunschweig
Technische Informatik II (INF 1211)
Seite 54

Logicfunctions_Minimization