So, damit begrüße ich Sie zur Vorlesung Grundlagen der Informatik 2.
Wir machen weiter, wo wir letztes Mal aufgehört haben, beziehungsweise
letztes Mal haben wir uns beschäftigt mit dem neuen Teil 2,
Architektur von Rechensystemen, Schaltnetze und Schaltwerke.
Wir haben dort einige Sachen schon getan.
Ich habe Ihnen was erzählt über bulsche Algebren.
Das kannten Sie im Prinzip schon, was für Sie neu war.
Das waren nicht diese Gesetze, sondern was für Sie neu war, das waren
vielleicht die bulschen Ausdrücke, aber eigentlich auch nicht.
Aber dann geht es los mit der Darstellung der bulschen Funktionen,
also insbesondere die binären Entscheidungsdiagramme, hier unten
angedeutet als eine dritte Möglichkeit, wie man Funktionen darstellt,
entweder durch Wertetafeln oder Schalttafeln, Wertetabellen, durch
bulsche Ausdrücke oder durch diese binären Entscheidungsgrafen oder
auch reduzierte Funktionsgrafen.
Ich habe Ihnen dann gezeigt, wie man solche binären oder binary
decision diagrams entwirft, auf Basis dieses Entwicklungssatzes für
bulsche Funktionen.
Und wir hatten das gesehen am Beispiel der Übertragsfunktion eines
binären Addierers, die wir dann sukzessive vereinfacht haben in der
Darstellung, also über diesen Baum, sind wir dann zu einer reduzierten
Darstellung gekommen, indem wir Knoten zusammengefasst haben, die
identisch sind und dann Knoten weggelassen haben, bei denen beide
Entscheidungsalternativen auf den gleichen Knoten führen, sodass wir
dann auf diesen einfachen Grafen dort gekommen sind.
Und ich habe das dann auch bei der XOR-Funktion Ihnen vorgestellt, das
waren also diese BDDs, die eine wichtige Datenstruktur sind für
Simulationen von Hardware, eine ganz wichtige Aufgabe, dass man im
Hardware -Entwurf, im Schaltungsentwurf in der Lage ist, effizient
Simulationen durchzuführen.
Das geht aufgrund dieser Datenstruktur, die man also generell, wenn
man komplexe Systeme darstellen möchte, wenn man dort Funktionen
braucht, ist es sinnvoll, die durch reduzierte Funktionsgrafen
darzustellen.
Spezielle reduzierte Funktionsgrafen sind eben diese binären
Entscheidungsdiagramme, bei denen es also auch eine Reihe von
Entwurfsproblemen gibt, da kommt man dann auch wieder auf eine ganze
Reihe von NP-vollständigen Problemen, aber das nur am Rande.
Und dann habe ich Ihnen etwas erzählt zur Schaltalgebra, also konkrete
Instanziierung an der Buchenalgebra durch Schaltelemente.
Ich habe Ihnen das dargestellt, wie man die Operationen im Prinzip in
Schaltungen darstellen kann, mit Reihenschaltung oder
Parallelschaltung und Reihenschaltung, also Konjunktion und
Disjunktion darstellen oder auch das Komplement über so eine Ruhe
-Kontakt -Schaltung.
Ich habe Ihnen dann Schaltfunktionen vorgestellt, wie kann man sie
eigentlich realisieren oder darstellen, hier in diesem Fall durch
buchische Ausdrücke.
Da haben wir jeweils die disjunktive Normalform genommen dafür, also
die Disjunktion aller Einszeilen jeweils vorgenommen oder der
Ausdruck, den Einszeilen entsprechen, das waren diese 16 verschiedenen
zweistelligen Schaltfunktionen.
Ich habe Ihnen was erzählt über Verknüpfungsbasen, dass es im Prinzip
ausreicht, eine Operation zu nehmen, das NAND oder das NORM, um alle
anderen Operationen oder um alle zweistelligen Funktionen tatsächlich
darzustellen.
Das heißt, man kann mit NAND oder mit NORM alle Schaltungen
tatsächlich bauen.
Tatsächlich verwenden wir aber in der Regel doch auch die anderen.
Nur wenn es darum geht, Bauteile zu reduzieren, ist es interessant zu
sehen, wie viele man eigentlich minimal dort braucht.
Ich habe Ihnen das dann vorgestellt, wenn es um grundlegende
Schaltungen geht, wie man diese logischen Operationen durch
Schaltelemente für Hardware realisiert oder darstellt zunächst mal auf
dem Zeichenblatt mit diesen verschiedenen Darstellungsweisen,
entsprechend dieser DIN, die das alles in solchen Rechtecken macht,
mit entsprechenden Beschriftungen oder eben grafisch dargestellt.
Und das war die letzte Folge beim letzten Mal.
Da habe ich mich am Ende so ein bisschen verhaspelt beim Darstellen
dieses Bildes.
Und das können wir jetzt heute nochmal machen.
Ich fange hier nochmal wieder an.
Ich werde mich heute nicht wieder verhaspeln dabei, sondern ich habe
das jetzt im Griff.
Warum habe ich das jetzt im Griff?
Weil ich festgestellt habe, woran es lag, dass bestimmte Dinge nicht
gingen beim letzten Mal.
Da wollte ich nämlich, wenn ich hier auf diese Animation gehe, um zum
Beispiel diese Schaltung darzustellen, dann hat er das jetzt das
Falsche gemacht.
Ich wollte nämlich hier rein, genau.
Ich wollte die Funktion aufrufen, den Logiflash, den Sie hoffentlich
mittlerweile sich alle runtergeladen haben.
Das ist also unser Logiflash.
Das Problem ist, ich habe bisher immer Schaltungen, die ich hier
entworfen habe, in ein Verzeichnis hinein gelegt, wo ich dann XML
-Beschreibungen der Schaltungen ablegen konnte.
Leider funktioniert diese Funktion nicht mehr so wie bisher, dadurch,
dass wir eine neue Flash...
Das Ganze ist also Logiflash, also basiert auf der Adobe Flash
-Technologie.
Und dummerweise ist der Zugriff auf Verzeichnisse irgendwie nicht mehr
so...
Also funktioniert nicht mehr so wie früher durch eine neue Flash
-Version.
Und deswegen kann ich nicht mehr auf die schönen Schaltungen
zurückgreifen, die ich in dem Verzeichnis dort abgelegt hatte.
Da ist leider etwas ärgerlich.
Ich kann aber, das habe ich gesehen, ich kann also ein internes
Verzeichnis nehmen.
Da habe ich jetzt ein paar von diesen Schaltungen mir wieder
hergestellt und da kann ich zum Beispiel das XOR Ihnen jetzt noch
einmal zeigen.
Ich kann das also laden und dann sehen Sie genau dieses XOR, das wir
vorher auf der Folie gesehen haben.
Ich habe hier jetzt das dargestellt und jetzt habe ich das hier, das
ist schon on.
Das heißt, ich kann jetzt hier zum Beispiel ein 1 einschalten da vorne
und dann sehen wir an den gelben Leitungen, dort fließt jetzt Strom,
beziehungsweise da könnte Strom fließen, wird hier so visualisiert.
Da legt die 1 an, an einem Und-Gatter.
Warum kommt hier eine 1 raus?
Weil wir das Signal, was von da kommt, das ist eine 0, das wird
entsprechend hier über diesen Kringel negiert zu einer 1 und dadurch
kommt hier bei dem Und am Ende auch eine 1 raus.
Und hier unten ist diese 1, die von oben kommt, ist negiert, kommt
also zweimal eine 0.
Das heißt, da kommt eine 0, aber da eine 1 beim Oder-Gatter ankommt,
leuchtet die Lampe hier hinten.
Wenn ich jetzt den zweiten Eingang auch auf 1 schalte, dann habe ich
bei beiden Und-Gattern jeweils eine 1, das gelbe, und hier ist ein
negierter Eingang, das heißt, da kommt jeweils die 0 rein.
Das heißt, beide Und-Gatter liefern die 0, das heißt, das Oder-Gatter
kann nur eine 0 liefern.
Und wenn ich jetzt hier das oben wieder ausschalte, dann haben wir
genau die andere Situation.
Eine 1 ist hier dran und das Ganze leuchtet hinten.
So kann ich also hier Schaltungen entwerfen.
Ich kann die auch beliebig hier hin- und herschieben.
Das ist ein schönes Zeichenwerkzeug, wo ich beliebig mit rumspielen
kann und kann also auch noch neue Zeichnungen bauen.
Nur, dass Sie nochmal sehen, das ist also eine solche Schaltung, die
das XOR jetzt genau darstellt.
Ich kann das XOR auch einfach als ein Element hier reinbauen.
Da steht jetzt gleich 1, nicht das 2k plus 1, wie ich das auf den
Folien habe.
Hier steht nur gleich 1, was aber dasselbe bedeuten soll, nämlich ich
habe bei Division durch 2 den Rest 1.
Das heißt, ich habe eine ungerade Anzahl von Einsen hier vorne dran
stehen, beziehungsweise bei zwei Eingängen ist genau ein Eingang eine
1 und der andere eine 0, damit am Ende eine 1 rauskommt.
Und hier muss mindestens ein Eingang eine 1 sein, damit eine 1
rauskommt.
Und bei diesem hier müssen beide eine 1 sein, damit eine 1 rauskommt.
Deswegen haben wir hier diese verschiedenen Situationen.
Gehen wir zurück zu unserer Folie und gucken mal weiter.
Wir können dann natürlich nicht nur zweistellige Gatter machen,
sondern auch mehrstellige Gatter.
Das ist nicht weiter schwierig, also wenn Sie jetzt ein mehrstelliges
Gatter machen wollen, also wenn Sie ein dreistelliges Oder-Element
machen wollen, naja, wie könnte man das bauen?
Sie bauen einfach hier ein, da haben Sie ein einstelliges und dann
machen Sie dahinter noch ein zweistelliges Oder.
Dann haben Sie hier zwei Eingänge, den dritten Eingang führen Sie da
rein, da kommt etwas raus.
Und das ist jetzt Ihr Gatter für ein dreistelliges Oder.
Das wäre also praktisch nur eine, also zeigt einfach, ich kann
natürlich aus mehreren dieser Bauelemente neue Bauelemente mir bauen,
die ich dann auch irgendwie darstellen kann optisch.
Wenn ich also ein solches Oder habe mit einer ganzen Reihe von
Eingängen, dann heißt das, ich habe im Prinzip das aufgebaut aus einer
Reihe von Oder-Gattern, die ich dann entsprechend verschalten muss.
Und das kann ich beim Oder-Gatter machen, kann ich beim End-Gatter
machen oder NORG, egal was Sie dort haben, kann also verschiedene
solche Gatter mit mehrfach Eingängen dadurch darstellen.
Und wofür verwenden wir das Ganze?
Ich hatte gesagt, das Ziel dieses Kapitels ist Ihnen zu zeigen, wie
wir tatsächlich Rechner bauen können.
Und um Rechner zu bauen, müssen wir irgendwelche Funktionen darstellen
können im Rechner durch entsprechende Schaltungen.
Das heißt, wir wollen konkret etwas größere Funktionen berechnen,
nicht nur ein Oder oder ein Und, sondern eine größere Funktion
berechnen.
Eine größere Funktion heißt nicht nur eine Funktion von B hoch N nach
B, sondern von B hoch N nach B hoch M.
Bei der Addition haben wir zum Beispiel eine Summe und einen Übertrag,
also zwei Werte, die uns interessieren.
Allgemein haben wir für ein Schaltnetz, einen solchen blauen Kasten in
diesem Fall, wo wir eine ganze Reihe von Eingängen haben, diese A1 bis
AN, das geht von B hoch N, also N Variablen, N Eingangsvariablen.
Ich habe M Ausgänge, an denen ich die Werte ablesen kann, die dieses
Schaltnetz berechnet.
Und diese Werte sind gerade die Werte von Schaltfunktionen.
Also Schaltfunktionen, also diese Fi, sind jeweils Abbildungen von B
hoch N nach B.
Das sind jeweils zweiwertige Funktionen und M von denen geben wir
gerade diese M verschiedenen Ausgaben, die ich dort produzieren
möchte.
Ich kann damit Funktionen darstellen durch ein Schaltnetz.
Man nennt solche Schaltnetze kombinatorisch in ihrem Verhalten, weil
sie nur darauf reagieren, welche Werte an den Eingängen angelegt
werden.
Es ist nicht abhängig davon, was vorher einmal dort angelegen hat.
Also diese Schaltnetze haben kein Gedächtnis.
Wenn Sie mehrfach nacheinander die gleichen Eingangskombinationen
anlegen, bekommen Sie immer das gleiche Ergebnis raus.
Das ist ein kombinatorisches Verhalten.
Im Gegensatz zu einem sequentiellen Verhalten, das werden dann die
Schaltwerke, die ein Gedächtnis haben und dann also unterschiedlich
reagieren können, auch wenn sie die gleichen Eingaben reinlegen.
Also das ist Wert an den Ausgängen nur abhängig von denen an den
Eingängen und das F, dieses kleine F hier von A, ist also die
Zusammenfassung von M Schaltfunktionen.
Das Ganze können wir sehr schön darstellen für Schaltnetze.
Also alle elementaren Schaltgatter sind natürlich insbesondere
Schaltnetze.
Ein Halbadierer ist ein einfaches Schaltnetz, das ein bisschen
komplizierter ist.
Da wollen wir nämlich Zweiwerte berechnen.
Also ein Halbadierer ist eine Komponente, die kann aus zwei Bits zwei
andere Bits produzieren, und zwar die Summe, das ist also dieser Wert
hier, und den Übertrag von zwei Bits, wenn wir die addieren.
Also wenn wir hier die A und B addieren, kommt immer dann eine 1 raus,
wenn wir eine 1 dort jeweils haben, wenn A oder B jeweils 1 sind.
Wenn beide 1 sind, kommt eine 0 raus, weil wir einen Übertrag
bekommen, da haben wir den einzelnen Übertrag mit einer 1.
Das heißt, das Summenbit ist eigentlich genau die XOR-Funktion, die
ich Ihnen gerade eben schon vorgestellt habe, und der Übertrag ist
eigentlich gerade unsere Konjunktion A und B.
Ist 1, wenn die beiden Werte 1 sind.
Das Ganze kann ich als Schaltnetz darstellen.
Ich habe also ein Schaltnetz, da gehen diese zwei Eingänge rein, A und
B, das sind unsere Eingänge, und die Ausgänge sind Ü und S, ist also
hier nicht von links nach rechts, wie auf dem Fotofolio, sondern von
oben nach unten dargestellt.
Und ich habe jetzt also einmal das UND-Gatter, das entspricht diesem
Ausdruck, und ich habe ein XOR-Gatter, da steht jetzt wieder 2k plus
1, ich hätte auch gleich 1 reinschreiben können, das ist also das XOR
der beiden Werte, und da kommt dann der Summenwert raus.
Und jetzt kann ich daraus ein Symbol machen, ein Schaltnetz-Symbol,
das ist jetzt der Halbadierer HA.
Das kann ich mir auch angucken im X-Wizard, weil Herr König da ist,
will ich immer Freude machen und den X-Wizard aufrufen.
Ich habe Ihnen ansonsten immer gesagt, das können Sie gerne zu Hause
machen, da habe ich keine Zeit für.
Hier sehen Sie also jetzt diese Schaltung, dieser Halbadierer, und Sie
sehen hier unten ein Skript, wie Sie also diesen Halbadierer
tatsächlich dort entwerfen können.
Das heißt, Sie bekommen dann eine PDF-Zeichnung, eine grafische
Darstellung einer Schaltung, die Sie hier in diesem Skript auch
entsprechend beschreiben können.
Das ist im Prinzip eine Hardware-Beschreibungssprache, die wir dort
zur Verfügung haben, um solche Schaltnetze zu beschreiben.
Wie man das genau macht, das kriegen Sie alles im X-Wizard mit und in
den Übungen, das können Sie sich genauer angucken.
Ich werde also den X-Wizard hier im Wesentlichen sagen, machen Sie das
in den Übungen.
Ich zeige Ihnen hier etwas mit Logiflash, weil ich da ein bisschen
mehr mit rumspielen kann.
Die Simulationsfunktion ist im PDF-Fall so nicht verfügbar, das geht
halt nur mit Logiflash oder Java.
Okay, also das ist ein einfacher Halbadierer.
Wenn es einen Halbadierer gibt, dann fehlt da irgendwas.
Was fehlt hier gegenüber dem, was wir bei einem Addierer eigentlich
brauchen?
Wenn wir jetzt eine mehrstellige Zahl haben, dann brauchen wir
natürlich einen Volladdierer.
Warum ein Volladdierer?
Wenn wir jetzt hier zwei Zahlen 0, 1, 1, 0 haben und meinetwegen hier
0, 0, 1, 1.
Wenn Sie die beiden addieren, dann haben Sie hier natürlich eine 1,
dann haben Sie hier eine 0 und Sie wissen, Sie brauchen Übertrag 1.
Dann haben Sie hier auf einmal drei Zahlen, die Sie addieren müssen.
Dann haben Sie hier nochmal eine 0 und dann haben Sie hier wieder eine
0 und Übertrag nochmal 1 und dann haben Sie hier die 1.
Das heißt, Sie brauchen drei Werte, die Sie addieren können.
Der Volladdierer, der also geeignet ist, um eine Summe von größeren
Zahlen tatsächlich zu berechnen, der muss in der Lage sein, drei Bits
geeignet zu verknüpfen und muss daraus Summe und Übertrag berechnen.
Und in dem Fall ist dann die Summe, das ist hier dieser Eintrag, die
Summe, das hatte ich Ihnen genau ja schon als Schaltung vorher
vorgestellt, als wir die BDDs betrachtet haben, ist dann das XOR
dieser drei Werte A, B und Ü.
Und der Übertrag, der hier rauskommt, das Ü' ist dann entsprechend die
Disjunktion dieser drei Konjunktionen.
Das heißt, der Übertrag ist 1, wenn mindestens zwei dieser drei
Eingabewerte 1 sind.
Und das ist dann entsprechend, wenn man sich nur diese Bool'schen
Ausdrücke anschaut, dann ist das die Vorlage, um eine Schaltung
tatsächlich zu bauen.
Deswegen die Bool'schen Ausdrücke brauche ich als Vorlage, um
tatsächlich Schaltnetze zu konstruieren.
Die zeigen mir, wie ich das machen muss.
Das kann ich nämlich genau umsetzen.
Ich habe hier also die drei Konjunktionen, jeweils diese drei
Konjunktionen von A, B, A, Ü und B, Ü und muss die ganzen disjunktiv
verknüpfen.
Das habe ich hier also ein Oder-Gatter mit drei Eingängen gemalt und
die anderen muss ich die drei Werte auch noch mit einem XOR
verknüpfen.
Sie haben eine Frage?
Noch nicht so ganz.
Also, warum 2k plus 1?
2k plus 1 soll nur heißen, dass wir ein XOR berechnen.
Und das XOR liefert eine 1, wenn wir eine ungerade Anzahl von Einsen
bei den Eingängen haben.
Bei einem zweiwertigen XOR wäre das eine 1 und der andere muss 0 sein.
Bei einem dreiwertigen XOR, also bei einem XOR für drei Eingänge, kann
ich also eine 1 haben oder drei Einsen.
Wenn ich ein siebenstelliges XOR hätte, dann dürften 1, 3, 5 oder 7
Eingänge 1 sein und ich müsste eine 1 rauskriegen.
Aber wann immer das 0, 2, 4 oder 6 sind, die Einsen sind, dann würde
ich eine 0 rausbekommen.
Das soll einfach nur andeuten, eine ungerade Zahl der Eingänge ist 1.
Dann muss der Wert 1 sein.
Deswegen 2k plus 1.
Und bei dem zweiwertigen XOR oder bei dem XOR mit zwei Eingängen, da
kann ich eben auch gleich 1 draufschreiben, weil dann genau einer der
beiden Eingänge 1 sein soll.
Okay, das war jetzt hier unser Volladdierer und den kann ich Ihnen
natürlich auch mit der Logiflash-Animation zeigen.
Ich habe jetzt hier noch Logic-SIM mit angegeben.
Auch den kann ich tatsächlich, dieses Logic-SIM kann ich auch bauen.
Ich will das mal ganz kurz, das zeige ich Ihnen beide Sachen.
Das ist jetzt eine Alternative.
Nachdem ich letzte Woche diese Probleme festgestellt hatte, jetzt
funktioniert das hier nicht.
Das ist wirklich ärgerlich.
Ich habe es gestern Abend probiert, ich habe das Ding anscheinend an
irgendeiner anderen Stelle abgelegt, sodass ich es jetzt hier nicht
richtig aufrufen kann.
Tut mir leid, es hat gestern Abend noch funktioniert.
Installieren Sie sich das Logic-SIM einfach selber, dann können Sie
sehen, wie Sie damit Schaltungen bauen können.
Das geht relativ einfach, ist ein bisschen andere Oberfläche als bei
Logiflash.
Ich gehe dann lieber jetzt, um keine Zeit zu verlieren, auf das
Logiflash wieder und zeige Ihnen, wie dann dieser Volladdierer
tatsächlich aussieht.
Dazu muss ich mir den hier wieder aufrufen, da habe ich ihn gestern
Abend noch schnell gebastelt.
Ja, ja, ja, ja, danke, danke, danke, danke.
Ja, ja, ja, das ist ja gar nicht gut.
Machen wir hier schnell ein Cancel.
So, danke.
So ist das, wenn man schnell irgendwo raufklickt, kann man auch einen
Fehler machen und schon ist alles weg.
Das wäre ja furchtbar.
Also, jetzt den Volladdierer, den lade ich jetzt und hier sehen Sie
ihn.
Das ist also jetzt genau dieser Volladdierer, ich habe ihn etwas
gekippt.
Hier wieder von links nach rechts haben wir also wie auf der ersten
Folie für so ein Schaltnetz, haben wir jetzt hier links die Eingänge,
rechts die Ausgänge.
Und jetzt wollen wir mal gucken, was da passiert.
Sie sehen, ich habe jetzt hier einfach kein dreiwertiges XOR genommen
oder ein dreiwertiges Oder, sondern ich sage immer zweiwertig.
Zweiwertig sind sie alle, die haben zwei verschiedene Werte.
Die XORs mit zwei Eingängen oder mit drei Eingängen, die mit drei
Eingängen habe ich nicht verwendet und das Oder mit drei Eingängen
nicht verwendet, sondern ich habe das aus den entsprechenden Gattern
mit zwei Eingängen, also die zweistelligen Operationen habe ich
genommen.
Nicht die endstelligen, sondern die zweistelligen und aus denen jetzt
jeweils das zusammengebaut.
Das heißt, ich habe hier aus den zweistelligen XORs jetzt das
insgesamt gebaut, die drei Werte A, B und Ü entsprechend hier
verknüpft.
Ich habe die Beschreibungen A, B und Ü nicht herangeschrieben.
Hätte ich auch noch machen können, dann hätte ich hier irgendwo noch
ein Textbutton machen müssen.
Das würde ich jetzt hier hinsetzen und könnte jetzt zum Beispiel hier
in diesen Text, da könnte ich jetzt schnell noch reinschreiben, dass
das hier meinetwegen jetzt, das wäre das Ü da oben.
Dann hätte ich da noch ein Ü herangeschrieben.
Geht also ganz einfach, sowas noch zu verändern.
So, jetzt will ich das Ganze Ihnen zeigen, was passiert, wenn ich hier
also jetzt einen Bit 1 hätte, dann würde also jetzt bei einem Bit 1,
die anderen beiden 0, ist die Summe eine 1.
Das steht da schon mal richtig.
Der Übertrag ist natürlich noch 0.
Wenn ich ein zweites Bit auf 1 setze, dann ist der Summen-Bit
natürlich eine 0.
1 und 1 gibt 0 und der Übertrag ist entsprechend eine 1.
Wenn ich alle 3 auf 1 setze, dann sehen Sie, habe ich jetzt wieder als
Summen -Bit eine 1.
Und jetzt sind also fast alle Leitungen auf 1.
Hier oben die eine Leitung nicht, aber diese hier gibt da hinten eine
1 ran.
Und deswegen sind jetzt Summe und Übertrag beide eine 1.
Entsprechend kann man damit rumspielen und eben Erfahrungen sammeln im
Schaltungsentwurf.
Sie erinnern sich, letztes Mal habe ich eine Schaltung gebaut, das war
nicht die richtige und ich habe sofort gemerkt, als ich da bei den
Eingängen gespielt habe, dass das falsche Ergebnis rauskam.
Also so können Sie in den Übungen damit auch rumspielen.
Das also zu diesem Logiflash, Sie können auch das Logixim einsetzen,
geht im Prinzip ähnlich, aber ist nicht ganz so schön von der
Nutzbarkeit her.
Hat also nicht ganz so viele Funktionen wie das Logiflash.
Dann gehen wir jetzt wieder zurück zur Präsentation.
Das nächste, was wir jetzt bauen aus dem Volladdierer, das war jetzt
ein Bauteil, jetzt setzen wir einfach mehrere solche Volladdierer
zusammen.
Jetzt haben wir also hier N Volladdierer und wir wollen mit denen
jetzt in der Lage sein, zwei Zahlen zu addieren.
Das heißt, wir wollen gerne die Zahlen A und B addieren, die jeweils N
Bits haben und möchte also die Summe ausrechnen, die dann besteht aus
diesen Summenbits, S0 bis S1-1 und eventuell noch einem Übertrag in
die nächste Position.
Das wäre eben, wenn wir einen Überlauf haben, also wenn Sie eine 8-Bit
-Logik haben und Sie eine Zahl, die größer ist als 256 oder 255,
bekommen Sie da einen Übertrag.
Und das wäre dann eine Bereichsüberschreitung, wenn Sie nur 8-Bit
-Zahlen hätten.
Sowas können Sie in Ihrem Programm, in Java, rufen Sie sowas ab,
können Sie als Exception dann entsprechend abrufen, wenn Sie eine
Bereichsüberschreitung haben.
Das kennen Sie aus der Programmierung.
Das steckt dahinter, dass Sie dann hier ein solches Signal bekommen.
Wir werden später noch sehen, welche konkreten Dinge man als
Exceptions dann im Prinzip abrufen kann, die wir hier in der Hardware
tatsächlich erzeugen.
So, das Problem ist, Sie haben hier eine lange Schaltzeit.
Warum kriegt man hier eine lange Schaltzeit?
Wir werden das gleich sehen.
Es kann ja sein, dass das Bit, das ganz rechts eingegeben wird, dass
das eine Auswirkung hat, dass dadurch, dass ich hier eine Zahl
addiere, auf einmal ein Übertrag entsteht, der dann dort auch einen
Übertrag produziert.
Das heißt, hier kommt dann eine Eins hin, da kommt da eine Eins hin,
da kommt da eine Eins hin usw.
Und das Ganze am Ende kommt hier der letzte Übertrag 1.
Und das dauert natürlich entsprechend den Schaltzeiten dieser
einzelnen Elemente.
So, ich zeige Ihnen das ganz kurz.
Ich könnte Ihnen das hier zeigen.
Ich zeige Ihnen aber das mit... ja, ich mache das gleich.
Also, ich zeige Ihnen erstmal eine kurze Bemerkung.
Wenn man jetzt diesen Ripple-Carry-Addierer aufbaut, dann kann man den
so aufbauen, wie ich das hier gesagt habe.
Dann haben Sie eine lineare Addition, eine sequenzielle Addition, die
in Linearzeit läuft.
Das heißt, da würde die Addition von 2,64 Bit zahlen doppelt so lange
dauern, wie eine Addition von 2,32 Bit zahlen.
Wäre natürlich schlecht.
Wenn Sie einen 64-Bit-Rechner haben, dann soll der eigentlich
schneller sein oder mindestens genauso schnell wie der 32-Bit-Rechner.
Sie haben sich einen leistungsfähigeren Rechner gekauft.
Wenn daher jetzt die Operationen alle doppelt so lange dauern wie
vorher, wäre das natürlich ein deutlicher Nachteil.
Das möchte man nicht.
Also muss man sehen, dass man eine Addition irgendwie in einer Zeit
hinbekommt, die unabhängig ist von der Anzahl der Bits.
Wie kann man das denn schaffen?
Eine Möglichkeit ist, dafür ein Prinzip zu nutzen, das man Pipelining
nennt.
Da komme ich gleich drauf.
Da macht man nämlich folgendes, dass man hier in der Lage ist, einfach
hier ein Verzögerungsglied einzubauen.
Wenn ich hier jeweils ein Verzögerungsglied einbaue, dann kann ich
einen A-Takt einbauen und sagen, ich lasse erstmal die ersten beiden
Bits addieren.
Dann wird hier ein Übertrag erzeugt und den gebe ich erst im nächsten
Takt weiter.
Und dann kommen erst diese beiden Bits, also diese beiden, die waren
hier zunächst mal in Wartestellung, A1 und B1.
Und erst dann rauschen die da unten rein und dann wird hier addiert.
Und im nächsten Takt kommen die A2 und B2, die waren hier oben
irgendwie in Wartestellung, kommen zwei Takte später da rein.
Und dann wandern die so hier zeitlich versetzt, wandern die da durch
und wir bekommen zeitlich versetzt die Ausgaben.
Was ist das denn für ein Vorteil?
Jetzt habe ich noch ein Verzögerungsglied eingebaut, das heißt die
Addition dauert noch länger.
Der Vorteil ist aber, dass ich in dem Augenblick, wo ich den ersten
Halbadierer hier genommen habe, also das erste Glied, und dort zwei
Bits addiert habe, der ist schon frei für die nächste Operation, wenn
er diese eine Addition gemacht hat.
Das heißt, ich kann sofort hier oben drüber A0' B0' eingeben für die
nächste Addition und habe dann hier die nächste Addition, die laufen
kann.
Das zeige ich Ihnen auf der nächsten Folie.
Ich zeige Ihnen das hier auf dieser Folie, den getakteten Ripple
-Carrier -Addierer, hier etwas angedeutet in dieser einfachen Form.
Und hier kommen jetzt die so zeitlich verschobenen Additionen da rein,
eine schwarze Addition, eine blaue, eine rote, eine grüne Addition.
Zeitlich so farbig markiert, dass Sie sehen, was da passiert.
Und ich habe jetzt hier jeweils Volladdierer genommen, das heißt, ich
brauche auch eine Eingabe, eine Übertragseingabe, deswegen mache ich
da zu Anfang 0 Überträge.
Wenn ich einen Nullübertrag habe, ist das gleich, als wenn ich einen
Halbadierer verwenden würde an der rechtesten Position.
Und jetzt mache ich die erste Addition.
A0' und B0' werden addiert auf die 0, das gibt dann unser erstes
Summenbit.
Dann kommt das Summenbit hier unten raus und der Übertrag geht zum
nächsten Element, da sind jetzt A1 und B1 der schwarzen Addition.
Und hier in dem ersten Halbadierer sind schon A0 und B0 der zweiten
Addition.
Und so geht das weiter.
Und hier habe ich eine Situation, wo alle vier Volladdierer
beschäftigt sind mit Additionen.
Alle sind aktiv, aber jeder Volladdierer ist beschäftigt mit einer
anderen Addition.
Der eine mit der schwarzen, das ist der hier, der mit der blauen, der
mit der roten, der mit der grünen.
Jetzt kann ich also auf diese Art und Weise in jedem Takt eine neue
Addition starten.
Das heißt, wenn ich viele Additionen nacheinander mache, dann habe ich
den Effekt, als würde ich für eine Addition nur so viel Zeit brauchen,
wie ein solcher Volladdierer braucht.
Und dann habe ich auf einmal die lineare Laufzeit für eine Addition im
Schnitt reduziert auf die Taktzeit eines Volladdierers.
Und das ist ein ganz elementares Prinzip, das man einsetzt.
Hier sehen Sie nochmal, wie das weiter durchrauscht.
Dann haben wir hier am Ende also das ganze Schema, das wir brauchen.
Wir haben hier die n aufeinanderfolgenden Takte, wo die Werte
eingegeben werden.
Unten sieht man das Ausgabeschema und wir haben hier von rechts noch
die Nullen, die wir eingeben.
Stellen Sie sich vor, Sie hätten längere Zahlen als 4-Bit-Zahlen.
Sie wollen jetzt 8-Bit-Zahlen addieren damit.
Dann würden Sie einfach hier oben eine weitere Addition machen.
Da würden Sie das Prinzip eingeben A4B4.
Hätte ich nur schwarz malen müssen.
Und Sie würden dann entsprechend hier den Übertrag von dort einfach
dort wieder eingeben.
Und dann hätten Sie im Prinzip eine Möglichkeit mit so einem 4-Bit
-Addierer auch 8-Bit-Zahlen zu addieren oder 12-Bit-Zahlen und so
weiter.
Sie müssten dann eben nur entsprechend sukzessive diese Blöcke von 4
-Bit -Zahlen durchschieben.
Das heißt, Sie hätten hier ein flexibles Gerät mit flexibler Hardware,
um auf unterschiedliche Art und Weise eine Addition zu beschleunigen.
Diese Beschleunigung ist etwas, was wir Pipelining-Prinzip nennen.
Ein Prinzip, das Sie kennen aus der Produktion, wird zugesprochen dem
Ford mit seinem T-Modell.
Neulich hörte ich bei der Jahrestagung Informatik einen Vortrag vom
aktuellen Präsidenten der Gesellschaft für Informatik.
Und der hat darauf hingewiesen, dass es etwa gleichzeitig mit dem T
-Modell auch den Tourneestuhl gab in Europa, in Deutschland.
Ich glaube, in Deutschland war das.
Also Deutschland oder Österreich.
Ich weiß nicht mehr genau.
Auf jeden Fall deutschsprachig.
Der Tourneestuhl wurde produziert als Massenfertigung.
Da wurden die Bauteile in Massenfertigung hergestellt und brauchten
nur mit zwei Schrauben flexiert zu werden.
Und da konnte man auf einmal 900.000 Stühle in einem Jahr produzieren,
was man in der handwerklichen Tätigkeit manuell niemals geschafft
hätte.
Das ist einfach Prinzip der Fließbandverarbeitung.
Da hat man mehrere Schritte gehabt.
Die Einführung der Fließbandverarbeitung ist nicht nur auf das T
-Modell von Ford zurückzuführen, sondern auch auf den Tourneestuhl,
der hier von einem Tischler entwickelt wurde.
Was ist der Effekt des Pipelining?
Das wäre die Ausführung in diesem Fall der Additionen ohne Pipelining.
Sie hätten jeweils N-Takte zu warten, bis Sie eine Addition ausführen
können und dann die nächste.
Das dauert sehr lange.
Wenn Sie Pipelining machen, dann sieht das Ganze so aus.
Da können Sie jeden Takt eine neue Addition starten und diese
Differenz hier ist genau die Taktzeit eines Volladdierers.
Das heißt, Sie haben auf einmal einen massiven Zeitgewinn, der sich so
ausdrückt, wenn Sie jetzt K-Berechnungen machen und Sie haben hier N
-Bezahlen, dann würden Sie, wenn Sie sich das hier anschauen, Zeit
brauchen K mal N.
Das ist die Anzahl der Bits und das ist die Anzahl der Berechnungen.
Wenn Sie das im Pipelining-Prinzip machen, wie viel Zeit brauchen wir
dann für K-Berechnungen?
Wir müssen K mal etwas eingeben, das sind K-Takte, und dann müssen wir
noch den Rest hier durchlaufen, das ist plus N-1.
Und das ist natürlich ein gewaltiger Unterschied, weil Sie auf einmal
den hohen Durchsatz haben und Sie können also sehr viele Berechnungen
laufen lassen.
Das ist übrigens das Geheimnis dahinter, dass unsere heutigen Rechner
so hohe Taktzahlen haben.
Sie haben einen Rechner, der hat irgendwie 3 Gigahertz Taktrate, der
kann keineswegs in einem Takt eine Operation ausführen.
Der braucht dafür eine ganze Reihe von Takten.
Aber er kann in jedem Takt eine neue Berechnung starten, eine neue
Operation, weil wir eine Fließbandverarbeitung in unseren Prozessoren
haben, die es uns erlaubt, in jedem Takt eine neue Berechnung zu
starten, es sei denn, Sie sind logisch voneinander abhängig, sodass
Sie warten müssen auf das Ergebnis einer Berechnung, bis Sie die
nächste anfangen können.
Da kommen wir später darauf zurück, wenn wir Rechnerarchitektur
machen.
Aber das ist also ein ganz wesentliches Prinzip, Pipelining-Prinzip,
Fließbandverarbeitung, setzt man an vielen Stellen ein in der
industriellen Fertigung.
Wenn Sie also solche gleichartigen Bauelemente haben, die nacheinander
oder gleichartigen Arbeitsstationen haben, die kleine Arbeitsschritte
ausführen, können Sie einen sehr hohen Durchsatz erzielen, auch wenn
die Gesamtzeit hier halt durchaus sehr groß sein kann.
Aber der Durchsatz wird hoch und das ist das Wesentliche.
Das also zum Pipelining-Prinzip, damit haben wir jetzt virtuell so
etwas wie konstante Zeit, aber tatsächlich dauert es doch länger.
Und Sie wollen nicht immer 100 Additionen nacheinander machen, sondern
Sie haben eben manchmal nur eine Addition zu machen.
Jetzt möchte ich die auch gerne schneller machen, von Linearzeit
irgendwie runterkommen.
Wie kriegt man das hin?
Eine Idee ist, den Standardansatz der Informatiker zu verwenden.
Ein Informatiker hat Angst vor großen Problemen.
Der sagt also, wenn ich so eine große Addition machen soll, ist mir
das viel zu schwierig, ich mache das lieber etwas kleiner.
Ich teile mein Problem auf und sage, ich gucke mir erstmal an, kann
ich denn das Ganze aufteilen in zwei Hälften.
Ich berechne also zwei Teilsummen.
Ich gucke mir einmal die rechte Seite an und die linke Seite.
Jetzt habe ich also A2 und B2, das ist die rechte Seite, die beiden
addiere ich, dann habe ich hier A2 plus B2 berechnet.
Es kann natürlich sein, dass hier ein Übertrag herauskommt.
Und jetzt berechne ich für die linke Seite aus dem A1 und B1, das sind
jetzt also die Hälften jeweils, das sind jetzt nicht einzelne Bits wie
vor, sondern das sind die Hälften.
Also hier steht jetzt, da steht das A1, das soll ein A sein, der
Strich ist wieder automatisch entstanden.
Und das ist hier unser A2.
Ich hätte auch links und rechts sagen können.
Also, jetzt habe ich hier zwei Summen berechnet.
Warum zwei Summen?
Ich berechne einfach gleichzeitig die Summe A1 plus B1 und die Summe
S1 plus 1.
Warum das?
Naja, ich brauche hier noch den Übertrag.
Wenn der Übertrag 1 ist, dann brauche ich für die endgültige Summe den
Wert S1 plus 1.
Wenn der Übertrag 0 ist, dann brauche ich den Wert S1.
Und das Ganze wähle ich einfach aus über ein Auswahlelement, das ist
ein sogenannter Multiplexer.
Und dieser Multiplexer, der wird gesteuert durch dieses Übertragsbit
und wählt aus für diese linke Hälfte, für diesen Teil hier, entweder
S1 oder S1 plus 1.
Und das heißt, ich habe jetzt gleichzeitig die beiden Hälften addiert,
brauche noch einen Schritt, um diese Auswahl zu treffen und bin
fertig.
Und das Ganze mache ich rekursiv, die Weide und Konkurrenz geht immer
rekursiv, das heißt, diese Addition hier läuft natürlich auch so, dass
ich sie wieder aufteile und entsprechend genau das gleiche Muster
einbaue.
Und wenn ich mir das anschaue, habe ich also ein großes Problem, oder
ich mache das jetzt mal andersherum, ein großes Problem, habe ich
jetzt, das ist mein großes Problem, teile ich auf in zwei kleine
Probleme und das wieder in kleinere Probleme und so weiter.
Sie kennen das, die Weide- und Konkurrenz-Prinzip, bis ich also ganz
runtergekommen bin und die Anzahl der Stufen bei einem Problem der
Größe n, wenn ich immer aufteilen kann in zwei Hälften, ist halt
gerade Log n.
Das heißt, ich muss genau Log n Stufen durchlaufen, alles, was in
einer Schicht ist, kann ich parallel machen.
Das heißt, meine Rechenzeit für die Addition ist auf einmal Log n,
logarithmisch in n.
Also für einen 32-Bit-Rechner brauche ich um zwei 32-Bit-Zahlen zu
addieren, wenn das genau Log n ist, fünf Stufen.
Wenn ich eine 64-Bit-Addition brauche, brauche ich sechs Stufen, eine
Stufe mehr.
Für einen 128-Bit-Rechner brauche ich entsprechend sieben Stufen und
so weiter.
Aber das ist eben eine Veränderung in der Rechenzeit, die ist nicht so
hoch.
Von linear auf logarithmisch ist das ein exponentieller Unterschied.
Und das heißt, das bringt mir eine gewaltige Verbesserung.
Eine Möglichkeit, die man ausführen kann, wird zum Teil auch
tatsächlich in Hardware genauso realisiert.
Additionen sind deswegen schnell ausführbar.
Das ist eine Möglichkeit.
Ich möchte Ihnen mal zeigen, dass es auch noch anders geht.
Das ist etwas, was man einen Carry-Look-Ahead-Adder nennt.
Nur, dass Sie sehen, Addition, das ist eine ganz einfache Aufgabe.
Läppisch haben Sie in der Schule gelernt, im Kindergarten gelernt, wie
man irgendwas addiert.
In der fünften Klasse spätestens konnten Sie binär addieren.
Das ist also gar keine große Schwierigkeit.
Und da soll so etwas Interessantes drinstecken.
Wir haben es schon gesehen, wir haben mal Pipelining kennengelernt am
Beispiel der Addition.
Wir haben jetzt den Divide-and-Conquer-Prinzip kennengelernt.
Jetzt schauen wir uns das noch mal ein bisschen genauer an.
Wenn ich zwei Zahlen addiere, also jetzt dieses 0, 1, machen wir mal
so, 0, 1, 1 zum Beispiel.
Dann habe ich, und hier addiere ich jetzt meinetwegen eine 0, 1, 0,
hier meinetwegen noch mal eine 1 und da das Ganze noch mal so drauf.
Was passiert jetzt?
Ich habe unterschiedliche Situationen.
Ich habe hier zwei Stellen, da steht eine 1, das steht hier auch.
Wenn ich mir nur diese Stelle angucke, dann weiß ich natürlich, ich
werde garantiert hier eine 1 hinbekommen als Übertrag.
Egal, was rechts daneben steht.
Weil ja 1 und 1 gibt einen Übertrag.
Und ich weiß auch, es wird garantiert aus dieser Situation bei den
beiden Nullen garantiert keinen Übertrag geben.
Das garantiert, der Übertrag daraus kommt 0.
Ich brauche hier nur vorne die beiden Nullen anzuschauen.
Aber ich weiß an dieser Position rechts daneben, da wird garantiert
ein Übertrag entstehen.
Und an dieser Situation hier mit 1 und 0, da weiß ich, naja, wenn
jetzt hier ein Übertrag 1 reinkäme, dann würde der weitergegeben
werden.
Also ein Übertrag Ü, der würde hier als Ü weitergegeben werden.
Weil nämlich 1 und 0 gibt 1 und Übertrag ist 0.
Wenn ich aber hier noch einen Übertrag 1 hätte, würde ich einen
Übertrag produzieren.
Das heißt, eine Situation, dass eine 0 und eine 1 addiert werden,
führt dazu, dass ein Übertrag von rechts nach links weitergeleitet
wird.
Die Situation 1,1 heißt, ich erzeuge einen Übertrag.
Und die Situation 0,0 heißt, ich absorbiere einen Übertrag.
Was uns jetzt interessiert, sind diese beiden Situationen hier.
Generate and Propagate.
Das heißt, ich habe jetzt eine größere Zahl und ich schaue mir das an.
Und ich habe meinetwegen für diesen Teil und für den Teil bereits ein
Generate and Propagate Signal erzeugt und hierfür auch ein Generate
and Propagate Signal.
Das heißt, ich weiß, für einen größeren Block erzeugt dieser Block
einen Übertrag 1 oder wird er einen weiterleiten.
Hier genauso, G und P steht für Generate und P für Propagate.
Nicht nur bezogen jetzt auf einen Bit, sondern auf den ganzen Block.
Und das Interessante ist, wenn ich diese Informationen verknüpfe zu
der Situation, die für den gesamten Block gilt, wie kann ich das
machen?
Ja, was ist denn, wann erzeugt denn, wenn ich nur G und P und G' und
P' hier betrachte, wann kommt denn dabei ein Übertrag garantiert raus?
Wenn ich hier links einen Übertrag produziere, dann wird doch
garantiert hier ein, da kann ich mich darauf beziehen, da wird ein
Übertrag entstehen aus dem Gesamten.
Wenn der linke Block einen Übertrag produziert, wird der gesamte Block
einen Übertrag produzieren.
Er wird aber auch einen Übertrag produzieren, wenn das G' 1 ist und
das Propagate-Bit hier auch 1 ist.
Das heißt, deswegen steht hier P und G'.
G' ist 1 und P ist auch 1, kommt da auch ein Übertrag nach links raus.
Und das Ganze wird einen Übertrag durchleiten von links nach rechts,
also wenn hier ein Übertrag reinkommt, wird er da links rausgegeben,
wenn beide Propagate-Bits 1 sind.
Jetzt habe ich also hier einen Ausdruck, um so zwei solche
Informationen über die Erzeugung und Weiterleitung von Überträgen zu
kombinieren.
Warum ist das interessant?
Das Weiterleiten der Überträge war ja gerade der Effekt, der dazu
führte, dass bei der normalen Addition wir eine lineare Laufzeit
haben.
Wir haben das bei dem Divide-and-Conquer-Ansatz schon gesehen.
Man kann diese Abhängigkeit durchaus ein bisschen aufbrechen.
Und hier sehen wir eine weitere Möglichkeit, die Information darüber,
wo ein Übertrag entsteht, kann man auch auf diese Art und Weise mit
solchen Operationen hinbekommen.
Das Interessante ist, dass diese Operation assoziativ ist.
Das dürfen Sie gerne sich selbst überlegen.
Fangen Sie das an, wenn Sie drei von denen kombinieren, kombinieren
Sie erst die ersten beiden und danach mal die anderen beiden.
Und Sie werden sehen, Sie kommen auf das gleiche Ergebnis.
Und assoziativ hat ja die wesentliche Eigenschaft, das hat man schon
gesehen, wir können statt einer solchen linearen Kette von Operationen
einen Baum aufbauen und also unsere Operationen so anordnen, dass wir
mit Log-N-Schritten und Log-N-Schichten die gesamte Operation
berechnen.
Das heißt, wir können den Gesamtübertrag, der uns interessiert, den
können wir berechnen über Log-N parallel ausgeführte Schritte.
Und damit können wir also wieder auf logarithmische Zeit kommen für
unsere Addition.
Weil wir diesen inneren sequentiellen Übertrag, die Berechnung,
aufspalten können durch diese Überlegung.
Nur, dass Sie sehen, was man alles machen kann mit so einer Addition.
Und dadurch haben wir logarithmische Zeit durch eine baumartige
Berechnung der Summe.
Das kann man für die Position hier ganz links machen und auch für alle
Positionen mittendrin und kann dann aus den G- und P-Informationen,
die man alle gleichzeitig berechnen kann für jede einzelne
Bitposition, kann man in logarithmischer Zeit die gesamten Summbits
berechnen.
Also das geht ja logarithmisch.
Und jetzt kommt noch ein Schritt, den man machen kann.
Das Interessante ist, ich kann auch wieder anders arbeiten.
Also Log-N ist mir viel zu lang.
Ich möchte gerne, wir hatten gesehen, bei Fließbandverarbeitung kann
ich auf konstante Zeit kommen.
Das ist nicht so, dass Herr König das nicht interessiert, aber der
kennt das alles schon.
Deswegen geht er einfach jetzt, weil er was anderes zu tun hat.
Also Carry-Safe-Adder, was ist das?
Das ist etwas ganz Wesentliches.
Sie haben Ihre zwei Zahlen.
Ich schreibe das mal hin.
A3, A2, A1, A0 und B3, B2, B1, B0.
Jetzt möchte ich gerne das Summbit berechnen.
Und ich berechne aber hier ein S0 und ein Ü0, den Übertrag.
Und ich berechne ein S1, S0 Strich, sage ich mal, ein S1 Strich, soll
das sein.
Und das wird ein S1 Strich und ein Ü1 Strich.
Ich berechne einfach an jeder Position das Summbit mit dem
Halbadierer, das Summbit und das Übertragsbit.
Das heißt, ich habe jetzt hier auf einmal zwei Zeilen.
Da habe ich jetzt hier eine S Strich Summe und hier habe ich, ich
schreibe das mal hier Ü Strich hin.
Das sind meine ganzen Überträge, die ich noch nicht durchgeleitet
habe.
Und das Interessante ist, ich kann jetzt die nächste Addition einfach
auf Zahlen ausführen, bei denen ich jeweils nicht die einzelnen Bits
durch eine Position dargestellt habe, sondern durch zwei Bits, durch
ein Summbit und einen gemerkten Übertrag.
Und diese Operation kann man jeweils an den einzelnen Positionen
parallel machen.
Dazu müsste ich Ihnen ein bisschen mehr etwas über Schaltnetze
erzählen, das habe ich jetzt nicht die Zeit für.
Aber das Interessante ist, dass ich in dieser internen Carry-Safe
-Darstellung, bei der ich die Überträge nicht durchlaufen lasse,
sondern jeder Position mir einfach nur merke, kann ich in konstanter
Zeit Additionen machen auf dieser Zahlendarstellung.
Das heißt, die Zahlendarstellung ist ganz wesentlich dafür, wie viel
Operationszeit oder wie viele Operationen ich machen kann zur gleichen
Zeit.
Das heißt, wie lange ich brauche, um eine Funktion zu berechnen.
Es gibt unterschiedliche Arten von Zahlendarstellungen.
Es gibt die Carry-Safe-Darstellung, es gibt noch eine redundante
Zahlendarstellung, bei der man die einzelnen Bits mit 1, 0 und –1
darstellt.
Dann haben Sie noch eine andere Darstellung, da können Sie auch in
konstanter Zeit addieren.
Sie müssen nur am Ende das Ganze wieder überführen in die normale
Zahlendarstellung und das dauert dann lineare Zeit in der Anzahl der
Bits.
Aber Sie können alle Operationen intern im Rechner in konstanter Zeit
machen.
Und überlegen Sie sich, Sie wollen multiplikation machen, Sie wollen
zwei Zahlen multiplizieren und da brauchen Sie, das hatte ich ja schon
mal Ihnen dargestellt, wenn Sie zwei Zahlen multiplizieren wollen,
dann müssen Sie ja sukzessive eine ganze Reihe von die einzelnen Bits
nehmen, um die andere Zahl damit zu multiplizieren und die müssen Sie
dann alle aufaddieren.
Da haben Sie, wenn Sie zwei endstellige Zahlen multiplizieren, müssen
Sie N-Additionen machen nacheinander und die können Sie intern alle
zum Beispiel in Carry-Safe-Darstellung machen und haben dann bei der
Multiplikation auf einmal wieder einen großen Zeitgewinn gegenüber der
naiven Implementierung, die Sie hätten, wenn Sie hier normale
Additionen machen würden.
Addierer oder Multiplizierer in Ihrem Rechner arbeiten häufig mit der
Carry -Safe-Darstellung.
Das ist also etwas, was man intern im Rechner verwendet, um in
konstanter Zeit addieren zu können.
In anderen Bauteilen wird man also den Ripple-Carry-Adder nehmen.
Ansonsten, die normalen Additionswerke sind häufig gerade die Carry
-Lucky -Addierer, die ich hier gerade gezeigt habe.
Also das ist die aktuelle Technik, wie man tatsächlich die Operationen
im Rechner realisiert, durch solche Bauteile.
Also Sie sehen, Addition ist eine ganz einfache Operation, aber hier
kann man genau die Prinzipien, die es gibt, um effiziente Algorithmen
zu entwerfen, die dazu führen, dass man in einer geringen Zahl von
Schritten interessante Operationen berechnen kann.
Die kann man hier sehr schön zeigen.
Okay, ich glaube, Sie haben eine kurze Pause verdient.
Danke.
So, ich denke, wir können weitermachen.
Nochmal kurz.
Also wir haben damit gesehen, dass man eben bei der Addition durch ein
bisschen Überlegungen in der Lage ist, von linearer Zeit
runterzukommen auf konstante Zeit, also durch Fließbandverarbeitung,
dann hat man halt den Durchsatz einfach erhöht, oder eben tatsächlich
auf logarithmische Zeit, wenn wir intelligente Verfahren anwenden, um
zu addieren, entweder durch Carry Safe oder durch Carry Lookahead
-Addierer.
Und wir können mit einer anderen Zahlendarstellung intern sogar noch
stärker reduzieren auf konstante Zeit und die einzelnen Berechnungen
in konstanter Zeit ausführen.
Ein deutlicher Fortschritt gegenüber dem, was man hätte, wenn man
einfach nur ein Addierer bauen würde.
Okay, jetzt kommen wir damit zum nächsten Punkt.
Nämlich, wir wollen nicht nur kombinatorische Schaltnetze bauen, wir
wollen auch im Rechner etwas speichern können.
Das heißt, wir brauchen Schaltwerke.
Was habe ich bei einem Schaltwerk?
Da habe ich eine etwas kompliziertere Geschichte.
Ups, das war jetzt etwas zu schnell.
Ich habe also jetzt ein Schaltnetz, das hier immer noch drin steht,
aber diesem Schaltnetz werden zwei Funktionen realisiert.
Einerseits eine Funktion f und dann eine Funktion g. Und ich habe
nicht nur n Eingaben, sondern ich habe n plus r Eingaben in dem Fall.
Und ich habe also hier die externen Eingaben a1 bis an und ich habe
dann noch interne Eingaben z1 bis zr.
Das sind meine Zustandseingaben, die repräsentieren also den Zustand
eines Schaltwerkes.
Und raus kommen am Ende irgendwelche Ausgaben, meine f1 bis fm, aber
eben auch neue Werte für diese Zustände, die ich mir merke.
Und die werden durch die Funktion g berechnet.
Also g von b hoch n Kreuz r auf b hoch r.
Da wird ein neuer Zustand berechnet.
Und wir haben damit also die beiden Funktionen hier drin, f und g. Wir
haben also einerseits eben hier auch diese Rückführung.
So, damit können wir jetzt sagen, wir haben also, vielleicht ist hier
noch mal drauf zu sehen, das ist nochmal dieses Bild.
Wir haben also das Schaltnetz für die berechneten beiden Funktionen f
und g, die sind also beide hier drin, das f und das g. Und wir haben
außerdem Verzögerungsglieder hier oben, um diese Werte für z1 bis zr
zu verzögern.
Wenn das zu schnell laufen würde, dann könnte es ja zu schnell hier
irgendwelche Veränderungen geben.
Deswegen haben wir hier so ein Verzögerungsglied.
Darauf gehen wir gleich noch etwas genauer ein.
Das Wesentliche ist eben, dass ich etwas, was ich früher gemacht habe,
wieder zurückgespielt bekomme für die Dinge, die ich als Nächstes
mache.
Also wenn ich hier die gleichen Werte eingebe an der linken Seite
nacheinander, dann wird das Ergebnis, was hier rauskommt, eventuell
unterschiedlich sein, je nachdem, was meine Funktion g hier als
Zustand sich gemerkt hat.
Das ist also ein Schaltwerk.
Und das muss sich sofort erinnern an etwas, was wir bei den Dingen zu
Beginn der Vorlesung gemacht haben.
Moor- und Milliautomaten sind genau Modelle für solche Schaltwerke.
Wir haben hier in jedem Takt im Prinzip eine Ausgabe, die abhängt von
der aktuellen Eingabe und dem aktuellen Zustand, kommt die Ausgabe
raus und es wird ein neuer Zustand berechnet, auch abhängig von
Eingabe und Zustand.
Also im Prinzip die Realisierung eines endlichen Automaten.
In diesem Fall wäre das ein Milliautomat, den wir hier darstellen.
Das ist also ein solches Schaltwerk.
Also im Prinzip entspricht das genau dem, was wir vorher als
Milliautomat genannt haben oder bezeichnet haben.
Das senkrechte Strich ist dummerweise wieder entstanden hier.
Und hier ist das Verhalten eben nicht kombinatorisch, sondern
sequentiell, weil wir eben die Information aus dem Teil davor einfach
hier uns merken können.
Und ein solches Schaltwerk nennen wir jetzt stabil, falls G von A, Z
gleich Z ist.
Der Zustand ändert sich gar nicht bei dieser Eingabe A.
Dann haben wir also eine Rückführung ohne Verzögerungsglieder.
Das Ganze bleibt stabil.
Wenn aber das G von A, Z ungleich Z ist, wenn sich der Zustand ändert,
dann ist es wichtig, dass man diese Verzögerungsglieder hat.
Und das zeige ich Ihnen jetzt an einem Beispiel.
Nämlich, Sie sehen hier zwei Schaltungen.
Und wir werden uns die jetzt einfach mal anschauen, was passiert, wenn
man die tatsächlich realisiert.
Also, Sie haben hier diese Schaltungen.
Na, wo sind sie?
Da muss ich jetzt wieder auf das Richtige klicken, die aufrufen.
Das wäre, genau, habe ich schon Taktgeber genannt.
Laden wir die mal rein.
Das sind die beiden Schaltungen, die wir gerade eben gesehen haben.
Und die sind hier jetzt so angegeben.
Wir haben also jetzt bei dem oberen, da haben wir also ein NAND.
Dann habe ich hier ein Verzögerungsglied eingebaut, damit man ein
bisschen was sehen kann gleich.
Und warum haben wir hier am Ende eine leuchtende Lampe?
Warum ist dort eine Eins am Ausgang?
Weil wir hier an dem UND-Gatter haben wir eine Null und eine Eins.
Weil es ein NAND ist, das heißt, das Ganze bekommt den Bit 1, wenn
hier vorne mindestens eine, also das Ganze wird eine Eins, wenn vorher
unser AND eine Null gegeben hätte.
Und die Null haben wir beim AND, wenn wir eben nur eine Eins haben,
also nicht zwei Einzelnen haben.
Also zwei Einzelheiten in dem Fall, dann müsste hier vorne eine Null
rauskommen bei dem NAND.
Jetzt schalte ich einfach mal, wenn ich also dieses Eingabe-Element
auf Eins schalte, was müsste passieren?
Wenn ich das auf Eins schalte, dann habe ich hier zweimal eine Eins an
dem NAND-Gatter.
Dann kommt da eine Null raus.
Okay, machen wir das doch mal.
Und Sie sehen, ja, kommt eine Null raus.
Und jetzt wird die Null natürlich weitergegeben.
Das heißt, kurzzeitig haben wir jetzt hier eine Null und dann wieder
eine Eins.
Und abhängig davon ändert sich immer der Wert am Ausgang.
Das heißt, ich habe hier eine Schaltung gebaut, da habe ich einmal
eine Eingabe gemacht, eine Eingabe Eins, und am Ende, hinten, bekomme
ich hier so ein pulsierendes Signal.
Und das leuchtet gerade oder blinkt in der Frequenz, die ich hier bei
den Verzögerungsgliedern eingestellt habe.
Ja, ansonsten würde das viel zu schnell gehen, wenn ich das da nicht
drin hätte.
Und wenn ich das wieder auf eine Null schalte, dann ist er
ausgeschaltet, dann habe ich also hier ein konstanter Eins am Ende
stehen.
Das heißt, auf die Art und Weise kann ich zum Beispiel einen Takt
geben, wenn ich eine Schaltung habe, eine größere, die sind
normalerweise alle getaktet, dann kann ich die mit einem Takt
versorgen.
Und wenn die nichts tun soll, dann höre ich auf, denen ein Taktsignal
zu geben.
Dann brauche ich nur diesen einen Wert zu verändern und ich habe ein
konstantes Signal und es passiert nichts mehr in dem Bereich.
Diese Technologie setzt man ein, um sogenannte Low-Power-Schaltwerke
oder Low-Power-Hardware zu bauen, bei denen man gewisse Bereiche
abschalten kann, wenn sie nicht gebraucht werden.
Kann man auf diese Art und Weise realisieren.
Was passiert, wenn ich mir diese Schaltung angucke hier unten?
Bei der anderen, da habe ich jetzt das NAND durch einen Oder-Gatter
ersetzt.
Das Oder-Gatter in diesem Fall sieht etwas anders aus oder führt zu
einer anderen Reaktion.
Wenn wir hier zwei Nullen haben, kommt natürlich eine Null raus und
ist am Ende auch eine Null.
Wenn ich jetzt das Ganze auf 1 setze, dann habe ich eine 1 hier vorne
gesetzt, das Ergebnis ist eine 1, äußert sich hier durch die
leuchtende Lampe und der Wert wird zurückgegeben und jetzt habe ich
hier vorne an dem zweiten Eingang auch eine 1 stehen.
Und wenn ich jetzt das Ding hier auf 0 setze, ist die 1 ja immer noch
da.
Das heißt, ich kann jetzt hier 0 oder 1 setzen, das interessiert
niemanden mehr.
Diese Schaltung hat immer den Wert 1.
Wenn ich einmal sie eingeschaltet habe mit einer 1, bleibt sie auf
diesem Niveau.
Das ist Schaltverhalten, bei dem ich Werte zurückführe auf Eingänge
von vorne und dadurch mir merken kann, was vorher passiert ist.
Insofern sehen Sie hier oben, das war der Beispiel eines instabilen
Netzes, ich ändere also die Eingabe gar nicht, für die Eingabe 1 ist
der Zustand, den ich hier darstelle durch die Lampe, den gebe ich
praktisch direkt aus, ändert sich der Zustand ständig, obwohl ich hier
die Eingabe gar nicht verändere.
Und wenn ich hier unten das anschaue, da habe ich ein stabiles
Netzwerk, ein stabiles Schaltwerk, weil der Zustand sich nicht mehr
ändert.
Da kann ich 0 oder 1 eingeben, der Zustand in dem Fall, der ändert
sich dadurch nicht, der bleibt konstant.
Das also zu diesem Beispiel, das Sie hier gesehen haben, das sind die
beiden Schaltungen und was Sie also sehen, ist, dass es darauf
ankommt, sich anzuschauen, wie sich so ein Schaltverhalten zeitlich
darstellt.
Das ist nämlich so, wenn ich mir so ein Schaltverhalten hier aufmale,
dann kann es sein, dass ich eben mal einen Wert 0 habe und dann soll
der Wert 1, der Wert 1 kommen heißt, ich habe hier irgendwann den Wert
1.
Da muss ein elektrisches Potenzial auf eine höhere Spannung gesetzt
werden, das dauert eine Weile.
Dann habe ich hier die höhere Spannung und dann irgendwann geht das
wieder runter, dann habe ich den Wert 0.
So, wann schaue ich eigentlich darauf, welchen Wert ein bestimmtes
Element hat?
Also hier habe ich den Wert 0, da habe ich den Wert 1 oder 5 Volt, je
nachdem wie man das benennt, das sind meine beiden interessanten
Potenziale.
Dann habe ich irgendwelche Zwischenwerte, die interessieren mich
eigentlich gar nicht.
Ich muss also zu bestimmten Zeitpunkten mir anschauen, welche Werte
die relevanten Punkte in meinem Schaltnetz haben.
Und deswegen macht man das Ganze so, dass man sich überlegt, wann man
den Schaltwerkszustand beobachten will, nämlich dann, wenn sich die
relevanten Punkte stabilisiert haben auf einen bestimmten Wert.
Und das macht man so, dass man dann einen zeitlichen Rhythmus von
außen vorgibt, das werden dann synchrone Schaltwerke und die sehen
dann so aus, dass ich Taktzeitpunkte habe.
Das heißt, ich habe dann solche Taktzeitpunkte hier in blau angegeben
und ich kann immer, wenn das Ding 1 ist, kann ich hier betrachten,
welchen Wert bestimmte Punkte in meiner Schaltung haben.
Und dann habe ich entsprechend die Möglichkeit, zu bestimmten
Zeitpunkten mir anzuschauen, was hier passiert.
Das also zu diesen Taktzeitpunkten, ich habe eine Taktzeit zwischen,
also ich habe immer eine gewisse Zeitspanne zwischen dem Auftreten der
1, das sind meine Taktzeiten.
Ich habe also eine gewisse Zeit zur Verfügung, um irgendwelche
Veränderungen vorzunehmen.
Die Zustandsänderungen erfolgen während der Taktzeiten und ich
beobachte zu bestimmten Zeitpunkten.
Sie wissen, dass kein System zu einem Zeitpunkt, also wenn ich hier
einen Punkt betrachte, kann ich keine Veränderung feststellen, kann
ich nur einen Zustand messen.
Wenn ich aber zwei Zeitpunkte betrachte, kann ich eine Veränderung
zwischen diesen beiden Zeitpunkten mir anschauen.
Oder wie gesagt, ich beobachte nur zu diesen Zeiten.
Wenn ich also dort und dort betrachte, dann habe ich hier für mein
rotes Signal dann unterschiedliche Werte festgestellt.
Sie können, wenn Sie etwas beobachten zu einem Zeitpunkt, nur einen
Zustand messen.
Wenn Sie eine Folge von Zustandsmessungen gemacht haben, können Sie
daraus auf die Veränderungen im System schließen.
Aber Sie können niemals zu einem Zeitpunkt eine Veränderung messen.
Sie können nur feststellen, eine Veränderung gegenüber einem früheren
Zeitpunkt.
Okay, das ist also das, was man macht.
Wir haben dann hier diese Takte und jetzt wollen wir ein Schaltwerk
takten.
Jetzt wird auf einmal dieses Verzögerungselement, was wir dort haben,
mit einem Takt versehen.
Ich möchte also erreichen, dass Werte, die hier ankommen, dort erstmal
aufgehalten werden und danach weitergehen, wenn ich hier diesen Takt
vorgebe.
So etwas kennen Sie aus einer ganz anderen Technik.
Stellen Sie sich vor, Sie haben einen Fluss oder einen Kanal und wenn
wir das von oben angeschaut...
und hier fährt also jetzt irgendein kleines Schiff.
Das möchte gerne hier hin.
Das kommt von hier und das möchte gerne dahin, damit wir die gleiche
Flussrichtung haben wie auf dem Bild da unten.
Wenn ich das in der Höhenlinie anschaue, sieht es so aus, dass ich
hier...
dieser senkrechte Strich soll jetzt nicht kommen, aber ich hoffe, dass
hier sollte ein senkrechter Strich kommen.
Und da kommt schon wieder einer.
Das ist wirklich sehr ärgerlich, diese ewigen Striche.
Sie wissen, dass ich mich jedes Mal darüber ärgere.
Und der sollte auch nicht da sein.
Versuchen wir es nochmal, das gut zu malen.
Also hier ist ein Schiff.
Hier habe ich jetzt mein Höhenlinienprofil.
Da habe ich jetzt einen Unterschied in der Höhe.
Wie macht man das bei einem Kanal?
Man baut einfach eine Schleuse ein.
Und ich lasse einfach das Schiff hier reinfahren.
Dazu mache ich diese Schleusentore auf.
Ich lasse das Schiff da reinfahren, mache die wieder zu.
Und dann lasse ich das Wasser raus, mache diese Tore auf und lasse das
Schiff rausfahren.
Das heißt, jetzt brauche ich aber nicht nur ein Signal, um das Tor
aufzunehmen.
Ich brauche noch ein zweites Signal, um das zweite Tor dann erstmal
noch zuzulassen und dann das aufzumachen, wenn das andere zu ist.
Wenn ich nämlich hier auf einmal ermöglichen würde, dass ein Wert von
hier nach dort durchrauscht, dann hätte ich ja für einen gewissen
Zeitraum eine Rückkopplung hier ganz rüber und ich hätte eine Dynamik
drin, die ich gar nicht haben möchte.
Ich möchte nur den Wert, der hier vorne anliegt, geordnet weitergeben,
zu einem gewissen Zeitpunkt weitergeben oder ab einem gewissen
Zeitpunkt weitergeben an den Eingang hier vorne.
Und deswegen brauche ich dafür zwei Ereignisse.
Ich muss das erstmal aufnehmen, mein Schiff oder meine Daten oder mein
Signal und dann muss ich in der Lage sein, das weiterzugeben, aber ich
darf dabei das Niveau hier nicht verändern.
Also deswegen brauche ich hier eine solche Realisierung eines Taktes.
Und wir werden das später sehen, wenn wir uns mit der physikalischen
Realisierung von Schaltnetzen beschäftigen, dass wir mit Transistoren
genau solche Bauteile tatsächlich erstellen können, die diese Auf- und
Zusystematik, diesen Schleuseneffekt genau realisieren können.
Also der Takt wirkt wie eine Schleuse.
Ich habe also zwei komplementäre Signale beziehungsweise ich habe eine
Aktion bei einem Ereignis und eine sieht aus wie bei einem anderen
Ereignis.
Ich kann auch sagen, wenn ich hier meinen Takt betrachte, ich
betrachte ja so etwas, das so aussieht, ich kann auch sagen, ich habe
einmal eine ansteigende Flanke, das ist diese hier, und eine
absteigende Flanke.
Und das sind die beiden Ereignisse.
Beide Realisierungen gibt es, dass ich mit einem Taktsignal und dann
ansteigender oder absteigender Flanke arbeite, das heißt eine
Veränderung von 0 auf 1 oder von 1 auf 0 löst eine Datenweitergabe aus
oder ich habe zwei Taktsignale, die die beiden Schleusentore
unabhängig voneinander schalten können.
Ich habe also jetzt meine Schaltwerke etwas anders dargestellt.
Ich habe jetzt die Eingaben zu einem Zeitpunkt T.
Jetzt habe ich also Zeitpunkte T, das sind jeweils die Zeiten, wo ich
etwas messen kann.
Da habe ich die Eingaben, die ich frei wählen kann.
Ich habe meinen Anfangszustand Z von 0.
Sie erinnern sich, das ist S0 bei unseren Automaten.
Kann sein, dass der irgendwie durch den Reset-Knopf automatisch
gewählt wird oder ich muss den irgendwie definieren.
Ich kann ihn fest initialisieren oder er kann auch beliebig sein.
Da muss ich ihn erstmal auf einen vernünftigen Zustand bringen.
Und der Folgezustand wird erzeugt, also zum Taktzeitpunkt T plus 1,
dadurch, dass ich die Eingaben zur Zeit T und die Zustände zur Zeit T
kombiniere, entsprechend und daraus den Zustand zur Zeit T plus 1
erzeuge.
Und das YT ist dann mein F von A von T und Z von T, also genau die
Milliautomaten -Funktionsweise.
Das ist dann das getaktete Schaltwerk.
Und die brauche ich jetzt tatsächlich, um Rechner zu bauen.
Um das zu bauen, wenn wir Gedächtnis haben wollen, um Rechner, brauche
ich solche Bauelemente.
Und jetzt fangen wir einfach an mit den einfachsten Bauelementen, die
sich irgendwas merken können.
Die einfachsten Bauelemente sind sogenannte Flipflops.
Warum Flipflop?
Die können nämlich Flip und Flop sagen.
Das ist also so, die haben die Möglichkeit, zwei verschiedene Zustände
anzunehmen, zwei stabile Zustände, Flip und Flop, 0 und 1.
Und ich muss in der Lage sein, diesen Zustand anzunehmen.
Das heißt, ich muss ihn speichern können.
Ich muss die 0 speichern können und die 1 speichern können.
Das muss ich reinschreiben können in den Speicher.
Ich muss also hier mein Element, muss in der Lage sein, Werte
aufzunehmen.
Und ich möchte es auch auslesen können.
Ich möchte wissen, was ist dort drin, das möchte ich nach außen
auslesen können.
Und diese drei Eigenschaften sind die Eigenschaften, die ein einfaches
Speicherelement im Rechner charakterisieren, ein sogenanntes Flipflop.
Ich kann den Wert 0 speichern, den Wert 1 speichern und ich kann die
dort reinschreiben und ich kann es wieder auslesen.
Und solche Elemente schauen wir uns jetzt genauer an.
Das einfachste oder ein einfaches solches Schaltelement oder solches
Flipflop ist das sogenannte RS-Flipflop.
RS steht für Reset und S für Set.
Also mit Set möchte ich einen Wert auf 1 setzen, mit Reset auf 0.
Wenn ich also S auf 1 setze, soll eine 1 rauskommen.
Das schauen wir uns gleich einfach mal an, über wieder unseren
Logiflash.
Da kann ich Ihnen das zeigen.
Und dauert wieder einen kleinen Augenblick, da haben wir es schon.
Dann können wir uns hier unser RS-Flipflop holen und laden das mal
rein.
Das wollte ich Ihnen gerade noch gar nicht zeigen.
Machen wir das Ganze erstmal aus.
Also, das ist unser RS-Flipflop.
Auf der Folie haben Sie das gerade gesehen.
Zwei NOR-Elemente hintereinander.
Sie sehen hier eine Rückkopplung von dem zweiten NOR.
Geht das an das hier vorderein.
Und das erste NOR hat einen Eingang in dieses zweite Schaltelement.
Im Prinzip ist das auch schon eine Art Rückkopplung.
Ich werde Ihnen das ein bisschen anders darstellen, dann sehen Sie,
dass das auch als Rückkopplung dargestellt werden kann.
Ich habe also jetzt hier diese beiden NORs und dann habe ich hier zwei
Lämpchen hingemalt und es soll so sein, dass ich jetzt eine 1
reinspeichern kann und eine 0.
Jetzt habe ich erstmal die beiden Eingänge, R und S in diesem Fall,
beide auf 0 gesetzt.
Wenn ich jetzt die Simulation anschalte, passiert das hier.
Warum passiert das jetzt hier?
Wenn die beide 0 sind, fangen wir es doch doch mal an, dann sind die
Ausgänge auch 0.
Wenn die jetzt beide 1 werden, gleichzeitig, wirklich genau
gleichzeitig, dann habe ich hier, wenn hier eine 1 kommt, dann habe
ich hier eine...
Wenn hier eine 1 kommt, dann kommt eine 1 raus, da kommt also nochmal
das Ganze...
Nein, nein, das ist so.
Es ist schon richtig.
Hier kommt eine 0 ran.
Dahinten habe ich auch 0.
Zwei 0 bringen als Ergebnis eine 0.
Das heißt, das NOR liefert dann eine 1.
Dann müsste also, wenn ich das gleich simuliere, hier eine 1
entstehen.
Das Gleiche passiert aber hier unten.
Ich habe ja hier zunächst mal zwei Nullen.
Wenn ich jetzt das simuliere bei zwei Nullen, kommt hier hinten aber
gleich eine 1 raus.
Das heißt aber, dass hier eine 1 kommt, dadurch, dass ich das jetzt
simuliert habe.
Und beim anderen kommt zurück auch eine 1.
Wenn ich aber bei beiden eine 1 stehen habe, bei dem einen Eingang,
dann habe ich ja eine 1.
Das heißt, das ODER würde eine 1 geben am Ergebnis.
Das NOR liefert eine 0.
Dann gehen die beiden hinten wieder aus.
Und deswegen habe ich genau dieses flackernde Verhalten.
Das heißt, das ist völlig instabil mit zwei Nullen.
Ich muss es zunächst einmal setzen.
Einen Eingang setzen auf eine 1.
Dann habe ich jetzt den Wert 1 dort eingespeichert.
Und jetzt kann ich den wieder ausmachen.
Und wir haben die 1 immer noch eingespeichert.
Der andere Wert hier unten ist gerade das Kompliment des Wertes, der
dort gespeichert ist.
Und das ist eine wichtige Eigenschaft, dass ich jetzt zwei Ausgänge
habe, die komplementäre Werte haben sollen.
Und das, was wir, wenn wir das noch einmal in diesem Zustand
betrachten, da habe ich hier ja im Prinzip bei den Ausgängen die
gleichen Werte.
Und das ist eine nicht erwünschte Situation, die eben, wie wir gesehen
haben, zu genau diesem instabilen Verhalten führt.
Ich muss es erst einmal auf einen Wert gesetzt haben.
Dann habe ich tatsächlich eine Situation, dass ein Wert 1 ist und der
andere 0.
Jetzt kann ich den wieder auf 0 setzen.
Der Wert bleibt hier bestehen, weil wir ja die 1 zurückgekoppelt
haben.
Das heißt, wir haben hier dann bei dem Nor-Element eine 0.
Die beiden Nullen liefern eine 1.
Das bleibt jetzt so bestehen.
Egal, ob ich hier jetzt eine 1 habe oder nicht.
In dem Augenblick, wo ich aber den zweiten Eingang auf 1 setze, ist
die Situation anders.
In dem Augenblick habe ich hier diese beiden hier auf 1 gesetzt.
Das heißt, wir haben hier bei dem Nor-Element eine 0 am Ausgang.
Und Sie sehen, jetzt haben wir auf einmal hier vorne, wir sind hier
zwei Nullen.
Vorher war dort das eine eine 1, jetzt sind hier zwei Nullen, deswegen
kommt hier eine 1 raus.
Und jetzt ist hier oben eine 0 und unten eine 1.
Komplementäres Ergebnis.
Das eine ist eine 0 geworden, das andere ist eine 1 geworden.
Jetzt kann ich das hier wieder ausmachen und ich kann es einschalten
oder ausschalten.
Es ist egal, es bleibt dieser Zustand erhalten.
Und ich könnte also auch wieder hier so einen Null machen, da wieder
eine 1 setzen und ich habe jetzt hier die 1 eingespeichert.
Was passiert, wenn ich jetzt den zweiten Wert auch auf 1 setze?
So, ups, das wollten wir eigentlich nicht.
Warum haben wir jetzt am Ausgang zwei Nullen?
Weil wir beide NOR-Gatter mit einer 1 versorgt haben.
Deswegen ist das Ergebnis am Ausgang jeweils eine 0.
Das heißt, beide Indikatoren zeigen eine 0 an.
Etwas, was wir verboten haben, das soll ein Schaltelement sein, wo die
eine Lampe den aktuellen Zustand einzeigt und die andere Lampe das
genaue Gegenteil, das Komplement davon.
Das ist hier nicht erfüllt.
Deswegen erlauben wir bei einem RS-Flip-Flop nicht, dass beide
Eingänge auf 1 gesetzt werden.
Weil wir dann nämlich zu der Situation kommen, dass wir hier zwei
Nullen haben und Sie wissen, dass dann könnte es zu Problemen kommen.
Wenn ich jetzt die beide gleichzeitig ausschalten würde, dann hätten
wir tatsächlich wieder so eine Situation, bei der wir ein instabiles
Verhalten bekommen, was wir nicht wollen.
Also zwei Probleme, die wir hier haben.
Und das ist also jetzt so ein RS-Flip-Flop, wie ich das Ihnen ja
aufgemalt habe, das man auch als Symbol angeben kann und vielleicht
nur, habe ich jetzt schon weggemacht, man kann es auch etwas anders
anordnen.
Dann bekommen Sie eine Darstellung, bei der Sie zum Beispiel hier R
und S, dann haben Sie hier jeweils die beiden Bauteile, die jeweiligen
NORs und Sie haben hier Ihre Lampen.
Das sind also unsere beiden Lampen.
Und dann geben wir den Wert von hier, den geben wir da noch ein, und
den Wert von da geben wir dort noch ein.
Dann haben wir eine Rückführung, die gleiche Schaltung, durch einen
senkrechten Strich, dummerweise wieder etwas verzerrt.
Das heißt, wir können die beiden NOR-Elemente, die Sie hier sehen, ich
kann dieses hier im Prinzip da rüberschieben und dann sieht das ganz
symmetrisch aus, dass man jeweils die Ausgänge der NOR-Elemente in die
Eingänge des jeweils anderen NOR-Elements hineinlegt.
Genau das machen wir hier.
Der Ausgang dieses NOR-Elements ist da wieder eingegeben worden, der
Ausgang dieses NOR-Elements wird da eingegeben.
Und der Ausgang ist jeweils hier Q quer und Q.
Also das ist ein solches RS-Flipflop.
Jetzt kann ich mir die Schalttabelle aufmalen dazu.
Da habe ich also hier meine RS, die beiden Eingänge.
Q-Stern ist das, was ich hier zurückgebe von hinten.
Und dann kommt das Ergebnis raus als der neue Wert von Q in dem Fall.
Wenn also hier beides eine Null ist, oder alles drei eine Null ist,
kommt eine Null raus.
Wenn beides alles eine Null ist und da hinten ist eins gespeichert,
dann kommt eine Eins raus.
Wenn ich das S auf Eins setze, dann wird eine Null auf eine Eins
gesetzt.
Wenn eine Eins schon da war, bleibt es eine Eins.
Wenn ich das R auf eine Eins setze und da hinten war eine Null, bleibt
es bei Null.
Wenn ich das R auf eine Eins setze und da hinten war eine Eins, dann
wird das auf Null gesetzt.
Das habe ich gerade gezeigt an dem Beispiel.
Und dieses Beides hier, dass ich R und S beide auf Eins habe, das ist
unzulässig.
Das wollen wir nicht haben.
Wegen dieses Effekts, dass dann auf einmal diese beiden Werte hier Q
und Q-quer nicht mehr komplementäre Werte anzeigen, sondern auf einmal
den gleichen Wert Null anzeigen.
Und das ist unerwünscht.
Das ist also unsere Schaltung.
Das kann ich daraus natürlich eine Schaltfunktion bauen.
Ich kann also die auch darstellen als Bullshit-Ausdruck.
Und mit einer gewissen Vereinfachung, weil ich weiß, dass R und S
gleich Eins sind, also das, was hier oben steht, ist einfach nur aus
dieser Schalttabelle abgeleitet, kann ich die Schaltfunktion für Q
einfach so darstellen, dass es S oder es ist die Konjunktion von Q
-Stern und dem Komplement von R.
Das ist also hier unsere Schaltfunktion für dieses RS-Flipflop.
Damit habe ich jetzt also die Schaltung.
Ich habe den entsprechenden Bullshit-Ausdruck dafür.
Und wir wissen, was man damit machen kann.
Wir können dort Werte speichern.
Und aus solchen Speicherelementen sind unsere Speicher im konkreten
Rechner aufgebaut.
Jetzt kann ich das Ganze auch noch synchron machen.
Wir wissen, wir wollen noch Takt-Signale haben.
Dazu brauche ich ein Takt-Signal T.
Und um das synchron zu machen, baue ich einfach hier zwei Und-Gatter
davor.
Und wenn ich jetzt das T auf 0 setze, wird hier nichts weitergegeben.
Wenn das T auf 1 ist, dann werden die beiden Werte von S und R
weitergegeben.
Dann habe ich also hier die Möglichkeit dafür zu sorgen, dass nur wenn
das T gleich 1 ist, sich etwas verändern kann.
Solange T gleich 0 ist, wird dieses Flipflop sich nicht verändern.
Da kann ich also hier vorne bei S und R beliebige Dinge verändern.
Erst wenn T auf 1 geht, werden die Werte dann entsprechend hier
weitergegeben.
Das ist also ein synchrones, getaktetes RS-Flipflop.
Und das wird dann als Schallsymbol, wird halt das T noch dazu gemalt
und hier angedeutet, dass abhängig von dem T die Werte am Ausgang dann
tatsächlich sich verändern können.
Jetzt hatten wir gerade eben das Problem mit unseren beiden Einsen,
die wir nicht haben wollten.
Und das stört uns.
Wir wollen gerne so etwas vermeiden, dass eine Eingangskombination
nicht erlaubt ist.
Wir wollen auch für die Eingangskombination 1,1 ein stabiles weiteres
Verhalten garantieren können.
Und deswegen kann man jetzt ein JK-Flipflop bauen.
Ein JK-Flipflop, da sind einfach nur die beiden Eingänge anders
benannt, mit J und K.
Da haben wir nach wie vor ein RS-Flipflop hier hinten dran, aber wir
haben davor noch zwei UND-Gatter, die jeweils dreistellig sind in
diesem Fall.
Das heißt, wir haben hier J und K dran, wir haben das T dort dran, wie
vor bei dem getakteten, synchronen RS-Flipflop.
Und wir haben gleichzeitig die Werte von Q und Q-quer mit nach vorne
geführt.
Was heißt das?
Im Normalbetrieb haben Q und Q-quer stets unterschiedliche Werte.
Sie sind stets komplementär.
Das heißt, wenn Q und Q-quer, also hier Q-stern und Q-stern-quer,
unterschiedlich sind, kann immer nur eines dieser beiden UND-Gatter
tatsächlich eine 1 weiterleiten.
Nämlich das, bei dem entweder Q-stern oder Q-stern-quer gleich 1 ist.
Ich kann also jetzt gerne hier J und K auf 1 setzen.
Es wird nur eine dieser 1 noch rechts weitergegeben.
Hier an diesen Stellen kann also nur stehen, entweder kann hier eine 0
und da eine 1 hinkommen, oder es kann da eine 1 und eine 0 hinkommen.
Die beiden Möglichkeiten gibt es.
Oder eben beides auf 0 sein.
Das kann auch noch passieren, beides eine 0.
Dann hätte ich diese drei Situationen, aber die 1, 1 können niemals
entstehen.
Also wenn T gleich 0 ist, da habe ich bei beiden eine 0 am Ausgang
stehen.
Die 1, 1 taucht dort gar nicht auf.
Was passiert, wenn beide 1 sind?
Dann vertauschen Q und Q-quer ihre Werte.
Das heißt, von 0 gehe ich auf 1, von 1 gehe ich auf 0.
Ich kippe praktisch das Bit, das dort im Speicher steht.
Das kann ich mit dem JK-Flipflop erreichen.
Das habe ich also auch noch hier als Schaltfunktion oder als
Buchsenausdruck dargestellt, abgeleitet von dem, was Sie hier in dem
Schaltbild sehen.
Und jetzt kommt noch als letztes, na, das schaffe ich nicht mehr, das
nächste wäre das RS-Flipflop, bei dem wir aus zwei synchronen RS
-Flipflops ein sogenanntes Master-Slave-Flipflop bauen, bei dem wir
tatsächlich in der Lage sind, einen Wert aufzunehmen und ihn
anschließend bei dem nächsten Ereignis weiter zu geben nach rechts.
Damit können wir die Schleuse bauen, die ich Ihnen versprochen habe.
Ich danke Ihnen für die Aufmerksamkeit.
Das war es für heute.