So, schönen guten Tag, ich begrüße Sie zur Fortsetzung der Vorlesung
der Grundlagen der Informatik II.
Ganz kurz zu Beginn ein Hinweis und zwar auf...
mal kurz gucken...
Hinweis nicht auf unsere Institutsseite, die ist auch sehr
interessant, aber ein Hinweis auf die Seite der Vorlesung.
Da, das müsste eigentlich funktionieren.
Schauen wir mal.
Ach ja.
Dauert einen kleinen Augenblick.
Ich muss noch, ich sehe gerade, ich habe etwas vergessen.
Ich muss noch schnell, ganz schnell die Nuked-Tools an, die noch
starten.
Da die Vorlesung Info II aufrufen und
genau, das ist ganz wichtig.
Und da müsste noch eine sein.
Diese hier.
Info II.
So, jetzt haben wir die auch.
Perfekt.
Und jetzt kommt noch, inzwischen ist hoffentlich die Seite da, genau.
Hier müsste jetzt eigentlich auf der Webseite stehen, dass die
Anmeldung zur...
Bitte?
Oh, das ist nicht so gut.
Dann gehen wir lieber nochmal zurück.
Studierendenportal.
Neun Semester.
Vorlesungsfavoriten.
Da haben wir VAB, 12-13, genau.
Hier steht...
Da steht noch nichts von der Bonus-Datei, von der Bonus-Klausur.
Da steht...
Aha.
Gut, hier kommen ganz viele Hinweise.
Also, letzte Woche fiel die Vorlesung aus, das haben Sie erfahren,
haben Sie gemerkt.
Ich hoffe, dass niemand von Ihnen vergeblich morgens in der Vorlesung
gewesen ist.
Am 10.
Dezember in einer Woche haben wir hier keine Vorlesung, sondern es ist
eine große Saalübung.
Mit so Hinweisen auf so wesentliche Punkte, die bei den Übungen eine
Rolle spielen können und die man wissen sollte, die man lernen sollte.
Und etwas, was mich wundert, ist Folgendes.
Wegen veränderter Nachfrage wurden zwei interaktive Tutorien in
klassische umgewandelt.
Da möchte man das Wort so verlieren.
Also, was sind klassische Tutorien?
Klassische Tutorien entsprechen eigentlich nicht dem Erziehungsideal
oder dem Bildungsideal einer Hochschule.
Klassische Saalübungen sind reiner Frontalunterricht, da werden
Aufgaben vorgerechnet, da machen wir zwar ein bisschen was in der
Gruppe, aber das ist im Wesentlichen passiv.
Das passt nicht zu einer Universität.
Es ist leider der Standard, deswegen sagt man, das ist die klassische
Übung.
Die klassische Übung ist die Übung, wo Sie aktiv dabei sitzen, sich
mit Aufgaben beschäftigen, Lösungen vorrechnen, wo Sie aktiv dabei
sind.
Das sind eigentlich die klassischen Übungen.
Leider hat sich da eine andere Klassik eingebürgert und wir hatten vor
ein paar Jahren gesagt, wir bieten für diejenigen, die Interesse
haben, sich ein bisschen intensiver mit dem Stoff zu beschäftigen, die
meinen, sie könnten vielleicht mehr lernen, wenn sie sich aktiver mit
dem Stoff beschäftigen und auch mal lernen, Dinge zu präsentieren,
Rückmeldung kriegen darauf, wenn sie was präsentieren, für die bieten
wir was an, und zwar diese aktiven Übungen.
Und das war zu Anfang eine ziemlich starke Resonanz, in diesem Jahr
ist die Resonanz relativ niedrig.
Das heißt, Ihr Interesse, nach vorne zu gehen und was zu präsentieren,
Rückmeldung zu kriegen, das ist nicht mehr da.
Oder das ist deutlich geringer als früher.
Ich weiß nicht warum.
Das, was Sie brauchen, eine Fähigkeit in Ihrem Berufsleben, ist die
Fähigkeit, sich selbst zu präsentieren, Dinge zu präsentieren, die Sie
mit anderen besprechen wollen.
Sie wollen mal irgendwann Wirtschaftsmanager werden, Sie wollen als
Wirtschaftsingenieur Dinge gestalten, Projektleiter werden und
ähnliches.
Die entscheidende Kompetenz besteht darin, richtig zu kommunizieren.
Übungen, aktive Übungen sind die Gelegenheit, sowas zu tun.
An welcher Stelle bekommen Sie sonst die Möglichkeit, direkt etwas
vorzutragen, Rückmeldung darauf zu bekommen.
Diese Rückmeldung ist nicht immer positiv, aber genau das brauchen
Sie.
Wenn man eine positive Rückmeldung kriegt, doch, das können Sie
vergessen.
Sie brauchen kritische Rückmeldungen, daran lernen Sie.
Und da lernen Sie etwas, was wichtig ist.
Ja, das hat zwar hier im Grundlagen Informatik 2 zu tun, wir
interessieren das schon.
Auch das ist eine schlechte Einstellung.
Das müsste Sie schon interessieren, weil Sie Wirtschaftsingenieur aus
Karlsruhe sein wollen, irgendwann mal, die wissen, welche Bedeutung
Informationstechnologien haben.
Aber, dass das Interesse sinkt an den aktiven Übungen, ist für mich
völlig unverständlich.
Ich weiß nicht, woran das liegt.
Vielleicht zu einer Zeitüberlastung, aber Sie müssen sich überlegen,
wo Ihre Prioritäten sind.
An welchen Stellen im Studium Sie Gelegenheit haben, etwas selbst zu
präsentieren, das zu lernen, ohne dass Sie dafür sofort Noten kriegen.
Das ist ja nicht schädlich für Sie, wenn Sie da mal eine Aufgabe
vorrechnen und die war nicht in Ordnung.
Und dann wissen Sie, wie man es besser machen muss.
Da lernt man nur.
Es werden keine Noten vergeben.
Sie können nur lernen.
Sie können Dinge lernen, wichtige Fähigkeiten dort erwerben, die
wichtig sind für die Zukunft.
Deswegen kann ich es auch noch nachvollziehen, warum wir auf einmal
wegen der dringenden Nachfrage, jetzt mehr aktive Übungen, klassische
Übungen machen.
Ist für mich eine Entwicklung, die ist völlig entgegen den
eigentlichen Herausforderungen, denen Sie sich stellen müssen als
Student.
Das muss sich loswerden.
Jetzt Bonusklausur.
Am 19.1.
ist die Bonusklausur und Sie können sich jetzt anmelden.
Startet am 1.12.
die Anmeldezeit.
Also am Samstag hat er gestartet.
Sie können sich anmelden für die Bonusklausur.
Und wenn Sie sich nicht anmelden, können Sie auch nicht teilnehmen.
Die Anmeldefrist ist bis zum 31.12.2012.
Ist zwar noch ein bisschen Zeit, aber wenn Sie dann in den
Weihnachtsurlaub fahren und dann in der ersten Januarwoche
zurückkommen, dann sollten Sie nicht sagen, oh, ich wollte mich da
eigentlich anmelden.
Machen Sie das sofort, melden Sie sich gleich an und dann machen Sie
nichts falsch.
Wenn Sie sich nicht angemeldet haben und wollen teilnehmen, dann
machen Sie das falsch.
Dann können Sie nämlich nicht mehr teilnehmen.
Das dazu, das war alles, was ich jetzt hier mitteilen sollte.
Also wegen der klassischen Tutorien, da haben meine Mitarbeiter mich
nicht darauf hingewiesen, dass ich da die Bemerkung machen sollte,
aber die kommt einfach spontan von mir.
So, jetzt zur Vorlesung zurück, zu den interessanten Themen.
Was machen wir denn gerade?
Wir beschäftigen uns mit Architektur von Rechensystemen, sind da auf
ein neues Thema gegangen, endlich.
Übrigens, wenn Sie sich fragen, warum wird in dieser Vorlesung nicht
evaluiert, in allen anderen Vorlesungen gibt es die Fragebögen, wo man
wirklich was an der Meinung sagen kann, zu dem, was hier in der
Vorlesung läuft.
Wir wollen das so machen, dass wir Sie darum bitten, das direkt vor
der Bundesklausur zu machen, denn da sind Sie alle da.
Jetzt sind eben nicht alle da, weil wir ja den schönen Service bieten,
dass Sie sich die Vorlesung aufgezeichnet zu Hause anhören können.
Und ich möchte gerne auch Rückmeldung bekommen von denjenigen, die
nicht hier zur Vorlesung kommen, sondern sich die Vorlesung zu Hause
anhören, weil die genauso Rückmeldung geben können, wie Sie mit der
Vorlesung zurecht kommen und welche Rückmeldung Sie für uns hätten.
Deswegen machen wir das so, das haben wir auch so gemacht und das hat
gut geklappt.
Also vor der Klausur werden Sie Kurzgelegenheit haben, die
Volationsbögen auszufüllen.
Dann ist auch die Vorlesung so ein bisschen weiter fortgeschritten,
dann haben Sie einen breiteren Zeitraum, über den Sie was sagen
können.
Insbesondere sind noch andere Themen etwas intensiver dabei gewesen,
die vielleicht auch eine Rolle spielen bei dem, wie Sie das Ganze
bewerten werden.
Also, das war hier jetzt nochmal wieder zurück unsere Vorlesung.
Wir sind hier gerade jetzt bei Rechnerarchitektur.
Ein Thema Busch Algebra habe ich Ihnen kurz vorgestellt.
Grundlage für die Beschreibung von Schaltfunktionen.
Und diese Schaltfunktionen, die Buschenfunktionen, Schaltfunktionen,
muss man auf geeignete Weise darstellen können.
Da hatte ich Ihnen noch vorgestellt, die binären
Entscheidungsdiagramme, BDDs, Ich hatte Ihnen gezeigt, wie man die
entwickelt.
Das Beispiel der Übertragsfunktion eines binären Algiers.
Wir hatten gesehen, man kann dadurch solche relativ effizienten
Darstellungen der Funktionen bekommen.
Insbesondere kann man auf die Art und Weise eine sehr effiziente
Auswertung von Funktionen vornehmen.
Auch ein ganz wichtiger Punkt, dass wir maximal lineare Zeit in der
Anzahl der Variablen brauchen, um eine Funktion auszuwerten, also den
Funktionswert zu berechnen, während das bei der Darstellung über einen
bulischen Ausdruck halt deutlich mehr Zeit kosten kann.
Ich hatte Ihnen da ein paar Beispiele angegeben.
Wir hatten uns dann begonnen, mit dem Thema Schaltalgebra zu
beschäftigen.
Was hat Schaltalgebra mit Buschalgebra zu tun?
Die Schaltalgebra ist halt ein Anwendungsbereich, wo wir etwas formal
beschreiben müssen.
Und man stellt halt fest, wir können über die Darstellung von
Variablen als Schaltelementen oder Darstellung von Schaltelementen von
Schaltern als Variablen und Reihen- und Parallelschaltungen von
solchen Schaltelementen tatsächlich Operationen realisieren, die was
mit Produkt und Summe zu tun haben und Komplementbildung und damit
haben wir also eine algebraische Struktur, die jetzt genau solch eine
Buschalgebra ist.
Und jetzt machen wir auf dieser Folie auch weiter.
Also wir haben hier zunächst mal eine Frage zu beantworten, die ich
gerade sehe.
Ich muss das mal ein bisschen weiter reinziehen.
So, ich glaube, das wird so etwa aufgezeichnet.
Wie lange ist die Folie noch zweimal die Woche?
Also dieses Jahr auf jeden Fall noch, im nächsten Jahr dann wohl nicht
mehr.
Wir werden es rechtzeitig mitteilen, dass die Vorlesung, also die ist
eigentlich dreistündig.
Und ich mache immer die eine Hälfte vierstündig und den Rest
zweistündig.
Und die zweistündige Hälfte ist etwas kürzer als die vierstündige
Hälfte.
Das ist leider so, weil ich etwas mehr Zeit brauche, Ihnen die Sachen
etwas ausführlicher zu erklären und dann dauert es halt leider etwas
länger.
Also ich bemühe mich schon, das nicht zu sehr auszuweiten.
Okay, machen wir weiter.
Das war hier die Folie mit den Verknüpfungen und der Überlegung, dass
diese Algebra-Struktur, diese Schaltalgebra auch eine Buschalgebra
ist.
Das heißt, alles was wir Buschalgebren kennen, gilt auch für die
Beschreibung von Schaltfunktionen und Schaltelementen.
Und jetzt schauen wir uns mal an, was wir eigentlich mit zweistelligen
Schaltfunktionen alles machen können.
Und das, was ich Ihnen jetzt zeigen werde, ist also, welche
Schaltfunktionen es überhaupt gibt, zweistellige.
Und wir werden sie jeweils darstellen, einmal durch, das werden Sie
gleich sehen hier, durch die Wertetabelle.
Also das, was wir hier angegeben haben, das ist ja gerade die
Wertetabelle, die Werte für alle möglichen Eingaben.
Alle möglichen Eingaben sind 2 hoch 2 Eingaben.
Wenn wir so eine k-stellige Funktion hätten, hätten wir 2 hoch k
verschiedene Möglichkeiten, Eingaben zu variieren für eine k-stellige
Funktion.
Und wie viele Möglichkeiten gibt es, k-stellige Funktionen anzugeben?
Für jede Eingabekombination gibt es 2 verschiedene Möglichkeiten.
Das heißt, für 2 hoch k Positionen, jeweils 2 verschiedene
Möglichkeiten, also 2 hoch 2 hoch k.
In diesem Fall ist k 2, 2 hoch 4 ist 16.
Wir werden also hier gleich 16 verschiedene Funktionen sehen.
Und jetzt steht hier die kanonische disjunktive Normalform.
Was denn normal?
Mal die kanonische disjunktive Normalform.
Die kanonische disjunktive Normalform gibt hier alle Zeilen in der
Wertetabelle, bei denen eine 1 als Ergebnis steht, jeweils eine
Konjunktion der Werte dort.
Das heißt, eine Konjunktion, die 1 ist.
So, in diesem Fall, erste Funktion, haben wir nur Nullen stehen.
Deswegen steht da auch nur die 0, das ist die 0-Funktion.
Wir haben keine 1-Zeile.
Bei der nächsten Funktion haben wir eine 1 stehen, und zwar hier
unten.
Da steht eine 1.
In dem Fall sind a und b 1.
Das ist die einzige 1-Zeile.
Deswegen steht hier eine Konjunktion, a und b.
Diese Funktion ist 1, wenn a und b 1 sind.
Schauen wir die nächste Funktion an.
Wieder nur eine 1-Zeile, nämlich für den Fall, dass a 1 ist und b 0.
Wenn b 0 ist, ist b quer 1, deswegen a und b quer beschreibt genau
diese eine 1-Zeile.
Nächste Funktion.
Da stehen hier unten zwei 1.
Das heißt, in den beiden Zeilen, a und b quer, das sind eine, sowie a
und b haben wir eine 1.
So beschreiben wir mit der kanonischen, disjunktiven Normalform die
jeweiligen 1-Zeilen bzw.
die Funktion.
Dann haben wir hier in der zweiten Zeile eine 1, das ist gerade der
Fall, dass a 0 ist und b 1, also a quer und b.
Eine ganz einfache Art, wie man Funktionen beschreiben kann.
Dann haben wir hier zwei 1 stehen, in diesen beiden Zeilen, also für a
quer und b, oder a und b, das sind die beiden 1-Zeilen.
Wieder eine 0-Funktion.
Dann haben wir hier zwei 1 stehen, das ist genau für den Fall, dass
wir a quer und b haben, also a 0 und b 1, oder a 1 und b 0.
Und diese Funktion kennen wir, die haben wir schon kennengelernt, das
war gerade die XOR-Funktion.
Also man hat dann 1, wenn wir eine ungerade Anzahl von 1 haben.
Für zwei Elemente, also gerade wenn eine 1 da ist und nicht 0 1 oder 2
1.
Dann gibt es die Disjunktion, sieht erstaunlich groß aus, dieser
politische Ausdruck.
Disjunktion, in einer disjunktiven Normalform, hat an drei Stellen
hier eine 1.
Also haben wir drei Terme dort stehen, drei Konjunktionen, a quer und
b, also a 0 und b 1, a 1 und b 0, oder a und b beide 1.
Das sind genau diese drei Zeilen.
Dann steht hier nochmal eine mit einer 1 oben, das ist also genau a
quer und b quer, zwei Nullen.
Das ist das sogenannte NOR, also nicht oder, genau das Gegenteil der
oder -Funktion, genau alles komplementär.
Und dann haben wir hier die Äquivalenz 1, genau dann wenn beide
Argumente gleich sind, beides Nullen oder beides Einzelnen.
Also das genaue Gegenteil der XOR-Funktion.
Und das ist halt gerade a quer und b quer, also beide 0 oder beide 1.
Und entsprechend geht das hier weiter, ich mach das jetzt mal ein
bisschen schneller.
Und Sie sehen dann hier alle 16 Funktionen, von 0 bis 15
durchnummeriert.
Das sind die ganzen Funktionen und am Ende, wenn wir hier also nur 1
-Zeilen haben, haben wir halt entsprechend alle vier möglichen Terme
in dieser disjunktiven Normalform.
Also das sind alle zweistelligen Schaltfunktionen oder
Prüfenfunktionen.
Hier nennen wir das halt Schaltfunktionen, weil wir uns auf
Schaltelemente beziehen.
Das können wir alles mit zweistelligen Funktionen machen, irgendwie
durch Schaltungen realisieren, wie man es durch Schaltungen
realisiert, steht hier.
Wir werden noch sehen, wie man das dann konkret umsetzt, ausgehend von
solch einem Ausdruck, wie man daraus eine Schaltung bauen kann, da
kommen wir heute noch drauf.
So, vielleicht mache ich jetzt an dieser Stelle etwas...
Ich habe das letzte Mal eigentlich schon machen wollen, aber nicht...
Ach, da muss ich hin.
Ich wollte woanders hin.
Wo bin ich denn?
Also, ich wollte jetzt eigentlich...
Wie komme ich denn jetzt auf den Explorer?
Das ist ja ein Ding.
Der zeigt mir das.
Ich möchte bei dem Explorer sehen.
Da ist er.
Perfekt.
So, jetzt wollte ich gerne Ihnen eine Frage stellen.
Ich weiß nicht, wie viele von Ihnen die App geöffnet haben.
Ich wollte gerne eine Frage stellen.
Und zwar wollte ich Sie gerne fragen, Wie viel Zeit benötigt man im
schlechtesten Fall, um die Erfüllbarkeit einer aussagenlogischen
Formel in disjunktiver Normalform zu überprüfen?
Was ist das für eine komische Frage?
Sie kennen doch diese Frage bereits.
Ich habe Ihnen doch das Erfüllbarkeitsproblem beschrieben.
Satt.
Wieso stelle ich jetzt eine komische Frage?
Wie war das Erfüllbarkeitsproblem formuliert?
Das Erfüllbarkeitsproblem war formuliert, ist eine Formel, eine
beliebige aussagenlogische Formel, die in konjunktiver Normalform
gegeben ist, erfüllbar.
Jetzt schreibe ich hier so eine komische Frage.
Wie viel Zeit benötigt man im schlechtesten Fall, um die Erfüllbarkeit
einer aussagenlogischen Formel in disjunktiver Normalform zu
überprüfen?
Ist das anders?
Ist das gleich?
Was meint?
Einer meint, zwei meinen, linear in der Länge der Formel.
Also zum Beispiel hier, da unten haben wir so eine Aussagenlogische
Formel.
Um festzustellen, ob eine Formel in disjunktiver Normalform, also in
kanonischer disjunktiver Normalform, disjunktion aller Eins-Zahlen der
Wertgebung ist.
Ob die erfüllbar ist?
Vier, exponentiell in der Anzahl.
Drei meinen das jetzt.
Ah, bei allen klickt irgendjemand.
Linear in der Anzahl aller Variablen, quadratisch in der Anzahl aller
Variablen, sagt auch jemand.
Ja, die meisten meinen vier.
Wobei ich mal bei vier habe ich gemeint, wenn man also, wir wissen ja
p gleich np ist ungelöst, also wir gehen jedenfalls im Augenblick
davon aus, wenn das so ist, dann wäre das das.
Hier sagt noch jemand, linear in der Länge der Formel.
Interessant.
Noch einer sagt das.
Überlegen Sie mal.
Wie lange müssen Sie dann gucken, in so einer langen Formel, um
festzustellen, ob diese Disjunktion erfüllbar ist.
Wann ist eine Disjunktion erfüllbar?
Überlegen Sie mal.
Wann ist eine Disjunktion, wo Sie viele Elemente haben, die a oder b
oder c oder x oder y oder sowas, wann ist die erfüllbar?
Eine k-stellige Disjunktion.
Wie viele Elemente müssen eins sein, damit eine k-stellige Disjunktion
erfüllbar ist?
Bitte?
Ein.
Ja, prima.
Genau.
Wie hängt das damit zusammen?
Sie haben hier zum Beispiel eine dreistellige Disjunktion.
Da stehen jeweils Konjunktionen da drin.
Was müssen Sie denn da angucken?
Wenn Sie so eine... Einer von denen muss wahr sein.
Kann... Das erste wäre a-quer und b-quer.
Wie können Sie feststellen, ob das wahr, ob das erfüllbar ist?
Sie brauchen das nur hinzuschreiben.
Wenn da steht a-quer und b-quer, wollen wir denn a-quer und b-quer
wahr?
Mit welcher Belegung?
0,0.
Ganz einfach.
Schon fertig.
Ich schaue mir einfach den ersten Term an.
Die erste Konjunktion.
Ich spiele die einmal durch und da steht ja, welche Belegung das Ding
wahr macht.
Mir brauche ich gar nichts zu tun.
Das ist ja ganz einfach.
Also, welche Alternative ist denn dann die richtige?
Bitte?
Zwei.
Völlig richtig.
Interessant.
Aber spontan sagt man, es ist doch völlig egal, ob konjunktive oder
disjunktive Normalformen.
Aber nein, ist es nicht.
Aber dann könnte ich doch eigentlich ganz einfach vorgehen, wenn ich
eine Formel in konjunktiver Normalform habe, wandle ich sie einfach um
in disjunktive Normalformen und ich bin fertig.
Dann geht es ja ganz schnell.
Für die Frage dürfen Sie sich aber noch nachdenken, was man damit
machen kann.
Also, das ist...
Ich denke, das war ganz instruktiv, sich die Frage anzugucken.
Sie können es noch drüber nachdenken, wenn Sie wollen.
So, das ist Close Question.
Gut, wieder zur Vorlesung zurück.
Also, wir haben hier, also Alternative 2 war richtig.
Ich brauche nur, der erste Term, die erste Konjunktion hat maximal so
viele Variablen drin, wie ich halt Variablen in meiner Funktion habe.
Also, wenn ich eine k-stellige Funktion habe, habe ich gerade k
-verschiedene Variablen.
Das ist damit geklärt.
Das zu diesen 16 Funktionen ist die Frage, wie kann ich damit umgehen.
Etwas, was uns auch noch interessiert ist, wie muss ich eigentlich,
wie kann ich diese verschiedenen Funktionen darstellen in Hardware zum
Beispiel.
Wie mache ich das?
Und in Hardware darstellen heißt, ich muss für jede Operation, die
dort vorkommt, ja irgendetwas hinschreiben.
Und wie viele verschiedene Möglichkeiten muss ich dafür vorsehen?
Theoretisch formuliert reden wir da von sogenannten Verknüpfungsbasen.
Wenn eine Menge von Verknüpfungen heißt Verknüpfungsbasis für eine
Funktionsmenge f, genau dann, wenn sich jede Funktion f aus f allein
mit Verknüpfungen v aus v darstellen lässt.
Also, in diesem Fall haben wir eine Menge von Funktionen.
Ich hatte hier also die zweistelligen Funktionen gerade betrachtet.
Das sind also alle Funktionen, alle zweistelligen Funktionen.
Hier hat jemand eine Frage.
Die Lösung war nicht b, sondern 2, also b oder 2.
Das habe ich glaube ich gerade beantwortet.
Und jetzt haben wir die zweistelligen Funktionen, das sind 16 Stück.
Und wir haben ja eine Verknüpfungsbasis.
Wir haben nämlich die Konjunktion, die Disjunktion und das Komplement.
Das ist unsere Verknüpfungsbasis, die die Buscher Algebra oder auch
die Scheißalgebra definiert.
Kann ich das auch kürzer machen?
Kann ich mit weniger Operationen auskommen?
Und was man sich sofort überlegen kann ist, selbstverständlich kann
ich mit weniger auskommen.
Ich brauche ja nur mir das hier anzugucken.
Und und Komplement.
Konjunktion und Komplement.
Wie kann ich denn eine Disjunktion?
Ich möchte gerne a oder b darstellen.
Und das möchte ich darstellen durch eine Konjunktion und ein
Komplement.
Naja, wir kennen ja die demogrischen Gesetze und wir wissen, wir
brauchen nur hinzuschreiben a quer und b quer.
Wir machen darüber ein Querstrich und das ist ja gerade gleich a oder
b.
Ja, das ist a quer quer oder b quer quer und a quer quer ist a und b
quer quer ist b.
Also offensichtlich ist das hier ganz einfach.
Symmetrisch können Sie Disjunktion, Komplement, die Konjunktion
darstellen.
Das interessante ist, wir können das sogar mit einer Operation machen.
Wir können uns die NOR-Funktion hier nehmen oder die NAND-Funktion und
können damit alle anderen darstellen.
Wie geht das denn jetzt?
Also, das sieht schon fast so aus.
Hier haben wir die Disjunktion und hier steht ein, das ist ein NAND,
aber da steht noch a quer und b quer.
Wie kann ich denn a quer darstellen?
a quer über ein NAND.
Naja, a quer ist doch genauso das gleiche wie a.
Das ist doch einfach a zum Beispiel und a quer.
Ja, das ist gleich, dieses a und a quer ist gleich a quer oder a quer
und a quer oder a quer ist a quer.
Also das ist ganz einfach.
Und entsprechend können Sie, haben Sie also a quer, können Sie da
nochmal direkt reinschreiben.
Also hier a und a quer, das ist b und b quer und das Ganze nochmal als
mit NAND verknüpft.
Das heißt, Sie können dieses a oder b sehr einfach durch die NAND
-Funktion darstellen.
Sind zwar mehrere NAND-Funktionen, die Sie da brauchen, aber ist
nicht.
Also, ich kann im Prinzip eine Verknüpfung nehmen und damit alle
anderen Schaltfunktionen darstellen.
Ich muss also nur die geeignet verknüpfen.
Das heißt, ich bräuchte im Prinzip nur einen Baustein zu machen, der
diese eine Verknüpfung realisiert.
Und dann muss ich den nur geeignet mit anderen verknüpfen, also mit
anderen zusammen machen.
Ich brauche aber nur diesen einen Baustein.
Es gibt tatsächlich Schaltungen, die sind überwiegend über NAND oder
nur aufgebaut.
Wir machen darüber durchaus auch Anlass, wollte nur darauf hinweisen,
dass man das so machen kann.
Das ist eine einfache technische Realisierung, aber die Anzahl der
Verknüpfungsglieder wird größer und deswegen erhöhen sich die Kosten.
Sie brauchen also weniger Bausteine zu entwickeln, haben aber höhere
Kosten, weil Sie mehr Bausteine brauchen.
Also insgesamt mehr Schaltelemente in den Schaltungen.
Und wir werden uns solche Schaltungen gleich genauer anschauen.
Grundlegende Schaltungen.
Was sind grundlegende Schaltungen?
Also Schaltungen, mit denen man Verknüpfungen realisieren kann.
Eine Schaltung zur Realisierung spezieller ausgezeichneter
schaltalgebraischer Verknüpfungen nennt man Schaltgatter.
Auch digitales Verarbeitungsglied oder Gatter.
So, nun gibt es dafür verschiedene Bausteine.
Zum Beispiel gibt es das Negationsglied, um das Komplement
darzustellen.
Das Negationsglied, wir müssen A auf A quer transformieren.
Bisher haben wir nur Schalter angegeben, jetzt geben wir Schaltgatter
an, A auf A quer.
Dieses Symbol hier, 1, also ein Eingang, dieser Kringel da hinten sagt
negieren, Negation.
Ganz einfaches Element, zur Vereinfachung manchmal auch einfach nur
dieser Kringel.
Dann haben wir das Odergatter, die Oderverknüpfung.
Dafür gibt es auch eine Gatterangabe, also ein Schaltgatter, das in
der aktuellen Norm so aussieht.
Aus den beiden Eingängen A und B soll A oder B werden.
Also ein Signal, das den Wert A oder B repräsentiert.
Und hier steht drin, größer gleich 1.
Größer gleich 1 bedeutet, mindestens ein Eingang muss 1 sein, damit
der Ausgang 1 ist.
Genau das, was wir gerade eben noch überlegt hatten.
Bei einer Disfunktion reicht es, wenn ein Argument 1 ist, damit da
eine 1 rauskommt.
Und schließlich noch das Undgatter, das haben wir die elementaren
Funktionen alle dargestellt.
Das Undgatter, da steht aber nur das Und-Zeichen drin, oder ampersand
im Englischen.
Das heißt, hier müssen alle Eingänge 1 sein, damit eine 1 rauskommt.
Und jetzt sehen Sie, also das sind die elementaren Gatter, jetzt sehen
Sie auf dieser Seite hier noch so komische andere Symbole.
Und hier sehen Sie, die sehen ja völlig anders aus.
Warum macht man das?
Das hier, was ich hier angebe, ist seit 1976 so.
Und diese Symbole hier, die sehen schöner aus, die sind viel runder,
eleganter und so weiter, die hat man früher gehabt.
Also so ein Halbkreis hier mit einem schwarzen Punkt daneben, ein
ausgeführter Punkt, oder dieser Halbkreis und hier gehen zwei
Leitungen rein, hier bleiben sie davor, das waren also die Symbole für
Oder und Undgatter.
Warum wechselt man diese Technologie, also diese Beschreibungen?
Sie haben ja technische Spezifikationen, Sie haben technische
Zeichnungen von Schaltungen, wo solche Elemente auftauchen.
Und auf einmal entscheidet man sich, diese Norm, die man bis 1976
gehabt hat, zu ersetzen durch eine solche Norm, wo solche Symbole
drinstehen.
Aber eigentlich die Form ist bei allen gleich.
Hier sehen Sie aus der Form sofort, was das für eine Bedeutung ist,
hier sehen Sie das nicht aus der Form heraus.
Sie müssen angucken, was da drinsteht.
Warum macht man das?
Das hat einen ganz einfachen technischen Grund.
1976 begann man Computer-Aided-Design zu machen.
Schaltkreise direkt mit dem Rechner zu schreiben, zu zeichnen.
Und wenn Sie sich so ein Zeichengerät anschauen, das ist ein
sogenannter Flotter, die können etwas zeichnen.
Und ein Flotter, der hat hier unseren Arm, der hier rauf geht, der hat
dann hier einen Stift dran und kann sich hin und her bewegen.
Und den kann ich steuern.
Man musste sich also überlegen, wenn ich das maschinell machen will,
dann muss ich die Fähigkeiten dieser technischen Zeichengeräte
möglichst gut ausnutzen und es muss mit jedem solchen Zeichengerät
funktionieren.
Und das Problem war, diese Zeichengeräte konnten zwar hervorragend
horizontale und vertikale Linien zeichnen und die konnten auch kleine
Buchstaben oder kleine Kreise zeichnen.
Also Buchstaben konnten die malen, aber die konnten nicht solche
Rundungen zeichnen.
Das heißt, mit dieser Norm hier, die in anderer Form, aber ähnlich
auch mit solchen runden Formen auch im amerikanischen Bereich
verbreitet war, konnte man auf einmal keine technischen Zeichnungen
machen, wenn man sie mit einem Rechner machen möchte, mit einem
Flotter.
Und deswegen hat man gesagt, wir machen jetzt die Schaltelemente so,
dass sie mit horizontalen und vertikalen Linien auskommen.
Wir können etwas reinschreiben, wir können diese Zeichen durchaus da
reinschreiben, also die 1, Größe 1 und und.
Wir können also Buchstaben schreiben, aber wir können eben nicht
solche größeren Halbkreise malen.
Und so bestimmt also eine technische Randbedingung der Zeichengeräte
die Norm für die Darstellung von solchen Komponenten in technischen
Zeichnungen.
Heutzutage könnten wir problemlos solche etwas viel schöner
aussehenden Elemente zeichnen, aber wir haben immer noch diese Norm.
Ich würde kaum wieder zurückgehen zu einem Standard vor 1976, was wäre
das denn?
Also wir sind jetzt an diese Norm gebunden, die werden wir bewenden,
nur ich wollte Ihnen einfach mal zeigen, wie solche Normen entstehen.
In diesem Zusammenhang, weil die Flotter nur in der Lage waren, halt
in dieser Richtung und in der Richtung sich zu bewegen, nur
rechtwinklig konnten Buchstaben schreiben, rechtwinklig sich bewegen,
Linien zeichnen, aber eben keine solche Kreislinien zeichnen.
Das ging einfach.
Also, so verändern sich die technischen Standards.
Schauen wir uns das noch ein bisschen genauer an, ein bisschen weiter,
wir haben ja nicht nur Komplement oder und.
Wir haben zum Beispiel auch eine Norm von Sonoris, ganz einfach, da
brauchen wir nur das oder-grad-da-hinten-noch-ein-Negationsspiel dran
zu basteln.
Geht also ganz einfach, entsprechend das NAND, auch einfach nur ein
Negationsglied hintendran an das und.
Und wir können natürlich, wenn wir tatsächlich das realisieren, können
Sie das mit solchen komischen Teilchen hier mit ganz vielen Beinchen
dran machen.
Und da drin könnte zum Beispiel mehrere solche, in dem Fall wären das
NAND -Glieder.
Vier NAND könnten Sie auf einen integrierten Schaltkreis haben.
Die sind hier einfach nur nebeneinander dargestellt.
Hier wird nur dargestellt, wie man also tatsächlich das technisch
realisiert.
Ich könnte also auch in so einem IC, Integrated Circuit, zum Beispiel
solche vier NAND reinschreiben.
Ich hätte dann hier zwei Eingänge für das NAND, für dieses NAND hier.
Und da wäre der Ausgang, dann habe ich hier noch eine Stromversorgung
und da habe ich die Erdung.
Also ich muss mir Strom versorgen, ich kann bestimmte Dinge machen.
Mit solchen Dingen werden wir uns auch noch genauer beschäftigen, wenn
wir solche integrierten Schaltkreise haben.
Jetzt möchte ich noch ein bisschen komplexere Funktionen darstellen,
zum Beispiel ein XOR.
Wie kann ich ein XOR darstellen?
Zum Beispiel dadurch, dass ich hier diese Elemente nehme, aber
eigentlich sieht doch ein XOR anders aus.
Also ein XOR ist doch diese Schaltfunktion, beschrieben durch den
butschen Ausdruck A quer und B oder A und B quer.
Jetzt steht hier einfach nur 2k plus 1.
Warum 2k plus 1?
Das heißt, hier muss eine ungerade Anzahl von Eingängen 1 sein, damit
eine 1 rauskommt, ansonsten kommt eine 0 raus.
Für 2 Eingänge ist es einfach, da habe ich nur eine 1 oder eben an dem
einen oder anderen Eingang, dann ist es eine 1, ansonsten ist es eine
0.
Aber ich kann damit eben auch mehrstellige machen.
Das ist nochmal die Darstellung, wenn ich direkt die Gatter nehme.
Ich könnte jetzt ja meine Gatter, die ich gerade gebaut habe,
verwenden, um das hier darzustellen.
Ich hätte also hier zwei UNT-Gatter.
So gehe ich von einem Ausdruck in eine Schaltung über.
Ich brauche einen UNT-Gatter.
Ich male einen UNT-Gatter hin und muss jetzt da reinschreiben, dass
der eine Eingang A, der wird negiert.
Da habe ich den Kringel hingemalt.
Und der andere wird so genommen.
Und dann mache ich den UNT-Gatter, das gleiche nochmal symmetrisch für
A quer und B.
Und das Ganze wird mit der Distribution verbunden und am Ende kommt
hier ein Wert aus.
Okay, das ist also eine solche Schaltung, die abgekürzt ist auf diese
einfache Art und Weise.
Das kann ich natürlich auch mehrstellig machen.
Bei dem Baustein muss ich nur einfach dann entsprechend mehrstellige,
also mehrere Eingänge da reinmalen.
Wenn ich das auf Schaltung realisiere, habe ich ein bisschen mehr
Bauteile.
Und jetzt, also das ist klar, die 2K plus 1 ist nochmal diese
Überlegung.
Wenn ich bei der Ungradanze von einem Gegner 1 anliege, dann ist das
Ganze 1.
Nennt man eben auch Paritätsfunktion, da hätte ich sich mal drauf
hingewiesen.
Und jetzt kommt endlich ein Werkzeug dazu, das ich Ihnen schon lange
zeigen wollte.
Jetzt habe ich endlich Gelegenheit dazu.
Es geht um das Werkzeug Logiflash.
Ich hoffe, dass Sie das alles schon runtergeladen haben.
Es ist Ihnen bereitgestellt worden auf den zusätzlichen Materialien,
die wir Ihnen bieten.
Und Logiflash ist also ein Werkzeug, mit dem wir Schaltungen malen
können.
Ich hatte gerade gesagt, wie wir ein XOR-Element darstellen können.
Also was sehen wir hier?
Wir sehen hier eine ganze Reihe von verschiedensten Menüteilen.
Ich möchte jetzt ein... wir wollen ein UND-Glied bauen.
Ich sage also, ich klicke mal hier rauf auf AND.
Da gehe ich hier rein, klicke einmal rauf, da habe ich ein UND
-Element.
Ich klicke da nochmal rauf, da habe ich noch ein UND-Element.
Wir brauchen ein oder.
Das male ich mal hier hin.
Und jetzt brauchen wir noch entsprechende Möglichkeiten, Eingaben
anzugeben.
Wie kann ich Eingaben angeben?
Da brauche ich einen sogenannten Button, einen Knopf.
So ein Button, der kann also so aussehen.
Einer.
Und ich brauche noch einen.
Und ich muss Ihnen das Ergebnis darstellen können.
Das Ergebnis stelle ich aber mit einer Lampe dar.
Die machen wir da hinten hin.
So.
Das sind die Bauteile, die wir brauchen.
Nicht ganz, wir mussten ja... jetzt gehe ich also hier rein.
Wenn ich hier rein gehe in dieses Feld, dann kann ich die Teile, die
ich hier rauf gebaut habe, weiter bearbeiten.
Klicken wir das mal an.
Jetzt möchte ich zum Beispiel hier dafür sorgen, dass wir hier die
verbinden können.
Also ich nehme hier einfach mit dem Cursor hier rauf, klicke die linke
Maustaste und das Ganze ist verbunden.
So.
Jetzt kann ich also hier dieses Element hin und her ziehen.
Sehen Sie, da ist jetzt das Ding, kann ich beliebig hier das jetzt
verbinden miteinander.
Genauso kann ich dieses Umkleb nehmen und kann das damit verbinden.
Und ich kann dieses Umkleb nehmen, den Ausgang nehmen und den damit
verbinden.
So.
Kann ich aber auch das jetzt hier beliebig so...
Ups, da ist noch etwas nicht in Ordnung.
Der muss ja damit verbunden sein.
Sehen Sie, hier kann ich jetzt beliebig das Ding hier hin und her
ziehen.
Und jetzt muss ich dafür sorgen, wenn das hier A sein soll, der
Eingang A, dann muss ich den damit verbinden.
Das B verbinde ich mal zum Beispiel damit.
Und jetzt soll... ja, war ja noch was.
Wir sollten ja hier in der Lage sein...
Das machen wir so mal vor, wir wollten ja hier A und B quer draus
machen.
Das Ganze hier soll einmal negiert werden.
Ich habe jetzt auf Alt gedrückt und auf die linke Maustaste, dann wird
das negiert hier vorne.
Also nochmal Alt und linke Maustaste.
Dann kommt das dort hin.
Jetzt muss ich dafür sorgen, dass der Wert von A, dass der auch noch
hier rüber geht.
Wie kann ich das denn jetzt hinkriegen, dass ich hier noch das
verzweigen kann.
Also, das machen wir so.
Da gehe ich auf Steuerung, gehe hier rauf auf Steuerung und klicke
einmal die linke Maustaste an.
Dann habe ich da einen solchen Punkt.
Und dann gehe ich... ich hoffe, dass das jetzt funktioniert.
Mal gucken, ob das...
Wenn ich nur den Knopf jetzt ziehe, ziehe ich das, dann habe ich jetzt
hier so eine Verknüpfung, so eine Möglichkeit, da was zu tun.
Jetzt gehe ich mal auf Alt und... das geht nicht.
Also, wie habe ich das jetzt gemacht?
Ich habe das doch ausprobiert.
Ich versuche mal Alt und... das geht nicht.
Mein Gott, wie war das denn einmal?
Ich muss da rauf gehen,
gehe mal auf Steuerung.
Sie sehen, ich habe hier... ich bin auch nicht allwissend.
Manchmal wird das extra mir angeguckt.
Das ist ja echt dumm.
Ach ja, wie kann ich jetzt hier nochmal das da rausziehen?
Ich konnte das doch ganz einfach machen.
Wie ist denn das nochmal?
Ah, jetzt geht es.
So, ich habe auf Steuerung und linke Maustaste gedrückt.
Jetzt kann ich dieses hier rüberziehen.
Ah, und das soll jetzt damit verbunden werden.
Ist das verbunden.
Und das gleiche mache ich hier.
Einmal Alt und linke Maustaste.
Dann müsste hier solch ein...
na?
Steuerung und linke Maustaste.
Da ist er, genau.
Und jetzt kann ich das hier verbinden.
So, und hier rüber.
Das ist alles, was wir brauchen.
Wieso ist das alles?
Das ist jetzt also die Schaltung.
Zwei, zweimal Mundgatter, das mit dem Untergatter verbunden und hier
hinten die Lampe.
Jetzt machen wir das Ganze an.
Jetzt wird das mit Strom, mit Spannung versorgt.
Natürlich nur virtuell.
Ich kann hier raufklicken.
Jetzt habe ich aus einem Null eine Eins gemacht.
Wenn ich aus einer Eins mache, wird die Leitung entsprechend hier...
Es wird also dargestellt dadurch, dass ich hier die Farbe verändere.
Und die Leitungen, auf denen jetzt eine Eins liegt, sind jetzt mit das
Gelb markiert.
Hier kommt eine Null an.
Das wird aber negiert.
Das heißt, insgesamt haben wir hier eine Eins am Ausgang.
Beim Untergatter kommt eine Eins am Eingang.
Das heißt, der Ausgang wird auch Eins.
Deswegen leuchtet die Lampe.
Machen wir das auch auf Eins.
Dann haben wir A und B eins.
Dadurch kommt hier eine Null hin.
Das Mundgatter wird Null.
Das Mundgatter wird auch Null.
Wir haben zwei Null.
Die Lampe geht aus.
Mache ich das Ding wieder aus, ist entsprechend die Lampe wieder an.
Und wenn ich die Lampe auch ausmache, ist natürlich wieder alles aus.
Also, jetzt haben Sie kurz gesehen, wie man sowas macht.
Also nochmal, wenn ich hier mit Steuerung und rechter Maustaste auf
eine Leitung gehe, dann kann ich dann einen Verzweigungspunkt einbauen
und kann dann auch von dem Verzweigungspunkt aus weiter zeichnen.
Das müssen Sie alles ausprobieren.
Es gibt auch eine Anleitung dafür.
Das steht alles in den Werkzeugen bereit.
Dann wissen Sie genau, wie man sowas macht.
Dann kann man hier auch noch solche Dinge tatsächlich genauer
darstellen.
Sie können also hier lesen aus der Bibliothek.
Und dann sehen Sie, steht hier also das XOR zum Beispiel.
Das hätte ich mir auch laden können.
Lade ich laden.
Dann habe ich es hier etwas anders dargestellt.
Ich habe es ein bisschen einfacher gemalt.
Ich habe also insbesondere hier nicht das A quer über so einen
Negationsglied gemacht und habe das einfach am Eingang hier verändert.
Das ist also eine Alternative zu dem, was ich gerade dargestellt habe.
Aber das ist also nicht das XOR-Element.
Das gleiche nochmal.
Und ich kann halt hier beliebig die Elemente verändern.
Das ändert also an der Funktion gar nichts.
Das ist alles schön verbunden miteinander.
Was habe ich mit diesem Werkzeug also für eine Möglichkeit?
Ich kann Schaltungen zeichnen durch diese grafischen Komponenten, die
ich zur Verfügung habe und ich kann gucken, was passiert, wenn ich
jetzt hier bei den Eingängen irgendwas verändere.
Ich kann also simulieren, was eine Schaltung macht.
Also ein Werkzeug, um also rechnergestützten Entwurf von Schaltungen
zu machen.
So können wir also Hardware entlernen.
Gut, dazu gehen wir zurück zur Vorlesung.
Und wir gehen zum nächsten Element.
Mehrstellige Gatter.
Wir können also OR-Gatter mit N Eingängen machen.
Das gleiche Symbol, es steht einfach größtenteils 1 drin.
Oder wir machen ein AND-NOR oder ein AND-Gatter mit mehreren
Eingängen.
Auch kein Problem.
Da will ich jetzt gar nicht auf die Animation gehen.
Ich will zum nächsten Thema.
Wir können also jetzt mit solchen Schaltelementen, können wir solche
Verknüpfungen darstellen.
Wir wollen aber eigentlich mehr machen, als einfache Schaltfunktionen
darstellen.
Wir wollen zum Beispiel Schaltnetze bauen.
Das heißt, wir haben irgendwelche Eingänge, A1 bis AN.
Das sind irgendwelche Eingaben, binäre Eingaben.
Und ich habe eine Schaltfunktion, irgendein Schaltnetz.
Und dann kommen da N Werte los.
Ich habe für jeden dieser Werte, für jeden dieser Ausgänge eine
Schaltfunktion.
Ich habe aber eben nicht nur einen Wert, einen binären Wert, sondern
mehrere solche Werte.
Und das sind meine Ausgaben.
Und die Schaltfunktion muss ich geeignet beschreiben.
Also diese Schaltfunktion besteht aus der Kombination von M solchen...
oder das Schaltnetz besteht aus der Kombination von M solchen
Schaltfunktionen.
Und das Schaltverhalten ist in dem Sinne kombinatorisch, das ist also
ein wichtiger Begriff, den wir hier haben.
Man nennt das also kombinatorisch.
Es werden die Werte an den Ausgängen erzeugt aus den Werten an den
Eingängen.
Und nichts anderes spielt eine Rolle.
Nur diese Werte.
Das heißt, wenn ich mehrfach den gleichen Wertort und die gleiche
Kombination angebe, bekomme ich immer das gleiche Ergebnis.
Ich habe in dem Sinne kein Gedächtnis in diesem Element, in diesem
Schaltnetz.
Dieses Schaltnetz ist also eine Zusammenfassung von M solchen
Schaltfunktionen.
So, und jetzt schauen wir uns das Ganze mal ein bisschen offen an.
Also ein Beispiel, also unser Halbaddierer.
Was ist ein Halbaddierer?
Der kann Zahlen oder Bits addieren.
Wir wollen zwei Dualziffern addieren.
Also wenn wir Dualziffern addieren, kann sowas passieren, dass wir 0
und 0 addieren, kommt natürlich ein 0 raus.
Oder wir addieren 0 und 1, dann kommt natürlich eine 1 raus.
Das wäre das Summenbind.
Wenn wir aber 1 und 1 addieren, wissen wir, da kommt eine 0 raus und
eine 1 als Übertrag.
Das ist etwas, was hier steht, hier unten.
Ein Übertrag, wenn beide Werte 1 sind.
So etwas muss ich darstellen können durch ein Schaltelement, auch eine
Verknüpfung von zwei Elementen.
Und ich habe halt zwei Ausgänge, das Summenbind und das Übertragsbind.
Und das Ganze ist natürlich sehr einfach zu sehen.
Das sind zwei zweistellige Schaltfunktionen.
Wir wissen, wie man die darstellt.
Das eine ist die XOR-Operation und das andere, also S ist gerade A XOR
B.
Und der Übertrag ist gerade die Konjunktion der beiden.
Das heißt, wir haben einen Halbaddierer, der einfach die Kombination
dieser beiden Bauteile ist.
Können wir als Schaltung aufbauen, als Schaltnetz mit zwei Ausgängen.
Und dafür können wir auch ein Symbol einführen.
Das ist unser Schaltnetz mit zwei Eingängen und zwei Ausgängen, Ü und
S.
Zwei Schaltfunktionen.
Und entsprechend, wenn es einen Halbaddierer gibt, gibt es auch einen
Volladdierer.
Und der Volladdierer ist dazu geeignet, tatsächlich bei größeren
Zahlen etwas zu addieren.
Das heißt, da haben wir nicht nur zwei Eingänge, sondern wir haben
drei Eingänge.
Ich sagte ja, wenn wir hier zum Beispiel so etwas wie 0, 1, 1, 0 und
wir wollen hier eine 0 sein.
Wir machen hier jetzt 0, 1, 0.
0 meinetwegen.
Dann haben wir hier natürlich als Ergebnis 0 stehen.
Hier steht auch eine 0.
Dann haben wir hier den Übertrag 1.
Das heißt, hier müssen wir drei Werte addieren können.
Deswegen diese drei Werte.
An den Stellen, wo ich nichts hingeschrieben habe, steht natürlich
auch etwas.
Da steht also jetzt, hier kommt eine 1 hin, dann kommt hier eine 0 und
wieder ein Übertrag.
Dann machen wir eine 1 und dann kommt hier unten auch eine 1 hin.
Dann haben wir Übertrag 0.
Das heißt, wir haben hier jeweils einen Übertrag stehen.
Und dieser Übertrag wird zusammen mit den beiden Eingaben Bits
berücksichtigt.
Wir haben unsere drei Eingänge, eine dreistellige Funktion.
Bei den dreistelligen Funktionen haben wir entsprechend 2 hoch 3 Werte
-Kombinationen.
Also wird die Tabelle ein bisschen größer.
Und das Summen-Bit ist natürlich nach wie vor gleich 1, wenn wir eine
ungerade Zahl von 1en haben.
Und das Übertrag-Bit ist 1, wenn wir mindestens zwei 1en haben.
Mindestens zwei 1en kommt mit Übertrag 1 raus.
Wenn wir drei 1en haben, kommt als Übertrag auch eine 1 raus.
Aber auch der Summen-Bit ist dann 1.
Und die Schaltung sieht entsprechend so aus.
Einfach diese Formel hier, die beiden Formeln hergenommen.
Für das Summen-Bit ist es die einfache XOR-Funktion, also ein dreifach
XOR.
Für das Übertrags-Bit ist es eine Disjunktion dieser drei
Konjunktionen, wo wir jeweils zwei Elemente zusammenbauen.
Auch das können wir uns angucken in der Logiflash-Animation.
Nur um das nochmal kurz zu zeigen, wie dieses aussieht.
Wenn wir also hier uns angucken, der Volladierer, genau, das ist er.
Wenn wir den laden, dann ist das hier genau die Schaltung.
Hier allerdings einmal 90 Grad gedreht.
Unsere drei Eingänge, A, B, C.
Und die kann ich jetzt zum Beispiel mit A auf 1 setzen.
Hier ist es mit Rot markiert, kann man also Farben auswählen, wie man
andeuten will, dass das Signal in Einsordnung besteht.
Noch eine kleine Abweichung von dem, was ich Ihnen gerade dargestellt
habe.
In dieser Logiflash-Animation hat man aus Platzgründen nicht 2K plus 1
reingeschrieben, sondern nur einfach gleich 1.
Gleich 1 heißt also, das soll 2K plus 1 sein.
Das heißt, ich habe entweder beim zweistelligen nur ein Element dort
drin stehen.
Nur Eingang gleich 1.
Genau, so einer ist 1.
Und ansonsten, wenn ich ein mehrstelliges machen würde, soll es halt
andeuten, dass es ungerade ist.
Die Anzahl der Einsen, die ich brauche.
Das also zu diesem Element hier.
Und dann habe ich hier die Möglichkeit, wie gesagt, wenn A und B 1
sind, dann ist die Summe 0, das XOR.
Der Übertrag ist aber 1.
Wenn alle 3 1 sind, wird die Summe auch 1.
Der Übertrag bleibt 1.
Wenn wir das A zum 0 machen, bleibt der Übertrag 1.
Die Summe geht auf 0.
Wird B auch 0.
Und der Übertrag ist 1.
Kommt da Summe 1 raus und der Übertrag ist 0.
Also das ist ganz einfach hier in diesem Fall.
Einfache Schaltung.
Machen wir beide zu.
Und wir gehen wieder zur Präsentation.
An diese Stelle.
Und sind hier wieder drin.
Und haben da den Stift.
Und das ist jetzt unser Schaltelement hier für den Volladierer.
Wir haben 3 Eingänge.
Das Ü ist so komisch an die Seite gemalt, weil das ja immer von rechts
kommt.
Von der nächsten Stelle.
Und das Ü' die Ausgabe, der Übertrag nach draußen, der wird so nach
links rüber gemalt.
Und im Ausgang wird der ja in die nächste Stelle reinlaufen, wie Sie
gleich sehen werden.
Und die beiden Bits unserer Zahl, die wir addieren wollen, die stehen
halt hier oben drüber.
So, das Ganze können wir auch zusammenbasteln zu einem größeren
Schaltelement.
Ein sogenannter Ripple-Carry-Adder.
Ein Ripple-Carry-Adder.
Was macht der?
Der nimmt zwei Zahlen her.
Addierer mit durchlaufendem Übertrag, Deutsch.
Der nimmt zwei Zahlen, A und B.
Also zwei endstellige Zahlen, AN-1 bis A0 und BN-1 bis B0 und addiert
die beiden Zahlen.
Und dann kommt eine Summe raus.
Und das ist dann entweder hier SN bis S0 oder kann man sagen UN bis U.
Also der Übertrag des letzten Volladdierers.
Und Sie sehen, ich brauche hier für die rechteste Stelle, für das
niedrigsignifikante Bit, brauche ich keinen Volladdierer, also nur
einen Halbaddierer, weil ich ja hier keinen Anfangsübertrag habe.
Und ansonsten schreibe ich überall Volladdierer rein, weil ich hier
den Übertrag aus der davorgehenden Stelle jeweils mit berücksichtigen
muss.
Und dann kann ich eben hier das ganze Ding auch tatsächlich bauen.
Ich habe hier glaube ich noch ein Beispiel drin, habe ich hier nicht.
Ich werde es gleich nochmal zeigen, wie das in Logiflash aussieht.
Die Schaltzeit, die ist hier relativ lang.
Warum ist die relativ lang?
Wobei ich sagen muss, die ist manchmal relativ lang.
Wenn ich nur hier unten Nullen, also wenn ich hier oben überall Nullen
habe und nur hier eine 1 bei einem der Eingänge, dann muss ja nur hier
unten das S0 sich verändern, alle anderen bleiben 0.
Jetzt könnte es sein, dass Sie hier, wenn Sie Zahlen haben, wie zum
Beispiel 1, 1, 1, 1, 0, Sie machen hier eine 1, 0, 0, 0, 0.
Was passiert denn dann?
Vorher meinte ich gar nicht, ich meine, ich mache hier doch noch eine
1 hin.
Ich addiere hier eine 1 drauf.
Dann wird hier am Ende, kommt dann hier eine 0 und dann eine 1 hin.
Nein, keine 1, Übertrag 1, wieder eine 0.
Das habe ich, genau, ich habe zwei 1, habe eine 0, dann kommt da eine
0 hin, kommt da eine 0 hin, da eine 0 und da eine 1.
Und das heißt, wir müssen hier so der Reihe nach hier durchlaufen.
Wenn wir erst einmal ganz durchgelaufen sind, von rechts nach links,
haben wir am Ende das Ergebnis produziert.
Deswegen lange Schaltzeit, linear in der Anzahl der Bits unserer Zeit.
Interessant, lineare Zeit.
Wenn Sie also eine 32-Bit-Arithmetik machen mit einer 64-Bit
-Arithmetik, würde hier nach die 64-Bit-Arithmetik doppelt so lange
dauern wie die 32-Bit-Arithmetik.
Die Rechner werden aber gar nicht so viel lang dauern.
Dann würde es doch nicht Sinn machen, die so zu bauen, mit 64-Bit
-Arithmetik das zu machen.
Da kommen wir gleich drauf.
Ich gehe jetzt nochmal hier, ich kann hier noch ein paar andere Sachen
machen.
Ich kann auch noch Verzögerungselemente einbauen, da kommen wir gleich
drauf.
Jetzt gehe ich erstmal wieder auf das Logiflash und zeige Ihnen, wie
wir hier für den Ripple-Carry-Adder, wie der hier aussieht.
Das ist ein Ripple-Carry-Adder.
Der hat jetzt hier den Halbadierer, ganz rechts, hat einen
Volladierer, Volladierer, Volladierer, Volladierer.
Also ein 5-Bit-Addierer.
Jetzt haben wir hier überall...
Nun, ich mache das Ding mal auf.
Und jetzt setze ich mal beim A überall das, was hier steht.
1, 1, 1, 0.
1, 1, da soll hier eine 0 sein.
Und das B ist hier gerade eine 1.
Jetzt falten wir das ein.
Dann sehen Sie, genau das muss da rauskommen.
Da haben wir überall Einsen.
Und jetzt mache ich hier draus, aus diesem Bit, eine 1.
Und das sehen Sie, so lange dauert das gar nicht.
Das verliniere Zeit in der Länge der Schaltung.
Nochmal.
Wenn ich jetzt das A 0 mache, dann sind diese alle 1.
Und wenn ich das zu einer 1 mache, dann laufen die Einsen hier so
durch.
Also, das sind ja nur 5-Bit, das geht relativ schnell.
Wenn das eine lange Zahl ist, daraus zu sprechen, länger.
Linierab in der Anzahl der Bits.
Und jetzt wollen wir das Ganze einfach mal...
Ich hatte da so eine komische Bemerkung, man kann ja auch
Verzögerungslieder einbauen.
Dann nehmen wir doch mal das mit Verzögerungslieder ein.
Getakteten Ripple-Carry-Adder.
Was ein Takt ist, darauf kommen wir gleich noch zu sprechen.
Getaktet.
Ich habe also hier ein Verzögerungslied eingebaut.
Das ist hier das Delay-Element.
Da kann man verschiedene Sachen einstellen.
Man kann also hier einen idealen Verzögerungslied haben oder einen
Absorber.
Also ein Element, das einfach den Wert verschluckt.
Ich kann es auch in zwei Richtungen machen.
Da gibt es verschiedene Möglichkeiten dafür.
Ich habe hier einfach ein Delay-Element.
Jetzt wollen wir uns das Ganze einmal hier angucken.
Jetzt wieder unsere Zahl.
Ich mache hier wieder eine 1 rein.
Dann haben wir an diesen vier Stellen hier, das W0 macht auch eine 1.
Dann haben wir hier unsere vier Summen-Bits auf 1.
Wir haben an keiner Stelle irgendeinen Übertrag.
Das ist also ganz einfach.
Jetzt wird das A0 zu 1.
Und jetzt sehen Sie hier geht es etwas...
sieht man deutlicher diese Verzögerung.
Ich kann auch hier die Werte einfach alle verändern.
Ich kann hier meinetwegen 10 reinschreiben.
Und da kann ich entsprechend auch eine 10, nicht 101, das wollte ich
nicht.
10, dafür eine 10.
Und hierfür eine 10.
Dann dauert es ein bisschen länger.
Dann sehen Sie diesen Effekt ein bisschen deutlicher.
Wenn das jetzt hier 0 ist, dann haben wir...
Ups, was ist das denn?
Bitte?
Ah, da ist es.
Es dauert.
1, 1, 1, 1, 0 und 0, 0, 0, 0, 1.
Und jetzt wird hier raus eine 1.
Dann sehen Sie mit... ah, da habe ich 101 geschrieben, deswegen dauert
das so lange.
Genau, das machen wir wieder zu einer 10.
Das ist etwas besser.
Dann geht es etwas schneller.
Ja, nochmal, wenn ich das hier zu einer 0 mache, dann wird es
entsprechend...
das wandert natürlich jetzt auch durch, weil hier sukzessive die
Nullen durchwandern müssen.
Wenn ich das 0 auf eine 1 setze, dann wird entsprechend mit
Verzögerung jeweils hier das durchlaufen.
Warum baut man da jetzt ein Verzögerungselement ein?
Weil es einen Vorteil hat, es wird ja alles viel langsamer.
Es hat aber einen Vorteil.
Ich kann nämlich das ausnutzen bei meiner Eingabe.
Schauen wir das mal wieder an.
Ich habe das jetzt hier auf der Folie dargestellt.
Wir können bei unserem Addierer das auch ein bisschen anders
gestalten.
Wir haben also den getakteten Ripple-Carry-Addierer, der jetzt hier
nochmal etwas symbolisch, etwas abstrakter dargestellt ist.
Das ist unser getakteter Ripple-Carry-Addierer.
Und ich mache jetzt einfach eine verzögerte Eingabe.
Und zwar sage ich, da habe ich hier in dem Fall sogar vier volle
Addierer.
Und ich gebe hier links Anfangsüberträge ein.
0, 0, 0, 0.
Der Anfangsübertrag ist 0.
Dann diese Eingänge sind durchnummeriert, die Ausgänge sind auch
durchnummeriert.
Und jetzt kommt der erste Takt.
A0 und B0 werden addiert, zusammen mit der 0.
Und es kommt ein Summen mit raus.
Mit Verzögerung.
Jetzt ist der nächste... also jetzt sind die weitergelaufen.
Jetzt kommen A1 und B1 rein in den nächsten Volladdierer hier.
Und es kommt das S0 dort unten raus.
Und ich habe jetzt hier wieder ein A0, B0 stehen, aber das ist A0, B0
von der blauen Addition.
Ich habe hier eine schwarze Addition, eine blaue, eine rote, eine
grüne.
Zeitlich versetzt.
Und jetzt kommt hier das Summen mit raus, S1, für die erste Addition,
die schwarze Addition, und das Summen mit S0 von der blauen Addition.
Wenn wir jetzt so weitermachen, dann haben wir hier nebeneinander
unsere vier Volladdierer, die aktiv sind, um A0, B0, der grünen
Addition, zu berechnen.
Das Summen mit S0 dafür.
A1, B1, das werden also jetzt von der roten Addition berechnet oder
addiert.
A2, B2 werden addiert aus der blauen Addition und A3, B3 aus der
schwarzen Addition.
Wir haben dafür gesorgt, dass wir diese lineare Verzögerung ausnutzen
können, um trotzdem alle vier Volladdierer aktiv sein zu lassen,
gleichzeitig.
Das heißt, wenn wir das jetzt hier weiter durchlaufen lassen,
sukzessive werden alle Bits dort durchgeschoben und am Ende haben wir
also hier diese Situation.
Wir haben vier Additionen gemacht.
Wir haben jeweils hier die Bits für eine Addition so nacheinander
zeitlich versetzt eingegeben.
Aber in jedem Takt versorgen wir unser...
Ups, das wollte ich nicht.
Da müssen wir wieder zurückkommen zu dem, wo ich gerade war.
Das ist hier, also ich habe in jedem Takt alle meine vier Volladdierer
aktiviert.
Ich kann in jedem Takt vier Summenbits produzieren, aber aus vier
verschiedenen Additionen.
Das heißt, ich nutze meinen Addierer mit bestmöglicher Leistung.
Alle Komponenten sind stets aktiv für unterschiedliche Berechnungen.
Und das heißt, das was ich mache hier ist ein sogenanntes Pipelining.
Und der Effekt kann so dargestellt werden, normalerweise würde ich die
Additionen so durchführen, die schwarze Addition, die blaue Addition,
die rote Addition, bei der Addition, wenn es nicht im Pipelining
-Verfahren läuft, nacheinander.
Wenn ich das Ganze aber im Pipelining-Verfahren mache, dann sieht das
so aus.
Dann kann ich mit jeweils einem Takt Abstand eine neue Addition
beginnen.
Das heißt, wenn ich N solche Additionen mache, kann ich die in N
aufeinanderfolgenden Takten anfangen, bis hier hin.
Und dann muss ich noch die Zeit durchsichtigen, um einmal
durchzulaufen.
K bits, noch K-1 weitere, also N plus K-1 und ich bin fertig.
Während wenn ich das hier mache, N Additionen von K-Bit-Operanden,
brauche ich N mal K.
Wir haben also eine deutliche Verbesserung im Zeitverhalten.
Ich kann in jedem Takt eine Addition beginnen.
Im Prinzip habe ich, wenn ich viele Additionen nacheinander mache, ist
die erwartete Zeit konstant.
Nur bestimmt durch die Schaltzeit eines Volladditors.
Und ich kann also viele Operationen mit einem hohen Durchsatz
bearbeiten.
Das ist das Pipelining-Prinzip, taucht bei vielen Bereichen in der
Industrie, nutzt man das auch bei der Fertigung von Fahrzeugen, wissen
Sie, T-Modell von Ford war deswegen so preiswert zu tragen, weil man
das im Pipelining-Verfahren gemacht hat, da konnten die
Produktionsressourcen bestmöglich aufgenutzt werden.
Das war Anfang des vorigen Jahrhunderts.
Pipelining nutzen wir im Rechner an ganz vielen Stellen, unter anderem
in der Rechnerarithmetik.
Und das zeigt hier eben sehr deutlich, dass man hier von einer
linearen Laufzeit für die einzelnen Berechnungen, die sich gar nicht
ändert, die Laufzeit für die einzelnen Berechnungen ist genau gleich.
Vielleicht sogar ein bisschen größer, weil ich ja hier noch
Übersorgungsglieder mit drin habe, aber der Durchsatz wird deutlich
erhöht, weil ich die Elemente in jedem Tag alle ausnutzen kann.
Und deswegen also ein deutlicher Zeitbild.
Ganz wichtig zur Beschleunigung von Rechnern.
Ihre Rechner, die Sie verwenden, sind nur so schnell, wir können nur
in den Gigahertzbereich reinkommen, weil wir mit Pipelining arbeiten.
Ohne Pipelining wären wir bei wenigen Megahertz.
Das ist also alles ein Effekt von Pipelining.
Da kommen wir später noch dran.
Das ist also ein wichtiger Effekt.
Wir können durch diese getakteten Elemente, da hatte ich Sie schon mal
drauf hingewiesen.
Ich hatte gesagt, es gibt Millionen Moorautomaten.
Moorautomaten kann ich verwenden in Situationen, wo wir Pipelining
verwenden.
Das sind im Prinzip ja alles kleine Moorautomaten, die wir
zusammenbauen.
So, nächste Alternative.
Ich baue einen ganz anderen Addierer.
Nur, dass Sie mal sehen, was man macht, wenn man Hardware entwirft.
Also binäre Additionen sind wirklich das einfachste von der Welt.
Das ist doch ganz klar, dass da der Übertrag von der einen Stelle
abhängt von dem Übertrag von der vorgehenden Stelle.
Selbstverständlich habe ich diese linearen Abhängigkeit.
Ich brauche dafür lineare Zeit.
Wie soll das anders laufen?
Der Informatiker, der sagt, der bearbeitet sehr ungern große Probleme.
Der Informatiker sagt, ich teile meine Probleme auf.
Ich möchte gerne nicht zwei große Zahlen addieren, sondern ich teile
das auf, mache daraus zwei halb so große Zahlen, beziehungsweise zwei
Additionen von halb so großen Zahlen und addiere die ein.
Ich habe also die Aufgabe reduziert auf die Hälfte, die bei einem
Konkeransatz.
Und habe jetzt also hier nur die beiden linken Hälften zu addieren,
beziehungsweise die beiden rechten Hälften.
Das Problem ist nur, wenn ich die Summe hier berechne, das ist mein
S2, ist das zwar die richtige Summe von A2 und B2, aber wenn ich das
A1 und B1 berechne, ist das nicht notwendigerweise das, was hier
stehen muss?
Dieser Teil, der muss ja den Übertrag hier noch berücksichtigen.
Jetzt macht man einfach einen Trick.
Man sagt, naja, welche Möglichkeiten habe ich denn für diesen
Übertrag?
Die Möglichkeiten sind, dass ich den Übertrag 1 habe oder den Übertrag
0.
Und das kann ich ja beides berücksichtigen.
Ich berechne einfach parallel A1 plus B1 und A1 plus B1 plus 1.
Und habe dann diese Summe und diese Summe.
Die berechne ich einfach nebeneinander.
Ich habe ja keinen genügend Hartz-Wirr-Spinn hier.
Und außerdem berechne ich das S2.
Und dann muss ich nur noch überlegen, welcher dieser beiden, dieser
oder dieser Teil ist richtig.
Und das wird bestimmt durch diesen Übertrag, der aber erst zur
Verfügung steht, wenn ich fertig bin mit der Addition.
Das heißt, ich brauche dafür einen sogenannten Multiplexer.
Ein Element, ein Schaltelement, das eine Auswahl treffen kann.
Dieser Multiplexer wird gesteuert durch dieses Übertragsbit.
Und wir berechnen also die Summe der linken Hälfte, die Summe der
rechten Hälfte.
Bei der linken Hälfte berechnen wir auch noch alternativ das S1 plus
1.
Und dann, sobald der Übertrag jetzt zur Verfügung steht, wird er
verwendet, um auszuwählen, ob ich die Bits brauche aus der linken
Hälfte oder der rechten Hälfte.
Also aus S1 oder aus S1 plus 1.
Das ist ein konstanter Aufwand, um hier durchzulaufen.
Und dann habe ich an dieser Stelle S1 oder S1 plus 1.
Und hier habe ich A2 plus B2 stehen.
Ups, an dieser Stelle.
Das heißt, insgesamt ist dann das, was hier steht, genau das, was hier
oben berechnet wird.
Das ist ja viel komplizierter, als wenn man die einfache Addition
macht.
Da brauchen wir noch einen Multiplexer, wir müssen hier S1 berechnen,
S1 plus 1 und so weiter.
Aber Sie sehen, wir haben jetzt hierfür den halben Aufwand.
Also der Aufwand, die Zeit, um eine n-Bit-Addition zu machen.
Wenn wir das nebeneinander machen, parallel, dann ist das der Aufwand,
um eine Addition von Elementen der Größe n halber zu machen, plus, ich
sage mal, plus 2.
Mehr ist das nicht.
Also hier, dieses muss ja noch was auswählen, eigentlich sogar nur
plus 1, also bloß eine Konstante.
So, und das ist eine tolle Formel.
Wenn ich jetzt T von, sagen wir mal gegen T von 1, gegen T von 2.
Also T von 1 ist sowieso, das ist 1, der Aufwand.
Und wenn wir 2, das ist alles ganz einfach.
Das ist die Basis, T von 1 ist 1.
Wenn Sie eine solche Rekursionsformel haben, Sie sehen, wir machen das
Ganze natürlich rekursiv.
Das hier machen wir natürlich auch so, dass wir hier entsprechend
aufteilen, da teilen wir auch entsprechend auf.
Dann haben wir auf einmal insgesamt als Zeitaufwand logarithmische
Zahlen.
Weil wir nämlich eine Baumstruktur haben.
Wir haben im Prinzip Berechnungen, wenn wir das hier so uns angucken,
jeweils in einem Viertel der Zeit, in einer halben Zeit, das gibt uns
das ganze Ergebnis.
Wir haben hier insgesamt dann als Höhe des Baumes Log N, wenn wir also
insgesamt hier Länge N haben, und das heißt, wir haben von einer
linearen Laufzeit der einzelnen Additionen, das reduziert auf eine
logarithmische Laufzeit.
Das ist also ein exponentieller Unterschied.
Deutlich weniger.
Wenn Sie also 1.000 Bit-Zahlen addieren wollen, können Sie das hier im
Prinzip mit Größenordnung 10 Zeiteinheiten machen.
Ich lasse mal Konstanten weg.
Und brauchen nicht 1.000 Zeiteinheiten.
Großer Unterschied.
Also, Sie haben jetzt eine Rechenzeit in Log N, aber einen höheren
Flächenaufwand.
Das ist nicht die einzige Art, wie man das machen kann.
Noch mehr Möglichkeiten.
Das nächste ist ein Addierer, dieser CarrySelectAdder ist ein
Addierer, der tatsächlich in bestimmten Anwendungen verwendet wird.
CarryLookAtAdder, noch ein anderer, der auch verwendet wird in der
Realität.
Und zwar wird jetzt noch was anderes ausgenutzt.
Also wenn ich hier zwei Zahlen...
Ich habe hier meine zwei Zahlen, die ich addieren möchte.
Das stehen hier 1 und 1.
Wenn ich die beiden addiere, dann weiß ich, hier kommt irgendwas raus,
aber der Übertrag, der ja noch entstehen muss, den male ich mal hier
unten runter.
Und da kommt irgendwas hier unten, also ein Bit.
Und der Übertrag, der hier entsteht, ist garantiert ein 1.
Völlig unabhängig davon, was rechts davon steht.
Und wenn ich das hier angucke und da stehen zwei 0, dann weiß ich,
egal was hier von rechts dazu kommt, selbst wenn hier eine 1 steht, es
wird hier garantiert eine 0 stehen.
Unabhängig davon, was rechts da stand, weil nämlich der Übertrag gar
nicht weiterlaufen kann.
Wenn aber hier zwischen irgendwie eine 0 und eine 1 war und da kommt
eine 1 dazu, dann weiß ich, an der nächsten Stelle muss auch eine 1
stehen.
Dann muss da auch eine 1 sein, weil der Übertrag hier, wenn hier
bereits eine 1 steht, einer von den beiden ist bereits eine 1, das ist
dieses Propagate, dann wird der Übertrag weitergehalten.
Das heißt, ich habe im Prinzip, je nachdem, was hier steht, drei
verschiedene Situationen.
Eine Generate-Situation, das wird der Übertrag erzeugt, garantiert
erzeugt, unabhängig davon, was rechts der Fall war.
Es wird den Übertrag weitergeleitet, weil dort nur einer von den
beiden Argumenten eine 1 ist.
Oder ich weiß, der Übertrag kann gar nicht weiterlaufen.
Und das heißt, wenn ich an dieser Stelle hier vorne wissen will, was
ist denn hier der Übertrag, der da rauskommt.
Und ich habe hier vorne zwei Einsen stehen, weiß ich sofort, bin
fertig, kann die Einsen schreiben, ich brauche gar nicht zu warten,
bis es alles durchgelaufen ist.
Wenn dort 0, 0 steht, weiß ich, da vorne steht auch eine 0 und ich bin
fertig.
Wenn dort 0 und 1 steht, dann reicht es.
Naja, ich habe also diese verschiedenen Situationen.
Generate, Propagate.
Das Absorbieren ist jetzt in diesem Fall gar nicht so sehr relevant,
das war die andere Alternative, die man auch noch anschauen kann.
Und jetzt machen wir Folgendes.
Wir sagen, ich habe jetzt meine beiden Zahlen, die ich agieren möchte.
Ups, etwas schlecht gemalt.
Kurz nochmal weglöschen.
Ich habe also hier meine beiden Zahlen, die ich agieren möchte.
Und jetzt interessiert mich das, was ich hier hinschreiben kann und
was ich da hinschreiben kann.
Ich überlege Folgendes.
Ich schreibe hier zwei Bits hin, ein G und ein P. Und diese beiden
Bits, G und P, geben mir an, ob dieses Stück einen Übertrag erzeugt,
generiert oder weitergeht.
Und hier genauso, G' und P'.
Und jetzt interessiert mich, wie sind denn dann die Werte für beides
zusammen.
Wenn ich also etwas weiß über diese Teile, über diese beiden teile ich
hier die rechte Hälfte und die linke Hälfte.
Die rechte Hälfte hat also hier eine Eins stehen, wenn ein Übertrag
erzeugt wird, ein P stehen, wenn ein Übertrag von der rechten Seite
hier also ganz durchgeschoben wird.
Und entsprechend das G' und P'.
Wann wird denn, wenn ich mir das anschaue, aus dem Gesamten ein
Übertrag erzeugt?
Garantiert.
Na, es wird auf jeden Fall, wenn mein...
Wann wird da ein Übertrag erzeugt?
Jetzt steht hier...
Ah, das ist jetzt gerade anders herum.
Entschuldigung, das muss ich hier...
Das hat mich ein bisschen verwirrt.
Der Strich da weg, hier der Strich hin.
So steht es in der Form.
G, P und G' P'.
Rechts stehen G' P', links drehen G und P. Wann wird hier ein Übertrag
erzeugt, aus dem Ganzen?
Wenn das G1 ist, heißt das, der linke Teil erzeugt eine Eins, dann
steht hier vorne auf jeden Fall eine Eins.
Oder bin ich davon, was im Ganzen rechts ist?
Dann ist mir das völlig egal, was dieses G' und P' sagen.
Das steht hier, G.
Oder, es wird über G', das ist eine Eins, und dieser Übertrag wird
durchgereiht.
Das P ist auch Eins.
Also, der Teil L, das ist der Teil R, der Teil L leitet einen Übertrag
durch und der Teil R erzeugt einen Übertrag.
Das ist der andere Fall, der passieren kann.
Damit hier ein Übertrag erzeugt wird insgesamt, also entweder erzeugt
der linke Teil einen Übertrag oder der rechte Teil erzeugt einen
Übertrag und wird weitergeleitet.
Und wann wird insgesamt etwas durchgereicht?
Von ganz rechts nach ganz links, wenn P und P' beide Eins sind.
So habe ich also eine Möglichkeit, diese Paare von Bits, die mir
angeben, ob ein bestimmter Bereich meiner zu addierenden Zahlen einen
Übertrag generiert oder propagiert, das sind die beiden Bits, die kann
ich kombinieren und dadurch die entsprechenden G- und P-Werte für,
also das wäre in dem Fall hier G2' und P2', für einen größeren
Bereich, für den kombinierten Bereich anzugeben.
Und jetzt kommt eine wesentliche Aussage, das ist hier die wesentliche
Erkenntnis, diese Operation ist assoziativ.
Da habe ich Sie schon darauf hingewiesen, das ist eine ganz wichtige
Erkenntnis.
Assoziativ heißt nämlich, ich habe verschiedene Alternativen, sich
Operationen auszuführen.
Ich kann die Operation Kringel entweder so ausführen, dass ich sie
sequenziell ausführe, oder ich kann sie so ausführen, in einer
baumorientierten Art und Weise.
Die Reihenfolge der Ausführung der Operation ist egal.
Und dann kann ich auch die baumorientierte Art wählen und ich habe
einen Baum mit der Höhe Log N.
Das heißt, ich kann bei genügender paralleler Ausführung, bei
genügender Hardware, die zur Führung steht, diese ganzen Kringel
-Operationen weitgehend parallel machen und kann dafür, um das G und P
für die ganze Zahl zu erzeugen, brauche ich nur Log N Schritt.
Für jede Ebene hier einen Schritt und ich bin fertig.
Also hier kann das so noch weitergehen.
Entsprechend kann ich also das Ganze mit Log N Schritten machen und
habe dann G- und P-Signale.
Was habe ich jetzt davon, wenn ich G- und P-Signale habe?
Ich möchte doch Summenbits und Übertragsbits haben.
Naja, ich kann aus den G- und P-Signalen sofort die Summenbits und
Übertragsbits ableiten.
Das geht ganz einfach.
Das heißt, im Prinzip, also kann ich jetzt die Addition mit diesen G-
und P-Signalen, für diese Operationen hier brauche ich Bausteine, um
die zu kombinieren, kann ich eine Addition auf einmal in
logarithmischer Zeit machen.
Das heißt, wieder die Reduktion, wie bei Carry-Select-Adder, Reduktion
von linearer Zeit auf logarithmische Zeit.
Eine drastische Reduktion.
Natürlich sind die Operationen hier an den einzelnen Stellen, um
hierfür muss an jeder Stelle muss ich ein G- und P-Signal berechnen.
Und entsprechend dann die Dinger kombinieren.
Und ich habe einen Baum, beim Baum habe ich lange Leitungen, das
kostet auch alles noch Zeit.
Aber trotzdem, ich habe eine insgesamt logarithmische Zeit, unter
gewissen Annahmen bezüglich der Laufzeit von Signalen über lange
Leitungen, und habe dadurch die Reduktion von linear auf
logarithmisch.
Und ich kann also auch, ohne dass ich Pipelining mache, nur durch
Parallelität dafür sorgen, dass ich eine deutliche Beschleunigung
herbekomme.
Auch dieser Addierer wird in der Praxis sehr viel verwendet, es steckt
in vielen Rechnern drin, als Realisierung von Addierern.
Das heißt eben, wenn Sie jetzt von einem 32-Bit-Addierer auf einen 64
-Bit -Addierer gehen, brauchen Sie nur einen Schritt mehr.
Verdoppelte Anzahl von Bits heißt, Logarithmus geht um Einzug.
Das ist natürlich durchaus tolerierbar.
Jetzt kommt noch als Letztes eine kurze Bemerkung, ich kann es noch
weiter treiben.
Ein sogenannter Carry-Safe-Head.
Was macht der denn?
Der hat folgende Idee.
Wir wollen zum Beispiel jetzt hier unsere Zahlen addieren und ich male
hier mal irgendwas drunter.
So, die beiden Zahlen, wo wir addieren.
Und wir wissen, da müssen wir eine Reihe Überträge erzeugen.
Und die erzeuge ich jetzt einfach.
Ich male einfach hier eine, da kommt der Übertrag hier wäre 1 und die
Summe ist 0.
Ich male hier einfach hin, ein Carry und ein Summit.
Hier ist, jetzt male ich aber das nicht, genau, male ich da hin.
Und hier sind 0 und 1, erzeugt keinen Übertrag, Summit 1.
1 und 0 erzeugt keinen Übertrag, Summe 1.
1 und 1 erzeugt Übertrag, Summe 0.
0 und 0 erzeugt keinen Übertrag und Summit 0.
Und diese Operationen an jeder Stelle kann ich auch unabhängig von
dem, was an den anderen Stellen passiert.
Die kann ich alle gleichzeitig ausführen.
Eine sogenannte Carry-Safe addiere ich, bewahre mir den Übertrag
erstmal auf.
Ich schreibe mir den zwar rein, aber ich lasse ihn nicht durchlaufen.
Jetzt arbeite ich einfach intern nur mit dieser Darstellung.
Und hier kann ich auf einmal jede einzelne dieser Operationen in
konstanter Zeit machen.
Weil ich das voll parallel machen kann.
Am Ende muss ich aber dafür sorgen, dass am Ende eine richtige Zahl
rauskommt.
Dass nur einmal die Überträge tatsächlich von rechts nach links hier
durchgereicht werden.
Das braucht nochmal mehr Zeit.
Wenn ich aber viele solcher Operationen mache, zum Beispiel innerhalb
von Multiplikationen, da habe ich viele Additionen.
Wenn ich alle diese Additionen da drin auf die Art und Weise machen
kann, habe ich konstante Zeit für die Berechnung.
Jede einzelne.
Und am Ende muss ich noch einmal linear durchlaufen.
Das bringt mir eine tolle Zeitersparnis.
Weil ich jede einzelne Operation mit konstanter Zeit mache.
Also ich kann...
Der Anfangspunkt war linear, lineare Additionen.
Da wird man doch nichts anderes machen, das ist doch so klar, dass das
gar nicht anders geht.
Bisschen nachdenken, wie bei dem Volker-Ansatz bringt, logarithmische
Zahlen.
Bisschen anderes nachdenken.
Und zwar anderes Nachdenken in der Form, ich mache einfach eine andere
Zahlendarstellung, eine Carry-Safe-Darstellung, bringt auf einmal
konstante Zahlen.
Das heißt, wir haben hier Möglichkeiten durch geeignete Modifikationen
der Darstellungen und der Art, wie wir etwas machen, verändern eine
inhärenzsequenzielle Operationsreihenfolge in eine assoziative
Reihenfolge, die andere Operation, bringt uns Vorteile.
Und dann kann man, wir haben also hier diese Carry-Safe-Darstellung,
habe ich Ihnen gerade dargestellt, und man kann sogar auch noch eine
andere Darstellung machen, man kann noch in so genannte einer
redundanten Zahlendarstellung gehen, bei der man nicht mit binären
Zahlen oder Zahlen nicht binär darstellt, sondern mit den Bits, also
mit drei verschiedenen Bits, minus 1, 0 und 1.
Wenn Sie jede Stelle einer Zahl durch eine 1, 0 oder minus 1
darstellen, haben Sie eine redundante Zahlendarstellung mit drei Bits
und nicht mit zwei Bits.
Und hier können Sie auch in konstanter Zeit addieren.
Sie müssen eben nicht über die Carry-Safe-Addition, aber dafür sorgen,
dass Sie am Ende einmal wieder auf die normale Darstellung kommen.
Das ist teuer, aber intern ist alles ganz gut.
Also das Wesentliche, was ich Ihnen hier jetzt mitteilen wollte, war
ganz wichtig, dass man nachdenkt, wie kann man ein großes Problem
modifizieren, durch die Weide-Konker-Ansatz, oder wie kann ich die
interne Darstellung ändern, durch Carry-Safe oder Ähnliches.
Und auf einmal habe ich völlig andere Möglichkeiten, ein Problem zu
bearbeiten.
Ich kann deutlich Zeit sparen, muss ein bisschen in Hardware
investieren, aber kann dadurch auf einmal eine ganz andere
Berechnungsstruktur erzeugen.
Also man sollte nicht immer bei den naiven Überlegungen stehen
bleiben.
Und jetzt noch kurz, bevor wir für heute fertig sind, Thema
Schaltwerke.
Wir haben eigentlich schon ein Schaltwerk kennengelernt, nämlich wir
haben den getakteten Ripple-Carry-Addierer kennengelernt.
Und bei dem getakteten Ripple-Carry-Addierer, da haben wir sowas wie
ein Verzögerungselement.
Und hier ergänzen wir unser Schaltnetz, nicht intern, wie wir das
gerade gemacht haben bei dem Ripple-Carry-Addierer, mit so intern ganz
vielen Verzögerungselementen, sondern wir haben hier einen
Verzögerungsblock, der einige Ausgänge sich hernimmt und die
zurückführt in Eingänge eines Schaltnetzes.
Und diese beiden Arten, die Ausgänge zu verarbeiten, trennen wir in
zwei Funktionen auf.
Das eine ist nach wie vor unser Schaltnetz für die Berechnung der
Ausgaben, von B hoch N, Kreuz B hoch R nach B hoch M, wir haben nach
wie vor M verschiedene Ausgaben.
Aber wir haben eben N-Eingänge und wir haben noch R-interne Eingänge,
die zurückgeführt wurden von den Ausgängen.
Von diesen hier.
Und diese Ausgänge, die wurden erzeugt durch eine zweite Funktion, G,
die also auch von B hoch N, Kreuz B hoch R arbeitet und dann unsere R
-Ausgänge erzeugt.
Und diese Werte nennen wir Zustände.
Das merken wir uns, was dort rausgeht und führen das wieder vorne
rein.
Und das, was wir hier machen, ist eigentlich etwas, dass wir hier eine
Funktion haben, das ist unsere Ausgabefunktion Lambda eines Automaten,
Sie erinnern sich an die endlichen Automaten, und das hier entspricht
der Übergangsfunktion, nein, doch, richtig, das entspricht der
Übergangsfunktion Delta, Zustandsübergangsfunktion unseres Automaten.
Das heißt, wir haben jetzt hier die Eingänge, das wäre also jetzt,
indem wir hatten beim endlichen Automaten hatten wir eine
Eingabemenge, G, wir hatten eine Zustandsmenge, Z oder S, und haben
hier wieder Zustandsmenge, Z oder E-Kreuz S, wenn wir S für straight
sagen wollen.
Das ist also unsere Zustandsübergangsfunktion und das andere ist
unsere Ausgabefunktion.
Und auf einmal können wir hier einen Automaten realisieren, durch ein
Schaltnetz, in dieser Art und Weise.
Damit haben wir also hier diese Grundeinheiten eines Schaltnetzes, wir
haben das Schaltnetz hier vorne, was uns genau wie vorher angeht, wie
ich aus den Eingängen irgendwelche Ausgänge produziere, und ich habe
die Verzögerungsglieder, die einen Teil da aus der berechneten Werte,
nämlich die ersten R hier, das ist unser Zustand, der wird
zurückgeführt an die Eingänge, und dann kann ich also etwas mehr
merken, über das, was ich vorher getan habe, und jetzt habe ich also
nicht mein kombinatorisches Verhalten, dass jedes Mal, wenn ich hier
meine Werte A1 und An irgendwie mit Werten belege, oder meine Variable
mit Werten belege, immer das gleiche Ergebnis liefert, sondern das,
was hier rauskommt am Ausgang, hängt davon ab, was wir intern
gespeichert haben.
Das heißt, auf diese Art und Weise können wir endliche Automaten
darstellen.
Mo - und Miliautomaten.
Und das werden wir am Mittwochmorgen nochmal genauer uns angucken.
Vielen Dank für die Aufmerksamkeit.