Vorlesung Teil 2 - Beuth Hochschule für Technik Berlin

Сomentários

Transcrição

Vorlesung Teil 2 - Beuth Hochschule für Technik Berlin
2.2 Schaltfunktionen und ihre Darstellung
2.2.1 Boolesche Algebra
• Boolesche Algebra und physikalische Realität
• Symbole der Schaltalgebra
• Die Booleschen Postulate
• Die Booleschen Theoreme
• De Morgan‘sches Theorem
• Entwurf einfacher Schaltungen
• Beispiele ( Laborübung)
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 45
Nur für Lehrzwecke
2.2.1 Boolesche Algebra
•
George Boole, britischer Mathematiker, 1815-1864
"The mathematical analysis of logic“ (Algebra zur
systematischen Behandlung von Logik) 1847, 1854
•
E.V. Huntington (1874 bis 1952) führt 1904 eine
axiomatische Ableitung dieser Algebra ein (Harvard Univ.)
•
George Boole
1938 leitet Claude Elwood Shannon (1916-2001, USA, Bell
Labs) eine 2-wertige Boolesche Algebra zur Beschreibung
binärer Schaltung ab (Schaltalgebra, Switching Theory)
Sinn: Analyse, Vereinfachung und Synthese von digitalen
Schaltungen nach definierten Gesetzen
Claude Elwood
Shannon, 1916-2001,
Prof. am MIT
Begriffe:
Axiom
Ursatz, der nicht bewiesen (abgeleitet) werden kann
Postulat Forderung; unbeweisbare, aber unentbehrliche Annahme
Theorem Lehrsatz
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 46
Nur für Lehrzwecke
Boolesche Algebra und physikalische Realität
Technologie
0
1
Relais
Schalter offen
Schalter geschlossen
Glasfaser
Licht aus
Licht an
Compact Disk
Keine Vertiefung
Vertiefung
CMOS Schaltkreis
0 – 1,5 Volt
3,5 – 5 Volt
TTL-Schaltkreis
0 – 0,8 Volt
2 – 5 Volt
Low:
High:
Signal im niedrigeren Spannungsbereich
Signal im höheren Spannungsbereich
Zuordnung von Low und High zu einem logischen / booleschen / digitalen Wert:
Positive Logik:
Negative Logik :
Low = 0 High = 1 (intuitive, natürliche Festlegung)
Low = 1 High = 0 (weniger gebräuchlich)
Symbol eines digitalen Schaltkreises (Gatters):
Eingänge
Ausgang
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 47
Nur für Lehrzwecke
Symbole der Schaltalgebra, Darstellung nach DIN/ISO
Definitionen
Zeichen
__
Benennung
a=
b=
0
0
a=1
a=0
y=0
y=1
1
0
0
1
1
1
Schreib- und Sprechweise
Symbol
y = ā = ¬a; (a’, \a, /a)
nicht a
a
1
¬
Negation
∧
Konjunktion,
UND/AND
y=
0
0
0
1
y = a ∧ b;
a und b
a
b
&
y
∨
Disjunktion,
ODER/OR
y=
0
1
1
1
y = a ∨ b;
a oder b
a
b
≥1
y
0
y = a ∧ b;
a nand b
a
b
&
y
a
b
≥1
y
a
b
=
y
a
b
=1
y
y
___________________________
____
∧
NAND
y=
1
1
1
__________
∨
NOR
y=
1
0
0
0
y = a ∨ b;
a nor b
≡
Äquivalenz,
(E)XNOR
y=
1
0
0
1
y = a ≡ b;
a äquivalent b
a EXNOR b
Antivalenz,
(E)XOR
y=
0
1
1
0
y = a ⊗ b;
a antivalent b
a EXOR b
____
≠
⊗
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 48
Nur für Lehrzwecke
Symbole der Schaltalgebra, US - Darstellung
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 49
Nur für Lehrzwecke
Die Booleschen Postulate
Definition:
Grundlage der Booleschen Algebra ist die Menge A mit den
Elementen 0 und 1, in der die zweielementigen Operationen "+" und
"·" (bzw. "∨" und "∧") definiert sind, so dass gilt:
Postulate (Annahmen):
•P1:
a = 0 oder a = 1 mit a ∈ A
•P2:
0 · 0 = 0
•P3:
1 + 1 = 1
•P4:
0 + 0 = 0
•P5:
1 · 1 = 1
•P6:
1 · 0 = 0 · 1 = 0
•P7:
1 + 0 = 0 + 1 = 1
Unter Heranziehung der Booleschen Postulate (Annahmen, Voraussetzungen)
können jetzt die Booleschen Theoreme (Lehrsätze) aufgestellt werden.
Die Richtigkeit dieser Lehrsätze kann jederzeit mit Hilfe der Postulate überprüft
werden (z.B. unter Verwendung von Wahrheitstafeln).
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 50
Nur für Lehrzwecke
Die Booleschen Theoreme
Ein Theorem in der Booleschen Algebra ist eine Regel, die eine fundamentale
Beziehung zwischen den Booleschen Variablen zum Ausdruck bringt.
Die Anwendung der Theoreme wird es dann erlauben, logische Schaltungen in
vielfältiger Form zu manipulieren bzw. zu vereinfachen.
1.
Kommutativgesetz (Vertauschungsgesetz)
2.
Assoziativgesetz (Zusammenfassungsgesetz)
3.
Distributivgesetz (Verteilungsgesetz)
4.
Idempotenzgesetz (Identitätsgesetz)
5.
Absorptionsgesetz (Verschmelzungsgesetz,
Redundanzgesetz)
6.
Null- und Eins-Gesetz
7.
Komplement-Gesetz
8.
De Morgansches Theorem
Im folgenden werden die Theoreme vorgestellt:
• In algebraischer Form und
• als praktische Anwendung beim Schaltungsentwurf mit Logik-Gattern.
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 51
Nur für Lehrzwecke
Kommutativgesetz (Vertauschungsgesetz)
Disjunktion und Konjunktion sind kommutativ
Algebraische Form:
a + b = b + a
a · b = b · a
Interpretation:
Es ist offenbar gleich, in welcher Reihenfolge die Variablen a und b
disjunktiv ("+") bzw. konjunktiv ("·") verknüpft werden.
Schaltungstechnisch:
a
b
b
≥1
≡
a
≥1
a
b
&
b
≡
&
a
Es ist offenbar gleich, in welcher Reihenfolge die Eingangsvariablen
an die Eingänge der ODER- bzw. UND-Gatter gelegt werden.
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 52
Nur für Lehrzwecke
Assoziativgesetz (Zusammenfassungsgesetz)
Disjunktion und Konjunktion sind assoziativ
(a + b) + c = a + (b + c)
(a · b) · c = a · (b · c)
Algebraische Form:
Interpretation:
Es ist offenbar gleich, in welcher Reihenfolge die Variablen a, b und c
disjunktiv ("+") bzw. konjunktiv ("·") verknüpft werden.
Schaltungsa
c
≥1
≥1
technisch:
≥1
≥1
≡
b
c
a
b
a
c
&
&
b
c
≡
&
&
b
a
Jeder Klammerung, die in der algebraischen Form auftritt, entspricht bei der
Gatterimplementierung einer Gatterebene
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 53
Nur für Lehrzwecke
Distributivgesetz (Verteilungsgesetz)
Die Funktionen "Disjunktion" und "Konjunktion" sind distributiv
(verteilend), d.h.
"ODER„ verteilt sich über "UND,
"UND" verteilt sich über "ODER".
Algebraische a + (b · c) = (a + b) · (a + c)
a · (b + c) = (a · b) + (a · c) = a · b + a · c
Form:
Interpretation:
• Der Ausdruck "a + (b · c)" ist genau dann wahr,
wenn "a" wahr ist oder wenn "b" und "c" beide wahr sind.
• "(a + b) · (a + c)" ist genau dann wahr,
wenn jeder der beiden Klammerausdrücke wahr ist.
Schaltungstechnisch:
c
c
≥1
&
≥1
b
≡
&
a
≥1
a
b
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 54
Nur für Lehrzwecke
Idempotenzgesetz (Identitätsgesetz)
Algebraische Form:
a + a = a
a · a = a
Interpretation:
Die Variable bleibt bei disjunktiver bzw. konjunktiver Verknüpfung mit
sich selbst unverändert.
Schaltungstechnisch:
a
a
≥1
a
a
&
a
a
Die Gatterschaltung ist logisch redundant. Sie verzögert allerdings
das Signal "a" und hat damit technische Bedeutung.
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 55
Nur für Lehrzwecke
Absorptionsgesetz (Verschmelzungsgesetz, Redundanzgesetz)
a + (a · b) = a
a · (a + b) = a
Algebraische Form:
Interpretation:
für "a + (a · b)":
Ist "a" wahr, dann ist der Wert von "b" irrelevant.
Ist jedoch "a" falsch, kann (a · b) nicht mehr wahr werden.
Der Ausdruck ist also vollständig durch "a" bestimmt, "b" wird "absorbiert".
für "a · (a + b)":
Ist "a" wahr, dann ist auch "(a + b)" wahr, d.h. der gesamte Ausdruck ist wahr.
Ist "a" falsch, so ist der gesamte Ausdruck falsch.
Der Ausdruck ist also vollständig durch "a" bestimmt, "b" wird "absorbiert".
a
Schaltungstechnisch:
&
≥1
b
a
a
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 56
Nur für Lehrzwecke
Null- und Eins-Gesetz
0 + a = a
0 · a = 0
Algebraische Form:
1 + a = 1
1 · a = a
Schaltungstechnisch:
0
1
≥1
≥1
a
a
1
a
0
1
&
&
0
a
a
a
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 57
Nur für Lehrzwecke
Komplement-Gesetz
Algebraische Form:
a + ¬a = 1
a · ¬a = 0
Interpretation:
Zu jedem Element "a" existiert ein komplementäres Element " ¬ a".
" ¬ a" wird Komplement von "a" genannt
Schaltungstechnisch:
a
a
≥1
1
a
&
0
a
Damit kann eine „1“ oder eine „0“ erzwungen werden.
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 58
Nur für Lehrzwecke
De Morgan’sches Theorem
Dualität: Jedes Gesetz der Schaltalgebra bleibt gültig, wenn
0 und 1 sowie ∧ und ∨ vertauscht werden
Algebraische Form:
(a + b) = a • b
(a • b) = a + b
Augustus De Morgan
*1806 in Indien
†1871 in England
Interpretation:
Die Umwandlung von NOR- zu UND-Schaltungen bzw. von NAND- zu
ODER-Schaltungen ist unmittelbar möglich.
Schaltungstechnisch:
a
a
≥1
&
NOR ⇒ UND
≡
b
b
NOR
a
NAND ⇒ ODER
&
b
a
≡
≥1
b
NAND
Das De Morgansche Theorem hat sehr große Bedeutung für die
Schaltungstechnik, insbesondere bei der Transformation von Schaltungen.
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 59
Nur für Lehrzwecke
Ausblick Schaltungsentwurf
•
Ein aus "UND", "ODER" und "NOT" gebildetes System wird auch als
"vollständiges Logik-System" bezeichnet.
•
Zur Realisierung jeder beliebigen Schaltung werden nur diese
Funktionen benötigt.
•
Daher kann man sich beim Entwurf von Schaltungen auf einige wenige
Bauteile beschränken.
•
Das führt zur Einführung so genannter "universeller Logik-Blöcke", die
wiederum die Grundlage für die "Programmierbare Logik" bilden.
•
Ein vollständiges System kann sogar durch nur eine einzige Funktion
voll bestimmt werden.
•
Funktionen, die diese Eigenschaft besitzen sind die negierten Formen
der Funktionen "UND" bzw. "ODER",
die als "NAND" (Not-AND) bzw. "NOR" (Not-OR) bezeichnet werden.
NAND = Sheffer-Funktion
NOR = Peirce-Funktion
•
Hinweis: Weder NOR noch NAND sind assoziativ!
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 60
Nur für Lehrzwecke
Beweis: Vollständiges System am Bsp. der Sheffer-Funktion (NAND)
Negation
f (a ) = a = ( a • a )
UND
f (a,b) = a • b = (a • b) + (a • b) = (a • b) + (a • b)
f (a,b) = (a • b) • (a • b)
ODER
f (a, b) = a + b = a + b = a • b
f (a, b) = (a • a) • (b • b)
Darüber hinaus können auch die notwendigen Konstanten "0" und "1" mit Hilfe der
Sheffer- (oder Peirce-) Funktion realisiert werden:
0 = (a • a )
1 = 0 = (a • a)
Da auch die beiden Konstanten erzeugt werden, spricht man von einem
"stark vollständigem System"
In der Elektronik lassen sich am einfachsten die NAND- und NOR-Funktionen
realisieren
z.B. NAND in TTL-Logik, NOR in ECL-Logik, NAND und NOR in CMOS-Logik
TTL = Transistor-Transistor-Logik
ECL = Emitter Coupled Logic, Emittergekoppelte Logik
CMOS = Komplementäre MOS-Logik, MOS = Metal Oxide Semiconductor
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 61
Nur für Lehrzwecke
Aus drucktechnischen Gründen leere Folie!
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 62
Nur für Lehrzwecke
2.2.2 Spezifische Schaltnetze und ihre Verbesserung
2.2.2.1 Entwicklung kombinatorischer Schaltungen
Grundlagen kombinatorischer Schaltungen
Vorgehen bei der Entwicklung kombinatorischer Schaltungen
Beispiel: Quadrierer
2.2.2.2 Wichtige kombinatorische Grundschaltungen
Addierer
Halbaddierer
Volladdierer
Addierwerk
Subtrahierwerk
Dekoder
Multiplexer
Komparator (Vergleicher)
2.2.2.3 Karnaugh-Veitch (KV) – Diagramm
Grundlagen des Verfahrens
Minimierung bei mehreren Ausgängen
Schaltungsentwurf mit dem KV-Diagramm
1 aus 10 Dekoder zur Anzeige von BCD-Zahlen
Übungsbeispiel
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
SU-TGI12.ppt
Folie 63
Technische Grundlagen der Informatik
Nur für Lehrzwecke
2.2.2.1 Entwicklung kombinatorischer Schaltungen
Kombinatorische Schaltung (Schaltnetz, Gatterschaltung):
• Ausgangswert = f (Eingangswerte)
• Enthält keine Speicherelemente
• Funktionsbeschreibung durch Funktionstabelle (Wahrheitstabelle, Wertetabelle)
a•(a•b)‘ = a•(a‘+b‘)
Beispiel:
= a•b‘
&
a
0
0
1
1
b
0
1
0
1
(a=b)
1
0
0
1
(a>b)
0
0
1
0
(a<b)
0
1
0
0
= (a>b)
a
≥1
&
b
(a•b‘+a‘•b)‘ = (a=b)
&
(a•b)‘
Sequentielle Schaltung (Schaltwerk):
b•(a•b)‘ = b•(a‘+b‘)
= a‘•b
= (a<b)
• Ausgangswert = f (Eingangswerte, Zeit)
• Enthält Speicherelemente („Gedächtnis“)
• Funktionsbeschreibung durch Zustandstabelle, Zustandsgraf
Beispiel:
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 64
Nur für Lehrzwecke
Vereinfachung von logischen Schaltungen
Satz:
Mit den zwei Verknüpfungen „·” und „+” sowie der
Negation kann man alle Schaltfunktionen erzeugen
Verfahren:
• Disjunktive oder konjunktive Normalform erzeugen
(liefert oft komplizierte Ausdrücke)
• Anwendung von Methoden zur systematischen Vereinfachung
Beispiel für die Darstellung einer logischen Schaltung:
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 65
Nur für Lehrzwecke
Entwicklung kombinatorischer Schaltungen
Vorgehen:
1. Problemerfassung mittels Funktionstabelle (Wahrheitstabelle,
Wertetabelle, Schaltbelegungstabelle - SBT)
2. Funktionsgleichungen aufstellen
3. Schaltungsvereinfachung (Minimierung) mit geeigneten
Verfahren (algebraisch, KV-Diagramm, Quine-McCluskey Verfahren, rechnerunterstützt)
4. Schaltungsrealisierung, Bauteileauswahl
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 66
Nur für Lehrzwecke
Darstellung logischer Funktionen
Minterm (Vollkonjunktion):
Konjunktion, in der alle Variablen
(bejaht oder negiert) einer Funktion
vorkommen
z.B. (a ∧ b) oder (¬a ∧ b)
Maxterm (Volldisjunktion):
Disjunktion, in der alle Variablen
(bejaht oder negiert) einer Funktion
vorkommen
z.B. (a ∨ b) oder (¬a ∨ b)
Normalform (NF):
Jeder Teilausdruck (bzw. jede
Klammer) der Schaltfunktion
enthält alle Eingangsvariablen (ist
also Min- oder Maxterm)
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Formale Angabe der
Minterme und Maxterme für
drei Variablen:
a b c
Minterm
für y=1
Maxterm
für y=0
0 0 0 a‘ b‘ c‘
a +b +c
0 0 1 a‘ b‘ c
a + b + c‘
0 1 0 a‘ b c‘
a + b‘ + c
0 1 1 a‘ b c
a + b‘ + c‘
1 0 0 a b‘ c‘
a‘ + b + c
1 0 1 a b‘ c
a‘ + b + c‘
1 1 0 a b c‘
a‘ + b‘ + c
1 1 1 a b c
a‘ + b‘ + c‘
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 67
Nur für Lehrzwecke
Disjunktive Normalform (DNF)
DNF:
Disjunktive Verknüpfung derjenigen Minterme (d.h. Zeilen
(sum of products) der Wertetafel), für die die Schaltfunktion den Wert 1
annimmt
Regel:
DNF = p1 + p2+ ...pn
pi = k1 • k2 •...kn
mit kj =
xj , falls in dieser Zeile eine 1 in Spalte j steht
¬ xj , falls dort eine 0 steht
Beispiel:
y = x1 • x2 • x 3 + x1 • x 2 • x 3 + x1 • x2 • x3
Anmerkung:
Die disjunktive Normalform ist günstig,
wenn in der Wertetabelle für y wenige
„1“ stehen. Sonst ist die konjunktive
Normalform vorzuziehen.
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
x1
0
0
0
0
1
1
1
1
x2
0
0
1
1
0
0
1
1
x3
0
1
0
1
0
1
0
1
Technische Grundlagen der Informatik
y = f(x1,x2,x3)
0
0
1
0
1
0
0
1
SU-TGI12.ppt
Folie 68
Nur für Lehrzwecke
Konjunktive Normalform (KNF)
KNF:
Konjunktive Verknüpfung derjenigen Maxterme (d.h. Zeilen
(product of sums) der Wertetafel), für die die Schaltfunktion den Wert 0
annimmt
Regel:
KNF = s1 • s2 • ...sn
si = k1 + k2 +...kn
mit kj =
xj , falls in dieser Zeile eine 0 in Spalte j steht
¬ xj , falls dort eine 1 steht
Beispiel: y = (x1+x2+x3)••(x1+x2+x3)••(x1+x2+x3 )••(x1+x2+x3)••(x1+x2+x3)
x1
0
0
0
0
1
1
1
1
x2
0
0
1
1
0
0
1
1
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
x3
0
1
0
1
0
1
0
1
y = f(x1,x2,x3)
0
0
1
0
1
0
0
1
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 69
Nur für Lehrzwecke
Algebraische Erzeugung der DNF
Beispiel:
Gegeben sei in disjunktiver unvollständiger Form:
y = a‘ b‘ + a‘ c‘ + b‘ c‘
1.
2.
3.
Schritt
y = a‘ b‘ c + a‘ b‘ c‘ + a‘ c‘ + b‘ c‘
= a‘ b‘
Schritt
y = a‘ b‘ c + a‘ b‘ c‘ + a‘ b c‘ + b‘ c‘
= a‘ c‘
(die ergänzende Konjunktion
a‘ b‘ c‘ kann weggelassen werden,
da sie bereits im ersten Schritt
erzeugt wurde)
Schritt (Lösung)
y = a‘ b‘ c +a‘ b‘ c‘ + a‘ b c‘ + a b‘ c‘
= b‘ c‘
(die ergänzende Konjunktion
a‘ b‘ c‘ kann weggelassen werden,
da sie bereits im ersten Schritt
erzeugt wurde)
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 70
Nur für Lehrzwecke
Minimierung logischer Ausdrücke
Ziel: Minimale Anzahl von Eingängen und Größe von Schaltgattern
Methoden:
• Algebraische Minimierung der Logikfunktion
Algebraische Umformungen,
häufiges Hilfsmittel ist das Absorptionsgesetz: x∨(x∧y)=x usw.
• Grafischer Ansatz nach Karnaugh-Veitch
Für kleinere Probleme zur manuellen Lösung geeignet
(max. 6 Variable)
• Algorithmus nach Quine-McCluskey
Systematisches Verfahren für prinzipiell beliebig große Ausdrücke
• Heuristische Algorithmen
a) Ersatz des exakten, aber aufwändigen Algorithmus von QuineMcCluskey
b) „Probierverfahren“, die schneller (mit weniger Rechchenleistung und
Speicherbedarf) minimale oder fast minimale Lösungen erreichen
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 71
Nur für Lehrzwecke
Algebraische Minimierung
Verfahren:
• Gesetze der Booleschen Algebra schrittweise so oft anwenden, bis ein
minimaler Ausdruck dargestellt ist
Nachteile:
• Keine systematische Vorgehensweise
• Ergebnis ist abhängig von der Erfahrung und Geschicklichkeit des
Designers
• Ist nur für wenige Variable und überschaubare Ausdrücke anwendbar
Beispiel:
DNF:
y = a‘ b‘ c + a b‘ c + a‘ b c‘ + a‘ b c
1. Schritt: Anwendung Distributivgesetz
y = [ (a‘ + a) b‘ c ] + [a‘ b (c‘ + c) ]
a • (b + c) = (a • b) + (a • c)
2. Schritt: Anwendung Komplementgesetz a + a‘ = 1
y = b‘ c + a‘ b
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 72
Nur für Lehrzwecke
Beispiel: Quadrierer für 2-stellige Dualzahl
Ein Quadrierer für 2-stellige Dualzahl hat die
Eingänge: a0, a1
Ausgänge: b0, b1, b2, b3
Funktionstabelle:
a1
a0
b3
b2
b1
b0
0
0
1
1
0
1
0
1
0
0
0
1
0
0
1
0
0
0
0
0
0
1
0
1
Gleichungen für die Ausgänge:
b0 = a1‘a0 + a1a0 = a0
b1 = 0
b2 = a1a0‘
b3 = a1a0
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 73
Nur für Lehrzwecke
Aus drucktechnischen Gründen leere Folie!
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 74
Nur für Lehrzwecke
2.2.2.2 Wichtige kombinatorische Grundschaltungen
• Addierer
• Halbaddierer
• Volladdierer
• Addierwerk
• Subtrahierwerk
• Dekoder
• Multiplexer
• Komparator (Vergleicher)
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 75
Nur für Lehrzwecke
Addierer
Aufgabe:
Beispiel:
Zwei Dualzahlen addieren
1011
+1111
111
11010
(Übertrag)
Lösungsschritte:
Halbaddierer: Zwei einstellige Dualzahlen addieren; Ergebnis ist
Summenbit und Übertragsbit (Carry-Bit)
Volladdierer: Zwei einstellige Dualzahlen und eingehendes
Übertragsbit addieren; Ergebnis ist Summenbit und
(ausgehendes) Übertragsbit
Addierwerk: Zwei mehrstellige Dualzahlen addieren
(Kombination von Volladdierern)
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 76
Nur für Lehrzwecke
Halbaddierer
Aufgabe:
• Addiert zwei einstellige Dualzahlen
• Erzeugt als Ergebnis ein
- Summenbit (S)
- Übertragsbit bzw. Carry-Bit (C)
a
0
0
1
1
Funktionstabelle:
DNF:
b
0
1
0
1
S
0
1
1
0
C
0
0
0
1
S = ab‘ + a‘b
C = ab
Keine Vereinfachung mit KV-Diagramm möglich
a
0
1
b
0
1
0
1
a
0
1
0
1
S
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
b
0
1
0
0
0
1
C
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 77
Nur für Lehrzwecke
Halbaddierer - Schaltung
Direkte Umsetzung in eine Schaltung:
a
b
&
≥1
S
&
&
C
Vereinfachung mit XOR (Antivalenz):
S = ab‘ + a‘b = a ⊕ b
a
b
=1
&
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
S
C
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 78
Nur für Lehrzwecke
Volladdierer
Aufgabe:
• Addiert zwei einstellige Dualzahlen mit eingehendem
Übertragsbit (c = Carry in), d.h. es sind drei Bit zu addieren
• Erzeugt als Ergebnis ein
- Summenbit (S)
- Übertragsbit bzw. Carry-Bit (C)
Funktionstabelle:
a
0
0
0
0
1
1
1
1
b
0
0
1
1
0
0
1
1
c
0
1
0
1
0
1
0
1
S
0
1
1
0
1
0
0
1
C
0
0
0
1
0
1
1
1
Betrachtungen für das Summenbit S:
DNF:
ab 00
c
0
0
S = a’b’c + a’bc’ + ab‘c‘ + abc
KV-Diagramm:
keine Vereinfachung möglich (ebenso mit dem 1
Verfahren nach Quine McCluskey ( Übung!)
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
1
01
11
10
1
0
1
0
1
0
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 79
Nur für Lehrzwecke
Volladdierer - Schaltung
Direkte Umsetzung in eine Schaltung:
a
b
c
&
&
≥1
&
&
≥1
&
S
&
≥1
&
&
sehr aufwändig, komplex
bessere Lösung suchen
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 80
Nur für Lehrzwecke
Volladdierer – Optimierung für das Summenbit
Algebraische Vereinfachung:
Ziel: Nur XOR – Gatter verwenden
S = a’b’c + a’bc’ + ab‘c‘ + abc
= a‘ (b‘c + bc‘) + a (b‘c‘ + bc)
mit x‘y + xy‘ = x ⊕ y
und x‘y‘ + xy = (x ⊕ y)‘ = x
wird
(XOR, Antivalenz)
(XNOR, Äquivalenz)
y
S = a‘ (b ⊕ c) + a ( b ⊕ c)‘
= a ⊕ (b ⊕ c)
S =a⊕b⊕c
x
y
XOR
XNOR
0
0
0
1
0
1
1
0
1
0
1
0
1
1
0
1
Schaltung für das Summenbit:
a
b
=1
=1
S
c
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
SU-TGI12.ppt
Folie 81
Technische Grundlagen der Informatik
Nur für Lehrzwecke
Volladdierer – Optimierung für das Carry-Bit
Betrachtungen für das Carry-Bit C:
Funktionstabelle:
a
0
0
0
0
1
1
1
1
b
0
0
1
1
0
0
1
1
c
0
1
0
1
0
1
0
1
S
0
1
1
0
1
0
0
1
C
0
0
0
1
0
1
1
1
DNF: C = a‘bc + ab‘c + abc‘ + abc
KV-Diagramm:
C = ab‘c + ab + a‘bc
= c (ab‘ + a‘b) + ab
C = c ( a ⊕ b) + ab
Schaltung für das Carry-Bit:
ab 00
c
0
0
01
11
10
0
1
0
a
b
1
1
1
1
c
0
Anmerkung:
Es wird nur eine Vereinfachungsmöglichkeit
im KV-Diagramm in Anspruch genommen,
da sich der Ausdruck dann besser
vereinfachen lässt!
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
=1
&
≥1
C
&
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 82
Nur für Lehrzwecke
Volladdierer – optimierte Schaltung
Zusammenbau der Schaltungen für Summenbit und Carry-Bit:
a
=1
=1
b
c
S
&
&
≥1
C
Vergleich mit Halbaddierer:
a
b
c
=1
=1
S
&
&
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
≥1
C
Der Volladdierer ist aus
zwei Halbaddierern und
einem ODER-Gatter
aufgebaut.
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 83
Nur für Lehrzwecke
Addierwerk - 1
Ziel:
Zwei mehrstellige Dualzahlen addieren
Erinnerung: Addition von Dualzahlen
1011
+1111
111
(Übertrag)
11010
Verfahren: Bits der beiden Operanden und ggf. Carry-Bit addieren; für die
unterste Stelle ist das eingehende Carry-Bit immer Null
Schaltungsrealisierung: Aneinanderreihung von Volladdierern (für die
Stelle Null würde auch ein Halbaddierer reichen)
Den zuvor entwickelten Volladdierer kann man auch anders darstellen:
a
=1
ai
=1
b
c
S
Cout
&
&
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
bi
≥1
C
Cin
Si
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 84
Nur für Lehrzwecke
Addierwerk - 2
Paralleladdierwerk (Ripple Adder):
an
a1
bn
Cout
Cin
Cout
Sn
Vorteil:
b1
Cin
S1
a0
b0
Cout
Cin
„0“
S0
- Einfache Schaltung
- Modularer Aufbau (Volladdierer an Stelle 0 erlaubt
Kaskadierung – das Carry-in kann dann aber 0
oder 1 sein)
- Theoretisch beliebig ausbaubar
Nachteil: Langsam, da sich die Ausführungszeiten der
einzelnen Volladdierer summieren
Lösung: Carry-Look-Ahead-Addierwerk (schneller, aber
aufwändiger)
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 85
Nur für Lehrzwecke
Addierwerk – Carry-Look-Ahead
Prinzip:
• Zusammenfassung von z.B. acht Volladdierern zu einem Addierwerk
• Carry-Bit wird dem darüber liegenden Addierwerk zur Verfügung
gestellt, bevor die Addition vollständig ausgeführt ist
Für das Carry-Bit des Volladdierers war:
C = ab + c (a ⊕ b)
Mit ab = G = „carry generate“-Signal
(wenn a,b beide 1 sind, wird ungeachtet des Carry-in
ein Carry-out erzeugt)
und a ⊕ b = P = „carry propagate“-Signal
kann man verallgemeinert schreiben
Ci+1 = Gi + PiCi
und sukzessive entwickeln
C1 = G0 + P0C0
C2 = G1 + P1C1 = G1 + P1 (G0 + P0C0) = G1 + P1G0 + P1P0C0
C3 = G2 + P2C2 = G2 + P2 (G1 + P1G0 + P1P0C0)
= G2 + P2G1 + P2P1G0 + P2P1P0C0
usw.
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 86
Nur für Lehrzwecke
Addierwerk – Schaltung für Carry-Look-Ahead
Schaltung:
usw.
&
≥1
&
P2
C3
&
Vorteil:
G2
• Hohe Beschleunigung
des Addierers
&
≥1
P1
&
C2
G1
P0
&
≥1
G0
C0
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
C1
Nachteile:
• Aufwand nimmt mit
zunehmenden
Addierstufen sehr stark
zu (vergl. sukzessive
Entw.)
• Teuer, z.B. für 32 oder
64 Bit Addierer
SU-TGI12.ppt
Folie 87
Technische Grundlagen der Informatik
Nur für Lehrzwecke
Subtrahierwerk
Subtraktion zweier Dualzahlen:
x
y
z= x⊕y
Zweierkomplement des Subtrahenden bilden, z.B.:
0
0
0
0
1
1
1
0
1
1
1
0
100001
011110 (1er Kompl.)
011110 + 1 = 011111 (2er Kompl.)
Subtraktion ist dann die Addition des 2er Komplement
z=y
z = y‘
Schaltung für einen 4-Bit Addierer / Subtrahierer:
a3
b3
a2
b2
=1
a1
b1
=1
a0
b0
=1
=1
Steuerleitung:
Cout
Cin
S3
Cout
Cin
S2
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Cout
Cin
S1
Cout
Cin
0 = Addieren
1 = Subtrahieren
S0
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 88
Nur für Lehrzwecke
Dekoder
Funktion: Ein Dekoder ermittelt aus n Eingängen, die einen numerischen
Wert repräsentieren, einen entsprechenden Ausgang
Ein typisches Beispiel dafür ist die Wandlung einer Binärzahl in
einen "1 aus n"-Code.
Dekoder werden häufig zur Auswahl (Selektierung, Adressierung)
von integrierten Bausteinen eingesetzt
Beispiel: 1 aus 4 Dekoder (auch 2 zu 4 Dekoder genannt); vergl. 1 aus 10 Dek.!
c
Funktionstabelle:
I1
0
0
1
1
DNF:
I0
0
1
0
1
O3
0
0
0
1
I1 I1 I0 I0
O2
0
0
1
0
O1
0
1
0
0
O0
1
0
0
0
Schaltung:
O3 = I1 • I0
O2 = I1 • I0‘
I0
1
I1
1
O1 = I1‘ • I0
O0 = I1‘ • I0‘
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
&
O3
&
O2
&
O1
&
O0
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 89
Nur für Lehrzwecke
Beispiel: Adressdekoder
Beispiel: Es seien 8 gleichartige Speicherbänke zu je 1 KByte vorhanden.
• 1 KByte = 1024 Byte = 210 Byte, also 10 Bit (a0 bis a9)
(mit den 10 Bit wird codiert, welches der 1024 Byte angesprochen wird)
• 8 = 23 Speicherbänke, also 3 Bit (a10 bis a12)
(mit den drei Adressbits a10 bis a12 wird der Chip bestimmt, auf den zugegriffen
werden soll).
Das wird mit einem (1 aus 8)-Dekoder realisiert.
Jeder Chip hat einen zusätzlichen Eingang (Chipselect).
a12 a12 a11 a11 a10 a10
&
&
≈
≈
CS Bank 0
CS Bank 1
≈
&
CS Bank 7
Anmerkung:
Dekoder: Bit-Anzahl Eingangscodewort < Bit-Anzahl Ausgangscodewort
Encoder: Bit-Anzahl Eingangscodewort > Bit-Anzahl Ausgangscodewort
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 90
Nur für Lehrzwecke
Multiplexer
Multiplexer (MUX):
• Mehrere Eingangsports, einen Ausgangsport
• SELECT (S) Leitungen wählen denjenigen Eingangsport aus, dessen
Werte am Ausgangsport erscheinen sollen
Ein Multiplexer verhält sich also wie ein Umschalter, welcher durch
einen Code (Dualzahl) an den SELECT Eingängen den Ausgangsport
mit einem der Eingangsports verbindet.
d1
DIN-Symbol:
(mit Enable)
d2
y
dn
Anders ausgedrückt: Die n Eingangssignale si dienen dazu, eine der
2n Eingangsleitungen dk auf den Ausgang y durchzuschalten, diesen
Eingang also zu "selektieren".
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 91
Nur für Lehrzwecke
Beispiel: 4 zu 1 Multiplexer (MUX)
Beispiel:
Funktionstabelle: S1 S0
O=
Si = Steuereingänge
Ii = Dateneingänge
O = Datenausgang
4 zu 1 MUX
O
0
0
I0
0
1
I1
1
0
I2
1
1
I3
S1S1I0 I0
S1’ S0’ I0 + S1’ S0 I1
+ S1 S0’ I2 + S1 S0 I3
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
I3
&
I2
&
≥1
I1
&
I0
&
S0
1
S1
1
Technische Grundlagen der Informatik
O
SU-TGI12.ppt
Folie 92
Nur für Lehrzwecke
Anwendungsbeispiel für Multiplexer
Anwendungen: Datenübertragung, Messwerterfassung.
Dabei findet eine Parallel-Seriell- und eine Seriell-Parallel-Umsetzung statt.
Es sind zwei Fälle zu unterscheiden:
• Die Konzentration von n Kanälen auf einen Kanal
• Die Verteilung von einem Kanal auf n Kanäle: Demultiplexer
Multiplexer
Multiplexer
Demultiplexer
Demultiplexer
SRC 0
DST 0
SRC 0
DST 0
SRC 1
DST 1
SRC 1
DST 1
SRC 2
DST 2
SRC 2
…
…
SRC n
Leitung
DMUX
…
DST n
SRC
SELECT
MUX
DST 2
…
SRC n
DST n
SRC
SELECT
DST
SELECT
DST
SELECT
SRC = Source, Quelle, Sender
DST = Destination, Ziel, Empfänger
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 93
Nur für Lehrzwecke
Komparator
Komparator (Vergleicher): Ein n-Bit-Zahlenkomparator vergleicht die
Ziffernstellen zweier n-Bit Dualzahlen und stellt das Ergebnis am Ausgang
zur Verfügung.
Anwendung: Z.B. in Rechnern zum Abprüfen von Sprungbedingungen
(aufwändige Realisierung; daher werden 2-Bit-Komparatoren kaskadiert).
Ergebnis eines Vergleichs: a) = („gleich“)
b) > („größer“)
c) > („kleiner“)
a
&
b
Einfache
binäre
Vergleichsschaltungen:
a
b
&
a
&
A<B
(ab‘ + a‘b)‘ = (a ⊕ b)‘ = a
b
a
A>B
≥1
b
A=B
&
b
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 94
Nur für Lehrzwecke
Anwendungsbeispiel: Komparator
Vergleich zweier 1-Bit-Werte:
a
0
0
1
1
Funktionstabelle:
b
0
1
0
1
a=b
: y = a‘b‘ + ab = a
a>b
: y = ab‘
a<b
: y = a‘b
(a=b)
1
0
0
1
(a>b)
0
0
1
0
b = (a ⊕ b)‘
&
Schaltungsrealisierung:
a
b
(a<b)
0
1
0
0
a•(a•b)‘ = a•(a‘+b‘)
= a•b‘
= (a>b)
≥1
&
(a•b‘+a‘•b)‘ = (a=b)
&
(a•b)‘
Vorteil dieser Lösung:
Grundelement für Mehrbit-Komparator.
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
b•(a•b)‘ = b•(a‘+b‘)
= a‘•b
= (a<b)
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 95
Nur für Lehrzwecke
2.2.2.3 Vereinfachungsmethode nach Karnaugh-Veitch
Maurice Karnaugh:
Amerikanischer Elektroingenieur, der Anfang der 1950er Jahre bei den
Bell Labs die Vereinfachungsmethode entwickelt hat.
(geb. 1924 in den USA, arbeitete in den Bell Labs und ab 1970 bei IBM)
Maurice Karnaugh: "The Map Method for Synthesis of Combinational
Logic Circuits”.
Transactions of the AIEE, Vol. 72, No. 9 (1953), 593-599
Edward W. Veitch:
Amerikanischer Mathematiker, der ungefähr gleichzeitig eine ganz
ähnliche Methode mit etwas anderer graphischer Darstellung erfunden
hat.
E. W. Veitch: "A chart method for simplifying truth functions“.
May 1952, Proc. Assoc. for Computing Machinery, Pittsburgh
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 96
Nur für Lehrzwecke
Karnaugh-Veitch-Methoden
Zwei Methoden:
Minterm-Methode
Vereinfachung durch Ausnutzen von
DNF: a • b + a • b‘ = a • (b + b‘) = a
Vorgehen:
• Funktion in disjunktive Normalform bringen
• KV-Diagramm konstruieren
• Minterme mit Ergebnis 1 ins KV-Diagramm übertragen
• Benachbarte Spalten- und Zeilenfelder mit durchgängig 1
zusammenfassen (immer 2 oder 4 oder 6 usw.)
• Produktterme disjunktiv zusammenfassen
Maxterm-Methode
Vereinfachung durch Ausnutzen von
KNF: (a + b) • (a + b‘) = a + (b • b‘) = a
Vorgehen:
• Funktion in konjunktive Normalform bringen
• KV-Diagramm konstruieren
• Maxterme mit Ergebnis 0 ins KV-Diagramm übertragen
• Benachbarte Spalten- und Zeilenfelder mit durchgängig 0
zusammenfassen (immer 2 oder 4 oder 6 usw.)
• Summenterme konjunktiv zusammenfassen
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 97
Nur für Lehrzwecke
Konstruktion des KV-Diagramms
Verfahren:
• Eine einzelne Variable wird durch ein Feld repräsentiert;
ein benachbartes Feld steht für die Negation der Variablen
• Für jede weitere Variable wird das Diagramm durch Hinzunahme
der neuen Variablen gespiegelt, und zwar abwechselnd an
• der unteren waagerechten Kante und
• der rechten senkrechten Kante
a
b
0
1
a
a
0
1
ab
ab
ca 00
11 10
01
b
0 abc abc abc abc
ab
ab
1 abc abc abc abc
ca
01
11 10
db 00
00 abcd abcd abcd abcd
d
01 abcd abcd abcd abcd
11 abcd abcd abcd abcd
c
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
c
10 abcd abcd abcd abcd
Technische Grundlagen der Informatik
d
SU-TGI12.ppt
Folie 98
Nur für Lehrzwecke
Minimierung mit dem KV-Diagramm
Minimierungsidee:
Da horizontal und vertikal (auch randüberlappend) benachbarte „1“-Felder
nur in einer Variablen differieren, können benachbarte „1-en“ (Minterme)
gemäß dem Absorptionsgesetz (Term • Variable) + (Term • ¬ Variable) in
einem einzigen Term kombiniert werden („Nachbarschaftsbeziehung“)
Vorgehen:
1.
Markierung aller maximal großen rechteckigen Blöcke mit „1-en“
(„Nachbarschaftsbeziehung“ beachten)
2.
Bildung der zughörigen konjunktiven Terme
- Variable immer 0 in Markierung
Variable im Term komplementiert
Variable im Term unkomplementiert
- Variable immer 1 in Markierung
- Variable 0 und 1 in Markierung
Variable im Term weglassen
3.
Disjunktive Verknüpfung der konjunktiven Terme
Beispiel:
b
0
y = (a b)+(a b‘)+(a‘ b)
a
0
1
0
1
minimale Lösung
a
y=a+b
1
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
1
1
b
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 99
Nur für Lehrzwecke
Minimierung mit dem KV-Diagramm für drei Variable
Beispiel:
y = (a‘ b‘ c) + (a‘ b c‘) + (a b‘ c) + (a b c)
ab 00
c
0
0
01
11
10
1
0
0
1
0
1
1
1
a‘ b c‘
b‘ c
y = (a c) + (b‘ c) + (a‘ b c‘)
ac
Räumliche Anordnung eines
KV-Diagramms für drei Argumente a,b,c:
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 100
Nur für Lehrzwecke
Minimierung mit dem KV-Diagramm für vier Variable
Beispiel: y = (a b c d) + (a‘ b c d) + (a b c‘ d) + (a‘ b c‘ d)
cd
ab 00
00 0
01
0
01
11
10
0
0
0
1
1
0
y=b•d
11
0
1
1
0
10
0
0
0
0
Anmerkung:
cd 00
ab
00 0
Für „Don‘t Care“ –
Eingangskombinationen ist die
Ausgangsfunktion nicht definiert.
Die Belegung der „Don‘t Cares“ erfolgt
dann so, dass die markierten
Rechtecke möglichst groß werden.
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
01
11
10
0
0
0
cd 00
ab
00 0
01
11
10
0
0
0
01
0
1
1
0
01
0
1
1
0
11
0
1
X
0
11
0
1
1
0
10
0
0
0
0
10
0
0
0
0
SU-TGI12.ppt
Folie 101
Technische Grundlagen der Informatik
Nur für Lehrzwecke
Bezeichnungen beim Karnaugh-Diagramm
Implikant
Feldverbund
Primimplikanten (PI): Bezeichnung für die so groß wie möglich gewählten
Blöcke von „Einsen“ im Karnaugh-Diagramm.
Essentielle PI:
Primimplikanten, die mindestens eine „Eins“ enthalten,
die sonst von keinem anderen Block abgedeckt ist.
Die minimale Lösung enthält zumindest die
essentiellen Primimplikanten.
Nicht-essentielle PI: Primimplikanten, die obige Bedingung nicht erfüllen.
Nur eine Teilmenge, die alle Einsen abdeckt, muss
berücksichtigt werden (mehrere Lösungen)
Redundante PI:
Nicht essentielle PI, die nur bereits von essentiellen PI
abgedeckte „Einsen“ markieren.
Überflüssig.
Beispiel: f = (a‘•b‘•c‘•d) + (a‘•b‘•c•d) + (a‘•b•c‘•d) + (a‘•b•c•d‘) + (a‘•b•c•d) +
(a•b‘•c‘•d) + (a•b•c‘•d‘) + (a•b•c‘•d) + (a•b•c•d‘) + (a•b‘•c‘•d‘)
Essentielle PI:
a•c‘ , a‘•d
cd 00
ab
00 0
01
11
10
1
1
0
Nicht essent. PI: a‘•b•c , b•c•d‘ , a•b•d‘
01
0
1
1
1
Redundanter PI: c‘•d
11
1
1
0
1
Minimale Lösung: f = (a•c‘) + (a‘•d) + (b•c•d‘)
10
1
1
0
0
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 102
Nur für Lehrzwecke
Zusammenfassung KV-Diagramm
• Grafisches Verfahren zur Minimierung Boolescher Ausdrücke
• Übersichtlich, gut nachvollziehbar
• Führt systematisch zum Ziel
• Ist für bis zu maximal sechs Variablen geeignet
• Ist für bis zu vier Variablen manuell praktikabel
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 103
Nur für Lehrzwecke
Beispiel: 1-aus-10-Dekoder - 1
Aufgabe: Dekodierung und Anzeige von BCD-Zahlen
Eine von 10 Lampen, die mit den Ziffern 0 – 9 beschriftet
sind, soll mit einer BCD-Zahl angesprochen werden, d.h. die
entsprechende Lampe soll eingeschaltet werden.
0
1
2
3
4
5
6
7
8
9
Vorgehen:
1.
Funktionstabelle aufstellen
2.
Disjunktive Normalform für die Ausgänge aufstellen
(auch für Don‘t Care)
3.
Minimierung der Funktion (z.B. KV-Diagramm)
4.
Lösung aufschreiben
5.
Schaltung erstellen (und Bauteilauswahl)
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 104
Nur für Lehrzwecke
Beispiel: 1-aus-10-Dekoder – 2 (Funktionstabelle)
Eingänge
BCD
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Ausgänge
D
C
B
A
a
b
c
d
e
f
g
h
i
j
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
1
0
0
0
0
0
0
0
0
0
X
X
X
X
X
X
0
1
0
0
0
0
0
0
0
0
X
X
X
X
X
X
0
0
1
0
0
0
0
0
0
0
X
X
X
X
X
X
0
0
0
1
0
0
0
0
0
0
X
X
X
X
X
X
0
0
0
0
1
0
0
0
0
0
X
X
X
X
X
X
0
0
0
0
0
1
0
0
0
0
X
X
X
X
X
X
0
0
0
0
0
0
1
0
0
0
X
X
X
X
X
X
0
0
0
0
0
0
0
1
0
0
X
X
X
X
X
X
0
0
0
0
0
0
0
0
1
0
X
X
X
X
X
X
0
0
0
0
0
0
0
0
0
1
X
X
X
X
X
X
Anmerkung: Da immer nur ein Term den Ausgang bestimmt, sind
nur aufgrund der Don‘t Care Vereinfachungen zu erwarten
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 105
Nur für Lehrzwecke
Beispiel: 1-aus-10-Dekoder - 3
Beispiel: 1-aus-10-Dekoder
Disjunktive Normalform für Don‘t Care (Muster für die folgenden Schritte):
X = A‘ B C‘ D + A B C‘ D + A‘ B‘ C D + A B‘ C D + A‘ B C D + A B C D
KV-Diagramm:
CD
00
AB
00
01
11
10
01
11
10
X
X
X
X
X
Disjunktive Normalform für a:
a = A‘ B‘ C‘ D‘
KV-Diagramm:
CD
00
AB
00 1
01
11
10
0
X
0
X
01
0
X
X
0
11
0
X
X
0
10
0
0
X
0
Keine Vereinfachung möglich
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 106
Nur für Lehrzwecke
Beispiel: 1-aus-10-Dekoder - 4
Beispiel: 1-aus-10-Dekoder
Disjunktive Normalform für c:
c = A‘ B C‘ D‘
Lösungen für die anderen Anzeigen:
(Übungsaufgabe)
KV-Diagramm:
CD
00
AB
00 0
01
11
10
0
X
0
b = A B‘ C‘ D‘
d = A B C‘
01
1
X
X
0
e = A‘ B‘ C
11
0
X
X
0
f = A B‘ C
10
0
0
X
0
g = A‘ B C
h=ABC
Lösung:
i = A‘ D
c = A‘ B C‘
j=AD
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
SU-TGI12.ppt
Folie 107
Technische Grundlagen der Informatik
Nur für Lehrzwecke
Beispiel: 1-aus-10-Dekoder - 5
Schaltung eines BCD in 1-aus-10-Dekoders:
a
b
A
c
B
Beuth Hochschule für Technik Berlin
Fachbereich VI - Informatik und Medien
Linnemann, WiSe 2016/2017
d
e
f
C
g
h
i
j
D
Technische Grundlagen der Informatik
SU-TGI12.ppt
Folie 108
Nur für Lehrzwecke

Documentos relacionados