Post on 10-Oct-2020
transcript
Computer-Systeme – WS 12/13 - Teil 2/Butler 09.10.2012 1
Computer-Systeme
Teil 2: Die Maschine des Butlers
Computer-Systeme – WS 12/13 - Teil 2/Butler 2
Literatur
Spoerl, Alexander: Spoerls Computer Buch. Ullstein, 1971[1-6]
A.S. Tanenbaum, J. Goodman: Computerarchitektur. PrenticeHall, 2001, S.155-166
[1-5]
Kelly, John: Logik im Klartext. Pearson Studium, 2003, S.34-48[1-4]
Kelch, Rainer: Rechnergrundlagen – Von der Binärlogik zum Schaltwerk. Fachbuchverlag Leipzig, 2003, S.66-78
[1-3]
Hübscher, Heinrich et al.: IT-Handbuch, IT-System-elektroniker/-in, Fachinformatiker/-in. Westermann, 2. Auflage, 2001, S.71,100,103
[1-2]
Engelmann, Lutz (Hrsg.): Abitur Informatik – Basiswissen Schule. Duden-Verlag, 2003, S.228-238
[1-1]
Die Idee der Maschine für einen Butler stammt aus dem Buch von AlexanderSpoerl ([1-6]).
Computer-Systeme – WS 12/13 - Teil 2/Butler 3
Übersicht
• Prädikate und Aussagenlogik• Repräsentation von Prädikaten• Schaltnetze und Schaltwerke
Am Beispiel des Baus einer Maschine werden erläutert
• Repräsentation = Interne Darstellung eines Sachverhaltes oder einer Sache (Objekt)
• Präsentation = Wahrnehmbare äußere Darstellung eines Sachverhaltes oder einer Sache (Objekt)
Es werden die Repräsentationen mathematischer und logischerSachverhalte ("Objekte") innerhalb Computern vorgestellt.
Auf dieser Repräsentation basieren alle Computer.
Computer-Systeme – WS 12/13 - Teil 2/Butler 4
Die Aufgabe
Aufgabe:Es soll eine Maschine gebaut werden, die einem Butler hilft, das richtige Essen für einen verwöhnten Grafen aufzutragen.
Dazu sagt der Graf dem Butler, welche Kombinationen vonMahlzeiten akzeptiert werden.Leider hat unser Butler ein schlechtes Gedächtnis, so dass erals Hilfe eine Maschine benötigt - eben die, die gebaut werden soll.
Computer-Systeme – WS 12/13 - Teil 2/Butler 5
Aussagen als Bedingungen
Was darf der Butler dem Grafen auftischen?A1="Hühnchen passt mir mit gelber Soße"A2="Aber nie Soße mit Pudding"A3="Nie Fisch und Hühnchen zusammen"A4="Pudding passt nicht zu Fisch"A5="Nie etwas allein auftischen"A6="Aber immer irgendetwas auftischen"
Lösungsweg:1. Elemente der Aussagen identifizieren
Hühnchen (H), Fisch (F), Soße (S), Pudding (P)2. Zustände der Elemente bestimmen
Gereicht (J) oder nicht-gereicht (N)3. Tabelle mit allen Kombinationen aufstellen4. Aussagen A1 bis A6 in die Tabelle einarbeiten
Computer-Systeme – WS 12/13 - Teil 2/Butler 6
Wertetabelle / Wahrheitstabelle I
N
N
N
N
N
J
J
N
N
J
N
N
N
N
N
N
In Ordnung
JJJJ
NJJJ
JNJJ
NNJJ
JJNJ
NJNJ
JNNJ
NNNJ
JJJN
NJJN
JNJN
NNJN
JJNN
NJNN
JNNN
NNNN
PuddingSoßeFischHühnchen
J steht für JaN für Nein
Computer-Systeme – WS 12/13 - Teil 2/Butler 7
Wertetabelle / Wahrheitstabelle II
• Eine Wertetabelle definiert für Variablen in allen Wertekombinationen die zugeordneten Werte.
• Als Wertekombinationen kommen nur J und N in Betracht.• Statt J und N kann auch von F (falsch) oder 0
und W (Wahr) oder 1 gesprochen werden.• In dem Beispiel wird gereicht (J) als Wahr (1) und nicht-
gereicht (N) als Falsch (0) interpretiert, entsprechendes gilt für die Variable „In-Ordnung“.
0,5 V
5V
Technisch
0
1
ArithmetischLogischSprachlichMöglichkeit
FalschNeinTrifft nicht zu
WahrJaTrifft zu
Verschiedene Formen der Interpretation:
Computer-Systeme – WS 12/13 - Teil 2/Butler 8
Umformen in logische Ausdrücke I
Die Aussagen werden direkt in logische Bedingungenumgeformt:
Prädikat H Prädikat SUnd
"Hühnchen passt mir mit gelber Soße"
Prädikate:Hühnchen (H), Fisch (F), Soße (S), Pudding (P)
Computer-Systeme – WS 12/13 - Teil 2/Butler 9
Umformen in logische Ausdrücke II
¬(¬H ∧ ¬ F ∧ ¬ S ∧ ¬ P)"Aber immer irgendetwas auftischen"
¬((H ∧ ¬ F ∧ ¬ S ∧ ¬ P) ∨(¬ H ∧ F ∧ ¬ S ∧ ¬ P) ∨(¬ H ∧ ¬ F ∧ S ∧ ¬ P) ∨(¬ H ∧ ¬ F ∧ ¬ S ∧ P))
"Nie etwas allein auftischen"
¬(P ∧ F)"Pudding passt nicht zu Fisch"
¬(F ∧ H)"Nie Fisch und Hühnchen zusammen"
¬(S ∧ P)"Aber nie Soße mit Pudding"
H ∧ S"Hühnchen passt mir mit gelber Soße"
Logischer AusdruckAussage
H, S, P und F sind Variablen, die unterschiedlich interpretiert werden können.
Computer-Systeme – WS 12/13 - Teil 2/Butler 10
Logische Operatoren
Zeichen für das exklusive Oder (Exclusive OR = XOR)" ⊕ "
Zeichen für das negierte Oder (NOT OR = NOR)" ∇ "
Zeichen für das negierte Und (NOT AND = NAND)" | "
Zeichen für die logische NegationAlternative Zeichen: "NOT", "!"
" ¬ "
Zeichen für das logische Oder (Disjunktion)Alternative Zeichen: "OR", "|", "||"
" ∨ "
Zeichen für das logische Und (Konjunktion)Alternative Zeichen: "AND", "&", "&&"
" ∧ "
Computer-Systeme – WS 12/13 - Teil 2/Butler 11
Bedeutung der logischen Operatoren
XOR
F
W
W
F
A ⊕ B
NORNANDOder(OR)
Und(AND)
FFWWWW
FWWFFW
FWWFWF
WWFFFF
A ∇ BA | BA ∨ BA ∧ BBA
F steht für FalschW steht für Wahr
Die Bedeutung wird durch eine Wertetabelle definiert
Computer-Systeme – WS 12/13 - Teil 2/Butler 12
Die Maschine als Black Box
Ist dasEssenok?
Eingangs-variable(n)
Ausgangs-variable(n)
H
F
S
P
ok
Schalter Lampe
Interpretation der Variablen (Prädikate)Variablen, die gesetzt werden müssen: EingangsvariablenNein -> Falsch = Schalter auf, Ja -> Wahr = Schalter zu
Variablen, die "berechnet" werden: AusgangsvariablenNein -> Falsch = Lampe aus, Ja -> Wahr = Lampe brennt
Computer-Systeme – WS 12/13 - Teil 2/Butler 13
Und wie geht’s weiter?
Wir benötigen eine Technik, die sich physikalisch so verhält,wie die Wahrheitstabellen der Aussagenlogik es beschreiben.
Im folgenden werden zwei Technologien vorgestellt.
NANDORAND
FWWWW
WWFFW
WWFWF
WFFFF
A | BA ∨ BA ∧ BBA
Computer-Systeme – WS 12/13 - Teil 2/Butler 14
Technologie (Schalter)
x1
x2
x3
xn
y=x1 ∧ x2 ∧ x3 ∧... ∧xn y=x 1 ∨ x2 ∨ x3 ∨...∨xn y= ¬x
x1
x2
x3
xn
Am Hebel ziehenist 1, sonst 0
x
Schalter ist geschlossenund wird beim Ziehen desHebels geöffnet
Computer-Systeme – WS 12/13 - Teil 2/Butler 15
Technologie (Dioden-Transistor-Logik, DTL)
H (High) -> UH..UB, z. B. 4,5V bis 5V [Spannungsbereich für H]L (Low) -> 0..UL, z. B. 0V bis 0,7V [Spannungsbereich für L]
R
UB
....
x1
x2
x3
xn
y
0
y=x1 ∧ x2 ∧ x3 ∧... ∧xn
R
0
x1
x2
x3
xn
....
UB
y
y=x1 ∨ x2 ∨ x3 ∨...∨xn
UB
R
0
xy
y= ¬x
Computer-Systeme – WS 12/13 - Teil 2/Butler 16
DTL-AND - Beispiel
H (High) -> UH..UB, z. B. 4,5V bis 5VL (Low) -> 0..UL, z. B. 0V bis 0,7V
R
UB
x1=L
x2=Ly=L
0
R
UB
x1=H
x2=Ly=L
0
R
UB
x1=H
x2=Hy=H
0
Fall (1) Fall (2) Fall (3)
Computer-Systeme – WS 12/13 - Teil 2/Butler 17
DTL-OR - Beispiel
H (High) -> UH..UB, z. B. 4,5V bis 5VL (Low) -> 0..UL, z. B. 0V bis 0,7V
x1=L
x2=Ly=L
R
0
UB
x1=H
x2=Ly=L
R
0
UB
x1=H
x2=Hy=H
R
0
UB
Fall (1) Fall (2) Fall (3)
Computer-Systeme – WS 12/13 - Teil 2/Butler 18
Bemerkungen
• Diese Diode-Transistor-Logik (DTL) war Ende der 60er Jahre modern. Die DTL-Technik ist aber leicht verständlich, kann selbst gebaut werden und enthält alle Ideen der späteren Technologien.
• Die AND/OR-Gatter (Schaltungen) sind passiv und verschlechtern die Signale, so dass Verstärker in Form von NOT-Schaltungen (mit verstärkenden Transistoren) erforderlich sind. Daher (und auch aus Gründen der Ersparnis) werden entweder nur NAND- oder nur NOR-Gatter benutzt.
• Gatter = Technische Komponente, die einen einfachen aussagelogischen Ausdruck realisiert
• Die Zuordnung von H und L zu den Spannungsbereichen kann auch anders herum erfolgen.
Computer-Systeme – WS 12/13 - Teil 2/Butler 19
Weitere Technologien
http://www.kingswood-consulting.co.uk/giicmCMOS
http://www.kingswood-consulting.co.uk/giicmTTL
http://www.mikrocontroller.net/articles/74xxTTL
http://de.wikipedia.org/wiki/LogikfamilieTTL
TTL = Transistor-Transistor-Logiksiehe: http://de.wikipedia.org/wiki/Transistor-Transistor-Logik
CMOS = Complementary Metal Oxide Semiconductorsiehe: http://de.wikipedia.org/wiki/CMOS
Computer-Systeme – WS 12/13 - Teil 2/Butler 20
Symbole für Gatter
y=x1 ∧ x2 ∧ x3 ∧... ∧xn y=x 1 ∨ x2 ∨ x3 ∨...∨xn y= ¬x
x1x2x3
xn....
y
x1x2x3
xn....
y x y& ≥1 1
Zum Zusammensetzen der "Formel" werden jetzt Symbole dertechnischen Bausteine verwendet.
Deren Zusammensetzung entsprechend der Wahrheitstabelleoder der Formel ergibt dann die Maschine.
Computer-Systeme – WS 12/13 - Teil 2/Butler 21
Umformen von Gattern nach De Morgan
Umformungnach De Morgan
x1x2x3
xn....
y≥ 1
x1x2x3
xn....
y&
Umformungnach De Morgan
x1x2x3
xn....
y&
x1x2x3
xn....
y≥ 1
Computer-Systeme – WS 12/13 - Teil 2/Butler 22
Umformen zu NAND-Gattern I
– Es braucht nur ein Gattertyp (NAND) mit einer unterschiedlichen Anzahl von Eingängen hergestellt zu werden (was die Kosten reduziert).
– Die Und-/Oder-Gatter-Techniken haben keine das Signal regenerierende Eigenschaft, so dass die Signale beim Passieren jeden Gatters abgeschwächt werden.Wenn immer abwechselnd ein Und-Gatter und eine verstär-kende Negation benutzt wird, gibt es weniger Probleme mit den Abschwächungen der Signale.
Natürlich funktioniert alles auch mit NOR-Gattern,dann werden alle Und-Gatter nach NOR umgewandelt.
Um nur NAND-Gatter zu benutzen, werden alle Oder-Gatterentsprechend der De Morgan'schen Formel umgeformt.
Dies hat folgende Vorteile:
Computer-Systeme – WS 12/13 - Teil 2/Butler 23
Umformen zu NAND-Gattern II - Beispiel
Die einzelnen Negationen an den Eingängen können auch mitNAND-Gattern mit 2 Eingängen realisiert werden.
&
x1x2x3
y&
&
& y&
x1
x2
x3
Computer-Systeme – WS 12/13 - Teil 2/Butler 24
Schaltnetz für unseren Butler I
1. Jede Zeile in der Wertetabelle entspricht einer Konjunktion (Und-Ausdruck), dessen Bestandteile negiert oder nicht negiert sind.
2. Die Konjunktionen mit dem Resultat Wahr werden mit Oder verknüpft.Die resultierende Formel ist immer dann Wahr, wenn eine gültige/erwünschte Kombination der Variablen vorliegt.
3. Als Ergebnis liegt ein 2-stufiges Schaltnetz vor:– Erste Stufe mit Und-Gattern samt Negationen an den
Eingängen– Als zweite Stufe die Oder-Zusammenfassung der Und-
Ausgänge– Statt Stufe kann auch Ebene gesagt werden.
Computer-Systeme – WS 12/13 - Teil 2/Butler 25
Schaltnetz für unseren Butler II
Wenn die Negationen an den Eingängen auch durch NAND-Gatterersetzt werden, werden nur NAND-Gatter benötigt.
HFSP
¬H∧F∧S∧¬P H∧¬F∧¬S∧P H∧¬F∧S∧¬P
ok okUmgeformt nach derDe Morgan'schen Formel
Jedes Und-Gatterentspricht einer Zeilein der Wahrheitstabellemit einem Wert für okvon Wahr
≥1
& && & & &
&
HFSP
¬H∧F∧S∧¬P H∧¬F∧¬S∧P H∧¬F∧S∧¬P
Zusammenfassungder Und-Werte durchein Oder-Gatter
Computer-Systeme – WS 12/13 - Teil 2/Butler 26
Schaltnetz für unseren Butler III
Damit das Schaltnetz funktioniert, sind noch weitere Hardware-Komponenten nötig, die hier nicht betrachtet werden:– Kippschalter zur Eingabe sowie eine Elektronik, die
übereinstimmend mit dem Schalterzustand das entsprechende Signal sendet
– Lampen zur Anzeige der vier Variablen sowie Verstärker für die Lampen
– Netzteil, Gehäuse etc.
Computer-Systeme – WS 12/13 - Teil 2/Butler 27
Varianten der Symbole
Gatterart Altes Symbol DIN 40700 Amerikanisch
AND-Gatterx1x2x3
xn....
y
x1x2x3
xn....
y
x y
x1x2x3
xn....
y
x1x2x3
xn....
y
NAND-Gatter
OR-Gatter
NOR-Gatter
Negation
x1x2x3
xn....
y&
x1x2x3
xn....
y≥1
x1x2x3
xn....
y&
x1x2x3
xn....
y≥1
x y1
Computer-Systeme – WS 12/13 - Teil 2/Butler 28
Denken in Schichten I
Lösungsbeschreibung
Arbeitssituation
Physik
Bauelemente
Gatter
Jede Ebene (Schicht) hat eine eigene "Denkwelt"
In dieser Welt kann eigenständig unabhängig vonder Umwelt gedacht werden, nur die Schnittstellenach "oben" und "unten" muss beachtet werden
Nach "oben" werden Leistungen erbracht, von"unten" werden Leistungen benutzt
Jede Ebene hat eine eigene "Sprache", in der diedie Modelle dieser Ebene formuliert werden.
"benutzt""nutzt-aus"
Computer-Systeme – WS 12/13 - Teil 2/Butler 29
Denken in Schichten II
• Schicht (Ebene, Layer) ≈ Eigenständige Denkwelt mit spezieller SpracheSchichten werden mit der gerichteten Benutzt-Beziehung (Relation) mit anderen Schichten verbunden.In strengen Schichtensystemen ("Torten") benutzt eine Schicht maximal eine andere und wird von maximal einer anderen selbst benutzt.Sprache wird hier als allgemeines Ausdrucksmittel zur Formulierung von Sachverhalten verstanden.
• Benutzt-Relation ≈ "A benutzt B" bedeutet, dass die von B erbrachte Leistung bei der Leistungserbringung von A erforderlich ist.Die Korrektheit von A hängt damit von der Korrektheit von B ab.
Computer-Systeme – WS 12/13 - Teil 2/Butler 30
Zwischenergebnis
• Mit der vorgestellten Verfahrensweise ist es möglich, alle aussagenlogischen Ausdrücke maschinell auszuwerten.
• Zu Ehren von George Boole werden Daten mit zwei Zuständen als von der Art „boolean" oder „bool" bezeichnet.Ausdrücke damit sind daher "Boole'sche Ausdrücke" - sie haben nur zwei Werte: Wahr (True) und Falsch (False) bzw. 1 und 0.
• Typ = Art von Ausdrücken oder DatenEs wird auch von Datentyp gesprochen.
Computer-Systeme – WS 12/13 - Teil 2/Butler 31
Unser Graf will noch mehr
• Unser Graf ist etwas wählerisch, denn er möchte, dass nie dasselbe Essen zwei Mal hintereinander serviert wird.
• Leider ist unser Butler total vergesslich, so dass sich unsere Maschine das jeweils letzte Essen merken und bei der Bewertung berücksichtigen muss.
Unser Schaltnetz kann sich nichts merken - warum?
• Mit Schaltnetzen können keine Computer gebaut werden, in denen etwas "abgespeichert" werden kann.
• Speicher lassen sich nur mit rückgekoppelten Schalt-netzen, die sich dann Schaltwerke nennen, realisieren.
Computer-Systeme – WS 12/13 - Teil 2/Butler 32
Flip Flop als Speicher I
Ein Flip-Flop ist ein rückgekoppeltes Schaltnetz, das eine Speicher-wirkung hat - hier ein einfaches RS-Flip Flop.RS = Reset Set
0
1
1
Zustand: Q = 1
&
&
R
S Q
R
S Q1
0
0
Zustand: Q = 0
&
&
Computer-Systeme – WS 12/13 - Teil 2/Butler 33
Flip Flop als Speicher II – Etwas erweitert
• Ein Flip Flop mit einem Takteingang behält seinen Zustand unabhängig von den Zuständen an dem Data-Eingang bei.
• Nur wenn der Takt auf 1 ist, wird der Wert am Data-Eingangübernommen.Hier die Übernahme einer 0 als gespeicherter Wert.
Q
Takt
Data& &
&&1
10
1
0
1
1Q
Takt
Data& &
&&1
0
0
X
01
1
0
1
1
Q=1, Speicherzustand Übernahme einer 0: Q=0
Computer-Systeme – WS 12/13 - Teil 2/Butler 34
Schaltwerk
• Schaltwerk = Schaltnetz mit Speicher, dessen Zustände in die Funktion eingehenDer Funktionswert hängt von den Eingangsvariablen und vom inneren Zustand ab.
• Zustand = Wert einer Funktion, der länger als ein technisch bedingter Zeitraum lang anhält(dies ist die Schaltzeit)
• Speicher = Schaltwerk, dessen Zustände nur unter festgelegten Bedingungen sich ändern, ansonsten erhalten bleiben.
Alle Speicher des "Rechnerkerns" arbeiten nach dem vorgestellten Prinzip,auch wenn andere Technologien heute benutzt werden. Außerhalb desRechnerkerns - an der Peripherie - werden zum Speichern andere Technikenverwendet.
Computer-Systeme – WS 12/13 - Teil 2/Butler 35
Maschine für unseren vergesslichen Butler
• Für unseren Butler werden 4 Flip Flops benötigt, die jeweils den letzten servierten Zustand der Variablen H, F, S und P speichern und deren Zustände als Werte in das Schaltnetz zur Bestimmung, ob das Servierte in Ordnung ist, eingehen.
• Die Flip Flops werden gesetzt, wenn ein weiterer, neuer Eingang "Serviert" gedrückt wird.
Dies wird in einer viel größeren - hier nicht abgebildeten -Zustandstabelle berücksichtigt, in der als Spalten auch dieSpeicher-Flip Flops mit ihren alten und neuen Werten eingehen.
Computer-Systeme – WS 12/13 - Teil 2/Butler 36
Was haben wir erreicht?
Wir haben – gedanklich – eine Maschine mit einer festen Aufgabegebaut. Sie kann nur diese eine Sache.
Der nächste Schritt besteht darin, dass wir die Konzepte undIdeen verallgemeinern, damit wir auch andere Maschinen,universelle Maschine bauen können.
Computer-Systeme – WS 12/13 - Teil 2/Butler 37
Nach dieser Anstrengung etwas Entspannung....