Upload
duongtu
View
216
Download
2
Embed Size (px)
Citation preview
1
7. Vorlesung: KV-Diagramm
• Wiederholung– Minimalformen– KV-Diagramme
• KV-Diagramm (4 Variablen)• Don‘t Cares• Übung
2
Maxterm (Volldisjunktion)
• Ein Maxterm ist eine Disjunktion, die alle Eingangsvariablen, nicht negiert oder negiert, enthält.
• Für eine Boolesche Funktion mit n Eingangsvariablen existieren daher genau 2n Maxterme.
• Für exakt eine Kombination der Zustände der Eingangsvariablen nimmt ein Maxterm den Zustand falsch bzw. 0 an. Für alle anderen Kombinationen liefert der Maxterm 1.
3
Maxterme für zwei Eingänge1 2 0 1 2 3
0 0 1 1 10 1 1 1 11 0 1 1
00
0 11 01 1 1 1
X X M M M M
1 2 0 1 2 3
1 2 1 2 1 2 1 2
00
0
0 0 1 1 10 1 1 1 11 0 1 1 11 1 1 01 1
X X M M M M
X X X X X X X X∨ ∨ ∨ ∨
Bitte notieren Siedie algebraischeDarstellung für allevier Maxterme.
4
KV-Diagramm
• M. Karnaugh (1952) und E.W. Veitch (1953) entwickelten Verfahren zur graphischen Minimierung.
• Die Kombination beider Verfahren ist als Karnaugh-Veitch-Diagramm bekannt, das meist abgekürzt als KV-Diagramm bezeichnet wird.
• Bei diesem Verfahren können Minterme oder Maxterme zusammengefasst werden.
5
Konstruktion KV-Diagramm
0
1
2
3
0 00 11 01 1
B A YFFFF
0 1
2 3
F FF F
Y
00 0110 11
Y0 1
2 3
F FF F
Y A
B
7
Vereinfachungen für 2 Variablen1 2 3 4 5
0 0 0 1 1 0 10 1 0 1 0 1 11 0 1 0 1 0 11 1 1 0 0 1 1
B A Y Y Y Y Y
1 11 1
5Y A
B
0 01 1
1Y A
B1 10 0
2Y A
B
1 01 0
3Y A
B0 10 1
4Y A
B
1Y B= 2Y B=
3Y A= 4Y A=5 1Y =
8
Übung
0 0 10 1 01 0 11 1 1
B A Y
1 01 1
Y A
B
( ) ( ) ( )B A B A B A∧ ∨ ∧ ∨ ∧ ( ) (( ( ))= ∧ ∨ ∧ ∨B A B A A
( )B A B= ∧ ∨
A B= ∨
A B∨
DMF
( ) ( )= ∨ ∧ ∨B B A B
10
KV-Diagramm für 3 Eingangsvariablen
0
1
2
3
4
5
6
7
0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1
C B A YFFFFFFFF
Spiegelachse
0 1 5 4
2 3 7 6
F F F FF F F F
A
B
C
11
Torus-Topologie
Die Nachbarschaft von Feldern im KV-Diagramm basiert auf der Torus-Topologie.Dies bedeutet, dass Felder in der unterstenReihe Nachbarn der Felder in der oberstenReihe sind. Gleiches gilt für die Felder derrechten und linken Seite.
13
Übung: DMF
0 1 5 4
2 3 7 6
F F F FF F F F
A
B
C
DNF = m1+m3+m5
DMF?
0 1 1 00 1 0 0
A
B
C
( ) ( )A B A C∧ ∨ ∧
( )A B C= ∧ ∨
15
KV-Diagramm für 4 Eingangsvariablen
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0 0 0 00 0 0 10 0 1 00 0 1 10 1 0 00 1 0 10 1 1 00 1 1 11 0 0 01 0 0 11 0 1 01 0 1 11 1 0 01 1 0 11 1 1 01 1 1 1
D C B A YFFFFFFFFFFFFFFFF
0 1 5 4
2 3 7 6
10 11 15 14
8 9 13 12
F F F FF F F FF F F FF F F F
A
B
C
D
16
Don‘t Care
• Häufig ist eine Boolesche Funktion nicht für alle möglichen Kombinationen der Wertigkeit der Eingangsvariablen definiert.
• Die nicht definierten Kombinationen können beliebig realisiert werden und werden daher als Don‘t Carebezeichnet.
• Die Don‘t Care Kombinationen werden so festgelegt, dass die Funktion optimal minimiert werden kann.
18
0 0 0 0 00 0 0 1 00 0 1 0 00 0 1 1 00 1 0 1 10 1 1 1 11 0 1 0 01 0 1 1 01 1 0 0 11 1 0 1 11 1 1 0 0
D C B A Y Übung
Bitte erstellen Sie für diegegebene Wahrheitstabelleein KV-Diagramm.
19
Übung
0 0 1 *0 0 1 *0 0 * 0* * 1 1
A
B
C
D
0 0 0 0 00 0 0 1 00 0 1 0 00 0 1 1 00 1 0 1 10 1 1 1 11 0 1 0 01 0 1 1 01 1 0 0 11 1 0 1 11 1 1 0 0
D C B A Y
Bilden Sie die disjunktive oder konjunktive Minimalform, so dass Sie in einfacher Weise eine algebraische Umformung durchführen können, die eine Realisierung nur mit NOR-Gattern ermöglicht. Zeichnen Sie die Zu-sammenfassungen in das KV-Diagramm ein.