WEBVTT 00:00.910 --> 00:05.400 So, also jetzt beginnen wir nochmal mit der Vorlesung Grundlagen der 00:05.400 --> 00:07.060 Informatik II, Fortsetzung. 00:07.260 --> 00:11.720 Wir hatten letztes Mal uns angeschaut, nochmal abschließend das 00:11.720 --> 00:14.280 Kapitel Berechenbarkeit, Entscheidbarkeit, Komplexität. 00:15.000 --> 00:19.080 Und da hatte ich Ihnen nochmal erläutert, diese Probleme mit der 00:19.080 --> 00:21.120 Darstellung von Problemen als Entscheidungsproblem, 00:21.320 --> 00:23.600 Optimierungsproblem oder Konstruktionsproblem. 00:23.600 --> 00:27.120 Das Interessante ist, dass die im Prinzip in der gleichen 00:27.120 --> 00:33.660 Größenordnung jeweils lösbar sind, bis auf polynomielle Faktoren, das 00:33.660 --> 00:34.580 war das Wesentliche. 00:35.040 --> 00:38.960 Das heißt, man kann immer die Variante wählen, die gerade das 00:38.960 --> 00:41.280 sinnvollste ist für die aktuelle Problemstellung. 00:41.820 --> 00:48.020 Ich hatte Ihnen auch etwas erzählt, dann über die Konsequenzen, die 00:48.020 --> 00:53.320 das hat für den Umgang mit Problemen, dass man eben bei einem NP 00:53.320 --> 00:56.600 -vollständigen oder NP-schweren Problem, insbesondere bei NP 00:56.600 --> 00:59.880 -vollständigen Problemen, halt einfach sehen muss, wie geht man 00:59.880 --> 01:02.600 sinnvoll damit um, das Problem zu lösen. 01:03.420 --> 01:07.400 Das heißt, es kann sein, dass man darauf verzichtet, eine optimale 01:07.400 --> 01:10.920 Lösung zu finden, dass man sich damit zufrieden gibt, eine relativ 01:10.920 --> 01:12.060 gute Lösung zu finden. 01:12.060 --> 01:15.480 Wenn man Glück hat, gibt es ein Approximationsschema, sodass Sie bis 01:15.480 --> 01:21.900 auf einen kleinen Faktor in polynomieler Zeit tatsächlich eine gute 01:21.900 --> 01:25.100 Lösung finden, die also nur um einen kleinen Faktor schlechter ist als 01:25.100 --> 01:26.040 die optimale Lösung. 01:26.160 --> 01:28.900 Und das kann man beweisen, dass man also dann in polynomieler Zeit 01:28.900 --> 01:29.960 tatsächlich rankommen kann. 01:30.200 --> 01:33.180 Es gibt eine Reihe Probleme, die approximierbar sind, für die es 01:33.180 --> 01:34.480 Approximationsschema da gibt. 01:34.900 --> 01:38.880 Und dann gibt es eben eine ganz große Klasse von Werkzeugen, die etwas 01:38.880 --> 01:40.680 zu tun haben mit Randomisierung. 01:41.560 --> 01:45.280 Randomisierende Algorithmen sind ganz wichtige Werkzeuge für eine 01:45.280 --> 01:47.320 Vielfalt von schwierigen Problemen. 01:47.780 --> 01:50.720 Da genauer darauf einzugehen, wäre Thema einer eigenen Vorlesung. 01:50.860 --> 01:55.840 Da gibt es viele interessante Erkenntnisse, welchen Gewinn man haben 01:55.840 --> 01:59.180 kann dadurch, dass man Randomisierung in Algorithmen einbaut. 01:59.640 --> 02:02.500 Das geht deutlich über das hinaus, was Sie in anderen Vorlesungen über 02:02.500 --> 02:04.280 Monte Carlo Prozesse und Ähnliches hören. 02:04.280 --> 02:10.440 Da wird also Zufall in sinnvoller, systematischer Art und Weise in 02:10.440 --> 02:15.660 Algorithmen eingebaut, um schwierige Probleme in trotzdem günstiger 02:15.660 --> 02:17.860 Zeit bearbeiten zu können. 02:18.320 --> 02:21.500 Das war das, was wir im Wesentlichen hier betrachtet haben. 02:22.180 --> 02:26.260 Und dann kamen wir zum nächsten Kapitel, nämlich zum Kapitel über 02:26.260 --> 02:27.980 Schaltnetze, Schaltwerke. 02:27.980 --> 02:31.580 Da habe ich Ihnen auch schon ein bisschen was erzählt über burschen 02:31.580 --> 02:36.200 Algebren -Nachtragen oder wieder aufgefrischt die Kenntnis darüber, 02:36.580 --> 02:38.940 die verschiedenen Gesetze, die es dort gibt. 02:39.460 --> 02:43.080 Das heißt, wir können Eigenschaften ausnutzen solcher burschen 02:43.080 --> 02:46.240 Ausdrücke und können dann Vereinfachungen machen, Umformungen von 02:46.240 --> 02:48.800 burschen Ausdrücken entsprechend den vielen Gleichungen, die Sie hier 02:48.800 --> 02:53.160 sehen, die Sie im Prinzip auch kennen und die halt bei burschen 02:53.160 --> 02:55.900 Algebren ein bisschen anders sind, als man das kennt aus der 02:55.900 --> 02:59.000 Arithmetik, aber genauso wie halt in der Logik. 02:59.440 --> 03:03.560 Dort gibt es genau die gleichen, also die logischen Formeln sind 03:03.560 --> 03:05.880 spezielle burschen Algebren. 03:07.060 --> 03:10.100 Und wir hatten dann gesehen, dass man bursche Funktionen angeben kann, 03:10.720 --> 03:14.680 die man halt beschreibt, jeweils durch einen burschen Ausdruck oder 03:14.680 --> 03:17.620 durch eine Wertetabelle oder durch ein Binary Decision Diagram. 03:17.840 --> 03:21.700 Das war neu für Sie, das hatte ich Ihnen vorgeführt, wie man Binary 03:21.700 --> 03:25.460 Decision Diagrams entwickelt, dass man also eine Funktion aufspalten 03:25.460 --> 03:28.800 kann, entsprechend der einzelnen Variablen, indem man einfach sagt, 03:28.840 --> 03:31.620 ich gucke mir an die Funktion für einen speziellen Wert einer 03:31.620 --> 03:35.360 Variablen, in diesem Fall 0 oder 1, und dann muss ich halt 03:35.360 --> 03:38.960 entsprechend dafür sorgen, dass ich dann für den Fall, dass die 03:38.960 --> 03:43.020 Variable x1 den Wert 1 hat, ich dann entsprechend hier einen Term in 03:43.020 --> 03:44.180 einen Ausdruck reinschreibe. 03:44.180 --> 03:48.240 Und auf die Art und Weise kann ich das Ganze dann auch weiter 03:48.240 --> 03:54.320 aufspalten und entwickeln im Prinzip entsprechend den Variablen. 03:54.800 --> 03:58.620 Und ich kann das dann auch einfach grafisch darstellen, nämlich die 03:58.620 --> 04:02.900 erste Variable x1 nehme und dann entsprechend für die Werte 0 oder 1 04:02.900 --> 04:07.760 den Funktionswert f von 0 oder 1 dorthin schreibe beziehungsweise das 04:07.760 --> 04:11.420 dann weiter aufspalte und so kommt man dann zu diesen binären 04:11.420 --> 04:14.980 Entscheidungsdiagrammen beziehungsweise reduzierten Funktionsgrafen 04:14.980 --> 04:18.900 und wir hatten das dann an einigen Beispielen durchgeführt, wobei wir 04:18.900 --> 04:21.640 hier von der Darstellung der Funktion als Wertetabelle ausgegangen 04:21.640 --> 04:25.560 sind und dann sukzessive einen so entstandenen Baum, den man zunächst 04:25.560 --> 04:30.500 mal bekommt auf einfache Art und Weise von der Wertetabelle, dann den 04:30.500 --> 04:35.020 reduziert haben, indem wir identische Knoten identifiziert haben, 04:35.380 --> 04:39.240 identische Teilgrafen identifiziert haben und Knoten gelöscht haben, 04:39.600 --> 04:43.640 bei denen beide Entscheidungsalternativen auf den gleichen Nachfolger 04:43.640 --> 04:44.000 führen. 04:44.680 --> 04:47.980 Und das wurde in einem Beispiel vorgeführt, hier war ein Beispiel die 04:47.980 --> 04:51.440 Übertragsfunktion eines binären Addierers, wo wir gesehen haben, da 04:51.440 --> 04:55.260 kommen wir dann also von diesem doch etwas größeren Baum runter auf 04:55.260 --> 04:57.300 einen Baum, der doch sehr viel einfacher aussieht. 04:57.380 --> 05:00.720 Ich hatte Ihnen weitere Beispiele gezeigt für die Paritätsfunktion 05:00.720 --> 05:07.280 oder das XOR mit drei Variablen hier und wir hatten dann noch ein paar 05:07.280 --> 05:08.420 Bemerkungen dazu gemacht. 05:08.700 --> 05:10.960 Ich hatte Ihnen etwas erzählt, dass das noch allgemeiner geht. 05:11.120 --> 05:15.580 Wir hatten dann die Begriffe der Schaltalgebra, oder Quatsch, die 05:15.580 --> 05:22.000 Beschreibungsmöglichkeiten durch Boucher-Algebren übertragen auf eine 05:22.000 --> 05:25.360 Schaltalgebra, in der wir Schaltelemente als die wesentlichen 05:25.360 --> 05:30.300 Basiselemente haben und dann Operationen darauf definiert haben durch 05:30.300 --> 05:36.660 zum Beispiel Serienschaltung oder Parallelschaltung. 05:37.400 --> 05:40.380 Also Serien- und Parallelschaltung sind das Gleiche, das wäre die 05:40.380 --> 05:44.300 Konjunktion von zwei Variablen oder eben die Parallelschaltung, das 05:44.300 --> 05:46.480 ist die Disjunktion von Variablen. 05:47.160 --> 05:49.820 Und auf die Art und Weise kann man auf einmal Schaltungen 05:49.820 --> 05:51.980 identifizieren mit Boucher-Ausdrücken. 05:53.020 --> 05:56.880 Das heißt, wir können dann auch von Schaltfunktionen reden, die durch 05:56.880 --> 05:59.460 solche Schaltungen realisiert werden. 05:59.880 --> 06:04.200 Das Ganze ist, wenn man diese Realisierung durch die Operationen 06:04.200 --> 06:09.760 anschaut, tatsächlich genau entsprechend den Regeln der Boucher 06:09.760 --> 06:10.760 -Algebra aufgebaut. 06:10.960 --> 06:14.680 Das heißt, wir haben hier eine Schaltalgebra, die eine Boucher-Algebra 06:14.680 --> 06:15.040 ist. 06:15.140 --> 06:18.600 Wir hatten das dann weiter betrachtet, wir hatten hier die 06:18.600 --> 06:21.880 zweistelligen Schaltfunktionen betrachtet, wo jetzt hier die ganzen 06:21.880 --> 06:23.880 verschiedenen Funktionen ausgeblendet sind. 06:24.380 --> 06:27.080 Vielleicht sollte ich dann an dieser Stelle einfach auf die Animation 06:27.080 --> 06:30.800 gehen, dann können Sie das besser sehen, weil das ansonsten nicht 06:30.800 --> 06:31.360 Animation. 06:31.840 --> 06:35.240 Auf die Präsentation gehen, dann kann ich Ihnen das hier nochmal alles 06:35.240 --> 06:35.780 zeigen. 06:35.900 --> 06:39.200 Ich gehe gleich auf die Fragen ein, die da gekommen waren. 06:39.940 --> 06:46.040 Und hier sieht man dann die ganzen 16 verschiedenen Funktionen, die es 06:46.040 --> 06:49.980 gibt mit zwei Variablen, vier verschiedene Werte, die wir dort 06:49.980 --> 06:50.840 eintragen können. 06:50.960 --> 06:54.940 Und entsprechend haben wir halt 16 verschiedene Funktionen, von der 06:54.940 --> 06:56.540 Nullfunktion bis zur Einsfunktion. 06:56.940 --> 07:01.360 Und wir hatten jeweils die Funktionen beschrieben durch einen Boucher 07:01.360 --> 07:06.820 -Ausdruck, oder einen Ausdruck der Schaltalgebra, der gerade dadurch 07:06.820 --> 07:11.660 entstand, dass wir jede Einszeile in dieser Funktion jeweils genommen 07:11.660 --> 07:18.620 hatten und daraus dann entsprechend einen Ausdruck in der kanonischen 07:18.620 --> 07:21.640 disjunktiven Normalform aufgeschrieben haben, also jede Einszeile 07:21.640 --> 07:25.360 entsprechend die Werte der Variablen hergenommen, sodass wir zum 07:25.360 --> 07:29.060 Beispiel bei dieser F4 hier den Ausdruck... 07:29.060 --> 07:33.440 Ne, bei F5 nehmen wir mal, da haben wir zwei solcher Einszeilen halt A 07:33.440 --> 07:38.740 quer und B, da war das A Null, B Eins, oder eben A und B. 07:38.740 --> 07:42.520 Das heißt, wir summieren, wir schreiben eine Disjunktion hin von allen 07:42.520 --> 07:45.380 Situationen, für die diese Funktion wahr ist. 07:46.240 --> 07:51.000 Die ist halt für die Belegung der Variablen A auf Null und B auf Eins 07:51.000 --> 07:51.280 wahr. 07:51.400 --> 07:56.960 Das ist dieser Ausdruck, der erste Term hier und der zweite Term ist 07:56.960 --> 07:58.660 halt diese A und B. 07:59.000 --> 08:03.600 Wenn A und B beide Eins sind, ist der halt wahr, bekommt den Wert Eins 08:03.600 --> 08:05.300 und dann ist der andere Wert Null. 08:05.300 --> 08:09.240 Jetzt gehe ich mal kurz auf die Frage ein, mal sehen, was das war. 08:09.600 --> 08:11.580 Wo genau kann man sich für die Bonusklausur anmelden? 08:11.660 --> 08:13.180 Gut, dass Sie sich diese Frage stellen. 08:19.040 --> 08:24.480 Diese Bonusklausur, die Anmeldung läuft jetzt über die Webseite der 08:24.480 --> 08:26.220 Vorlesung, also über den VAB. 08:27.100 --> 08:30.420 Sie wissen ja alle, wo der VAB ist, da können Sie raufgehen. 08:30.780 --> 08:33.900 Der war jetzt übers Wochenende abgeschaltet, ist aber jetzt wieder 08:33.900 --> 08:38.020 verfügbar und dort ist der Link auf die Anmeldung zur Bonusklausur. 08:38.460 --> 08:41.420 Ganz wichtig, also ich schreibe das jetzt auch nochmal hier rauf. 08:42.080 --> 08:43.440 Ups, das wollte ich jetzt gar nicht. 08:43.720 --> 08:45.480 Ich wollte hier etwas schreiben können. 08:49.080 --> 08:50.000 Falscher Schalter. 08:50.980 --> 08:54.260 Ich wollte auf diesen Schalter, auf den Stift. 08:54.940 --> 08:56.520 Die Bonusklausur, 09:01.530 --> 09:03.670 da sollten Sie sich anmelden. 09:04.670 --> 09:05.990 Jetzt kriege ich das Melden hier nicht mehr hin. 09:08.490 --> 09:09.770 Dickes Ausrufezeichen. 09:10.410 --> 09:12.230 Bis Ende des Jahres können Sie sich anmelden. 09:12.370 --> 09:14.410 Es haben sich bisher erst 70 Personen angemeldet. 09:14.510 --> 09:18.910 Ich nehme an, dass mehr Teilnehmer der Vorlesung Interesse haben, die 09:18.910 --> 09:19.970 Bonusklausur zu schreiben. 09:20.650 --> 09:23.290 Es gibt übrigens auch nochmal zur Vorbereitung bzw. 09:23.310 --> 09:27.190 zur Verstärkung dessen, was Sie in den Übungen machen, nochmal eine 09:27.190 --> 09:33.530 Großübung, wo Ihnen hier spezielle Aspekte der verschiedenen 09:33.530 --> 09:36.690 Übungsaufgaben, die Ihnen so gestellt werden, nochmal zusammengestellt 09:36.690 --> 09:37.070 werden. 09:37.390 --> 09:40.170 Einige wesentliche Punkte aus der Vorlesung nochmal zusammengefasst 09:40.170 --> 09:40.510 werden. 09:40.950 --> 09:41.930 Das wird am 15. 09:42.230 --> 09:44.730 Januar sein, morgens um 8.00 Uhr. 09:44.870 --> 09:47.890 So hatten wir das jedenfalls schon mal vorbesprochen, dass das so sein 09:47.890 --> 09:48.170 wird. 09:49.050 --> 09:50.750 Und das heißt am 15. 09:50.910 --> 09:57.470 Januar morgens Gelegenheit, in dem Hörsaal am Fasanengarten, dort 09:57.470 --> 10:01.570 nochmal intensiver zu hören, was sind eigentlich die wesentlichen 10:01.570 --> 10:01.830 Themen. 10:01.830 --> 10:05.910 Wobei ich auf die ja schon immer ziemlich deutlich hinweise, was 10:05.910 --> 10:07.410 besonders wichtig ist. 10:07.530 --> 10:10.630 Aber wenn man das nochmal kurz gefasst zusammengestellt bekommt, ist 10:10.630 --> 10:11.650 das ganz sinnvoll. 10:11.810 --> 10:14.910 Außerdem können Sie da nochmal rückfragen und Sie bekommen ein paar 10:14.910 --> 10:19.710 typische Aufgaben dort gezeigt nochmal und auch Lösungen angeboten. 10:20.310 --> 10:26.230 Also diese Großübungen sind eigentlich immer als relativ hilfreich 10:26.230 --> 10:27.050 wahrgenommen worden. 10:27.050 --> 10:33.810 Sie wissen, dass Sie gleichzeitig ja auch noch jede Woche die Survey 10:33.810 --> 10:35.160 -Fragen haben zur Vorlesung. 10:35.770 --> 10:38.450 Da wird ja zu jedem Kapitel immer eine Reihe von Fragen Ihnen über 10:38.450 --> 10:40.090 unser Werkzeug angeboten. 10:41.110 --> 10:43.770 Das können Sie auch nutzen für Ihre Zwecke. 10:44.390 --> 10:47.930 Sie können sich dort auch die Ergebnisse des Surveys jeweils 10:47.930 --> 10:48.930 einblenden lassen. 10:49.330 --> 10:52.350 Aber ich würde Ihnen raten, zunächst mal die Aufgaben selbst zu 10:52.350 --> 10:52.970 beantworten. 10:53.050 --> 10:55.310 Dann können Sie sehen, inwieweit Sie richtig lagen oder nicht. 10:55.830 --> 10:59.430 Also das, denke ich, ist auch eine wichtige Rückmeldemöglichkeit 10:59.430 --> 11:01.690 bezüglich der Dinge, die Sie können und die Sie nicht können. 11:01.770 --> 11:04.690 Wenn Sie da falsch antworten, müssen Sie halt sehen, was war 11:04.690 --> 11:09.410 eigentlich falsch, was war richtig, wie ist die Begründung dafür, dass 11:09.410 --> 11:11.830 hier einige Sachen als richtig angegeben werden und andere nicht. 11:13.930 --> 11:18.370 Das andere war, ob ich die Folie 17 von Kapitel 9 neu bzw. 11:18.470 --> 11:19.670 korrekt hochladen könnte. 11:19.770 --> 11:20.730 Das ist diese Folie. 11:21.410 --> 11:24.170 Diese Folie habe ich natürlich in der PDF-Version hochgeladen. 11:24.170 --> 11:26.930 Ich habe einfach das PDF gemacht aus den Folien. 11:27.430 --> 11:32.430 Da ist natürlich das, was ich jetzt frei animiert habe, dann noch 11:32.430 --> 11:33.350 nicht animiert. 11:33.450 --> 11:37.770 Deswegen sind die vielen schönen Einträge hier nicht zu sehen. 11:38.970 --> 11:40.410 Das kann ich aber machen. 11:40.510 --> 11:43.430 Ich kann einmal eine Version erzeugen, wo das hier vollständig zu 11:43.430 --> 11:44.010 sehen ist. 11:44.810 --> 11:50.630 Das ist halt über die Transformation in PDF dann leider so nicht 11:50.630 --> 11:54.010 möglich, dass die Animationen genau mit übernommen werden. 11:54.450 --> 11:56.310 Jetzt gibt es hier noch eine Frage. 11:56.490 --> 11:57.910 Wieso ist die noch mal da? 11:57.970 --> 11:58.950 Ich habe die doch schon beantwortet. 11:59.030 --> 11:59.610 Jetzt ist sie weg. 12:00.230 --> 12:03.590 Also, zu dieser Frage Bonusklausur wollte ich sowieso darauf 12:03.590 --> 12:06.850 hinweisen, dass Sie sich da anmelden dürfen. 12:07.470 --> 12:10.370 Das ist ein Angebot von uns, dass Sie einen Bonus bekommen können für 12:10.370 --> 12:14.390 besondere Fähigkeiten, die Sie nachweisen in der Bonusklausur. 12:14.610 --> 12:18.190 Wer das nicht wahrnimmt, hat halt diesen Bonus von einer Verbesserung 12:18.190 --> 12:22.110 der Notenstufe bei einer bestandenen Klausur dann nicht wahrgenommen. 12:22.870 --> 12:25.030 Gut, das waren die Schaltfunktionen. 12:25.210 --> 12:27.110 Gehen wir weiter hier auf die nächste Folie. 12:27.570 --> 12:30.010 Verknüpfungsbasen, das war die letzte Folie gewesen letztes Mal. 12:30.490 --> 12:34.410 Da hatte ich Ihnen gezeigt, dass man diese 16 Funktionen alle 12:34.410 --> 12:35.210 darstellen kann. 12:35.210 --> 12:41.550 Man kann sie im Prinzip aufbauen auf Basis von wenigen Operationen, 12:41.590 --> 12:45.710 von Standardoperationen, selbstverständlich unter Verwendung der drei 12:45.710 --> 12:49.130 Operationen Konjunktion, Disjunktion und Komplement. 12:49.850 --> 12:53.350 Das ist selbstverständlich die Verknüpfungsbasis nach Definition der 12:53.350 --> 12:53.990 Schaltalgebra. 12:54.990 --> 12:58.490 Und dann konnte man eben einmal verzichten auf die Disjunktion oder 12:58.490 --> 12:59.590 auf die Konjunktion. 12:59.590 --> 13:01.650 Ich hatte Ihnen dargestellt, wie man z.B. 13:01.790 --> 13:05.770 die Disjunktion nur durch Konjunktion und Negation oder Komplement 13:05.770 --> 13:06.690 darstellen kann. 13:07.810 --> 13:14.890 Und man kann sogar sich beschränken auf eine Funktion, z.B. 13:15.050 --> 13:18.390 auf die NOR-Funktion oder auf die NAND-Funktion und dadurch alle 13:18.390 --> 13:19.270 anderen darstellen. 13:19.690 --> 13:21.930 Das ist also etwas, was Sie in den Übungen gerne machen können, sich 13:21.930 --> 13:24.730 da weiter mit beschäftigen, wie man das konkret macht. 13:24.830 --> 13:27.830 Da gibt es eine ganze Reihe von Möglichkeiten, sich damit zu 13:27.830 --> 13:31.450 beschäftigen, anhand von Fragen, die wir für Sie da entwickelt haben. 13:32.690 --> 13:35.810 Die Begründung oder die Motivation ist halt, dass man auf die Art und 13:35.810 --> 13:41.590 Weise nur eine Komponente braucht, nur einen Baustein, nämlich diese 13:41.590 --> 13:46.530 NOR -Funktion oder die NAND-Funktion und daraus alle anderen durch 13:46.530 --> 13:48.370 einfaches Verschalten aufbauen kann. 13:48.670 --> 13:51.430 Was es eigentlich heißt, dieses einfach so Verschalten, das schauen 13:51.430 --> 13:54.110 wir uns jetzt im nächsten Kapitel an, bei den grundlegenden 13:54.110 --> 13:57.290 Schaltungen, da geht es jetzt darum, wie können wir eigentlich darüber 13:57.290 --> 13:59.030 reden, wie wir Schaltungen aufbauen. 13:59.310 --> 14:01.810 Gerade eben, das war eine Schaltalgebra, das war mehr so die formale 14:01.810 --> 14:04.170 Beschreibung, jetzt wollen wir gucken, wie wir das praktisch 14:04.170 --> 14:05.270 tatsächlich machen können. 14:06.130 --> 14:08.690 Und dazu schauen wir uns einmal an, was ist eigentlich ein 14:08.690 --> 14:09.710 Schaltgatter? 14:10.490 --> 14:13.690 Also wir hatten vorher gesehen, man kann solche Verknüpfungen machen, 14:14.210 --> 14:18.550 und und oder und sowas von irgendwelchen Schaltelementen bauen. 14:18.550 --> 14:21.930 Und sowas nennen wir einfach ein Schaltgatter. 14:22.070 --> 14:24.310 Das heißt, wir abstrahieren da so ein bisschen von, machen daraus 14:24.310 --> 14:25.070 einen Baustein. 14:25.870 --> 14:31.690 Und jetzt gibt es dafür einige Standardnotationen. 14:32.290 --> 14:34.510 Jetzt habe ich hier schon wieder eine Frage. 14:36.970 --> 14:39.230 Findet die Vorlesung am 23.12. 14:39.530 --> 14:39.790 statt? 14:41.450 --> 14:42.010 Selbstverständlich. 14:42.970 --> 14:44.890 Vorlesungsfrei ist ab 24.12. 14:46.490 --> 14:48.250 Und am 23.12. 14:48.390 --> 14:49.210 ist Vorlesungszeit. 14:49.890 --> 14:51.370 Ich werde am 23.12. 14:51.470 --> 14:52.310 hier eine Vorlesung halten. 14:53.050 --> 14:56.990 Und ich freue mich, wenn ich dort Personen sehe, die eine Vorlesung 14:56.990 --> 15:00.010 sehen wollen, die sicherlich dann auch ein paar andere Aspekte noch 15:00.010 --> 15:02.130 mit drin haben wird, als nur den Inhalt der Vorlesung. 15:02.330 --> 15:04.310 Aber das ist Ihnen natürlich überlassen. 15:04.890 --> 15:07.250 Sie wissen, dass ich die Vorlesung aufzeichne, deswegen denke ich, ist 15:07.250 --> 15:11.770 es kein großes Problem für jemanden, der aus irgendwelchen Gründen das 15:11.770 --> 15:12.750 nicht schafft, herzukommen. 15:12.750 --> 15:16.030 Aber ich fände es schon gut, wenn da zumindest ein paar Leute da 15:16.030 --> 15:19.790 sitzen, sodass ich nicht vor einem sehr leeren Hörsaal hier eine 15:19.790 --> 15:20.610 Vorlesung halten muss. 15:20.970 --> 15:24.270 Aber ich möchte die Gelegenheit nutzen, um die Vorlesung dann wirklich 15:24.270 --> 15:24.790 zu halten. 15:28.030 --> 15:31.810 Und es ist Vorlesungszeit, der Tag gehört mit dazu, deswegen halte ich 15:31.810 --> 15:32.570 da auch die Vorlesung. 15:32.910 --> 15:35.050 Also das zu dieser Frage. 15:35.250 --> 15:37.250 Tutorien finden an dem Tag nicht mehr statt. 15:38.730 --> 15:41.490 Tutorien finden erst wieder dann Anfang Januar statt. 15:42.590 --> 15:45.950 Aber auch erst nach dem 6., nicht in der Woche davor. 15:46.530 --> 15:50.350 Nicht so wie in anderen Bundesländern, wo man am 2. 15:50.470 --> 15:53.230 Januar wieder anfängt mit der Vorlesungszeit. 15:54.590 --> 15:57.610 Gut, das also zu dieser auch wichtigen Frage. 15:57.970 --> 16:01.310 Jetzt kommen wir zurück zu unseren Schaltgattern. 16:01.470 --> 16:02.510 Was ist ein Schaltgatter? 16:03.030 --> 16:09.170 Damit will man grafisch andeuten, Operationen auf Schalt oder auf 16:09.170 --> 16:09.610 Werten. 16:09.610 --> 16:13.990 So, wir wollen zum Beispiel die Negation angeben können. 16:15.010 --> 16:18.890 Die wird in der Regel auf zwei verschiedene Art und Weisen angedeutet. 16:19.070 --> 16:23.490 Entweder durch so ein, da steht jetzt ein Kasten, ein Rechteck mit 16:23.490 --> 16:25.990 einer Eins drin und dahinter so ein Kringel. 16:27.550 --> 16:31.010 Und der Kringel sagt, wir wollen etwas negieren. 16:32.210 --> 16:34.330 Das ist eine Negation oder Komplementbildung. 16:34.330 --> 16:39.150 Das heißt, aus dem A, was da reingeht, soll rechts ein A quer 16:39.150 --> 16:39.670 rauskommen. 16:39.750 --> 16:43.970 Die Operation, Negation wird angewandt auf das, was hier durchlaufen 16:43.970 --> 16:44.690 soll, diesen Wert. 16:45.410 --> 16:49.090 Wird manchmal vereinfachend auch einfach nur als so ein Kringel 16:49.090 --> 16:49.590 gemalt. 16:51.990 --> 16:53.850 Dann sehen Sie daneben noch ein anderes Symbol. 16:54.130 --> 16:58.090 Das ist auch eine frühere Darstellung dieser Symbole. 16:58.190 --> 16:59.190 Ich gehe darauf gleich noch ein. 17:00.070 --> 17:05.630 Dann haben wir das Oder-Gatter oder Oder-Schaltelement. 17:06.890 --> 17:08.390 Die Dissjunktion wollen wir darstellen. 17:08.470 --> 17:10.310 Wir haben zwei Eingaben, A und B. 17:11.410 --> 17:15.030 Und was dort rauskommt auf der rechten Seite, soll die Dissjunktion 17:15.030 --> 17:15.270 sein. 17:15.350 --> 17:18.270 Ich hatte Ihnen vorher gesagt, wie man das tatsächlich schalten kann 17:18.270 --> 17:20.350 über Parallelschaltung. 17:20.450 --> 17:23.090 Hier machen wir jetzt einfach, sagen wir, das ist so ein Baustein. 17:23.830 --> 17:26.470 Und da steht drin, größer gleich eins in diesem Rechteck. 17:26.470 --> 17:33.370 Größer gleich eins soll bedeuten, der Wert am Ausgang ist eins, wenn 17:33.370 --> 17:38.710 es größer gleich ein Argument gibt an den Eingängen, das den Wert eins 17:38.710 --> 17:39.010 hat. 17:41.170 --> 17:42.690 Das ist die Bedeutung. 17:42.950 --> 17:48.050 Mindestens eines dieser Elemente am Eingang, A oder B, hat den Wert 17:48.050 --> 17:48.550 eins. 17:48.790 --> 17:50.970 Dann kommt am Ausgang auch eine Eins raus. 17:50.970 --> 17:55.990 Und wir wissen, wenn eine der beiden Variablen, mindestens eine der 17:55.990 --> 17:58.310 Variablen eins ist, ist die Oder-Funktion gleich eins. 17:58.690 --> 18:00.930 Also ist das das entsprechende Schaltelement dafür. 18:01.670 --> 18:06.710 Und dann gibt es für die Und-Operation, für die Konjunktion, einen 18:06.710 --> 18:07.970 ähnlichen Baustein. 18:08.930 --> 18:13.470 Und hier haben wir ein Und-Zeichen in diesem Rechteck drin stehen. 18:14.010 --> 18:18.490 Und dieses Und-Zeichen soll andeuten, dass rechts nur dann eine Eins 18:18.490 --> 18:22.730 stehen soll, wenn an beiden Eingängen eine Eins ist. 18:23.110 --> 18:26.170 Deswegen das Und-Zeichen, alle Eingänge. 18:26.410 --> 18:28.190 Man hätte auch für alle Zeichen reinschreiben können. 18:28.970 --> 18:30.630 Man hat aber das Und-Zeichen reingeschrieben. 18:32.470 --> 18:35.490 Jetzt sehen Sie rechts daneben noch andere Symbole. 18:37.950 --> 18:39.690 Die hat man früher verwendet. 18:40.070 --> 18:44.550 So einen schönen Halbkreis mit einem schwarzen Kringel oder einen 18:44.550 --> 18:47.450 Halbkreis, wo die beiden Eingänge hier so reingingen. 18:47.450 --> 18:49.850 Das war das Oder-Zeichen und das hier ist das Und-Zeichen. 18:51.470 --> 18:56.470 Jetzt hat man sich irgendwann entschieden, 1976 auf diese Notation 18:56.470 --> 18:57.270 umzusteigen. 18:57.350 --> 18:58.570 Warum macht man sowas? 18:58.910 --> 19:04.250 Das war eingeführter Standard für alle Leute, die Schaltungen 19:04.250 --> 19:05.070 entworfen haben. 19:06.090 --> 19:07.630 Leicht anders sieht das aus. 19:07.790 --> 19:09.050 Das war also der deutsche Standard. 19:09.990 --> 19:13.390 Es gibt im amerikanischen Bereich noch einen etwas anderen Standard, 19:13.490 --> 19:15.050 der zum Teil heute immer noch verwendet wird. 19:15.050 --> 19:17.050 Der sieht wiederum ein bisschen anders aus. 19:18.110 --> 19:21.090 Kleine Variationen davon, aber auch mit solchen Rundungen. 19:21.770 --> 19:24.370 Warum geht man auf einen solchen Standard über, wo man hier doch 19:24.370 --> 19:28.690 sofort optisch sieht, was damit gemeint ist, während man hier 19:28.690 --> 19:32.330 eigentlich nur Rechtecke hat und es steht da irgendwas drin. 19:32.810 --> 19:33.850 Warum macht man sowas? 19:36.210 --> 19:39.990 1976 hat man neue Geräte erfunden und neue Geräte entwickelt. 19:40.610 --> 19:41.970 Man hat sogenannte Plotter entwickelt. 19:41.970 --> 19:45.790 So ein Plotter, das ist also so ein Tablett, da kann man drauf 19:45.790 --> 19:46.470 zeichnen. 19:47.170 --> 19:50.190 Da gibt es so ein Zeichengerät, das konnte hier irgendwas zeichnen, 19:50.310 --> 19:52.710 hat einen Stift, konnte da was zeichnen. 19:54.830 --> 20:00.290 Diese Geräte konnten aber nur in dieser Richtung laufen oder in der 20:00.290 --> 20:00.650 Richtung. 20:01.750 --> 20:03.910 Die konnten keine Bögen zeichnen. 20:05.190 --> 20:10.230 Man wollte aber gerne diese Plotter, die man so schön automatisch 20:10.230 --> 20:13.550 ansteuern konnte, nutzen, um Schaltungen zu zeichnen. 20:13.630 --> 20:18.090 Ein technischer Zeichner, der über eine Schablone solche Elemente 20:18.090 --> 20:20.110 gezeichnet hat, der ist teuer. 20:20.270 --> 20:23.150 Eine Maschine kann man einfacher einsetzen, automatisiert. 20:23.590 --> 20:26.630 Die kann aber nicht einfach eine Schablone bedienen. 20:28.150 --> 20:33.450 Das Gerät konnte zu dem Zeitpunkt, zumindest das konnten alle auf dem 20:33.450 --> 20:39.810 Markt verfügbaren Plotter, konnten senkrechte, horizontale Linien 20:39.810 --> 20:43.250 malen und sie konnten Buchstaben malen. 20:43.630 --> 20:44.330 Das ging auch. 20:44.970 --> 20:45.450 Zeichen. 20:46.730 --> 20:49.530 Also eins konnten die zeichnen, größer gleich eins könnten die auch 20:49.530 --> 20:50.050 zeichnen. 20:50.610 --> 20:54.370 Das Und-Zeichen können die zeichnen, ein Für-Alle-Zeichen, sowas. 20:55.650 --> 20:58.750 Das ist kein Zeichen, das auf dem normalen Zeichensatz drin ist, das 20:58.750 --> 20:59.650 konnten die auch nicht zeichnen. 21:00.070 --> 21:01.650 Deswegen das Und-Zeichen muss das sein. 21:01.650 --> 21:06.230 Und dieser Kringeln hier, das ist einfach ein kleines O, auch kein 21:06.230 --> 21:06.590 Problem. 21:07.150 --> 21:07.930 Können die auch zeichnen. 21:09.490 --> 21:13.070 Das heißt, der Standard ist bestimmt durch die technischen 21:13.070 --> 21:16.310 Randbedingungen der damaligen Zeit, in der man etwas automatisieren 21:16.310 --> 21:20.750 wollte, man musste sich auf den kleinsten gemeinsamen Nenner der 21:20.750 --> 21:26.590 verfügbaren Geräte abstützen und musste entsprechend diesen 21:26.590 --> 21:30.890 verfügbaren technischen Möglichkeiten den Standard für das Zeichnen 21:30.890 --> 21:32.050 von Schaltungen verändern. 21:33.890 --> 21:37.670 Mittlerweile könnten wir problemlos wieder beliebige Figuren 21:37.670 --> 21:39.290 automatisch zeichnen lassen. 21:39.810 --> 21:40.750 Macht man aber nicht. 21:41.750 --> 21:43.030 Wir zumindest nicht in Deutschland. 21:43.170 --> 21:46.210 Wir haben diese Norm, das jetzt so zu machen. 21:46.730 --> 21:48.750 Es gibt noch ein paar weitere, die sehen Sie auf der nächsten Folie. 21:49.490 --> 21:53.630 Aber nur, dass Sie sehen als Hintergrund, warum macht man so, warum 21:53.630 --> 21:55.410 vereinbart man einen bestimmten Standard. 21:56.130 --> 22:01.290 Der hat etwas damit zu tun, was technisch möglich ist und wie man sich 22:01.290 --> 22:04.770 über viele Firmen hinweg, über viele Anbieter von Geräten hinweg 22:04.770 --> 22:08.550 einigen kann auf den kleinsten gemeinsamen Nenner. 22:11.470 --> 22:13.890 Dann weiß ich, das können alle. 22:13.890 --> 22:21.570 So, und damit haben wir also hier eine Möglichkeit, solche Schaltungen 22:21.570 --> 22:22.710 und Schaltelemente zu schreiben. 22:22.870 --> 22:24.110 Das sind die elementaren Gatter. 22:24.670 --> 22:25.690 Es gibt aber noch weitere. 22:26.890 --> 22:30.810 Es gibt, ich sagte, wir haben die NOR-Funktion und die NEN-Funktion. 22:31.290 --> 22:35.670 Ein NOR ist aber schon kein elementares Gatter mehr, sondern das NOR 22:35.670 --> 22:39.590 kann ich ja einfach darstellen über ein ODER-Schaltgatter, verknüpft 22:39.590 --> 22:41.590 mit einem Negation hinten dran. 22:42.610 --> 22:47.290 Das, was rauskommt aus dem Disjunktionsglied, ist jetzt einfach 22:47.290 --> 22:48.410 negiert am Ende. 22:48.590 --> 22:50.550 Dann habe ich also die Pierce-Funktion oder das NOR. 22:50.790 --> 22:51.970 Entsprechend das NAND. 22:53.270 --> 22:56.470 Und dann kann ich weitere Schaltungen aufbauen. 22:56.550 --> 22:59.390 Nur mal hier zum Beispiel, also ich kann natürlich alles, was in 22:59.390 --> 23:02.950 solchen Schaltelementen oder in solchen integrierten Bausteinen drin 23:02.950 --> 23:05.130 ist, kann ich dann automatisiert zeichnen. 23:05.190 --> 23:08.730 Hier sehen Sie nochmal die Beispiele für UND-Gatter, so war das eben 23:08.730 --> 23:09.370 früher aus. 23:09.370 --> 23:14.190 Mittlerweile wird das immer so dargestellt, über diese Rechtecke. 23:15.730 --> 23:21.010 Hier ist noch ein weiteres Element, so ein Schaltgatter. 23:22.090 --> 23:25.890 Da haben wir jetzt zwei Eingänge drin, da steht jetzt 2K plus 1. 23:26.150 --> 23:27.770 Warum 2K plus 1? 23:28.450 --> 23:32.730 Manchmal finden Sie ja auch die Beschreibung, so ein Ding, da steht 23:32.730 --> 23:35.610 hier gleich 1. 23:37.610 --> 23:43.670 Das heißt, es muss genau ein Element 1 sein. 23:44.030 --> 23:45.250 Dann soll eine 1 rauskommen. 23:45.330 --> 23:48.450 Dieses 2K plus 1 ist eine Verallgemeinerung. 23:50.050 --> 23:54.170 Das heißt, wenn eine ungerade Anzahl von Eingängen den Wert 1 hat, 23:54.530 --> 23:56.390 dann soll rechts eine 1 rauskommen. 23:57.950 --> 24:01.590 Das ist also äquivalent zu dem, was ich hinschreibe, gleich 1. 24:01.670 --> 24:04.310 Für zwei Eingänge ist das identisch. 24:04.890 --> 24:07.490 Wenn ich mehr Eingänge habe, wird es ein bisschen aufwendiger. 24:07.850 --> 24:11.150 Das hier ist natürlich keine elementare Schaltung mehr. 24:12.710 --> 24:16.990 Das XOR, wissen wir, kann ich hinschreiben als einen Ausdruck. 24:17.910 --> 24:22.990 Das ist hier der Ausdruck für die XOR oder ein möglicher Ausdruck in 24:22.990 --> 24:28.050 disjunktiver Form für eine XOR-Funktion, A quer und B oder A und B 24:28.050 --> 24:28.350 quer. 24:28.350 --> 24:33.230 Es ist immer genau eine der beiden Variablen gleich 1, die andere 24:33.230 --> 24:33.730 gleich 0. 24:34.230 --> 24:36.070 Dann soll das 1 sein, ansonsten ist es 0. 24:37.550 --> 24:39.630 Wie kann ich so etwas aufbauen? 24:40.050 --> 24:41.790 Zum Beispiel auf diese Art und Weise. 24:42.710 --> 24:49.730 Das ist eine Schaltung, die ich jetzt aufbauen kann aus einem... 24:49.730 --> 24:54.330 Ich habe hier also zwei Und-Operationen, zwei Und-Gatter. 24:55.170 --> 24:57.750 Dabei ist jeweils der eine Eingang negiert. 24:57.750 --> 24:59.850 Das ist also hier über den Kringel dargestellt. 24:59.950 --> 25:04.010 Ich habe gesagt, wir lassen bei der Negation dieses Rechteck davor mit 25:04.010 --> 25:05.350 der 1 meistens weg. 25:06.270 --> 25:08.950 Und das Ganze wird disjunktiv verknüpft. 25:09.450 --> 25:10.930 Das ist diese Disjunktion hier. 25:11.390 --> 25:13.410 Und dann kommt da entsprechend das XOR raus. 25:13.470 --> 25:20.730 Das heißt, aus einem bool'schen Ausdruck, wie wir ihn hier sehen, 25:20.730 --> 25:26.090 können wir sofort eine Schaltung aufmalen, die genau die Struktur 25:26.090 --> 25:28.370 dieses Ausdrucks widerspiegelt. 25:29.210 --> 25:33.210 Wir haben die beiden Eingangsvariablen A und B. 25:33.970 --> 25:38.470 Die werden hier entsprechend verknüpft über Schaltgatter, in dem Fall 25:38.470 --> 25:39.470 Konjunktionen. 25:40.790 --> 25:42.390 Zum Teil werden sie negiert dabei. 25:42.850 --> 25:43.990 Hier haben wir noch eine Disjunktion. 25:43.990 --> 25:48.090 Das heißt, wir haben hier eine mehrstufige Schaltung entsprechend der 25:48.090 --> 25:54.410 Klammerstruktur dieses Ausdrucks und haben auf diese Art und Weise die 25:54.410 --> 25:59.710 Möglichkeit, Schaltungen zu bauen, die jetzt genau eine Funktion 25:59.710 --> 26:00.570 realisieren. 26:01.070 --> 26:04.430 Das heißt, wenn Sie hier an den Eingängen irgendwelche Werte anlegen, 26:04.610 --> 26:08.130 kommt hier am Ausgang genau das raus, was über zum Beispiel die 26:08.130 --> 26:11.870 Wertetabelle auch dargestellt ist oder über ein BDD dargestellt ist. 26:11.870 --> 26:16.910 Aber Sie sehen, aus einer Wertetabelle werde ich sicherlich nicht 26:16.910 --> 26:18.790 sofort eine solche Schaltung aufbauen können. 26:19.870 --> 26:24.910 Die Schaltung kann ich nur aufbauen auf die einfachste Art und Weise, 26:25.470 --> 26:29.670 indem ich hier mir anschaue, wie sieht der entsprechende Buhl'sche 26:29.670 --> 26:33.290 Ausdruck aus für diese Buhl'sche Funktion oder Schaltfunktion. 26:34.190 --> 26:38.210 Und diesen Ausdruck kann ich direkt, weil ich dort die Operation sehe, 26:38.750 --> 26:40.210 umsetzen in eine Schaltung. 26:41.350 --> 26:47.450 So, das Ganze ist, wie gesagt, 2K plus 1, weil das auch die 26:47.450 --> 26:49.490 Paritätsfunktion ist, da hätte ich Sie schon mal darauf hingewiesen. 26:50.250 --> 26:56.970 Und jetzt möchte ich gerne das Ganze Ihnen zeigen, wie man das 26:56.970 --> 27:03.910 eigentlich, das wollte ich, habe ich verkehrt geklickt, das wollte ich 27:03.910 --> 27:10.730 beibehalten, gehe aber sofort wieder auf die Präsentation und ich 27:10.730 --> 27:15.970 wollte hier eigentlich nur kurz den, jetzt bin ich aber auch gar nicht 27:15.970 --> 27:21.830 drin in dem Stift, ich wollte hier raufgehen und jetzt ist hier ein 27:21.830 --> 27:24.310 potenzielles Sicherheitsrisiko, das ist überhaupt kein Problem. 27:24.970 --> 27:28.230 Ich rufe nämlich eine Funktion auf, die ich sehr gut kenne, ich möchte 27:28.230 --> 27:32.370 den Vorgang fortsetzen und die können auch noch Viren enthalten, ich 27:32.370 --> 27:33.670 möchte sie trotzdem öffnen. 27:34.190 --> 27:38.130 Sie wissen, das sind alles Fragen, typische Sicherheitsfragen, die wir 27:38.130 --> 27:42.310 eingebaut haben in alle unsere Operationen, Zugreifen auf irgendwelche 27:42.310 --> 27:45.570 Komponenten, da frage ich, ob das alles in Ordnung ist, ob ich ein 27:45.570 --> 27:51.470 Zertifikat kenne oder akzeptieren möchte oder nicht und oft sagen wir 27:51.470 --> 27:55.530 einfach immer ja, ja, ja, ja, ja und auf einmal sind alle unsere Daten 27:55.530 --> 27:57.630 ausgespäht oder irgendein Virus ist auf dem Rechner. 27:57.730 --> 28:00.250 Da muss man aufpassen, was man macht, in diesem Fall weiß ich aber, 28:00.350 --> 28:06.270 was ich mache und ich möchte Ihnen gerne jetzt ein Werkzeug zeigen, 28:06.350 --> 28:09.230 das Sie hoffentlich schon mal runtergeladen haben, nämlich unser 28:09.230 --> 28:10.030 Logiflash. 28:11.030 --> 28:14.370 Logiflash ist eine Möglichkeit, Schaltungen zu zeichnen. 28:15.730 --> 28:18.390 So, jetzt haben wir gerade eine Schaltung überlegt gehabt, das war die 28:18.390 --> 28:19.830 Schaltung für die XOR-Funktion. 28:20.670 --> 28:23.030 Jetzt möchte ich gerne die XOR-Funktion zeichnen. 28:23.130 --> 28:23.890 Wie mache ich das? 28:24.470 --> 28:27.230 Das ist also unser Werkzeug, das wir Ihnen über Links schon zur 28:27.230 --> 28:32.790 Verfügung gestellt haben und jetzt brauche ich also, ich brauche ein 28:32.790 --> 28:33.910 Und -Gatter. 28:34.050 --> 28:37.190 Ich sage einfach, ich gehe jetzt hier auf, da gehe ich mal auf Off, 28:37.250 --> 28:38.890 ich möchte noch gar nichts weiter hier sehen. 28:39.610 --> 28:43.610 Ich brauche ein Und-Element und zwar brauche ich davon eins und ich 28:43.610 --> 28:44.930 brauche noch eins. 28:45.830 --> 28:50.010 Heißt, ich habe das angeklickt gehabt, das Und-Element und dann bin 28:50.010 --> 28:53.990 ich hier raufgegangen und habe einfach einmal raufgeklickt und dann 28:53.990 --> 28:56.450 entsteht das hier oder dann taucht das hier auf. 28:56.450 --> 29:00.250 Wir hatten also zwei Konjunktionen und eine Disjunktion, also brauche 29:00.250 --> 29:02.630 ich auch ein oder-Element, das war irgendwo weiter hier hinten. 29:04.010 --> 29:07.530 Dann brauche ich zwei Negationen, wo habe ich denn die Negationen, die 29:07.530 --> 29:08.130 habe ich auch irgendwo. 29:08.930 --> 29:10.870 Muss ich mal gucken, ich glaube, die sind hier hinten. 29:12.350 --> 29:13.810 Ne, wo habe ich jetzt die Negationen? 29:14.450 --> 29:16.070 Ich vergesse das immer, wo die sind. 29:21.570 --> 29:23.270 Da ist es nicht, natürlich nicht. 29:25.110 --> 29:28.910 Die Negationen, mein Gott, miscellaneous, Inverter. 29:29.170 --> 29:30.010 Sehen Sie, da habe ich ihn. 29:30.430 --> 29:37.550 Da ist der Inverter und von dem Inverter brauche ich auch zwei Stück. 29:37.810 --> 29:41.070 Sie sehen, hier ist er vollständig dargestellt mit diesem blöden 29:41.070 --> 29:42.590 rechteckigen Kasten noch daneben. 29:42.670 --> 29:43.550 Den kriege ich leider nicht weg. 29:44.830 --> 29:46.410 Das sind meine Bau-Elemente, das ist halt nicht alles. 29:46.510 --> 29:48.730 Ich muss noch irgendwo in der Lage sein, etwas einzugeben. 29:50.170 --> 29:53.230 Wenn ich etwas eingeben will, brauche ich einen sogenannten Button. 29:54.710 --> 29:56.770 Und bei diesem Button, es gibt verschiedene Möglichkeiten. 29:57.170 --> 29:58.670 Ich gehe einfach auf einen Button. 29:58.870 --> 29:59.990 Wir werden gleich sehen, wie der aussieht. 30:00.350 --> 30:00.990 Das sage ich OK. 30:01.930 --> 30:05.390 Und ich brauche also einen Button für das A, ich brauche einen Button 30:05.390 --> 30:06.830 für das B. 30:06.970 --> 30:08.110 Das sind meine beiden Eingänge. 30:08.990 --> 30:12.050 Und am Ende möchte ich noch etwas sehen, auch hier gibt es 30:12.050 --> 30:12.790 verschiedene Möglichkeiten. 30:12.930 --> 30:15.990 Wenn Sie immer in dieses Segment da unten reingehen, bekommen Sie 30:15.990 --> 30:18.570 verschiedene Möglichkeiten, Ausgaben anzuzeigen. 30:19.050 --> 30:20.650 Ich möchte jetzt nur die Lampe hier sehen. 30:21.010 --> 30:23.970 Am Ende wollen wir gerne eine Ausgabe sehen. 30:24.110 --> 30:25.830 Die Ausgabe soll 0 oder 1 sein. 30:26.470 --> 30:28.890 Und das können wir hier einfach so darstellen, dass wir eine Lampe 30:28.890 --> 30:31.790 leuchten lassen wollen oder nicht leuchten lassen wollen. 30:31.850 --> 30:34.750 Wenn sie leuchtet, ist es 1, wenn sie nicht leuchtet, ist es 0. 30:37.730 --> 30:40.250 Jetzt müssen wir ein bisschen mehr machen, jetzt müssen wir das Ganze 30:40.250 --> 30:40.950 zeichnen. 30:40.950 --> 30:44.870 Dazu gehe ich hier auf diesen Button da oben. 30:46.310 --> 30:49.010 Da sind so alle möglichen Symbole drauf. 30:49.570 --> 30:53.070 Wenn ich den eingeschaltet habe, kann ich hier Elemente miteinander 30:53.070 --> 30:54.710 verbinden oder auch hier hin- und herschieben. 30:55.390 --> 30:59.430 Vorher sind bei jedem Klick auf die Fläche Elemente entstanden. 30:59.990 --> 31:02.370 Jetzt sage ich, ich möchte dieses Element, da muss ich mit der Maus 31:02.370 --> 31:06.690 raufgehen, auf das Element hier, ich möchte das verbinden mit der 31:06.690 --> 31:06.950 Lampe. 31:07.010 --> 31:07.730 Jetzt habe ich die verbunden. 31:07.730 --> 31:10.950 Das kann ich also hier, das Ding hier beliebig nehmen, Sie sehen, die 31:10.950 --> 31:11.530 sind verbunden. 31:12.290 --> 31:13.430 Das ist meine Lampe. 31:14.370 --> 31:15.490 Gehen wir noch ein bisschen weiter rüber. 31:16.970 --> 31:20.590 Und wir wissen, wir müssen den Ausgang von dem, das ist das eine Und 31:20.590 --> 31:24.910 -Element, wir müssen den Ausgang von dem einen Und-Gatter verbinden 31:24.910 --> 31:29.210 mit dem einen Eingang des Oder-Gatters und den Ausgang von dem anderen 31:29.210 --> 31:32.930 Und -Gatter verbinden mit dem anderen Eingang des Oder-Gatters. 31:33.770 --> 31:35.450 Da haben wir den Teil schon mal fertig gemacht. 31:36.270 --> 31:42.810 Jetzt wissen wir, wir müssen der eine Eingang unseres Und-Gatters 31:42.810 --> 31:49.290 hier, der war jetzt nicht verbunden, jetzt ist es verbunden, der 31:49.290 --> 31:55.450 sollte negiert sein und hier muss der andere Eingang negiert sein. 31:57.510 --> 31:58.510 Jetzt haben wir das. 31:59.410 --> 32:03.750 Und wir haben, hier kann ich auch ganz dicht dran machen, das ist so, 32:03.830 --> 32:04.550 alles in Ordnung. 32:05.770 --> 32:09.470 Und ich weiß, nehmen wir mal an, dass das hier mein A ist. 32:10.990 --> 32:13.870 Ich könnte hier auch noch einen Text dazu malen, das könnte ich also 32:13.870 --> 32:16.050 auch noch machen, wenn ich hier auf Text gehe, könnte ich sagen, ich 32:16.050 --> 32:16.870 mache hier einen Text. 32:17.690 --> 32:20.370 Und dann könnte ich hier jetzt das hier, sehen Sie, das habe ich 32:20.370 --> 32:23.530 nochmal raufgeklickt, das wollte ich gar nicht, habe ich jetzt, doch, 32:23.570 --> 32:25.110 ich brauche den zweiten Text. 32:25.570 --> 32:32.590 Könnte den Text, den kann ich jetzt, sehen Sie, ich kann diesen, ich 32:32.590 --> 32:35.410 kann den hier unten hinschieben zum Beispiel, dahin, einmal Text, 32:35.490 --> 32:36.070 nochmal Text. 32:36.570 --> 32:39.850 Den hier möchte ich nicht haben, den möchte ich gerne löschen, dann 32:39.850 --> 32:45.550 muss ich da raufgehen, auf das Kreuz und einmal raufgehen, jetzt ist 32:45.550 --> 32:45.830 er weg. 32:46.450 --> 32:52.770 So, jetzt gehe ich wieder hier rauf und jetzt, also das hier wird zum 32:52.770 --> 33:00.510 Beispiel meine Variable B und das hier wird meine Variable A und jetzt 33:00.510 --> 33:06.590 weiß ich, dass, wenn das hier mein B ist, das soll ja direkt 33:06.590 --> 33:11.630 verbunden, ups, nicht so, ich muss hier ran, na, genau. 33:12.650 --> 33:18.570 Jetzt habe ich da ein B quer eingebaut in das obere und das A, das 33:18.570 --> 33:22.510 soll, jetzt habe ich hier A und B quer, liegt da an. 33:23.630 --> 33:25.990 Jetzt könnte ich schon mal gucken, was passiert dann, wenn ich das so 33:25.990 --> 33:30.170 verbinde, ich schalte das mal an, dann sehen Sie hier auf einmal so 33:30.170 --> 33:34.170 einen gelben, diese eine Leitung hier vorne ist auf einmal gelb 33:34.170 --> 33:34.510 geworden. 33:34.610 --> 33:35.690 Warum ist die gelb geworden? 33:37.170 --> 33:38.790 Gelb heißt, da liegt eine Eins an. 33:38.870 --> 33:39.850 Warum liegt da eine Eins an? 33:39.910 --> 33:42.190 Hier vorne liegt eine Null an, da liegt gar nichts an. 33:45.670 --> 33:47.770 Und negiert heißt, da kommt eine Eins rein. 33:48.490 --> 33:54.210 Wenn ich jetzt den hier anschalte, das A auf Eins schalte, dann haben 33:54.210 --> 33:57.270 wir bei dem Und-Gatter beide Eingänge auf Eins gesetzt. 33:57.910 --> 34:01.330 Es kommt hier auf dieser Leitung eine Eins an, geht in das Oder 34:01.330 --> 34:05.250 -Element rein und wir haben hier rechts am Ausgang eine Eins. 34:06.050 --> 34:06.930 Das leuchtet. 34:07.870 --> 34:10.610 Wenn ich hier eine Null mache, geht es wieder auf Null. 34:11.570 --> 34:14.670 Wenn ich hier eine Eins mache, passiert gar nichts, weil das Ganze, 34:15.150 --> 34:17.370 auch wenn ich hier jetzt eine Eins mache, passiert auch nichts weiter. 34:17.470 --> 34:20.470 Es sind zwar diese beiden Leitungen jetzt auf Eins gesetzt, aber an 34:20.470 --> 34:23.270 dem Und-Gatter ist halt nur eine Eins drin, nicht beide Eins. 34:25.030 --> 34:26.830 So, das war dieser Schaltmal wieder aus. 34:28.250 --> 34:32.750 Und jetzt müssen wir noch das andere Element versorgen mit Eingängen 34:32.750 --> 34:36.810 oder mit Werten, die aus diesen beiden Schaltern hier rauskommen. 34:38.170 --> 34:38.970 Wie machen wir das? 34:39.590 --> 34:41.970 Da muss ich jetzt überlegen, ob ich das auch richtig mache. 34:42.510 --> 34:46.190 Genau, wenn ich jetzt mit einem... 34:46.190 --> 34:48.970 Das ist das B, das soll dahin. 34:51.390 --> 34:57.490 Und da muss man also mit Steuerung und Maustaste kann man eine 34:57.490 --> 34:59.630 Verzweigung machen und das dann weiterleiten. 34:59.710 --> 35:04.130 Jetzt haben wir hier schon das B, einmal als B quer an dem oberen Und 35:04.130 --> 35:06.250 -Element und als B an dem unteren Element. 35:06.990 --> 35:09.730 Jetzt müssen wir hier auch noch sowas machen, also wieder Steuerung 35:09.730 --> 35:10.750 und darauf gehen. 35:10.750 --> 35:13.070 Dann habe ich hier dieses Element, dann kann ich das hier runterführen 35:14.170 --> 35:17.750 und dann mache ich das nochmal und gehe hier rüber und bin da dran. 35:18.090 --> 35:20.870 So, das ist jetzt meine Schaltung. 35:21.490 --> 35:24.090 Und jetzt kann ich sagen, jetzt setze ich hier A auf 1. 35:25.010 --> 35:27.930 Das ganze Ding ist erst einmal noch off, das heißt, ich muss es erst 35:27.930 --> 35:28.310 einmal anmachen. 35:28.370 --> 35:32.290 Jetzt habe ich 1 und 0 drin stehen, dann habe ich hier eine 1 am 35:32.290 --> 35:32.790 Ausgang. 35:33.370 --> 35:36.410 Bei 0,0 taucht rechts nichts auf. 35:36.410 --> 35:40.850 Wenn das hier 0 ist und das B ist 1, dann leuchtet die Lampe auch, 35:40.930 --> 35:46.070 weil jetzt auf einmal hier bei diesem unteren Und-Element über die 35:46.070 --> 35:50.730 Negation des A eine 1 ankommt und über das B auch eine 1, dann haben 35:50.730 --> 35:52.430 wir hier über die Diffusion auch eine 1. 35:52.870 --> 35:56.770 Und wenn ich beide auf 1 setze, dann ist wieder eine 0 dort, weil wenn 35:56.770 --> 36:03.330 beide auf 1 sind, dann ist jeweils ein Eingang beim Und-Element 0, 36:03.330 --> 36:06.650 nämlich gerade der negierte Eingang. 36:06.810 --> 36:11.090 Also das ist unser... so kann ich also ein XOR-Bild malen und ich kann 36:11.090 --> 36:14.290 das jetzt beliebig hier hin und her bewegen und kann das dann schön 36:14.290 --> 36:17.430 machen, indem ich hier irgendwie... ich kann also auch rechtwinklige 36:17.430 --> 36:20.430 Leitungen daraus machen, kann ich also beliebig jetzt das Ding hier 36:20.430 --> 36:26.110 drüber bewegen und das auch ganz klein machen oder was immer ich damit 36:26.110 --> 36:26.570 machen will. 36:26.790 --> 36:30.730 Ja, so sieht es nicht schön aus, so sah es schöner aus und so können 36:30.730 --> 36:32.030 Sie damit rumspielen, so viel Sie wollen. 36:32.030 --> 36:33.410 Das ist eine sehr einfache Schaltung. 36:34.770 --> 36:37.730 Dies ist also eine Möglichkeit, wie Sie Schaltungen entwerfen können, 36:38.110 --> 36:41.150 ein einfaches Werkzeug, das ich Ihnen empfehle, das Sie nutzen 36:41.150 --> 36:46.750 sollten, um das zu üben, wie man Schaltungen entwirft und Sie sehen 36:46.750 --> 36:50.470 eben sofort, was dort jeweils als Wert rauskommt. 36:50.590 --> 36:53.110 Und Sie können für die Eingabe eben auch viele verschiedene Dinge 36:53.110 --> 36:58.550 machen, Sie können zum Beispiel hier bei dem Button können Sie auch 36:58.550 --> 37:06.770 anstelle des Buttons können Sie auch unterschiedliche wiederholende 37:06.770 --> 37:10.790 Signale machen, Sie können also periodische Signale dort eingeben 37:10.790 --> 37:16.690 lassen, Sie können eine oszillierende Eingabe machen, Sie können 37:16.690 --> 37:20.370 konstante Eingabe machen, Sie können das immer auf Wert 1 oder immer 37:20.370 --> 37:24.510 auf Wert 0 setzen, Sie können auch die Größe verändern, also 37:24.510 --> 37:28.530 verschiedene Sachen, spielen Sie damit rum, dann merken Sie, wie man 37:28.530 --> 37:33.230 damit Schaltungen aufbauen kann, wie man die damit auch testen kann. 37:33.570 --> 37:38.570 Und man kann das Ganze auch abspeichern und kann also hier über diese 37:38.570 --> 37:42.210 ganzen Elemente das Ganze in verschiedenen Formaten abspeichern, in 37:42.210 --> 37:47.690 XML, also ein schönes Standardformat zur Beschreibung von Inhalten, in 37:47.690 --> 37:51.830 VHDL, das werden Sie noch kennenlernen, was das ist, Very High Level 37:51.830 --> 37:56.690 Hardware Description Language, Sprache zur Beschreibung von 37:56.690 --> 37:57.150 Schaltungen. 37:58.030 --> 38:02.430 Man hat also Sprachen, nicht nur um Programme zu beschreiben, sondern 38:02.430 --> 38:06.950 auch um Hardware zu beschreiben, weil man in der technischen Anwendung 38:06.950 --> 38:12.530 Schaltungen braucht, die bestimmte Funktionen realisieren. 38:13.470 --> 38:16.750 Wenn Sie Informationsverarbeitung machen, dann müssen Sie nicht nur 38:16.750 --> 38:19.930 Programme entwerfen, sondern Sie müssen auch Systeme entwerfen. 38:20.450 --> 38:23.070 Und zu einem Systementwurf gehört Software, aber auch Hardware. 38:23.610 --> 38:26.710 Und bestimmte Funktionen, die Sie brauchen in technischen Anwendungen, 38:26.770 --> 38:30.170 in technischen Geräten, müssen Sie direkt über Hardware realisieren. 38:30.850 --> 38:33.550 Deswegen müssen Sie wissen, wie man solche Hardware-Bausteine 38:33.550 --> 38:34.070 entwirft. 38:34.790 --> 38:37.950 Das ist also die ganze Idee hinter diesen Werkzeugen. 38:38.490 --> 38:43.410 Und damit kommen wir zurück zu unserer Präsentation. 38:43.410 --> 38:45.890 Jetzt wollen viele, dass ich schneller vorwärts gehe. 38:46.670 --> 38:47.730 Also nochmal zurück hier. 38:48.690 --> 38:51.430 Diese Werkzeuge, ich bin darauf extra jetzt etwas länger eingegangen, 38:51.530 --> 38:53.410 weil ich Ihnen zeigen wollte, wie man damit umgeht. 38:54.550 --> 38:58.750 Und es ist eine wichtige Kenntnis, die Sie haben sollten als 38:58.750 --> 39:04.850 Wirtschaftsingenieure, dass Hardware etwas ist, was nicht fest ist in 39:04.850 --> 39:06.910 dem Sinne, dass man sich darum nicht zu kümmern braucht. 39:07.310 --> 39:10.590 Wir haben ja alle unsere Rechner, die bestehen ja schon aus Hardware. 39:10.610 --> 39:11.930 Um Hardware kümmere ich mich nicht. 39:11.930 --> 39:15.650 Als Wirtschaftsingenieur werden Sie zukünftig immer mehr damit zu tun 39:15.650 --> 39:19.150 haben, intelligente Komponenten zu entwickeln oder als Produkt zu 39:19.150 --> 39:24.950 entwerfen oder entwerfen zu lassen, in denen solche intelligenten 39:24.950 --> 39:25.970 Schaltungen vorkommen. 39:26.770 --> 39:31.470 Und die werden eben auch systematisch entworfen. 39:31.790 --> 39:34.890 Und deswegen muss man wissen, was eigentlich der Hintergrund dafür 39:34.890 --> 39:36.290 ist, dass man die so entwerfen kann. 39:36.290 --> 39:41.310 Und das ist der Inhalt unserer heutigen Vorlesung und auch morgen und 39:41.310 --> 39:42.350 nächste Woche nochmal. 39:43.270 --> 39:45.210 So, das kann ich jetzt noch ein bisschen verallgemeinern. 39:45.290 --> 39:47.810 Nicht nur diese einfachen Schaltelemente, ich kann auch größere bauen. 39:47.950 --> 39:55.270 Ich kann also hier einen Oder-Gatter oder einen Und-Gatter mit 39:55.270 --> 39:57.070 entsprechend vielen Eingängen machen. 39:57.450 --> 40:00.190 Das ist ja einfach nur ein Modell, ein Symbol. 40:00.190 --> 40:05.470 Und wenn ich also zum Beispiel einen Oder-Gatter mit vier Eingängen 40:05.470 --> 40:11.190 malen will, das könnte ich auch malen, indem ich einfach hier vier 40:11.190 --> 40:16.690 Eingänge habe und hier jeweils größer gleich eins reinschreibe, größer 40:16.690 --> 40:22.090 gleich eins, und die beiden verbinde mit einem Oder-Gatter größer 40:22.090 --> 40:22.790 gleich eins. 40:22.890 --> 40:24.350 Und da geht es dann entsprechend raus. 40:24.350 --> 40:30.030 Das heißt, ich könnte über ein Schaltnetz mit drei solchen Schalt 40:30.030 --> 40:34.070 -Gattern, die jeweils zwei Eingänge haben, das sind dann nur 40:34.070 --> 40:38.870 elementare Gatter, auch ein solches vereinfachtes Gatter realisieren. 40:39.450 --> 40:42.330 Aber in der Darstellung ist es natürlich viel einfacher, wenn ich da 40:42.330 --> 40:45.330 einfach nur diesen größeren Kasten hinmale. 40:45.830 --> 40:48.190 Und auch hier steht es einfach nur größer gleich eins. 40:48.350 --> 40:51.750 Das heißt, ein Eingang muss eins sein, damit hier ein Wert eins 40:51.750 --> 40:52.310 rauskommt. 40:52.310 --> 40:57.170 Oder in diesem Fall und alle Eingänge müssen eins sein, damit ein Wert 40:57.170 --> 40:57.990 eins rauskommt. 40:59.050 --> 41:01.630 Auch dies hier könnten wir uns aufbauen als Schaltung, das will ich 41:01.630 --> 41:02.390 mir aber ersparen. 41:03.850 --> 41:06.290 Jetzt kommen wir zu dem, was wir eben daraus machen wollen. 41:06.350 --> 41:10.430 Aus den elementaren Gattern wollen wir Schaltnetze bauen. 41:11.350 --> 41:12.790 Was ist jetzt ein Schaltnetz? 41:12.870 --> 41:17.050 Das ist genau etwas, was wir aus solchen elementaren Schaltgattern 41:17.050 --> 41:21.390 aufbauen, um eine Schaltfunktion zu realisieren. 41:22.250 --> 41:27.690 Eine Abbildung von b hoch n nach b hoch m ist aber mehr als eine 41:27.690 --> 41:28.550 Schaltfunktion. 41:29.370 --> 41:35.150 Da haben wir jetzt, wenn Sie zurückgucken auf die Definition der 41:35.150 --> 41:39.870 Schaltfunktion, die Schaltfunktion hat jeweils irgendwelche Anzahl von 41:39.870 --> 41:44.710 Eingängen und ein binäres Ergebnis, null oder eins. 41:45.830 --> 41:50.850 Hier haben wir jetzt aber eine Funktion von b hoch n nach b hoch m. 41:52.190 --> 41:58.970 Das heißt, wir haben n Eingänge, a1 bis an, und irgendwelche m 41:58.970 --> 42:02.330 Ausgänge, f1 von a bis fm von a. 42:03.130 --> 42:07.130 Sie erinnern sich, ich hatte Ihnen einfache Beispiele genannt für 42:07.130 --> 42:11.530 Schaltfunktionen, die Schaltfunktionen, die zu einem binären Addierer 42:11.530 --> 42:11.950 gehören. 42:13.830 --> 42:17.630 Binärer Addierer, das wäre doch so etwas, dass ich gerne addieren 42:17.630 --> 42:22.750 möchte, und ich habe hier Eingänge a und b, und rauskommen soll ein 42:22.750 --> 42:24.810 Summenbit und ein Übertragsbit. 42:25.170 --> 42:28.970 Sie sehen, das wäre ein Schaltnetz, was ich dort haben möchte. 42:29.910 --> 42:33.910 Und wie man das jetzt realisiert, wie man also diese Funktion f, in 42:33.910 --> 42:39.470 dem Fall das plus realisiert von zwei solchen Bits, damit dort zwei 42:39.470 --> 42:43.950 Schaltfunktionen realisiert werden, nämlich die Summenfunktion und die 42:43.950 --> 42:47.410 Übertragsfunktion, das ist Sache, wie baue ich das aus meinen 42:47.410 --> 42:48.870 elementaren Schaltgattern auf. 42:50.190 --> 42:53.750 Also, diese einzelnen fj sind Schaltfunktionen, das sind die 42:53.750 --> 42:59.110 produzierenden Ausgaben, und das Wesentliche bei Schaltnetzen ist, 42:59.430 --> 43:04.430 dass ihr Verhalten kombinatorisch ist, in dem Sinne, diese Schaltnetze 43:04.430 --> 43:05.670 haben kein Gedächtnis. 43:06.480 --> 43:10.950 Die Werte an den Ausgängen sind nur abhängig von denen an den 43:10.950 --> 43:11.570 Eingängen. 43:12.270 --> 43:17.490 Wenn ich mehrfach die gleiche Eingabe anlege, kommt immer die gleiche 43:17.490 --> 43:18.290 Ausgabe raus. 43:18.850 --> 43:21.090 Egal, was ich zwischendurch anderes gemacht habe. 43:21.610 --> 43:25.690 Für gleiche Eingänge, für gleiche Eingaben kommen gleiche Ausgaben 43:25.690 --> 43:26.010 raus. 43:26.930 --> 43:30.490 Das Ganze ist also nur kombinatorisch, die Informationen, die 43:30.490 --> 43:34.510 reingegeben werden, kombiniert zu einem Ergebnis. 43:35.790 --> 43:42.610 Und dieses f hier vorne ist also eine Zusammenfassung von m einzelnen 43:42.610 --> 43:43.930 Schaltfunktionen. 43:44.330 --> 43:48.370 Einfaches Beispiel, der binäre Addierer mit den zwei Schaltfunktionen 43:48.370 --> 43:50.470 s für Summe und ü für Übertragung. 43:52.450 --> 43:54.430 Machen wir da ein paar Beispiele für. 43:54.790 --> 44:00.370 Da kommt jetzt etwas, ein Halbadierer, den habe ich im Prinzip Ihnen 44:00.370 --> 44:01.430 gerade aufgemalt. 44:02.110 --> 44:03.090 Was ist ein Halbadierer? 44:03.790 --> 44:07.590 Der Halbadierer soll also, das gebe ich hier schon mal weiter, das ist 44:07.590 --> 44:09.850 unser Symbol für den Halbadierer, das ist das, was ich Ihnen gerade 44:09.850 --> 44:10.590 aufgemalt hatte. 44:10.690 --> 44:14.990 Hier ist jetzt anders dargestellt, Eingänge von oben, hier geht es 44:14.990 --> 44:16.070 also in diese Richtung. 44:16.650 --> 44:19.170 Bei dem anderen Bild, was ich auf der vorigen Folie hatte, ging es von 44:19.170 --> 44:20.990 links nach rechts, hier geht es von oben nach unten. 44:20.990 --> 44:26.890 Zwei beliebte Aufzeichnungsweisen für Schaltnetze. 44:27.630 --> 44:30.070 Von oben nach unten oder von links nach rechts sollen hier die 44:30.070 --> 44:30.950 Informationen laufen. 44:31.350 --> 44:32.750 Sie sehen hier keine Pfeile. 44:33.530 --> 44:36.830 Ich hätte hier auch Pfeile ranmalen können, um anzudeuten, dass das 44:36.830 --> 44:38.930 eine Eingaben, das andere Ausgaben sind. 44:41.290 --> 44:42.490 Warum Halbadierer? 44:43.810 --> 44:46.710 Weil ich hier nur zwei Werte addiere, A und B. 44:47.690 --> 44:50.430 Sie erinnern sich, dass ich Ihnen, als ich Ihnen das Beispiel genannt 44:50.430 --> 44:54.670 habe für Übertrags- und Summenfunktionen, auch ein Beispiel gegeben 44:54.670 --> 45:00.890 habe, dass wir zwei Eingabewerte und einen Übertrag addieren mussten, 45:00.990 --> 45:04.850 um daraus, aus diesen drei Werten, einen Summenbit und ein neues 45:04.850 --> 45:06.670 Übertragsbit zu erzeugen. 45:07.510 --> 45:10.190 Wenn wir nur zwei Werte haben, können wir eigentlich nicht wirklich 45:10.190 --> 45:11.710 addieren, dann können wir nur halb addieren. 45:13.070 --> 45:15.390 Sie werden gleich sehen, wie man daraus dann einen Volladdierer machen 45:15.390 --> 45:15.710 kann. 45:15.710 --> 45:17.330 Was macht also der Halbadierer? 45:17.410 --> 45:20.690 Der nimmt sich diese beiden Werte her und entsprechend haben wir dann 45:20.690 --> 45:26.730 als Summenbit gerade das XOR der beiden Eingaben und als Übertragsbit 45:26.730 --> 45:30.770 gerade die Konjunktion der beiden Eingaben. 45:31.630 --> 45:32.570 Das kennen Sie schon. 45:34.630 --> 45:36.650 Jetzt kann ich daraus einen Volladdierer bauen. 45:38.250 --> 45:40.430 Und der Volladdierer, was muss der machen? 45:40.730 --> 45:42.770 Da haben wir jetzt die Tabelle, die Sie auch schon kennen. 45:43.770 --> 45:48.870 Hier ist das Summenbit, jetzt das XOR aller drei Werte. 45:50.230 --> 45:54.090 Hier haben Sie eine Eins, wann immer wir eine ungerade Anzahl von 45:54.090 --> 45:59.210 Einsen haben, bei den Eingängen, bei dem Summenbit. 45:59.970 --> 46:04.830 Und bei dem Übertragsbit haben wir eine Eins, wann immer mindestens 46:04.830 --> 46:09.170 zwei der Eingaben eins sind. 46:10.850 --> 46:12.190 Also zwei oder drei. 46:13.230 --> 46:18.010 Das heißt, wenn A und B eins sind oder A und Ü oder B und Ü eins sind. 46:18.550 --> 46:22.070 Die Klammern habe ich hier weggelassen, weil die Priorität der 46:22.070 --> 46:24.050 Ausführung immer so ist, Konjunktion vor Dissjunktion. 46:24.790 --> 46:26.070 Das ist also unsere Volladdierer. 46:26.130 --> 46:28.490 Jetzt könnte ich hieraus auch wieder direkt Schaltungen machen. 46:29.150 --> 46:29.790 Das ist das hier. 46:30.730 --> 46:34.890 Das wäre ein Schaltnetz, um ein Volladdierer aufzubauen. 46:35.650 --> 46:38.210 Sie werden später sehen, man kann auch einfach zwei Halbadierer 46:38.210 --> 46:41.370 nehmen, die geeignet kombinieren und daraus einen Volladdierer bauen. 46:42.570 --> 46:47.510 Jetzt habe ich also einen Volladdierer, der in der Lage ist, ein 46:47.510 --> 46:52.810 Summenbit zu erzeugen, aus drei Eingängen, A, B und Ü, die hier oben 46:52.810 --> 46:53.550 reingehen. 46:55.910 --> 47:02.610 Dann kann ich über die XOR-Funktion, 2K plus 1, der Baustein für die 47:02.610 --> 47:09.590 XOR -Funktion, das Summenbit erzeugen und über drei Konjunktionen von 47:09.590 --> 47:15.570 A, B, A, Ü oder B, Ü disjunktiv zusammengefasst das Übertastbit 47:15.570 --> 47:16.270 erzeugen. 47:16.990 --> 47:21.290 Eine einfache Umsetzung dieser beiden Ausdrücke in eine Schaltung. 47:22.890 --> 47:26.550 Sie sehen, wir haben also hier nicht zwei Schaltungen nebeneinander 47:26.550 --> 47:29.050 gesetzt, eigentlich schon, das sind die beiden Schaltungen. 47:29.150 --> 47:31.270 Das ist die eine Schaltung, das ist die andere Schaltung. 47:31.270 --> 47:34.930 Aber natürlich muss man nur dafür sorgen, dass entsprechend die 47:34.930 --> 47:38.410 richtigen Werte hier rauskommen, an den Ausgängen jeweils die 47:38.410 --> 47:40.950 entsprechenden Schaltfunktionen realisiert sind. 47:43.210 --> 47:49.390 Okay, damit weiß ich, wie ich also Funktionen umsetzen kann und ich 47:49.390 --> 47:53.210 könnte das jetzt auch noch genauer aufbauen. 47:53.210 --> 48:02.350 Ich will das aber etwas später machen bei einem anderen Element. 48:03.090 --> 48:07.930 Ich gehe auf einer späteren Folie wieder auf die Logiflash-Animation. 48:08.270 --> 48:11.610 Wollte ich mir jetzt hier ersparen, mache ich dann beim nächsten 48:11.610 --> 48:12.010 Beispiel. 48:13.230 --> 48:17.170 Das Symbol für diesen Volladierer ist in der Regel so A, B und dann so 48:17.170 --> 48:17.450 ein Ü. 48:17.690 --> 48:22.010 Durch diese Darstellung wird einfach angedeutet, dass es ein Element, 48:22.150 --> 48:27.170 das kommt aus der vorherigen Stelle, dieser Übertrag, und hier dieses 48:27.170 --> 48:31.270 Ü -Strich, der Übertrag, der da rauskommt, der geht an die links 48:31.270 --> 48:35.250 daneben liegende Stelle, zu dem höherwertigen Bit. 48:37.870 --> 48:43.570 Und jetzt sehen Sie, wie man aus einem Volladierer, nee, aus mehreren 48:43.570 --> 48:48.890 Volladierern und einem Halbadierer, einen Adierer für beliebige Zahlen 48:48.890 --> 48:49.730 aufbauen kann. 48:49.730 --> 48:57.170 Wir wollen also jetzt zwei Zahlen addieren, A und B, beides 48:57.170 --> 48:58.450 endstellige Zahlen. 48:59.350 --> 49:04.950 Das heißt, wir haben Bits A0 bis An-1 und B0 bis Bn-1. 49:05.930 --> 49:11.530 Und es werden A0 und B0 hier eingegeben, bei dem Halbadierer, weil ich 49:11.530 --> 49:18.010 zu Beginn ja nur zwei Bits habe, B0 und A0, also eigentlich steht das 49:18.010 --> 49:31.590 ja so übereinander, An-2 und so weiter bis A0, und hier Bn-1, Bn-2 bis 49:31.590 --> 49:34.850 B0, und da will ich die Ergebnisse jetzt addieren. 49:34.970 --> 49:40.170 Da kommt hier halt jetzt ein S0 raus und ein Übertrag. 49:40.610 --> 49:42.310 Der Übertrag aus der 0. 49:42.450 --> 49:46.690 Stelle geht rein in den Volladierer, das habe ich hier drei Werte, 49:46.830 --> 49:52.190 nämlich A1, B1 und Ü0, und daraus entsteht jetzt ein Ü1, der Übertrag 49:52.190 --> 49:54.910 in die nächste Stelle unter Summe mit S1 und so weiter. 49:55.130 --> 50:00.350 Das heißt, aus diesen N-1 Volladierern und einem Halbadierer kann ich 50:00.350 --> 50:01.990 jetzt einen Gesamtadierer bauen. 50:03.610 --> 50:07.470 Und wenn ich mir das Ganze jetzt anschaue, wie ist eigentlich der 50:07.470 --> 50:08.350 Aufwand dafür? 50:08.850 --> 50:11.730 Wirtschaftsingenieur fragt sofort, aber auch ein Informatiker, fragt 50:11.730 --> 50:15.810 sofort, was heißt das eigentlich für das Zeitverhalten eines solchen 50:15.810 --> 50:16.670 Bausteins? 50:17.430 --> 50:21.750 Auch Hardware hat ein Zeitverhalten und eine Zeitkomplexität und eine 50:21.750 --> 50:26.010 Platzkomplexität oder in diesem Fall eine Flächenkomplexität. 50:27.030 --> 50:29.350 Wie viel Chipfläche brauche ich, um sowas darzustellen? 50:29.450 --> 50:32.330 Das sprechen die Chipfläche für meine Volladierer und für den 50:32.330 --> 50:34.530 Halbadierer und die Fläche für die Leitungen. 50:36.490 --> 50:37.870 Und jetzt kommt noch die Zeit dazu. 50:37.950 --> 50:39.190 Wie sieht das mit der Zeit aus? 50:40.590 --> 50:43.170 Naja, ich gebe hier A0 und B0 ein. 50:47.200 --> 50:49.080 Dann kommt hier ein S0 raus. 50:49.980 --> 50:51.720 Es kommt eventuell noch ein Ü0 raus. 50:52.220 --> 50:59.460 Also wenn ich zum Beispiel jetzt auf die Zahl 0111 hier addiere, eine 50:59.460 --> 51:04.300 0001, was passiert denn dann? 51:04.680 --> 51:09.680 Dann bekomme ich hier vorne eine 0, dann habe ich hier einen Übertrag 51:09.680 --> 51:14.380 1, der geht hier rüber, dann habe ich hier wieder eine 0, ich habe 51:14.380 --> 51:18.120 hier einen Übertrag 1, Übertrag 1, entsprechend wieder eine 0, 51:18.760 --> 51:20.440 Übertrag 1, ich habe hier eine 1. 51:21.420 --> 51:26.000 Das heißt, ich muss hier einmal so durchlaufen, wenn ich Pech habe, 51:26.100 --> 51:30.580 bis ganz zum Ende, bevor ich eigentlich weiß, welchen Wert dieses UN-1 51:30.580 --> 51:30.960 hier hat. 51:31.520 --> 51:33.940 Der Übertrag aus der höchstsignifikanten Stelle. 51:34.860 --> 51:40.160 Das heißt, die Schaltzeit ist linear in der Wortlänge. 51:41.940 --> 51:48.100 Das dauert ziemlich lange, bis ich hier das Ergebnis ausgerechnet 51:48.100 --> 51:48.500 habe. 51:49.000 --> 51:54.140 Weil eben der Übertrag, deswegen heißt das Ripple Carry Adder, der 51:54.140 --> 51:58.160 läuft hier so langsam durch von Stelle zu Stelle, von der 51:58.160 --> 52:00.400 niedrigsignifikanten bis zur höchstsignifikanten Stelle. 52:00.400 --> 52:07.220 Also, Addition von zwei Zahlen braucht hiernach lineare Zeit in der 52:07.220 --> 52:07.660 Wortlänge. 52:08.360 --> 52:14.620 Wenn ich also einen 8-Bit-Addierer habe oder einen 16-Bit oder 32-Bit 52:14.620 --> 52:19.420 oder 64-Bit-Addierer, da braucht die Addition dann immer doppelt so 52:19.420 --> 52:19.960 lange Zeit. 52:20.100 --> 52:24.320 Mein Gott, wenn ich jetzt einen 64-Bit-Rechner habe und in dem 64-Bit 52:24.320 --> 52:28.260 -Rechner haben alle meine Zahlen 64 Bit und ich möchte addieren, ich 52:28.260 --> 52:31.200 möchte ja eigentlich mit dem 64-Bit-Rechner schneller arbeiten können 52:31.200 --> 52:32.820 als mit dem 32-Bit-Rechner. 52:33.740 --> 52:35.800 Da muss ich doppelt so lange warten, das ist ja furchtbar. 52:36.780 --> 52:37.700 Da muss man was dran tun. 52:37.800 --> 52:39.180 Wir werden gleich sehen, was man daran tun kann. 52:40.340 --> 52:44.960 Eine Sache, die man machen kann, ich gehe gleich auf diese Animation 52:44.960 --> 52:50.100 ein, ist, dass ich einfach Folgendes machen kann. 52:51.100 --> 52:57.500 Ich füge einfach in jedes Übertragselement hier ein Verzögerungsglied 52:57.500 --> 52:57.760 ein. 52:59.960 --> 53:06.660 Und ich mache das einfach so, dass ich sage, ich warte immer mit der 53:06.660 --> 53:14.700 Eingabe der A1 und B1, bis das Ergebnis aus A0 und B0 da ist. 53:17.360 --> 53:19.420 Dann erst gebe ich A1, B1 ein. 53:20.040 --> 53:23.860 Und wenn dann das Ergebnis von A1, B1 da ist, kann ich hier im Prinzip 53:23.860 --> 53:30.620 schon die nächste Zahl A0, B0, oder die nächsten niedrigsignifikanten 53:30.620 --> 53:31.500 Bits eingeben. 53:32.160 --> 53:37.880 Und ich habe dann auf einmal die Möglichkeit, hier die 53:37.880 --> 53:41.920 niedrigsignifikantesten Bits, also A0 und B0, für eine Addition zu 53:41.920 --> 53:42.180 machen. 53:42.900 --> 53:46.740 Ich male das mal hier so diagonal rein, auf der nächsten Folie kommt 53:46.740 --> 53:47.280 das gleich. 53:47.860 --> 53:50.620 Sie haben im Prinzip ein Eingabeschema, das sieht so aus. 53:51.880 --> 53:55.120 Und die nächste Zahl wird genauso eingegeben und die nächste Zahl 53:55.120 --> 53:57.020 genauso und die nächste Zahl genauso. 53:57.740 --> 54:03.120 Und wenn Sie jetzt diese Bits hier eingeben, dann haben Sie gerade 54:03.120 --> 54:09.900 alle anderen Bits an der dritten, zweiten und ersten Position, nehmen 54:09.900 --> 54:13.380 wir mal an, wir haben nur vier Bits, dann hätten Sie die gerade in den 54:13.380 --> 54:18.100 anderen Komponenten am Wickel und Sie könnten im Prinzip vier 54:18.100 --> 54:19.520 Additionen gleichzeitig machen. 54:21.380 --> 54:27.760 Und könnten dadurch mit einem Zeitversatz, der gerade der 54:27.760 --> 54:32.320 Verarbeitungszeit in einer dieser Komponenten entspricht, einzelne 54:32.320 --> 54:33.400 Additionen eingeben. 54:34.900 --> 54:39.540 Und das heißt, statt eines Additionsverfahrens, bei dem Sie 54:39.540 --> 54:45.940 nacheinander einzelne Additionen machen, können Sie jetzt, wenn das 54:45.940 --> 54:52.220 hier die Zeit ist und das hier die einzelnen Additionsnummern, dann 54:52.220 --> 54:56.780 können Sie jetzt das Ganze so machen, dass Sie hier die jeweils mit 54:56.780 --> 54:59.440 einem Takt Verzögerung eingeben. 54:59.440 --> 55:07.180 Und Sie hätten einen deutlich höheren Durchsatz durch Ihren Baustein 55:07.180 --> 55:07.740 Addiere. 55:08.400 --> 55:12.420 Sie könnten also mit im Prinzip konstanter Verzögerung, unabhängig von 55:12.420 --> 55:17.600 der Wortlänge, könnten Sie jetzt im Prinzip eine einzelne Addition 55:17.600 --> 55:21.240 durchführen, zumindest anstoßen und Sie würden mit einer Frequenz, die 55:21.240 --> 55:26.560 nur abhängt von der Geschwindigkeit, mit der Sie einen Baustein 55:26.560 --> 55:29.920 betreiben können, solche eine Folge von Additionen machen. 55:31.000 --> 55:35.580 Das ist ein ganz wichtiges Prinzip, das nennt sich, ich schreibe es 55:35.580 --> 55:41.720 auf Englisch hin, Pipelining, auf Deutsch Fließbandprinzip, ist 55:41.720 --> 55:47.060 industriell bei der Produktion des T-Modells von Ford auf den Weg 55:47.060 --> 55:51.140 gebracht worden, Fließbandverarbeitung in der automatisierten 55:51.140 --> 55:54.580 Fabrikation von komplexen Gegenständen. 55:54.580 --> 55:58.040 Pipelining setzt man im Rechner auch ein, nur deswegen sind unsere 55:58.040 --> 56:03.040 Rechner heutzutage so schnell, die können nur mit ein bis zwei oder 56:03.040 --> 56:06.700 drei Gigahertz getaktet werden, weil wir Pipelining einsetzen. 56:07.440 --> 56:11.320 Wenn wir immer warten müssten, bis eine ganze Addition durchgeführt 56:11.320 --> 56:14.640 ist, bevor wir die nächste Addition anstoßen, dann würden die mit 56:14.640 --> 56:17.720 wenigen Megahertz arbeiten. 56:18.280 --> 56:20.640 So können Sie im Gigahertz-Bereich arbeiten. 56:23.420 --> 56:27.080 Also, jede Addition dauert dann zwar in Takte, was ein Takt ist, 56:27.160 --> 56:30.260 darauf kommen wir später auch noch zu sprechen, aber man kann in jedem 56:30.260 --> 56:33.660 Takt eine neue Addition beginnen, also das wäre im Prinzip hier 56:33.660 --> 56:39.340 jeweils ein Takt und es können bis zur Endaddition gleichzeitig 56:39.340 --> 56:42.080 jeweils um einen Takt versetzt ausgeführt werden. 56:42.080 --> 56:50.580 Das hier will ich jetzt einmal kurz Ihnen vorführen und 56:57.710 --> 57:02.650 dazu will ich etwas aus dem XML rausholen. 57:02.950 --> 57:10.490 Das war Vorlesung, Unterstrich, Ripple. 57:11.190 --> 57:12.550 Na, was stand da jetzt? 57:13.650 --> 57:14.330 Ripple Carry? 57:19.330 --> 57:20.990 Ah, da stand was anderes. 57:21.110 --> 57:21.910 Lassen wir mal kurz gucken. 57:22.610 --> 57:23.610 Was stand hier eigentlich? 57:24.550 --> 57:30.450 Da stand Ripple Carry Vorlesung, Ripple Carry XML. 57:30.910 --> 57:32.410 Wieso kann der das nicht finden? 57:34.430 --> 57:35.550 Das ist ärgerlich. 57:37.710 --> 57:39.610 Ah, auch das noch. 57:39.650 --> 57:41.710 Ich habe die verkehrte Taste gedrückt. 57:42.510 --> 57:46.790 Dann muss ich das da wieder einmal kurz rausgehen und ich gehe kurz in 57:46.790 --> 57:53.290 dieses Verzeichnis rein, in das Verzeichnis Info 2, 57:56.730 --> 58:07.750 Logiflash, Circuits, da habe ich es, Ripple Carry XML. 58:09.230 --> 58:10.790 Das kann er natürlich nicht. 58:12.150 --> 58:14.830 Das wollte ich gar nicht. 58:15.870 --> 58:18.550 Jetzt können Sie gleich sehen, wie eine solche Funktion dargestellt 58:18.550 --> 58:18.750 ist. 58:19.350 --> 58:22.130 Das ist also eine solche XML-Darstellung, das wollte ich Ihnen gar 58:22.130 --> 58:22.570 nicht zeigen. 58:22.690 --> 58:23.630 Das sehen Sie jetzt trotzdem. 58:25.110 --> 58:27.350 Das konnte er aber leider nicht darstellen. 58:27.350 --> 58:31.470 Also das war jetzt, machen wir ein Cancel draus, das ist mal schnell 58:31.470 --> 58:31.930 wieder zu. 58:32.870 --> 58:41.430 Und ich wollte eigentlich, jetzt mache ich hier, mein Gott nochmal, es 58:41.430 --> 58:42.730 ist hier etwas durcheinander gegangen. 58:42.870 --> 58:48.650 Jetzt gehe ich hier noch einmal auf Logiflash und mache das gleiche 58:48.650 --> 58:49.030 nochmal. 58:49.930 --> 58:51.210 Gehe hier rauf, 58:54.480 --> 59:03.760 Vorlesung, unterstrichen, Ripple Carry, konnte nicht geladen werden. 59:03.820 --> 59:04.980 Was habe ich denn hier falsch gemacht? 59:06.040 --> 59:07.180 Das begreife ich nicht. 59:09.020 --> 59:12.180 Ich habe das ausprobiert, auf diese Art und Weise soll es auf jeden 59:12.180 --> 59:12.720 Fall gehen. 59:12.720 --> 59:15.740 Ah, das ist das Problem. 59:20.190 --> 59:25.850 Ich muss in ein anderes... 59:27.800 --> 59:30.360 Also das ist mir jetzt wirklich nicht klar, woran das liegt. 59:30.760 --> 59:39.520 Ich habe eine Vermutung, woran das liegt, aber ich lasse es. 59:41.440 --> 59:44.720 Es tut mir leid, ich lasse das jetzt, ich repariere das und dann 59:44.720 --> 59:45.620 können wir das hinbekommen. 59:45.620 --> 59:48.360 Es gibt ja einfach Probleme damit, dass ich auf ein Netzlaufwerk 59:48.360 --> 59:53.520 zugreife und das Netzlaufwerk macht dann leider daraus solch eine 59:53.520 --> 59:57.380 Darstellung und diese Darstellung mit dem Pfeil hier vorne, die mag er 59:57.380 --> 59:57.700 nicht. 59:58.340 --> 01:00:03.640 Dazu müsste ich das hier wegmachen, das war wieder verkehrt, das 01:00:03.640 --> 01:00:04.480 wollte ich nicht. 01:00:06.260 --> 01:00:08.520 Okay, das macht er nicht. 01:00:09.560 --> 01:00:13.220 Ich hätte das hier vorne... 01:00:13.220 --> 01:00:14.700 Es ist schrecklich. 01:00:18.030 --> 01:00:22.050 Es ist 01:00:25.910 --> 01:00:33.010 echt ärgerlich, wenn ich hier dieses mit Unterstrich T mache. 01:00:33.790 --> 01:00:34.510 Auch das macht er nicht. 01:00:34.590 --> 01:00:35.910 Hat er das alles verändert? 01:00:35.910 --> 01:00:42.890 Aus irgendeinem Grund hat er hier die falsche Folie da drin. 01:00:43.430 --> 01:00:49.250 Ich gehe nochmal hier rein in unsere Vorlesung, gehe hier auf die 01:00:49.250 --> 01:00:57.410 Präsentation und dann entscheint hier das Ding. 01:00:59.150 --> 01:01:03.210 Eigentlich soll der... genau, der geht bei C rein. 01:01:07.220 --> 01:01:08.700 Ja, das ist richtig. 01:01:12.420 --> 01:01:15.680 Und jetzt müsste hier... 01:01:22.140 --> 01:01:23.520 ein letzter Versuch. 01:01:28.780 --> 01:01:29.780 Jetzt gehe ich mal auf was anderes. 01:01:30.120 --> 01:01:31.540 Xm... ne, Quatsch. 01:01:32.600 --> 01:01:35.020 So, das hat er gemacht. 01:01:35.140 --> 01:01:36.500 Sehen Sie, das konnte er. 01:01:37.120 --> 01:01:40.480 Da muss diese eine Datei fehlen. 01:01:42.880 --> 01:01:43.840 Das konnte er. 01:01:48.290 --> 01:01:53.470 Ripple Carry, das kann er nach wie vor wahrscheinlich nicht. 01:01:55.270 --> 01:02:02.590 So, und die Ripple Carry T, die kann er auch nicht. 01:02:02.590 --> 01:02:04.730 Keine Ahnung, woran das liegt, das repariere ich. 01:02:04.830 --> 01:02:06.330 Ich mache jetzt mit der Vorlesung weiter. 01:02:06.790 --> 01:02:10.450 Ich habe nämlich auf der nächsten Folie eine selbstgestrickte 01:02:10.450 --> 01:02:15.170 Animation dieser... 01:02:19.550 --> 01:02:20.270 Bildschirmpräsentation fortsetzt. 01:02:20.410 --> 01:02:20.590 Genau. 01:02:20.930 --> 01:02:22.950 Wir gehen jetzt hier auf die nächste Folie. 01:02:23.270 --> 01:02:24.970 Also hier nochmal kurz eine Bemerkung, das hatte ich Ihnen schon 01:02:24.970 --> 01:02:27.950 gesagt, dass man hier dann durch Einfügen von solchen 01:02:27.950 --> 01:02:32.850 Verzögerungselementen einen solchen Pipelining-Effekt erzielen kann 01:02:32.850 --> 01:02:37.190 und damit hat man einen wesentlichen Punkt, dass man jetzt für k 01:02:37.190 --> 01:02:45.010 -Additionen nur n, also k plus n minus 1 Takte braucht und nicht k mal 01:02:45.010 --> 01:02:46.270 n Takte. 01:02:46.970 --> 01:02:50.810 Das heißt, wenn Sie 100 Additionen machen, von 4 bezahlen oder von 8 01:02:50.810 --> 01:02:56.850 bezahlen, brauchen Sie nur 107 Takte, um das auszuführen im Pipelining 01:02:56.850 --> 01:02:59.450 -Verfahren und nicht 800 Takte. 01:02:59.450 --> 01:03:03.130 Das ist ein riesiger Unterschied, führt zu der großen Beschleunigung, 01:03:03.790 --> 01:03:05.250 die wir in heutigen Rechnern haben. 01:03:05.670 --> 01:03:09.430 Sie haben in Ihren heutigen Rechnern sehr viel Fließbandverarbeitung 01:03:09.430 --> 01:03:09.690 drin. 01:03:10.150 --> 01:03:12.350 Dazu werden wir noch eine ganze Reihe von Beispielen sehen. 01:03:13.090 --> 01:03:15.750 Und das Ganze führe ich Ihnen jetzt nochmal hier etwas animiert vor 01:03:15.750 --> 01:03:16.450 auf der Folie. 01:03:17.790 --> 01:03:20.950 Hier haben wir zwei 4-Bit-Zahlen, die wir addieren wollen. 01:03:21.450 --> 01:03:24.850 In diesem Fall habe ich hier die Eingänge nummeriert und die Ausgänge 01:03:24.850 --> 01:03:29.790 nummeriert und wir wollen also jetzt Zahlen eingeben. 01:03:30.850 --> 01:03:32.930 Wir wollen also 4 Additionen machen. 01:03:33.410 --> 01:03:35.640 Eine schwarze Addition, das ist diese hier. 01:03:36.870 --> 01:03:40.710 Kleinen Augenblick, ich muss wieder auf den Stift gehen. 01:03:40.930 --> 01:03:42.450 Wir haben eine schwarze Addition. 01:03:43.270 --> 01:03:45.350 A0, B0 bis A3, B3. 01:03:45.850 --> 01:03:48.230 Eine blaue, eine rote, eine grüne Addition. 01:03:48.890 --> 01:03:52.410 Einfach optisch so unterschiedlich dargestellt, damit Sie sehen, was 01:03:52.410 --> 01:03:52.890 passiert. 01:03:52.890 --> 01:03:54.890 Und hier habe ich es jetzt noch etwas modifiziert. 01:03:55.550 --> 01:03:58.490 Hier sage ich, ich habe auch hier vorne einen Volladdierer und der 01:03:58.490 --> 01:04:01.150 Anfangsübertrag wird jeweils eingegeben von rechts. 01:04:02.310 --> 01:04:06.370 Und jetzt habe ich also die ersten beiden Bits dort drin, in dem 01:04:06.370 --> 01:04:08.390 rechtesten Addierer. 01:04:09.310 --> 01:04:10.370 In dem Fall ein Volladdierer. 01:04:10.550 --> 01:04:17.990 Es kommt das S0 raus und ich habe A1, B1 in dem zweiten Addierer drin. 01:04:18.130 --> 01:04:22.290 Dann habe ich A2, B2 in dem dritten Addierer und schließlich habe ich 01:04:22.290 --> 01:04:24.170 A3, B3 im vierten Addierer. 01:04:24.690 --> 01:04:28.810 Und jetzt sehen Sie, in diesem Fall werden gleichzeitig eine schwarze, 01:04:28.870 --> 01:04:31.670 eine blaue, eine rote und eine grüne Addition ausgeführt. 01:04:32.150 --> 01:04:34.270 Jeweils unterschiedlich weit gediehen. 01:04:35.190 --> 01:04:41.150 Und wir haben am Ende dann unsere ganzen Ausgaben produziert. 01:04:42.010 --> 01:04:47.030 Und wenn man das im Zusammenhang sieht, haben wir also durch diese Art 01:04:47.030 --> 01:04:51.490 der versetzten Eingabe und der Verzögerung zwischen den einzelnen 01:04:51.490 --> 01:04:54.330 Elementen, hier muss also jeweils ein Verzögerungsglied drin sein, 01:04:54.910 --> 01:04:56.290 davon habe ich hier abstrahiert. 01:04:57.750 --> 01:05:01.210 Dadurch habe ich die Möglichkeit, das Pipelining zu machen und einen 01:05:01.210 --> 01:05:04.090 wesentlich höheren Durchsatz zu erzeugen für die Addition. 01:05:05.350 --> 01:05:08.670 Jetzt sagen Sie, 4-Bit-Addition, wer will schon nur 4-Bit addieren? 01:05:09.210 --> 01:05:12.290 Wenn Sie 8-Bit-Zahlen addieren wollen, dann machen Sie einfach 01:05:12.290 --> 01:05:17.010 Folgendes, dass Sie das, was hier rauskommt, irgendwann dort wieder 01:05:17.010 --> 01:05:17.550 eingeben. 01:05:18.670 --> 01:05:24.370 Dann wird der Endübertrag wieder eingegeben für das niedrigstifikante 01:05:24.370 --> 01:05:24.670 Bit. 01:05:25.270 --> 01:05:28.870 Und dann könnten Sie das hier noch fortführen, könnten die nächsten 01:05:28.870 --> 01:05:29.650 Bits, also... 01:05:30.870 --> 01:05:32.450 Das wollte ich jetzt gar nicht. 01:05:33.270 --> 01:05:35.170 Ich weiß nicht, wieso der jetzt darauf gekommen ist. 01:05:35.970 --> 01:05:38.210 Das wollte ich auch nicht, überhaupt nicht. 01:05:41.370 --> 01:05:43.010 Ein nettes Bild. 01:05:44.450 --> 01:05:45.290 Ich wollte... 01:05:45.290 --> 01:05:49.170 Gehen wir mal schnell wieder zurück auf diese Darstellung. 01:05:50.650 --> 01:05:53.830 Ich wollte Ihnen nur darstellen, dass man jetzt eben dann in der Lage 01:05:53.830 --> 01:05:57.210 ist, auch beliebig lange Zahlen zu addieren. 01:05:58.110 --> 01:06:02.530 Sie müssen eben nur jeweils den Übertrag aus einer Zwischenposition 01:06:02.530 --> 01:06:07.410 wieder rechts eingeben und können dann so stückweise, jeweils 4-Bit 01:06:07.410 --> 01:06:13.030 -Zahlen addieren, können das so viermal nacheinander machen. 01:06:13.130 --> 01:06:15.690 Dann müsste halt hier die schwarze Addition anschließend wieder 01:06:15.690 --> 01:06:16.030 beginnen. 01:06:16.130 --> 01:06:19.810 Wenn das jetzt hier schwarz wäre, dann müsste ich hier die andere 01:06:19.810 --> 01:06:20.550 Farbe nehmen. 01:06:21.350 --> 01:06:24.430 Wenn ich es richtig machen will, schwarz. 01:06:24.430 --> 01:06:28.730 So, und dann male ich hier A0 und B0 bzw. 01:06:30.070 --> 01:06:31.690 A4 und B4. 01:06:32.030 --> 01:06:35.790 Könnte ich hier A5, B5 hinmalen und so weiter. 01:06:35.910 --> 01:06:40.170 Und oben drüber könnte dann entsprechend eine blaue, eine rote, eine 01:06:40.170 --> 01:06:41.450 grüne Addition folgen. 01:06:42.250 --> 01:06:43.790 Ich schalte aber wieder um auf rot. 01:06:44.850 --> 01:06:47.210 Das ist also ein getakteter Riffel-Karrierer. 01:06:47.790 --> 01:06:51.790 Eigentlich die gleiche Struktur, aber ich habe jetzt das etwas 01:06:51.790 --> 01:06:56.810 verzögert, sodass Sie auf einmal nicht mehr lineare Zeit brauchen, im 01:06:56.810 --> 01:06:59.070 Schnitt pro Addition, sondern nur noch konstante Zeit. 01:06:59.530 --> 01:07:03.170 Obwohl die einzelne Addition nach wie vor so lange dauert. 01:07:03.450 --> 01:07:04.610 Also das ist das Pipelining. 01:07:05.410 --> 01:07:08.430 Und hier ist das Bild nochmal angedeutet, was ich Ihnen schon 01:07:08.430 --> 01:07:09.290 aufgemalt hatte. 01:07:09.810 --> 01:07:11.530 Hier haben wir Pipelining-Effekt. 01:07:12.310 --> 01:07:16.610 Nach jedem kleinen Takt können wir sofort anfangen, neue Eingabe zu 01:07:16.610 --> 01:07:16.850 machen. 01:07:16.850 --> 01:07:21.050 Wir haben einen hohen Durchsatz, weil wir die Berechnung aufgeteilt 01:07:21.050 --> 01:07:22.290 haben, auf solche kleinen Schritte. 01:07:23.450 --> 01:07:29.310 Das ist Pipelining, ein wesentliches Konstruktionsprinzip für Hardware 01:07:29.310 --> 01:07:30.650 -Bauelemente heutzutage. 01:07:31.910 --> 01:07:34.730 Gut, das ist aber nicht alles, was man machen kann. 01:07:35.670 --> 01:07:37.790 Also Addition ist eine ganz einfache Funktion. 01:07:37.870 --> 01:07:39.110 Das kennen Sie ja alle, wie man addiert. 01:07:40.610 --> 01:07:43.590 Was hat addieren mit, also divide und conquer, was hat denn das damit 01:07:43.590 --> 01:07:44.070 zu tun? 01:07:45.250 --> 01:07:49.990 Sie erinnern sich, dass ich Ihnen mal gesagt habe, wenn ich eine 01:07:49.990 --> 01:07:54.910 Operation habe, die so sequentiell läuft, ja, dieses Bild habe ich 01:07:54.910 --> 01:08:00.330 Ihnen schon mal aufgebaut, und wenn eine solche Operation assoziativ 01:08:00.330 --> 01:08:04.750 ist, dann kann ich die ja überführen, wenn die assoziativ ist, das 01:08:04.750 --> 01:08:08.550 heißt, wenn die Reihenfolge der Ausführung der Operationen egal ist, 01:08:08.910 --> 01:08:10.790 dann kann ich daraus auch einen Baum machen. 01:08:16.370 --> 01:08:21.210 Dann kann ich auf einmal das, was vorher in linearer Zeit gelaufen 01:08:21.210 --> 01:08:26.130 ist, in einer Zeit machen, wenn ich nur die Anzahl, oder zumindest in 01:08:26.130 --> 01:08:31.830 einer Anzahl von Schritten machen, die logarithmisch ist in der Zeit, 01:08:31.890 --> 01:08:32.910 die ich vorher brauchte. 01:08:34.070 --> 01:08:38.210 Weil die Höhe, die Länge der Pfade in einem solchen Baum logarithmisch 01:08:38.210 --> 01:08:41.910 ist in der Anzahl der Blätter, und die Anzahl der Blätter in beiden 01:08:41.910 --> 01:08:46.350 Bäumen ist hier gleich, aber der eine Pfad hier hat die Länge linear 01:08:46.350 --> 01:08:49.890 in der Anzahl der Blätter, und der andere, in dem anderen Baum, habe 01:08:49.890 --> 01:08:54.330 ich nur eine logarithmische Pfadlänge, abhängig in der Anzahl der 01:08:54.330 --> 01:08:54.590 Blätter. 01:08:55.870 --> 01:08:58.410 Das heißt, mit die weiten Konker könnte ich ein bisschen was machen. 01:08:58.830 --> 01:09:03.030 Und Sie wissen, dass das ein typisches Prinzip ist der Informatik, uns 01:09:03.030 --> 01:09:04.370 sind Probleme häufig zu schwer. 01:09:05.510 --> 01:09:09.110 Deswegen sagen wir, das Problem ist mir zu schwer, ich mache daraus 01:09:09.110 --> 01:09:09.950 zwei Probleme. 01:09:11.830 --> 01:09:18.410 Ich schaue mir also erst mal das linke Problem an, A1, B1, das ist 01:09:18.410 --> 01:09:22.190 also jetzt hier mein A1, und das nenne ich jetzt A2, einfach 01:09:22.190 --> 01:09:24.250 aufgeteilt in zwei Operanten. 01:09:25.170 --> 01:09:28.730 Und mein B teile ich auf in einen B1 und einen B2. 01:09:30.010 --> 01:09:34.230 Und dann berechne ich einfach die beiden Summen, aus der rechten 01:09:34.230 --> 01:09:35.370 Hälfte und der linken Hälfte. 01:09:35.450 --> 01:09:37.910 Das kann ich natürlich auch rekursiv alles nochmal mit die weiten 01:09:37.910 --> 01:09:41.890 Konker machen, wenn mir das A2 plus B2 noch zu schwer ist, mache ich 01:09:41.890 --> 01:09:49.650 daraus irgendetwas A21 und A22, und B21 und B22, und habe dann das 01:09:49.650 --> 01:09:52.050 wieder aufgeteilt, dann habe ich so eine Baumstruktur. 01:09:54.350 --> 01:09:55.910 Aber erst mal auf der obersten Ebene. 01:09:57.510 --> 01:10:00.870 Wenn ich jetzt eine solche Addition mache, dann geht das für den 01:10:00.870 --> 01:10:04.390 linken Teil sehr schön, ich habe hier A1 plus B1, aber was ist 01:10:04.390 --> 01:10:07.770 eigentlich mit dem, ich habe ja hier noch einen Übertrag, wenn ich das 01:10:07.770 --> 01:10:11.630 rechts mache, da geht der Übertrag null rein, das kann ich alles 01:10:11.630 --> 01:10:13.870 ausrechnen und hier kommt irgendwann der Übertrag raus. 01:10:13.950 --> 01:10:18.610 Und ich weiß, das was hier als Übertrag rauskam aus der rechten 01:10:18.610 --> 01:10:23.650 Hälfte, das muss ich ja verwenden für die Summe auf der linken Hälfte. 01:10:25.950 --> 01:10:30.650 Und jetzt mache ich einfach folgenden Trick, ich sage, ich addiere A1 01:10:30.650 --> 01:10:36.710 und B1, da kommt eine Summe S1 raus, das ist meine Summe S1 A1 plus 01:10:36.710 --> 01:10:43.390 B1, und dann berechne ich einfach gleichzeitig, Hardware habe ich 01:10:43.390 --> 01:10:46.010 genug, S1 plus 1. 01:10:47.430 --> 01:10:52.770 Und jetzt muss ich mir überlegen, wenn ich das berechnet habe, was ist 01:10:52.770 --> 01:10:54.630 denn nun der Wert, der hier eigentlich richtig ist. 01:10:54.970 --> 01:11:02.850 Dann wähle ich einfach aus, welche der beiden Summen die richtige ist, 01:11:02.850 --> 01:11:07.530 und die Auswahl erfolgt über das berechnete Übertragsbit aus der 01:11:07.530 --> 01:11:08.650 rechten Hälfte. 01:11:09.570 --> 01:11:14.570 Das wählt mir aus, aus einem Multiplexer, also MUX steht für 01:11:14.570 --> 01:11:22.730 Multiplexer, und ein Multiplexer wählt aufgrund von Steuereingaben 01:11:22.730 --> 01:11:27.830 aus, welche der beiden Eingänge, links oder rechts, nach unten 01:11:27.830 --> 01:11:29.110 weitergegeben werden soll. 01:11:29.110 --> 01:11:34.410 Wenn der Übertrag also 1 ist, dann nehme ich den rechten Eingang, wenn 01:11:34.410 --> 01:11:37.150 der Übertrag 0 ist, nehme ich den linken Eingang. 01:11:37.250 --> 01:11:40.750 Das, was hier als ein Pfeil zu sehen ist, sind natürlich tatsächlich 01:11:40.750 --> 01:11:46.370 entsprechend dicke Pfeile für jede Bitposition in meinem A1 und B1, 01:11:46.450 --> 01:11:49.890 das sind jetzt Teilwörter, wenn ich also 64-Bit-Summe machen muss, 01:11:50.430 --> 01:11:56.170 oder 1024-Bit-Summe, da habe ich einmal einen 512-Bit-Block auf der 01:11:56.170 --> 01:11:59.690 rechten Hälfte, und einen 512-Bit-Block auf der linken Hälfte. 01:12:00.410 --> 01:12:03.390 Und dieses, was hier als ein MUX steht, ist also etwas, was sich auf 01:12:03.390 --> 01:12:05.010 jede einzelne Bitposition bezieht. 01:12:05.910 --> 01:12:08.210 Ich habe für jede Bitposition diese Auswahl zu treffen. 01:12:09.230 --> 01:12:10.790 Etwas vereinfacht dargestellt. 01:12:12.570 --> 01:12:15.450 Und wie sieht das jetzt aus mit der Zeit, die ich dafür brauche? 01:12:17.070 --> 01:12:22.690 Ich mache diese beiden Additionen, links und rechts, die laufen in 01:12:22.690 --> 01:12:23.410 linearer Zeit. 01:12:24.970 --> 01:12:31.390 Oder gar nicht, die laufen irgendwie in T von N-Halbe. 01:12:34.770 --> 01:12:41.370 Und dann brauche ich, ja, ich muss mir angucken, dieser Übertrag hier, 01:12:42.350 --> 01:12:47.890 der muss jetzt noch dazu kommen, plus 1, ich muss das noch auswählen, 01:12:48.030 --> 01:12:53.450 erst dann habe ich meine beiden, also jetzt habe ich die richtige 01:12:53.450 --> 01:12:54.450 Summe zusammengebaut. 01:12:55.870 --> 01:12:57.590 Und das ist mein T von N. 01:12:59.450 --> 01:13:01.730 T von N ist T von N-Halbe plus 1. 01:13:03.790 --> 01:13:07.050 Und wenn ich jetzt mir angucke, wie ist das T von N-Halbe, also die 01:13:07.050 --> 01:13:11.330 Zeit, um das hier auszuführen, dann mache ich das genauso. 01:13:12.610 --> 01:13:14.630 Das ist T von N-Viertel plus 1. 01:13:16.550 --> 01:13:20.970 Wobei natürlich, hier muss ich zwei Summen machen auf der linken 01:13:20.970 --> 01:13:22.070 Seite, da mache ich nur eine Summe. 01:13:22.830 --> 01:13:25.110 Ist aber nicht so relevant, das ist einfach nur Hardware. 01:13:25.350 --> 01:13:26.370 Ich gucke mir nur die Zeit an. 01:13:27.910 --> 01:13:30.610 Und wenn ich das immer weiter auftrüsele, komme ich am Ende auf zwei 01:13:30.610 --> 01:13:31.930 Bits, die ich addieren muss. 01:13:33.410 --> 01:13:35.070 Links und zwei Bits rechts. 01:13:35.770 --> 01:13:37.290 Und entsprechend zusammenbauen. 01:13:38.250 --> 01:13:43.550 Und insgesamt, wenn Sie sich das hier angucken, kommt da raus, T von N 01:13:43.550 --> 01:13:47.550 ist abhängig von Log N. 01:13:49.110 --> 01:13:52.430 Das kommt als Summe raus, oder als Ergebnis raus, aus dieser 01:13:52.430 --> 01:13:53.550 Gleichung. 01:13:54.730 --> 01:13:57.150 Das ist etwas, was man sich leicht überlegen kann, aus solchen 01:13:57.150 --> 01:14:02.550 Gleichungen kommt natürlich, dass T von 1, bzw. 01:14:02.870 --> 01:14:07.130 T von 2 in dem Fall, ist 2. 01:14:08.890 --> 01:14:10.570 Und dann sind Sie fertig. 01:14:13.710 --> 01:14:15.270 Dann haben Sie hier Log N insgesamt. 01:14:16.070 --> 01:14:20.850 Und das heißt, wir haben zwar einen hohen Flächenaufwand, aber können 01:14:20.850 --> 01:14:23.670 in logarithmischer Zeit eine Addition durchführen. 01:14:24.210 --> 01:14:28.950 Das heißt, wir brauchen für einen 64-Bit-Addierer nur einen Schritt 01:14:28.950 --> 01:14:31.370 mehr als für einen 32-Bit-Addierer. 01:14:32.210 --> 01:14:36.390 Oder für einen 1024-Bit-Addierer nur einen Schritt mehr als für einen 01:14:36.390 --> 01:14:37.650 512 -Bit-Addierer. 01:14:39.050 --> 01:14:40.730 Eine deutliche Verbesserung. 01:14:41.750 --> 01:14:43.950 Nicht mehr Linearzeit, sondern logarithmische Zeit. 01:14:44.990 --> 01:14:47.110 Es gibt noch eine Möglichkeit, das zu machen. 01:14:48.030 --> 01:14:50.730 Solche Carry-Select-Addierer werden in der Realität tatsächlich auch 01:14:50.730 --> 01:14:51.070 gebaut. 01:14:51.750 --> 01:14:54.210 Werden eingebaut in entsprechende Hardware. 01:14:54.910 --> 01:14:56.770 Der, den ich Ihnen jetzt zeige, wird auch eingebaut. 01:14:56.830 --> 01:14:58.170 Der hat noch wieder eine andere Idee. 01:14:58.850 --> 01:15:01.450 Nur, dass Sie sehen, Addition ist ein ganz einfaches Problem. 01:15:02.690 --> 01:15:04.850 Das ist doch ein kleiner Baustein, warum muss man sich damit 01:15:04.850 --> 01:15:05.450 beschäftigen? 01:15:05.490 --> 01:15:07.610 Aber Sie sehen, man kann sich ja auch damit beschäftigen, wie man 01:15:07.610 --> 01:15:08.690 sowas effizient macht. 01:15:09.420 --> 01:15:16.530 Da kommt es darauf an, ob Ihr Rechner nachher mit 250 MHz arbeitet 01:15:16.530 --> 01:15:18.250 oder mit 3 GHz. 01:15:19.230 --> 01:15:20.330 Das ist ein kleiner Unterschied. 01:15:22.110 --> 01:15:25.170 Also, Carry-Looker-Addierer, was macht der? 01:15:26.250 --> 01:15:33.670 Ich schaue mir an, eine Zahl, zum Beispiel so etwas. 01:15:36.010 --> 01:15:49.190 Und hier unten drunter schreibe ich 0, 1, 0, 1. 01:15:49.370 --> 01:15:50.570 Okay, das reicht schon. 01:15:51.850 --> 01:15:53.210 Was passiert hier? 01:15:54.950 --> 01:16:02.570 Wenn ich das addiere, dann schaue ich mir mal an, hier addiere ich die 01:16:02.570 --> 01:16:07.890 beiden, 1 und 0, 1 und 1, 0 und 0. 01:16:10.110 --> 01:16:11.870 Das sind eigentlich die drei Situationen. 01:16:11.950 --> 01:16:15.390 Natürlich könnte ich auch noch hier 0 und 1 hinschreiben, dann hätten 01:16:15.390 --> 01:16:16.810 wir alle vier Situationen. 01:16:17.610 --> 01:16:23.970 Entweder sind beide 0, beide 1, oder einer von den beiden Bits ist 1. 01:16:25.750 --> 01:16:31.730 Wenn ich jetzt ein Bit-Paar habe, 1, 1, dann weiß ich, es wird auf 01:16:31.730 --> 01:16:34.650 jeden Fall hier ein Übertrag 1 erzeugt. 01:16:38.650 --> 01:16:47.950 Wenn ich hier auch 1, 1 stehen hätte, wird hier auch eine 1 erzeugt. 01:16:50.490 --> 01:16:55.590 Und ich weiß auch, wenn ich 0, 1 stehen habe, also 1, 0 oder 0, 1, 01:16:55.590 --> 01:17:00.810 dann wird ein Übertrag, der hier reinkommt, garantiert weitergegeben 01:17:00.810 --> 01:17:01.710 bis zu dieser Position. 01:17:05.260 --> 01:17:10.680 Und wenn ich hier 0, 0 stehen habe, dann wird der Übertrag, der hier 01:17:10.680 --> 01:17:13.680 reinkommt, garantiert nicht weitergegeben, dann wird hier garantiert 01:17:13.680 --> 01:17:14.900 eine 0 stehen als Übertrag. 01:17:16.440 --> 01:17:22.640 Das heißt, ich brauche gar nicht, mir das ganze Wort anzugucken, 01:17:23.320 --> 01:17:28.900 sondern es reicht zu schauen, wird eigentlich aus einer Bit-Position 01:17:28.900 --> 01:17:34.860 ein Übertrag erzeugt oder weitergegeben, oder wird er absorbiert. 01:17:36.740 --> 01:17:42.420 Wenn wir zurückgehen hier auf unser Beispiel mit der Addition von zwei 01:17:42.420 --> 01:17:46.140 Zahlen, wir wollen das jetzt aufteilen in eine linke Hälfte und eine 01:17:46.140 --> 01:17:46.920 rechte Hälfte. 01:17:47.720 --> 01:17:58.380 Wenn hier 0, 0 steht, dann weiß ich, es wird garantiert kein Übertrag 01:17:58.380 --> 01:17:59.160 hier rauskommen. 01:17:59.840 --> 01:18:04.220 Ich brauche gar nicht abzuwarten, bis die Addition auf der rechten 01:18:04.220 --> 01:18:07.860 Hälfte gelaufen ist und ich kann sofort hier das richtige Summenbit 01:18:07.860 --> 01:18:08.400 hinschreiben. 01:18:12.080 --> 01:18:19.360 Wenn hier natürlich 0, 1 steht, dann könnte was durchgeschoben werden. 01:18:20.040 --> 01:18:24.440 Und wenn dort 1, 1 steht, dann weiß ich, es wird hier garantiert eine 01:18:24.440 --> 01:18:25.480 1 als Übertrag erzeugt. 01:18:28.660 --> 01:18:34.720 Und wenn ich mir also jetzt eine solche Addition anschaue und ich 01:18:34.720 --> 01:18:39.880 nehme hier irgendeinen Bereich raus, dann brauche ich nur zu wissen, 01:18:41.520 --> 01:18:45.420 wird dieser Teilbereich, wenn ich die beiden Zahlen addiere, die dort 01:18:45.420 --> 01:18:53.040 stehen, wird der einen Übertrag erzeugen oder wird er einen Übertrag 01:18:53.040 --> 01:18:53.940 weiterleiten. 01:18:56.640 --> 01:19:02.620 Und wenn ich hier einen Bereich habe, schaue ich mir das Gleiche an 01:19:02.620 --> 01:19:07.260 für diese hier und dafür genauso. 01:19:09.900 --> 01:19:13.620 Dann machen wir das Strich und hier machen wir mal G-Strich, 2-Strich 01:19:13.620 --> 01:19:14.660 und P-2-Strich. 01:19:15.680 --> 01:19:20.780 Ich kann mir also für irgendeinen Teilbereich meiner Bitfolgen, die 01:19:20.780 --> 01:19:29.320 hier zu addieren sind, überlegen, wird dieser Block einen Übertrag 01:19:29.320 --> 01:19:32.040 erzeugen oder wird er einen weiterleiten. 01:19:32.080 --> 01:19:35.540 Und wenn der hier einen weiterleitet, dann weiß ich, wenn der hier 01:19:35.540 --> 01:19:39.420 einen erzeugt, wird dann da vorne auch ein, wenn ihr so weißt, hier 01:19:39.420 --> 01:19:45.120 das G-2-Strich für diesen Block ist 1, wenn das 1 ist und hier steht 01:19:45.120 --> 01:19:51.100 auch eine 1, dann weiß ich, es wird dann garantiert hier vorne eine 1 01:19:51.100 --> 01:19:51.280 stehen. 01:19:51.280 --> 01:19:54.880 Dann weiß ich, dann ist das G-Strich, wenn ich das Beides hier jetzt 01:19:54.880 --> 01:20:00.560 zusammenfügen will zu einem Wert für das Beides zusammen, dann würde 01:20:00.560 --> 01:20:06.520 ich hier ein G-3-Strich erzeugen und ein P-3-Strich. 01:20:08.340 --> 01:20:13.400 Und wenn jetzt hier zum Beispiel steht eine 1, da eine 1 und selbst 01:20:13.400 --> 01:20:19.180 wenn hier eine 0 stand und hier meinetwegen auch eine 0, was steht 01:20:19.180 --> 01:20:21.820 denn dann an dieser Stelle für den ganzen Block, den ich jetzt so 01:20:21.820 --> 01:20:22.520 zusammenbaue? 01:20:23.800 --> 01:20:30.320 Naja, da stand eine 0, das P-Strich war eine 1, G-2-Strich war eine 1, 01:20:30.420 --> 01:20:37.720 das heißt, dieser Block hier, der hat eine 1 erzeugt, der wird 01:20:37.720 --> 01:20:42.320 weitergeleitet, das heißt, hier wird garantiert eine 1 entstehen. 01:20:47.660 --> 01:20:53.780 Und es wird also, da eine 1 entsteht, wird hier, also das P-Strich, P 01:20:53.780 --> 01:21:01.340 -2 -Strich ist 0, P-Strich ist 1 in dem Fall, also es würde etwas 01:21:01.340 --> 01:21:06.260 weiter reichen, es würde aber, das P-2-Strich gibt es nicht weiter, 01:21:06.360 --> 01:21:08.640 das heißt, es würde hier vorne eine 0 stehen. 01:21:08.640 --> 01:21:14.020 Es wird nicht eine 1, die hier reinkommt, durchgereicht, es wird aber 01:21:14.020 --> 01:21:16.980 eine 1 erzeugt aus diesem Block. 01:21:17.720 --> 01:21:24.880 Und jetzt sehe ich Folgendes, ich kann zwei solche Informationen, ich 01:21:24.880 --> 01:21:28.560 habe das jetzt so dargestellt, ich kann es genauso gut darstellen für 01:21:28.560 --> 01:21:33.120 die linken beiden, wenn ich das beides verknüpfen will, das ist das, 01:21:33.200 --> 01:21:34.460 was hier dargestellt ist. 01:21:34.460 --> 01:21:45.760 Ich schaue mir an, erzeugt der linke Block eine 1 als Übertrag, dann 01:21:45.760 --> 01:21:50.500 erzeugt auch der gesamte Block, der kombinierte Block, also dieses 01:21:50.500 --> 01:21:52.920 beides zusammen, erzeugt dann auch eine 1. 01:21:53.600 --> 01:21:58.200 Der andere Fall, dass da eine 1 rauskommt, ist, dass das P-1 ist und 01:21:58.200 --> 01:21:59.780 das G-Strich eine 1 ist. 01:21:59.780 --> 01:22:04.500 Dann wird nämlich der Übertrag aus dem rechten Bereich weitergeleitet 01:22:04.500 --> 01:22:05.080 nach links. 01:22:07.060 --> 01:22:12.520 Und hier bei der Frage, gibt dieser ganze Block jetzt eine 1 weiter, 01:22:13.020 --> 01:22:16.540 muss ich schauen, ob die 1 sowohl durch den rechten Block als auch 01:22:16.540 --> 01:22:19.900 durch den linken Block durchgereicht wird, das heißt, ob P und P 01:22:19.900 --> 01:22:20.940 -Strich beide 1 sind. 01:22:22.400 --> 01:22:28.840 Und das Interessante ist, dass diese Operation Kringel auf solchen 01:22:28.840 --> 01:22:34.780 Paaren G und P, Generate und Propagate-Signalen, assoziativ ist. 01:22:36.000 --> 01:22:39.160 Das heißt, diese Operation kann ich in beliebigen Reihenfolgen 01:22:39.160 --> 01:22:39.720 anwenden. 01:22:40.460 --> 01:22:44.260 Ich will natürlich irgendwann wissen, was ist eigentlich das, was für 01:22:44.260 --> 01:22:49.420 das Gesamte gilt, aber auch für jede einzelne Position möchte ich es 01:22:49.420 --> 01:22:49.660 wissen. 01:22:50.160 --> 01:22:52.640 Und ich kann daraus die Summenbits erzeugen. 01:22:53.620 --> 01:22:56.880 Und um die richtigen Summenbits erzeugen zu können, muss ich wissen, 01:22:57.000 --> 01:22:59.960 kommt da irgendein Übertrag von links oder rechts, äh, Quatsch, von 01:22:59.960 --> 01:23:01.840 rechts, von links kann keiner kommen. 01:23:04.020 --> 01:23:06.940 Und wenn ich nur den Ripple-Carrier-Addierer anschaue, ist das ein 01:23:06.940 --> 01:23:08.520 inhärent sequentieller Prozess. 01:23:09.680 --> 01:23:11.000 Der ist nicht assoziativ. 01:23:11.420 --> 01:23:14.100 Da muss ich rechts anfangen und durchwarten, bis ich ganz 01:23:14.100 --> 01:23:14.940 durchgelaufen bin. 01:23:14.940 --> 01:23:18.520 Diese Kringel-Operation kann ich assoziativ machen und kann darüber 01:23:18.520 --> 01:23:19.580 einen Baum aufbauen. 01:23:20.440 --> 01:23:26.140 Und damit habe ich die Möglichkeit, in logarithmischer Zeit, alle 01:23:26.140 --> 01:23:33.220 diese G- und P-Signale zu erzeugen für meine Zahlen, die ich addieren 01:23:33.220 --> 01:23:33.620 möchte. 01:23:34.360 --> 01:23:37.380 Und damit kann ich alle Summenbits erzeugen in logarithmischer Zeit. 01:23:37.940 --> 01:23:40.820 Und ich habe damit einen solchen Carry-Look-Ahead-Addierer. 01:23:41.760 --> 01:23:46.580 Es kommt noch ganz schnell die dritte Art, einen Addierer zu bauen, 01:23:46.940 --> 01:23:49.020 einen sogenannten Carry-Safe-Addierer. 01:23:49.060 --> 01:23:49.840 Was mache ich denn da? 01:23:51.160 --> 01:23:53.480 Beim Carry-Safe-Addierer mache ich folgendes. 01:23:57.560 --> 01:24:00.640 Da würde ich so arbeiten, dass ich einfach sage, ich schreibe hier 01:24:00.640 --> 01:24:04.800 hin, naja, das Summenbit oder das Übertragsbit in dem Fall ist 0, das 01:24:04.800 --> 01:24:05.680 Summenbit ist 1. 01:24:05.780 --> 01:24:10.220 Das Übertragsbit ist 0, das Summenbit ist 1, das Übertragsbit ist 1, 01:24:10.360 --> 01:24:11.480 das Summenbit ist 0. 01:24:11.480 --> 01:24:17.340 Hier ist das Übertragsbit 0 und das Summenbit ist auch 0. 01:24:18.360 --> 01:24:23.800 Da habe ich den Carry und das Summenbit, den Übertrag und das 01:24:23.800 --> 01:24:27.900 Übertragssignal und das Summensignal einfach nur hingeschrieben unten 01:24:27.900 --> 01:24:29.420 drunter, ohne es weiterzureichen. 01:24:30.740 --> 01:24:34.940 Ich habe die Information aber aufbewahrt und ich mache damit eine 01:24:34.940 --> 01:24:37.880 sogenannte Carry-Safe-Darstellung, die doppelt so viel Speicherplatz 01:24:37.880 --> 01:24:40.940 braucht, wie die normale Darstellung einer Zahl. 01:24:41.760 --> 01:24:45.660 Ich konnte aber diese vier Operationen hier unabhängig voneinander 01:24:45.660 --> 01:24:46.040 machen. 01:24:47.240 --> 01:24:51.720 Das heißt, jetzt kann ich in konstanter Zeit eine Addition ausführen, 01:24:53.260 --> 01:24:59.320 aber ich mache dann Operationen aus solchen Carry-Safe-Darstellungen 01:24:59.320 --> 01:24:59.900 von Zahlen. 01:25:00.960 --> 01:25:05.540 Auch das wird ausgenutzt, insbesondere wenn ich zum Beispiel zwei 01:25:05.540 --> 01:25:07.300 Zahlen multiplizieren möchte. 01:25:07.940 --> 01:25:11.260 Wenn Sie zwei Zahlen multiplizieren wollen, dann machen Sie das häufig 01:25:11.260 --> 01:25:18.220 so, dass Sie für jede Bitposition hier im Prinzip einen Wert erzeugen 01:25:18.220 --> 01:25:19.220 und die dann alle addieren. 01:25:19.880 --> 01:25:24.300 Dann haben Sie so viele Additionen und diese vielen Additionen machen 01:25:24.300 --> 01:25:27.120 Sie über eine interne Carry-Safe-Darstellung, das geht jeweils in 01:25:27.120 --> 01:25:27.980 konstanter Zeit. 01:25:28.760 --> 01:25:33.960 Dann haben Sie insgesamt lineare Zeit für eine Ausführung von einer 01:25:33.960 --> 01:25:39.160 Multiplikation, die mit einem naiven Ansatz quadratische Zeit brauchen 01:25:39.160 --> 01:25:39.480 würde. 01:25:41.020 --> 01:25:45.320 Also offensichtlich lohnt es sich anzuschauen, wie man so eine 01:25:45.320 --> 01:25:48.500 einfache Operation wie die Addition ausführen kann. 01:25:49.200 --> 01:25:53.260 Und Sie sehen, man kann das durch geschickte andere Darstellung des 01:25:53.260 --> 01:25:57.600 Problems, also wer kommt darauf, daraus eine Darstellung zu machen 01:25:57.600 --> 01:25:59.400 über Generate- und Propagate-Signale. 01:26:01.100 --> 01:26:03.760 Aber das ist ein Weg, eine andere Beschreibung der Operation. 01:26:04.740 --> 01:26:10.400 Und jetzt habe ich auf einmal eine assoziative Operation auf diesen 01:26:10.400 --> 01:26:13.660 Paaren von Bits und damit kann ich es schnell machen. 01:26:15.220 --> 01:26:16.500 Damit kann ich es parallelisieren. 01:26:17.620 --> 01:26:20.580 Also sobald Sie assoziative Operationen haben, können Sie 01:26:20.580 --> 01:26:25.260 parallelisieren, können Zeitgewinn erzielen und damit effizientere 01:26:25.260 --> 01:26:26.360 Operationen ausführen. 01:26:27.020 --> 01:26:31.200 Zeitlich effizienter, was den Flächenaufwand angeht, natürlich 01:26:31.200 --> 01:26:32.240 größerer Aufwand. 01:26:33.320 --> 01:26:35.860 Sie haben mehrere Bausteine, die nebeneinander arbeiten müssen. 01:26:37.840 --> 01:26:40.980 Und nächstes Mal am Mittwoch früh schauen wir uns dann das nächste 01:26:40.980 --> 01:26:42.560 Kapitel an, nämlich die Schaltwerke. 01:26:43.220 --> 01:26:44.300 Vielen Dank für die Aufmerksamkeit.