Computer-Systeme Teil 2: Die Maschine des Butlerswi.f4.htw-berlin.de/users/messer/LV/WI-GWI-RABS/Folien/CS-02/02-C… · Computer-Systeme – WS 12/13 - Teil 2/Butler 09.10.2012 1

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]).


Ü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.


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.


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


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


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:


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)


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.


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", "&", "&&"

" ∧ "


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


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


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


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


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


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)


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)


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.


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


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.


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


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:


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


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.


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


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.


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


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"


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.


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.


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.


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

&

&


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


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.


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.


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.


Nach dieser Anstrengung etwas Entspannung....

Documents

Computer-Systeme Teil 2: Die Maschine des Butlerswi.f4.htw-berlin.de/users/messer/LV/WI-GWI-RABS/Folien/CS-02/02-C… · Computer-Systeme – WS 12/13 - Teil 2/Butler 09.10.2012 1