WEBVTT

00:00.160 --> 00:01.880
So, schönen Tag.

00:01.980 --> 00:06.940
Ich begrüße Sie am letzten Tag vor Weihnachten zu der letzten

00:06.940 --> 00:11.240
Vorlesung über Grundlagen der Informatik II in diesem Jahr.

00:12.280 --> 00:16.900
Wir hatten uns letztes Mal beschäftigt mit Codierung und

00:16.900 --> 00:17.940
Zahlendarstellungen.

00:18.840 --> 00:21.400
Ich würde vorschlagen, dass Sie weiter nach vorne kommen, dann haben

00:21.400 --> 00:27.180
Sie etwas mehr Nähe zu den Dozenten und ich zu meinen Hörern.

00:27.180 --> 00:32.160
Wie zu erwarten, ist der Hörsaal nicht so sehr stark gefüllt.

00:32.440 --> 00:38.860
Es sind noch ein paar Plätze frei, aber ich freue mich, dass wir hier

00:38.860 --> 00:42.680
nicht alleine sitzen oder stehen, sondern dass ich die Vorlesung

00:42.680 --> 00:44.360
tatsächlich vor Hörern halten kann.

00:45.760 --> 00:48.440
Es werden natürlich viele Hörer noch da sein, die sich dann die

00:48.440 --> 00:51.060
Aufzeichnung anschauen oder anhören.

00:51.060 --> 00:56.380
Und Sie werden sehen, was wir heute alles hier in der Vorlesung zu

00:56.380 --> 00:57.000
Gesicht bekommen.

00:57.560 --> 01:01.540
Gut, Codierung und Zahlendarstellungen, herzlich willkommen.

01:03.320 --> 01:05.280
Und das war das Thema beim letzten Mal.

01:06.120 --> 01:09.560
Es sind also doch noch einige weitere Hörer gekommen, das freut mich

01:09.560 --> 01:09.800
sehr.

01:10.180 --> 01:13.740
Dann hatten wir uns hier beschäftigt mit verschiedensten Themen bei

01:13.740 --> 01:15.260
Codierung und Zahlendarstellungen.

01:15.260 --> 01:24.920
Ich hatte Ihnen einiges erzählt, wie man etwas darstellen kann.

01:25.060 --> 01:28.450
Wir haben ein bisschen angefangen, uns mit Codes zu beschäftigen.

01:29.020 --> 01:34.860
Wir haben erstmal die Zählcodierung angeschaut, dann die Morse

01:34.860 --> 01:38.720
-Codierung und hatten bei der Morse-Codierung, bei der man ja wie an

01:38.720 --> 01:45.480
diesem Baum hier zu sehen, eine Codierung hat, bei der viele Wörter

01:45.480 --> 01:48.180
bzw.

01:48.460 --> 01:53.420
bei denen viele Zeichen auf Wörter abgebildet werden, die auch

01:53.420 --> 01:57.180
hintereinander geschrieben, keine eindeutige Dekodierung zu lassen,

01:57.300 --> 02:00.420
wie zum Beispiel hier diese Folge von diesen Punkten, bei der man

02:00.420 --> 02:06.080
nicht weiß, sind das jetzt viele Es oder ist das eine Fünf gefolgt von

02:06.080 --> 02:07.340
ein paar Es oder ähnliche Dinge.

02:07.500 --> 02:09.500
Also das deutet schon auf Probleme hin.

02:09.500 --> 02:12.560
Da hatte ich Sie am Ende der letzten Vorlesung darauf hingewiesen.

02:12.700 --> 02:14.840
Wir hatten zunächst mal dann noch Klassen von Codierungen uns

02:14.840 --> 02:18.160
angeschaut, hatten definiert, was eine Chiffre ist, also eine einfache

02:18.160 --> 02:23.280
Substitution von Zeichen, eine Block-Codierung, bei der man auf eine

02:23.280 --> 02:27.000
Folge von Zeichen fester Länge abbildet und spezielle Codierungen

02:27.000 --> 02:30.560
waren dann die in die Menge der Zahlen 0 und 1, die wir dann auch

02:30.560 --> 02:35.440
Binär -Codierung nennen oder wenn es Blöcke fester Länge sind, eine N

02:35.440 --> 02:36.120
-Bit -Codierung.

02:36.120 --> 02:44.360
Das war im Prinzip das Problem mit der Umkehrung, das wir hier an

02:44.360 --> 02:45.440
diesen Beispielen gesehen haben.

02:45.500 --> 02:48.600
Wir können die Zähl-Codierung problemlos dekodieren, wenn wir sie auf

02:48.600 --> 02:49.340
ein Wort anwenden.

02:50.260 --> 02:52.620
Bei der Morse-Codierung geht das so zunächst mal nicht.

02:53.160 --> 02:59.200
Und ich hatte Ihnen dann gezeigt, dass man bei Codes die sogenannte

02:59.200 --> 03:03.200
Fano -Bedingung erfüllen, bei der also kein Codewort Anfangsstück

03:03.200 --> 03:07.380
eines anderen Codeworts ist, in der Lage ist, eindeutig zu dekodieren.

03:09.100 --> 03:12.660
Ein Beispiel hier nochmal dieser Morse-Codierung, hatten wir sie

03:12.660 --> 03:17.060
einfach erweitert, dadurch, dass wir an jedes Codewort der Morse

03:17.060 --> 03:19.260
-Codierung ein Doppelkreuz angefügt haben.

03:19.720 --> 03:24.540
Und dadurch konnte man dann sicherstellen, dass klar ist, was ein

03:24.540 --> 03:30.260
Codewort ist und die sind halt nicht mehr zu verwechseln.

03:30.260 --> 03:34.780
Das heißt, wenn man sich das hier anschaut, zunächst mal ist es klar,

03:35.120 --> 03:41.700
dass wenn C-Stern injektiv ist, wenn die Fortsetzung einer Abbildung

03:41.700 --> 03:48.400
auf Wörter injektiv ist, also zwei Wörter auch unterschiedliche Bilder

03:48.400 --> 03:52.420
haben, dann ist natürlich C selber auch injektiv, das ist klar.

03:52.980 --> 03:56.340
Andersrum ist es so, dass eben aus einem injektiven C nicht

03:56.340 --> 03:59.640
notwendigerweise folgt, dass die Fortsetzung auf Wörter injektiv ist,

03:59.740 --> 04:03.880
aber wenn diese Funktion die Phano-Bedingung erfüllt, jetzt muss ich

04:03.880 --> 04:08.380
hier wieder richtig auf die Projektion gehen, das ist ja eine neue

04:08.380 --> 04:15.980
Folie, wenn wir also eine injektive Funktion haben, die auch noch die

04:15.980 --> 04:20.540
Phano -Bedingung erfüllt, dann ist die Fortsetzung der Funktion auf

04:20.540 --> 04:21.440
Wörter injektiv.

04:21.500 --> 04:22.860
Das kann man sich ganz einfach überlegen.

04:22.860 --> 04:29.080
Wenn ich mir also irgendein Wort anschaue, das jetzt irgendwie ein C

04:29.080 --> 04:36.100
-Stern von W ist, dann brauche ich ja nur von Anfang an zu gucken, ich

04:36.100 --> 04:39.540
weiß ja, das erste Zeichen ist ja auf irgendein Codewort abgebildet

04:39.540 --> 04:39.940
worden.

04:40.340 --> 04:43.020
Das heißt, ich brauche nur hier zu gucken, bis ich irgendein Wort

04:43.020 --> 04:48.000
gefunden habe, also ein Codewort, das wäre dann zum Beispiel irgendein

04:48.000 --> 04:52.900
C von irgendein Zeichen A und ich weiß, dieses hier ist eine

04:52.900 --> 04:57.800
eindeutige Entscheidung, dass dieses Anfangsstück ein Codewort sein

04:57.800 --> 05:04.540
muss, das zu dem Zeichen A gehört, weil ja kein anderes Codewort den

05:04.540 --> 05:05.480
gleichen Anfang hat.

05:05.920 --> 05:08.280
Und danach kann ich entsprechend weitermachen, kann dann hier das

05:08.280 --> 05:11.240
nächste Zeichen, das nächste Codewort finden, das nächste Codewort

05:11.240 --> 05:15.240
finden, weil es eben nicht passieren kann, dass es irgendein Codewort

05:15.240 --> 05:21.000
gibt, das zwar mit einem anderen Codewort anfängt, aber dann auch

05:21.000 --> 05:21.580
weitergeht.

05:22.260 --> 05:24.320
Also das ist eindeutig voneinander getrennt.

05:24.680 --> 05:27.420
Es gibt kein Codewort, das eventuell hier noch weiter rüberlaufen

05:27.420 --> 05:27.800
würde.

05:28.200 --> 05:31.000
Das würde nicht die Fano-Bedingung erfüllen.

05:31.080 --> 05:34.140
Das ist also ein ziemlich einfach zu beweisender Satz oder eine

05:34.140 --> 05:40.600
Eigenschaft und damit wissen wir, was ein dekodierbarer Code ist, auch

05:40.600 --> 05:41.340
in der Fortsetzung.

05:42.080 --> 05:45.260
Und natürlich müssen wir solche Codes dekodieren können.

05:45.820 --> 05:48.680
Ein anderer Punkt bei der Darstellung von Zeichen in Rechnern ist,

05:48.800 --> 05:53.120
dass wir im Rechner immer mit irgendwelchen Fehlern rechnen müssen.

05:53.300 --> 06:00.260
Es kann sein, dass wir zum Beispiel bei der Übertragung von

06:00.260 --> 06:04.860
irgendeinem Rechner X auf einen Rechner Y hier eine Nachricht

06:04.860 --> 06:08.760
losschicken, die kommt hier irgendwann an, dann kann es sein, dass

06:08.760 --> 06:11.060
dort nicht mehr genau dieselben Zeichen vorhanden sind, dass

06:11.060 --> 06:12.320
irgendwelche Bits gekippt sind.

06:12.680 --> 06:16.580
Das Gleiche kann passieren, wenn Sie irgendetwas in einen Speicher

06:16.580 --> 06:19.920
hineinschreiben und anschließend aus diesem Speicher das Wort wieder

06:19.920 --> 06:20.400
rausholen.

06:20.480 --> 06:23.700
Kann es sein, dass aus irgendeinem Grund dort ein Bit gekippt ist,

06:23.780 --> 06:27.960
also von 0 auf 1 oder von 1 auf 0 oder auch mehrere 1 oder mehrere 0.

06:28.040 --> 06:31.660
Das sind typische Fehler, die auftreten, einfach weil es sich hier um

06:31.660 --> 06:33.360
physikalische Prozesse handelt.

06:33.360 --> 06:37.740
Und das, was wir gerne haben möchten, ist, dass wir in der Lage sind,

06:37.840 --> 06:39.960
die Fehler sinnvoll zu behandeln.

06:40.040 --> 06:43.440
Sinnvoll behandeln heißt, wir wollen zunächst mal überhaupt erkennen

06:43.440 --> 06:45.400
können, dass ein Fehler aufgetreten ist.

06:45.940 --> 06:49.380
Das heißt, wir müssen Eigenschaften der Codewörter kennen, um zu

06:49.380 --> 06:52.580
erkennen, dass irgendeine Folge kein Codewort sein kann.

06:53.180 --> 06:56.400
Und das Beste ist natürlich, wenn wir in der Lage sind, diese Fehler

06:56.400 --> 06:57.360
auch zu korrigieren.

06:57.940 --> 07:01.120
Wenn wir feststellen können, das ist ein Fehler, wir wissen, das war

07:01.120 --> 07:04.360
mal ein gültiges Codewort und dann wollen wir zurückschließen auf das

07:04.360 --> 07:08.240
Ursprungs -Codewort, in dem dieser Fehler aufgetreten ist.

07:08.840 --> 07:13.020
Wir werden uns jetzt im Wesentlichen auf Bit-Codierungen, also binäre

07:13.020 --> 07:17.560
Codierungen, beschränken, und zwar Block-Codierungen.

07:18.620 --> 07:23.040
Und jetzt gucken wir uns zunächst mal an, wie können wir überhaupt

07:23.040 --> 07:26.240
feststellen, dass Unterschiede auftreten zwischen zwei Wörtern.

07:26.240 --> 07:34.580
Also wir haben hier irgendwie zwei Wörter x und y, beides binäre

07:34.580 --> 07:35.740
Folgen gleicher Länge.

07:36.600 --> 07:41.680
Dann sagen wir, dass die Distanz oder der Hemmingabstand zwischen

07:41.680 --> 07:48.420
diesen Wörtern gleich der Anzahl der Positionen ist, an denen sich x

07:48.420 --> 07:49.900
und y unterscheiden.

07:49.900 --> 07:58.060
Also, das ist die Summe aller h von x, y, i und diese x, y, i sind

07:58.060 --> 08:01.860
halt Nullen und Einzelnen, sind also binäre Variable.

08:02.280 --> 08:07.100
Und das heißt, wenn die gleich sind, dann haben wir hier 0, wenn die

08:07.100 --> 08:08.120
ungleich sind, haben wir 1.

08:08.320 --> 08:11.860
Kann man genauso gut nicht nur auf binäre Variable beziehen, auch auf

08:11.860 --> 08:12.780
beliebige Zeichen.

08:12.920 --> 08:16.880
Einfach wenn zwei Zeichen folgen, wenn ich von denen den

08:16.880 --> 08:20.160
Hemmingabstand feststellen möchte, dann ist das die Anzahl der

08:20.160 --> 08:23.840
Stellen, an denen diese beiden Zeichenfolgen sich unterscheiden.

08:23.920 --> 08:29.240
Also eine sehr einfache Distanz, ein einfaches Distanzmaß.

08:29.740 --> 08:34.260
Und das wollen wir jetzt ausnutzen, um zu erkennen, ob Wörter einen

08:34.260 --> 08:37.580
Fehler haben, beziehungsweise feststellen, wann wir sie korrigieren

08:37.580 --> 08:37.940
können.

08:39.100 --> 08:41.900
Wenn wir jetzt einen Code haben, dann sind in diesem Code ja mehrere

08:41.900 --> 08:45.220
Codewörter drin, für jedes Zeichen des Alphabets ein Codewort.

08:45.220 --> 08:50.680
Und wir nennen dann den minimalen Abstand zwischen verschiedenen

08:50.680 --> 08:53.680
Codewörtern die Hemmingzahl des Codes.

08:54.860 --> 09:00.200
Sie haben eine Reihe von Codewörtern da drin, der minimale Abstand ist

09:00.200 --> 09:01.400
die Hemmingzahl des Codes.

09:02.020 --> 09:04.540
Übrigens, kleiner Randbemerkung, ich habe heute darauf verzichtet,

09:05.100 --> 09:11.120
unsere Werkzeuge hier mit zu starten, weil ich denke, bei einer

09:11.120 --> 09:14.200
relativ kleinen Teilnehmerzahl können Sie problemlos mir durch

09:14.200 --> 09:18.300
Handzeichen irgendeine Meldung machen und auch darum bitten, dass es

09:18.300 --> 09:21.180
langsamer geht oder schneller geht oder was immer Sie gerne mitteilen

09:21.180 --> 09:21.500
möchten.

09:22.820 --> 09:25.140
So, jetzt haben wir also hier diese Definition.

09:25.380 --> 09:28.620
Schauen wir uns eine einfache Codierung an, eine sogenannte Eins-aus

09:28.620 --> 09:30.100
-zehn -Codierung für Dezimalzettel.

09:30.180 --> 09:31.360
Warum Eins-aus-zehn?

09:31.400 --> 09:36.860
Wir haben in diesem Fall hier zehn Bits und ein Bit ist jeweils eine

09:36.860 --> 09:41.680
Eins in jedem Codewort, und zwar gerade an einer dieser zehn

09:41.680 --> 09:42.500
Positionen.

09:42.600 --> 09:46.060
Wenn das rechteste Bit eins ist, ist es eine Null, wenn das linkeste

09:46.060 --> 09:47.680
Bit eine Eins ist, ist es eine Neun.

09:48.880 --> 09:51.820
So, wie sieht der Abstand aus zwischen je zwei Codewörtern?

09:52.540 --> 09:56.720
Wenn wir das betrachten hier, diese beiden, da die Eins bei jedem

09:56.720 --> 10:00.160
Codewort an einer anderen Stelle steht, sind genau bei zwei

10:00.160 --> 10:03.340
Codewörtern zwei Positionen unterschiedlich, nämlich die beiden

10:03.340 --> 10:05.260
Positionen, wo jeweils die Eins steht.

10:06.140 --> 10:12.360
Das heißt, die Hemmingzahl in diesem Fall ist eindeutig zwei.

10:14.420 --> 10:19.420
Und das heißt doch sofort, wenn ich jetzt ein Codewort hätte oder ein

10:19.420 --> 10:23.640
Wort bekommen würde, das einen Abstand von eins hat zu irgendeinem

10:23.640 --> 10:30.300
dieser Codewörter, dann kann das kein Wort aus dem Code sein, weil ja

10:30.300 --> 10:32.980
die Codewörter alle einen Abstand von zwei haben.

10:32.980 --> 10:40.020
Wenn also ein Bit sich verändert, verändert sich der Hemmingabstand

10:40.020 --> 10:44.820
und damit kann ich feststellen, ob Fehler aufgetreten sind.

10:45.740 --> 10:47.820
Also, wann ist ein Fehler überhaupt erkennbar?

10:48.700 --> 10:50.360
Wenn durch...

10:54.520 --> 10:55.220
Genau,

10:59.300 --> 11:01.260
wenn durch ihn kein anderes Codewort entstehen kann.

11:01.260 --> 11:09.520
Also, ich habe ein Codewort, ich kann also alle Fehler erkennen, nehme

11:09.520 --> 11:13.140
mir irgendein Wort her und das wird jetzt irgendwie fehlerhaft

11:13.140 --> 11:13.640
verändert.

11:14.920 --> 11:20.820
Wenn durch die Fehler ein Wort entsteht, das auch wieder ein Codewort

11:20.820 --> 11:22.520
ist, dann kann ich diese Fehler nicht erkennen.

11:23.440 --> 11:31.440
Wenn also hier drin zum Beispiel hier anstehen würde 0, 1 und dann

11:31.440 --> 11:34.880
hier entsprechend Nullen, dann hätte ich an zwei Positionen etwas

11:34.880 --> 11:35.320
verändert.

11:35.560 --> 11:38.220
Die erste 1 zu einer 0, die zweite 0 zu einer 1 gemacht.

11:38.800 --> 11:42.720
Ich hätte wieder ein Codewort und könnte nicht erkennen, dass dort

11:42.720 --> 11:44.180
zwei Fehler aufgetreten waren.

11:46.240 --> 11:50.100
Das heißt, erkennen kann ich hier nur in dem Fall Fehler, bei denen

11:50.100 --> 11:51.760
die Abstände ungerade sind.

11:52.760 --> 11:55.420
Also Abstand 1 im kleinsten Fall.

11:56.380 --> 11:58.200
Wann ist ein Fehler korrigierbar?

11:59.820 --> 12:06.120
Wenn ein erkannter Fehler durch genau ein Codewort entstanden sein

12:06.120 --> 12:06.420
kann.

12:07.580 --> 12:11.900
Das heißt, ich habe ein Wort, das ist kein Codewort, es muss also ein

12:11.900 --> 12:16.700
Fehler aufgetreten sein und ich kann eindeutig sagen, aus welchem

12:16.700 --> 12:21.660
Codewort dieses fehlerhafte Wort entstanden sein muss.

12:23.660 --> 12:29.580
Also wenn ich feststelle, ich habe hier meinetwegen in dem Beispiel,

12:31.020 --> 12:37.000
wenn ich hier einen Fehler machen würde, zum Beispiel würde hier eine

12:37.000 --> 12:40.640
0 entstehen, hätte ich hier nur noch Nullen stehen.

12:42.420 --> 12:47.620
Ein Fehler, aber der Abstand zu allen anderen ist 1.

12:48.800 --> 12:52.980
Ich weiß überhaupt nicht, wenn ich nur die Nullen sehe, an welcher

12:52.980 --> 12:56.100
Position, ich weiß zwar, das ist kein Codewort, ich weiß aber nicht,

12:56.200 --> 12:58.520
an welcher Stelle der Fehler aufgetreten sein kann.

12:59.500 --> 13:02.340
Weil dieses Wort zu allen anderen den gleichen Abstand hat.

13:03.560 --> 13:05.740
Also dazu muss ich größere Abstände haben.

13:07.080 --> 13:12.360
Schauen wir uns ein anderes Beispiel an, ein Code hier mit drei

13:12.360 --> 13:13.840
Codewörtern.

13:15.700 --> 13:20.940
Wir haben hier einen Abstand, wir haben hier einen Unterschied, wenn

13:20.940 --> 13:30.260
wir die beiden X und Y anschauen, 1, 2, 3, 4, 5, 6.

13:30.260 --> 13:36.740
Wir hätten, das waren die Unterschiede, wenn ich diese Unterschiede

13:36.740 --> 13:41.800
anschaue, 1, 2, 3, 4, 5, 6.

13:43.180 --> 13:46.120
Und wenn ich die oberen beiden anschaue, habe ich da einen

13:46.120 --> 13:52.040
Unterschied, da einen, da einen, da einen.

13:52.040 --> 13:59.060
1, 2, 3, 4, 5, 6, müsste also eigentlich einen Abstand von, wie in

13:59.060 --> 14:02.420
diesem Bild hier zu sehen, Abstand von 6.

14:03.540 --> 14:06.300
Je zwei Wörter haben hier einen Abstand von 6.

14:07.520 --> 14:09.940
Die können auch unterschiedlich sein, die Abstände müssen nicht immer

14:09.940 --> 14:12.820
alle den gleichen Abstand haben, aber in diesem Fall ist es so, wir

14:12.820 --> 14:16.200
haben drei Codewörter, die den Abstand von 6 haben, hier so ein

14:16.200 --> 14:17.960
bisschen räumlich dargestellt.

14:17.960 --> 14:21.000
Und diese räumliche Darstellung werde ich gleich noch weiterverwenden.

14:21.400 --> 14:24.540
Was man hier jetzt sieht ist zum Beispiel, wenn ich das Z mir

14:24.540 --> 14:31.060
anschaue, mit einem Fehler kann aus dem Z dieses Wort entstehen, was

14:31.060 --> 14:32.780
offensichtlich kein Codewort ist.

14:34.240 --> 14:39.400
Und es ist offensichtlich, dass durch einen Fehler nur aus dem Z

14:39.400 --> 14:41.140
dieses Wort entstanden sein kann.

14:41.140 --> 14:46.440
Wenn ich noch einen Fehler einbaue, kann ich immer noch sagen, bei

14:46.440 --> 14:50.700
zwei Fehlern, dieses Wort kann nur aus dem Z entstanden sein.

14:52.380 --> 14:54.720
Jetzt habe ich drei Fehler.

14:56.520 --> 15:00.940
Und jetzt wird es schwierig, weil ich durch drei Fehler nämlich

15:00.940 --> 15:03.440
genauso von Y gekommen sein kann.

15:04.720 --> 15:10.580
Das heißt, das kann ich nicht mehr eindeutig feststellen, bei drei

15:10.580 --> 15:13.200
Fehlern, wo der Fehler eigentlich hergekommen ist.

15:13.920 --> 15:15.520
Also von welchem Wort ich ausgegangen bin.

15:16.900 --> 15:18.660
Und das werden wir uns jetzt weiter anschauen.

15:18.760 --> 15:23.320
Also hier haben wir genau die Abstände 3 und wenn es kleiner als 3

15:23.320 --> 15:27.460
ist, können wir feststellen, das ist aus Z oder wenn ich in der

15:27.460 --> 15:32.600
Umgebung von Y bin, aus Y hervorgegangen oder aus X, je nachdem, in

15:32.600 --> 15:34.080
welcher Nachbarschaft ich mich bewege.

15:34.160 --> 15:39.300
So habe ich hier also so eine Art Umgebungen meines Wortes und sobald

15:39.300 --> 15:43.920
ich eben über diese Grenze hinausgehe, kann ich nicht mehr feststellen

15:43.920 --> 15:50.880
eindeutig, aus welchem Codewort ich ausgegangen bin.

15:52.240 --> 15:56.560
Und damit kann ich jetzt sagen, wie ich jetzt eine Fehlererkennung und

15:56.560 --> 15:58.520
Korrigierbarkeit definiere.

15:58.520 --> 16:05.760
Ich sage, dass ein Codewort K-Fehler erkennbar ist, wenn durch

16:05.760 --> 16:10.920
Verfälschungen von bis zu K Stellen eines Codeworts kein anderes

16:10.920 --> 16:12.540
Codewort entstehen kann.

16:14.620 --> 16:18.300
Das heißt, bis zu K Fehler können auftreten, es kann kein anderes

16:18.300 --> 16:21.400
Codewort entstehen, dann weiß ich, da ist ein Fehler aufgetreten.

16:21.400 --> 16:23.060
Das ist hier nochmal ausgedrückt.

16:23.780 --> 16:29.200
Wenn also der Abstand eines Codeworts zu einem anderen Wort kleiner

16:29.200 --> 16:33.640
gleich K ist, dann ist das Wort Y kein Codewort.

16:35.060 --> 16:39.280
Und korrigieren kann ich den Fehler immer dann, wenn ich eindeutig

16:39.280 --> 16:42.620
feststellen kann, woher das Wort gekommen ist.

16:42.620 --> 16:47.940
Wenn ich also durch Verfälschung von bis zu K Stellen ein Wort

16:47.940 --> 16:52.960
erhalte, bei dem es immer noch möglich ist, eindeutig festzustellen,

16:53.140 --> 16:57.340
was das ursprüngliche Codewort war, dann ist der K-Fehler

16:57.340 --> 16:58.120
korrigierbar.

16:58.840 --> 17:10.020
Das heißt, wenn ich zwei Wörter habe, XY, zwei Codewörter und

17:10.020 --> 17:18.060
irgendein anderes Wort Z, wenn die beiden Wörter verschieden sind und

17:18.060 --> 17:24.700
der Abstand von Z zu X kleiner gleich K ist, bei einem K-Fehler

17:24.700 --> 17:29.500
korrigierbaren Code, dann muss der Abstand von Z zu Y größer als K

17:29.500 --> 17:29.800
sein.

17:32.540 --> 17:38.040
Damit habe ich sofort diese Aussage, und das kann man jetzt nochmal

17:38.040 --> 17:47.160
ein bisschen umdrehen, man kann daraus sofort erkennen, dass ein Code

17:47.160 --> 17:55.140
bis zu K-Fehler erkennen kann, also ein bis zu K-Fachfehler, solange

17:55.140 --> 18:01.980
dieses K kleiner ist als die Hemmingzahl dieses Codes.

18:02.520 --> 18:06.100
Kleiner als der minimale Abstand der aufeinanderfolgenden oder der

18:06.100 --> 18:07.640
benachbarten Codewörter.

18:08.320 --> 18:16.460
Und wenn der Abstand dieses verfälschten Wortes kleiner ist als der

18:16.460 --> 18:21.840
halbe Abstand zwischen zwei Codewörtern, dann ist die Codierung auch K

18:21.840 --> 18:22.860
-Fehler korrigierbar.

18:23.960 --> 18:27.140
Da kann ich also eindeutig zurückschließen, das war das, was wir hier

18:27.140 --> 18:31.540
gesehen hatten, wenn wir kleiner als 3 sind, bis zu 2-Fachfehler

18:31.540 --> 18:37.740
können wir in dem Fall erkennen und die anderen halt nicht.

18:41.620 --> 18:46.920
Damit haben wir also hier nochmal diese räumliche Darstellung, wir

18:46.920 --> 18:49.980
machen hier diese Kreisdarstellung um diese Codewörter.

18:49.980 --> 18:53.920
Wir können also feststellen, solange diese Kreise, die Umgebungen

18:53.920 --> 19:00.600
eines Codeworts kein anderes Codewort enthalten, habe ich also gerade

19:00.600 --> 19:04.300
die Distanz, bis zu der ich K-Fehler-Erkennbarkeit habe.

19:04.740 --> 19:08.400
Bei Korrigierbarkeit, da sind halt diese K-Fachumgebungen immer

19:08.400 --> 19:09.040
disjunkt.

19:10.160 --> 19:12.480
Auch das muss hier gewährleistet sein.

19:13.240 --> 19:19.020
Also jede Codierung ist Hemmingzahl, also halbe Hemmingzahl, minus 1,

19:19.400 --> 19:20.540
Fehler korrigierbar.

19:23.280 --> 19:26.420
So, damit wissen wir etwas darüber, wie wir Fehler erkennen und

19:26.420 --> 19:27.300
korrigieren können.

19:27.460 --> 19:31.460
Hier nochmal ein Beispiel, 1 aus 10 Codierung, da war die Hemmingzahl

19:31.460 --> 19:32.160
2.

19:32.940 --> 19:36.680
Und damit ist dieser Cod-Einfachfehler erkennbar, das hatten wir

19:36.680 --> 19:37.280
festgestellt.

19:37.280 --> 19:40.800
Aber ich kann keinen Fehler korrigieren, weil durch einen

19:40.800 --> 19:44.620
Einfachfehler der Abstand zu allen anderen gleich ist.

19:45.820 --> 19:48.760
Wenn wir diese Codierung hier betrachten, hier werden vier Zeichen

19:48.760 --> 19:51.000
abgebildet.

19:51.920 --> 19:57.060
Wenn man sich das anschaut, hier sind die Abstände jeweils 3, können

19:57.060 --> 19:58.300
sich alle Beziehungen anschauen.

19:58.820 --> 20:01.520
Der minimale Abstand zwischen zwei Codewörtern ist 3.

20:01.520 --> 20:06.280
Und wenn ich einen Abstand 3 habe, kann ich also bis zu 2-fach Fehler

20:06.280 --> 20:09.520
erkennen und ich kann 1-fach Fehler korrigieren.

20:12.520 --> 20:13.980
Halbe, minus 1.

20:16.820 --> 20:20.540
Und dann haben wir hier noch einen Code, das war der, den wir vorher

20:20.540 --> 20:21.340
schon gehabt haben.

20:21.820 --> 20:26.000
Hier habe ich also in dem Fall eine 5-fach Fehler Erkennbarkeit.

20:26.770 --> 20:31.360
Der Abstand ist 6, der minimale Hemming-Abstand, also 5-fach Fehler

20:31.360 --> 20:34.880
können erkannt werden und 2-fach Fehler kann ich korrigieren.

20:36.680 --> 20:41.500
Auf diese Art und Weise kann man also mit Fehlern in der Hardware

20:41.500 --> 20:46.720
umgehen und kann, wenn man halt diese Eigenschaften so gesetzt hat,

20:47.160 --> 20:49.940
kann man dafür sorgen, dass man auch einige Fehler wieder korrigieren

20:49.940 --> 20:50.280
kann.

20:51.000 --> 20:53.240
Ich kann also mit den richtigen Werten weiterarbeiten.

20:55.600 --> 21:00.940
Jetzt kann es manchmal sein, dass ich einen Code entworfen habe, zum

21:00.940 --> 21:02.300
Beispiel den 1-aus-10-Code.

21:02.360 --> 21:05.580
Ich möchte den jetzt gerne 1-fach Fehler korrigierbar machen.

21:06.940 --> 21:09.160
Dann muss ich irgendwie die Abstände erhöhen.

21:10.460 --> 21:15.480
Und um die Abstände zu erhöhen, geht man so vor, dass man einfach ein

21:15.480 --> 21:17.420
Prüfbit anhängt.

21:18.280 --> 21:19.920
Sondern das Parity-Bit.

21:20.440 --> 21:24.260
Ich hatte Ihnen schon mal gesagt, dass wir bei dem XOR auch von einer

21:24.260 --> 21:25.700
Paritätsfunktion reden.

21:26.180 --> 21:33.180
Das Paritätsbit, das Prüfbit, führt einfach ein XOR aus auf den Bits

21:33.180 --> 21:39.220
einer Zahl oder eines Codeworts und hängt dann am Ende entsprechend

21:39.220 --> 21:42.240
noch eine 1 dran.

21:42.440 --> 21:47.360
Und zwar so, dass die Anzahl der Einsen in jedem Codewort einheitlich

21:47.360 --> 21:49.760
gerade oder ungerade ist.

21:49.900 --> 21:51.820
Also ich kann sagen, ich mache alles gerade.

21:52.280 --> 21:56.020
Dann habe ich also überall dafür gesorgt, dass in jedem Codewort eine

21:56.020 --> 21:57.380
gerade Anzahl von Einsen ist.

21:57.820 --> 21:59.040
Oder ich mache alles ungerade.

21:59.080 --> 22:02.060
Dann habe ich dafür gesorgt, dass in jedem Codewort eine ungerade

22:02.060 --> 22:03.140
Anzahl von Einsen ist.

22:03.140 --> 22:10.000
Und wenn jetzt ein Fehler, eine Null auf eine Eins geht oder eine Eins

22:10.000 --> 22:14.680
auf eine Null, ändert sich die Anzahl der Einsen um Eins.

22:15.360 --> 22:18.760
Und damit habe ich sofort eine Einfach-Fehler-Erkennbarkeit.

22:18.840 --> 22:26.100
Ich habe also in dem Fall den Abstand zwischen Codewörtern um Eins

22:26.100 --> 22:26.600
erhöht.

22:27.360 --> 22:31.780
Also ich habe zumindest für jede solche Codierung eine Hamming-Zahl,

22:31.880 --> 22:32.940
die größer gleich 2 ist.

22:33.020 --> 22:36.200
Ich kann damit eine Einfach-Fehler-Erkennbarkeit garantieren.

22:37.540 --> 22:42.180
Wenn ich jetzt mehrere Prüfbits anhänge, kann ich damit den Hamming

22:42.180 --> 22:43.480
-Abstand noch mehr erhöhen.

22:45.460 --> 22:48.580
Jetzt kann man das auch noch so machen, dass ich meinetwegen ein

22:48.580 --> 22:53.400
Codewort habe oder ein Wort habe und die Prüfbits, die können

22:53.400 --> 22:55.400
irgendwie verstreut sein.

22:56.420 --> 22:58.560
Und das können also meinetwegen Prüfbits sein hier.

22:59.200 --> 23:03.400
Oder ich kann auch einen Code machen, sodass ich hier am Anfang ein

23:03.400 --> 23:05.380
paar Prüfbits habe, also einen ganzen Prüfblock.

23:05.940 --> 23:12.460
Und jedes Prüfbit sichert jeweils einige Positionen in meinem Codewort

23:12.460 --> 23:15.420
ab, also auf entsprechende Parität.

23:16.900 --> 23:20.480
Und auf die Art und Weise kann man sogar noch mehr machen als nur

23:20.480 --> 23:25.560
diese einfache Korrigierbarkeit aufgrund des Abstandes zwischen zwei

23:25.560 --> 23:26.140
Codewörtern.

23:26.240 --> 23:30.040
Man kann da noch mehr Dinge reinkodieren, solche Dinge werden Sie in

23:30.040 --> 23:34.760
den Übungsaufgaben auch kennenlernen, andere Codes, die solche Dinge

23:34.760 --> 23:36.460
noch mit zusätzlich machen.

23:37.880 --> 23:44.180
Man kann auch das genauso machen bei nicht-binären Codes, also bei

23:44.180 --> 23:45.280
dezimaler Kodierung.

23:45.460 --> 23:49.000
Sie kennen das von Kontrollziffern bei Kontonnummern, bei

23:49.000 --> 23:49.800
Matrikelnummern.

23:50.500 --> 23:54.620
Wenn Sie irgendeine Zahlenfolge eingeben, werden Sie meistens eine

23:54.620 --> 23:57.440
Zahlenfolge erwischen, die gerade keine gültige Nummer ist, weil Sie

23:57.440 --> 24:00.020
irgendwelche Eigenschaften nicht beachtet haben.

24:00.020 --> 24:06.240
Also man kann dafür sorgen durch Regeln für die Codewörter, dass man

24:06.240 --> 24:09.760
eben erkennen kann, welche Wörter gültig sind und welche nicht, und

24:09.760 --> 24:13.200
dass man eben auch bei einfachen Fehlern dann diese wieder korrigieren

24:13.200 --> 24:13.460
kann.

24:13.920 --> 24:19.660
Es gibt eine sehr umfangreiche Theorie zu solchen Codes, zu der Art,

24:19.780 --> 24:21.260
wie man Codes aufstellt.

24:21.680 --> 24:24.520
Es gibt auch algebraische Codes, es gibt also sehr viel, was man hier

24:24.520 --> 24:25.040
machen kann.

24:25.620 --> 24:27.920
Das wäre Stoff für eine ganze Vorlesung.

24:27.920 --> 24:29.020
Machen wir hier nicht.

24:29.180 --> 24:33.080
Ich wollte nur das Thema Fehlererkennende und Fehlerkorrigierende

24:33.080 --> 24:37.340
Codes hier einmal angesprochen haben, dass Sie wissen, man kann mit

24:37.340 --> 24:42.400
Fehlern in einem Rechner umgehen und man geht auch genauso damit um.

24:44.080 --> 24:49.780
Normalerweise im Speicher haben Sie nicht einfach nur Nutzdaten, also

24:49.780 --> 24:54.260
außerhalb dieser Prüfbits, das wären die Nutzdaten in einem

24:54.260 --> 24:59.540
Speicherwort, sondern Sie haben auch Prüfdaten dort drin und sichern

24:59.540 --> 25:03.560
auf die Art und Weise dann Ihre Daten im Speicher ab.

25:04.140 --> 25:06.760
Manchmal sieht das auch so aus, dass Sie hier einen ganzen Block haben

25:06.760 --> 25:11.280
und erst am Ende dieses Blocks haben Sie dann einfach ein ganzes Wort,

25:11.700 --> 25:16.940
das nur Positionen in den anderen Positionen absichert, sodass Sie

25:16.940 --> 25:18.780
dann Fehlererkennung machen können.

25:18.780 --> 25:23.280
Also das ist eine umfangreiche Theorie, sehr wichtig, kann man sich

25:23.280 --> 25:24.420
intensiver damit beschäftigen.

25:24.880 --> 25:29.200
Wir gehen hier über diese einfachen Hemmingabstände und die daraus

25:29.200 --> 25:32.260
folgenden Erkenntnisse zur Erkennbarkeit und Korrigierbarkeit nicht

25:32.260 --> 25:32.620
hinaus.

25:34.260 --> 25:36.860
Damit sind wir schon beim nächsten Thema, nämlich bei den

25:36.860 --> 25:38.460
Häufigkeitsabhängigen Codierungen.

25:39.560 --> 25:43.540
Ich hatte gesagt, manchmal betrachten wir Blockcodes, wie gerade eben

25:43.540 --> 25:48.480
auch in dem Beispiel, oder bei diesen fehlerabhängigen Codes oder

25:48.480 --> 25:50.260
fehlerkorrigierenden und erkennbaren Codes.

25:51.140 --> 25:55.380
Manchmal möchte man aber mit möglichst wenigen Bits etwas darstellen

25:55.380 --> 25:55.740
können.

25:56.720 --> 25:59.360
Und wenn wir uns anschauen, zum Beispiel die Codierung von

25:59.360 --> 26:07.960
Dezimalzahlen, Sie haben zehn Ziffern, null bis neun, und brauchen um

26:07.960 --> 26:12.840
zehn Ziffern binär darzustellen, mehr als drei Bits.

26:12.920 --> 26:14.260
Mit drei Bits reicht es nicht.

26:14.380 --> 26:18.420
Nehmen Sie vier Bits, da könnten Sie 16 Zahlen darstellen, aber

26:18.420 --> 26:19.840
eigentlich brauchen Sie keine 16 Zahlen.

26:19.960 --> 26:24.200
Genauso, wenn Sie die Buchstaben des Alphabets darstellen wollen.

26:24.300 --> 26:28.520
26 Buchstaben im lateinischen Alphabet, da reichen Ihnen vier Bits

26:28.520 --> 26:28.960
nicht aus.

26:29.040 --> 26:31.140
Wenn Sie fünf Bits haben, haben Sie 32 Bit.

26:33.460 --> 26:37.580
Das heißt, Sie würden Bits verschenken, Sie würden zu viele Bits

26:37.580 --> 26:40.860
verwenden, wenn Sie einen langen Text codieren, weil Sie eigentlich

26:40.860 --> 26:43.880
weniger Informationen brauchen, als Sie da jetzt reinstecken.

26:44.440 --> 26:49.140
Und das nutzt man aus, wenn man eine häufigkeitsabhängige Codierung

26:49.140 --> 26:54.000
machen möchte, da berücksichtigt man einfach, wie häufig gewisse

26:54.000 --> 26:58.020
Zeichen eines Zeichenvorrats in Texten auftauchen.

26:59.520 --> 27:04.060
Also man geht davon aus, ich habe irgendeine Häufigkeitsverteilung

27:04.060 --> 27:05.620
gegeben.

27:06.520 --> 27:09.160
Naja, wie kann ich so eine Häufigkeitsverteilung geben?

27:09.240 --> 27:12.780
Ich kann also irgendein Dokument mir anschauen, da sind irgendwelche

27:12.780 --> 27:14.400
Wörter drin.

27:15.320 --> 27:18.120
Ich könnte mir die Häufigkeitsverteilung auf dieser Folie anschauen,

27:18.620 --> 27:20.100
alle Zeichen auf dieser Folie.

27:20.760 --> 27:23.540
Könnte ich durchzählen, wie oft tauchen hier die einzelnen Zeichen

27:23.540 --> 27:23.880
auf.

27:24.940 --> 27:31.520
Und dann könnte ich dafür sorgen, dass ich mit möglichst wenig

27:31.520 --> 27:35.180
Aufwand, mit möglichst wenig Platzaufwand, mit möglichst wenig Witz

27:35.180 --> 27:38.440
genau die Information darstellen kann, die hier angegeben ist.

27:39.560 --> 27:42.900
Und dann würde ich natürlich dafür sorgen, dass häufige Zeichen

27:42.900 --> 27:47.820
weniger Platz brauchen und seltene Zeichen durchaus etwas längere

27:47.820 --> 27:49.100
Codewörter bekommen können.

27:50.900 --> 27:53.820
Also die, die oft auftauchen, müssen mit weniger Platz dargestellt

27:53.820 --> 27:56.160
werden, als diejenigen, die nicht so häufig auftauchen.

27:57.700 --> 28:01.160
Kurze Codewörter für häufige Zeichen, lange Codewörter für seltene

28:01.160 --> 28:01.520
Zeichen.

28:02.340 --> 28:04.120
Dann muss ich die Verteilung kennen.

28:04.700 --> 28:07.620
Ich kann sie mir für ein Dokument, das ich binär codieren möchte,

28:07.700 --> 28:11.760
einfach ausrechnen, die Verteilungen, und dann daraus entsprechend

28:11.760 --> 28:15.600
eine Codierung machen, die häufigkeitsabhängig ist.

28:16.200 --> 28:19.160
Was ich also allgemein brauche, ist eine Wahrscheinlichkeitsverteilung

28:19.160 --> 28:25.680
P für die Zeichen meines Alphabets, also auf das reelle Intervall 0,1

28:25.680 --> 28:26.320
abgebildet.

28:26.940 --> 28:30.840
Und ich brauche eine Codierung, die natürlich die FANO-Bedingungen

28:30.840 --> 28:32.720
erfüllt, das heißt, die muss dekodierbar sein.

28:33.780 --> 28:42.580
Und jetzt sage ich einfach, dass ich mir für einen Code anschaue, die

28:42.580 --> 28:46.540
Länge der einzelnen Codewörter und die Wahrscheinlichkeit, mit der das

28:46.540 --> 28:52.380
Codewort auftaucht, und die Summe aller Produkte aus

28:52.380 --> 28:56.220
Wahrscheinlichkeit des Auftretens eines Zeichens und der Länge dieses

28:56.220 --> 28:59.680
Codeworts, nenne ich einfach die Codelänge.

29:01.340 --> 29:05.720
Und ich möchte dafür sorgen, dass die Codelänge minimal ist.

29:05.920 --> 29:11.000
Ich möchte also die Codelänge optimieren, dadurch ist dann auch die

29:11.000 --> 29:15.660
Darstellung eines Textes in Bezug auf dieses Optimierungskriterium

29:15.660 --> 29:17.980
halt einfach verkürzt.

29:19.740 --> 29:25.440
Und ich habe dann also, ein Code ist also optimal, wenn diese

29:25.440 --> 29:27.240
Codelänge hier minimal ist.

29:29.000 --> 29:32.380
Das heißt nicht unbedingt, dass der Text nicht noch einfacher hätte

29:32.380 --> 29:36.760
dargestellt werden können, dann müsste ich aber mehr machen, als nur

29:36.760 --> 29:39.800
die Häufigkeit von einzelnen Zeichen mir anschauen, dann müsste ich

29:39.800 --> 29:42.980
mir auch noch die Häufigkeit von irgendwelchen Wörtern oder

29:42.980 --> 29:49.560
Teilwörtern oder man einfach Zeichenpaaren oder Zeichentrippeln

29:49.560 --> 29:50.140
anschauen.

29:51.200 --> 29:52.540
All das wird auch gemacht.

29:54.280 --> 29:55.420
Also ein paar Bemerkungen.

29:56.160 --> 29:59.160
Man kann natürlich schauen, wenn ich einen deutschen Text habe oder

29:59.160 --> 30:02.980
einen englischen Text, habe ich sofort eine Häufigkeitsverteilung.

30:03.920 --> 30:06.920
Ich kann also alle möglichen deutschen Texte anschauen und stelle

30:06.920 --> 30:12.760
fest, in der deutschen Sprache habe ich diese Verteilungen von

30:12.760 --> 30:16.560
Zeichen, in der englischen Sprache sieht es ein bisschen anders aus.

30:17.580 --> 30:21.160
Sie sehen, das häufigste Zeichen ist in beiden Fällen das Zeichen E

30:22.080 --> 30:29.600
und das Zeichen X zum Beispiel, das ist in beiden relativ selten, das

30:29.600 --> 30:33.440
ist glaube ich das mit der geringsten Häufigkeit.

30:38.340 --> 30:42.200
Interessant, im Deutschen ist X am wenigsten, im Englischen ist Z am

30:42.200 --> 30:42.680
wenigsten.

30:48.180 --> 30:54.400
Sie sehen ja auch auf der Tastatur ist die Position von Z und Y häufig

30:54.400 --> 30:55.040
vertauscht.

30:55.040 --> 30:59.040
Die englische Tastatur hat an der Stelle, wo wir das Z haben, das Y

30:59.040 --> 31:00.800
und umgekehrt.

31:01.840 --> 31:04.700
Also das sind Häufigkeitsverteilungen allgemein in englischen und

31:04.700 --> 31:05.460
deutschen Texten.

31:06.740 --> 31:10.020
Eine optimale Kodierung ist natürlich nicht eindeutig bestimmt, die

31:10.020 --> 31:12.680
können Sie unterschiedlich machen, es kann viele geben, die ähnlich

31:12.680 --> 31:13.460
häufig sind.

31:14.320 --> 31:16.660
Und ich möchte Ihnen jetzt einen Algorithmus vorstellen, einen

31:16.660 --> 31:20.200
Standardalgorithmus, der genau das ausnutzt.

31:20.200 --> 31:28.980
Wir gehen davon aus, wir haben eine Häufigkeitsverteilung gegeben und

31:28.980 --> 31:32.560
jetzt wollen wir für eine Häufigkeitsverteilung einen Code erzeugen.

31:33.280 --> 31:35.560
Und das machen wir auf folgende Art und Weise, nehmen wir mal an, wir

31:35.560 --> 31:40.340
haben hier diese einfachen Häufigkeiten, meinetwegen von Zeichen,

31:40.540 --> 31:47.460
schreiben wir einfach mal rüber, A, B, C, D, E, F, nehmen wir an, die

31:47.460 --> 31:51.200
sind unsere Zeichen, das wäre die Verteilung, ich habe jetzt hier

31:51.200 --> 31:55.860
ganze Zahlen hingeschrieben, keine Wahrscheinlichkeiten, dividieren

31:55.860 --> 31:57.780
Sie es durch 100, dann haben Sie hier die Wahrscheinlichkeiten.

31:58.420 --> 32:03.860
Und jetzt steht hier, wir bilden für jedes Zeichen aus dem Alphabet

32:03.860 --> 32:10.740
einen Knoten, der genau mit der Wahrscheinlichkeit dieses Zeichens

32:10.740 --> 32:11.560
beschriftet ist.

32:11.560 --> 32:17.060
Das heißt, das sind jetzt alles Knoten, beschriftet mit der

32:17.060 --> 32:19.000
Wahrscheinlichkeit des jeweiligen Zeichens.

32:19.980 --> 32:21.980
Jetzt kommt der erste Schritt, was machen wir?

32:23.220 --> 32:29.940
Wir setzen also in diese Menge L hier, in unsere Liste, kommen alle

32:29.940 --> 32:31.060
diese Knoten hinein.

32:31.060 --> 32:39.480
Und jetzt wiederholen wir, solange diese Liste nicht leer ist oder

32:39.480 --> 32:46.360
mindestens mehr als ein Zeichen enthält, nehmen wir uns zwei Knoten

32:46.360 --> 32:49.440
raus, dafür brauchen wir natürlich mindestens zwei Elemente da drin,

32:50.360 --> 32:56.780
zwei Knoten mit den geringsten Bewertungen, die beiden Knoten mit den

32:56.780 --> 33:00.880
geringsten Bewertungen, wären diese beiden, die füllen wir zusammen zu

33:00.880 --> 33:01.920
einem neuen Knoten.

33:03.700 --> 33:07.680
Und dieser Knoten bekommt als Bewertung gerade die Summe der beiden

33:07.680 --> 33:08.520
Wahrscheinlichkeiten.

33:09.220 --> 33:10.640
Hier wäre das also eine 12.

33:13.160 --> 33:17.880
Das wäre also eine, hier in diesem Fall eindeutig, die beiden Knoten

33:17.880 --> 33:24.640
werden zusammengenommen und die Zahl 12 gibt gerade an, also 0,12, die

33:24.640 --> 33:27.600
Wahrscheinlichkeit dafür, dass ich ein Zeichen A oder B habe.

33:29.080 --> 33:35.180
Das wiederhole ich, ich nehme dann natürlich das, da muss noch mehr

33:35.180 --> 33:41.960
stehen, genau, ich füge diese Kanten hinzu und ich lösche die beiden

33:41.960 --> 33:46.280
Knoten, die ich jetzt verbunden habe, raus und füge den neuen Knoten

33:46.280 --> 33:46.920
hinzu.

33:47.940 --> 33:49.520
Also die 12 in dem Fall.

33:50.520 --> 33:51.880
Und das wiederhole ich jetzt.

33:53.280 --> 33:56.320
Hier habe ich in diesem Fall auch keine Wahl, ich muss die beiden

33:56.320 --> 34:00.340
zusammenführen zu einem neuen Knoten und da schreibe ich jetzt rein

34:00.340 --> 34:01.620
25.

34:05.120 --> 34:08.120
Jetzt kann ich wieder weitermachen, da hätte ich zwei verschiedene

34:08.120 --> 34:08.560
Möglichkeiten.

34:08.560 --> 34:15.280
Ich könnte zum Beispiel diese beiden zusammenfügen zu 45.

34:18.140 --> 34:23.040
Ich hätte auch diesen neuen Knoten hier unten, die 25 und die 20

34:23.040 --> 34:23.960
zusammenfügen können.

34:24.060 --> 34:25.000
Zwei verschiedene Möglichkeiten.

34:26.420 --> 34:29.980
Jetzt habe ich wieder keine andere Wahl, ich muss die 25 und die 30

34:29.980 --> 34:31.400
zusammenfügen.

34:32.300 --> 34:35.660
Dann habe ich hier jetzt 55.

34:37.700 --> 34:41.620
Jetzt habe ich noch zwei Knoten übrig, die beiden füge ich zusammen

34:41.620 --> 34:44.300
und oh Wunder, es kommt gerade 100 raus.

34:46.500 --> 34:51.000
Jetzt ist es klar, das ist jetzt die Wurzel unseres Baumes, da habe

34:51.000 --> 34:53.920
ich alle Zeichen im Prinzip zusammengefügt.

34:55.360 --> 34:59.620
Die Wahrscheinlichkeit ist 100, dass wir irgendein Zeichen dort stehen

34:59.620 --> 34:59.880
haben.

35:00.840 --> 35:06.300
Jetzt mache ich daraus einen Code, in dem ich folgendes mache, ich

35:06.300 --> 35:12.440
beschrifte jede nach links verlaufende Kante im entstandenen Baum mit

35:12.440 --> 35:12.740
0.

35:13.760 --> 35:17.400
Also 0, 0, 0, 0.

35:18.660 --> 35:23.020
Dann muss ich hier nochmal hingehen, da auch ein 0 hinschreiben.

35:23.900 --> 35:26.500
Und jede nach rechts verlaufende Kante mit 1.

35:26.500 --> 35:32.900
Also 1, 1, 1, 1, 1.

35:33.820 --> 35:40.960
Und jetzt ordne ich jedem Blatt als Codewort die Folge der

35:40.960 --> 35:44.060
Kantenbeschriftungen zu, von der Wurzel zum Blatt.

35:45.360 --> 35:50.940
Also, was für eine Folge bekommt das F?

35:50.940 --> 35:58.460
Bei dem F schreibe ich hin eine Folge der Kantenbeschriftungen, 0, 1.

35:59.200 --> 36:00.440
Also steht hier 0, 1.

36:01.060 --> 36:05.440
Bei dem I, da komme ich hin über 1, 1.

36:06.800 --> 36:09.500
Zu dem D komme ich über 1, 0.

36:10.980 --> 36:14.640
Zu dem C komme ich über 0, 0, 1.

36:16.040 --> 36:19.680
Zu dem B komme ich über 0, 0, 0, 1.

36:21.720 --> 36:24.540
Und zu dem A komme ich über 0, 0, 0, 0.

36:26.760 --> 36:33.040
Damit sehen Sie eine Kodierung für diese Zeichen A bis F, entsprechend

36:33.040 --> 36:36.140
der Wahrscheinlichkeit ihres Auftretens in irgendeinem Text.

36:37.500 --> 36:42.400
Und damit habe ich, das kann man zeigen, auf diese Art und Weise die

36:42.400 --> 36:43.900
Codelänge minimiert.

36:44.100 --> 36:45.760
Den Beweis werde ich Ihnen nicht antreten.

36:46.600 --> 36:49.400
Huffman-Kodierungen, die auf diese Art und Weise gebildet werden über

36:49.400 --> 36:55.600
solche Bäume, führen zu Kodierungen mit minimaler Kodlänge.

36:57.060 --> 36:59.440
Es ist nicht eindeutig, wie Sie hier gesehen haben.

36:59.580 --> 37:04.200
Ich hätte hier an der einen Stelle die beiden Knoten, die zu D und E

37:04.200 --> 37:07.360
gehören, zusammenfassen können und daraus 45 bekommen.

37:07.560 --> 37:12.140
Oder ich hätte die beiden Knoten hier, diesen konstruierten Knoten 25

37:12.140 --> 37:13.940
und das D zusammenfügen können.

37:13.940 --> 37:17.500
Dann hätte ich halt eine andere Kodierung gefunden.

37:19.320 --> 37:22.740
Also auf diese Art und Weise können wir jetzt Kodierungen erzeugen.

37:24.320 --> 37:27.620
Und hier ist nochmal ein anderes Beispiel, hier richtig schön mit

37:27.620 --> 37:28.800
Wahrscheinlichkeiten angegeben.

37:28.860 --> 37:33.880
Hier haben wir die Dezimalziffern 0 bis 9 mit schönen

37:33.880 --> 37:34.660
Wahrscheinlichkeiten.

37:34.760 --> 37:36.620
Und jetzt müssen wir hier genauso vorgehen.

37:37.080 --> 37:40.740
Wir müssen die Zeichen mit der geringsten Wahrscheinlichkeit zunächst

37:40.740 --> 37:44.700
zusammenfügen, das sind in diesem Fall hier mehrere Möglichkeiten.

37:44.980 --> 37:49.040
Man hätte also 8 und 9 zusammenfassen können, 7 und 9 oder 6 und 9.

37:49.900 --> 37:54.160
Ich habe hier, weil es einfacher zu malen ist, 8 und 9

37:54.160 --> 37:54.440
zusammengefasst.

37:55.060 --> 37:58.540
Dann sind 6 und 7 die beiden mit der kleinsten Wahrscheinlichkeit.

37:59.600 --> 38:06.440
Danach habe ich also weitere, dann sind 0,06 und 0,07 die kleinsten

38:06.440 --> 38:07.420
Wahrscheinlichkeiten.

38:08.500 --> 38:15.040
Danach sind die kleinsten hier 0,08 und 0,09, die müssen

38:15.040 --> 38:16.100
zusammengefügt werden.

38:16.940 --> 38:18.040
Was habe ich jetzt?

38:18.880 --> 38:26.420
Hier habe ich 0,1 und 0,15, da müssen die beiden...

38:26.420 --> 38:27.900
Ne, sehen Sie, ich habe schon einen Fehler gemacht.

38:28.300 --> 38:34.060
0,1 und 0,13, die werden zusammengefügt zu 0,23, da gab es keine

38:34.060 --> 38:34.760
andere Möglichkeit.

38:37.080 --> 38:43.740
Dann anschließend ist auch klar, dann haben wir die 0,17 und die 0,15,

38:43.900 --> 38:46.000
das sind die beiden mit der kleinsten Wahrscheinlichkeit.

38:46.720 --> 38:49.480
Dann muss ich zuerst die 0 und die 1 zusammenfügen, ups, wieder ein

38:49.480 --> 38:49.680
Fehler.

38:50.180 --> 38:51.060
Sehen Sie, man muss aufpassen.

38:51.800 --> 38:55.360
Hier ist ja die 0,23 entstanden zwischendrin, ist da so verborgen in

38:55.360 --> 38:55.760
dem Baum.

38:56.380 --> 38:58.600
Die muss ich zusammenfügen mit der 0,2.

38:59.340 --> 39:02.500
Und jetzt schaue ich mal, was ist noch übrig.

39:02.680 --> 39:12.520
Ich habe hier die 0,32, die 0,43, das sind die beiden und übrig ist

39:12.520 --> 39:13.700
noch hier die 0,25.

39:14.540 --> 39:19.440
Also muss ich jetzt die 0,25 mit der 0,32 zusammenfügen und

39:19.440 --> 39:22.420
anschließend die beiden restlichen Knoten und ich habe die 1,0.

39:24.240 --> 39:26.620
Auch hier hätten wir verschiedene Möglichkeiten gehabt.

39:26.620 --> 39:29.260
Wir hätten zu Anfang ganz anders anfangen können.

39:30.320 --> 39:35.280
Hätten dann entsprechend einen leicht anderen Baum gefunden.

39:35.760 --> 39:39.280
Die Kodierung in diesem Fall auch wieder mit Nullen und Einsen und wir

39:39.280 --> 39:43.560
bekommen daraus dann einen Code, der hier angegeben ist, zum Beispiel

39:43.560 --> 39:47.580
für das Zeichen 6, laufe ich halt auf diese Art und Weise durch.

39:48.580 --> 39:50.420
Und jetzt wollte ich noch ganz kurz zurück.

39:51.240 --> 39:54.300
Also das ist dann, oder ich habe hier auf der nächsten Folie, da sehen

39:54.300 --> 39:58.100
Sie jetzt für alle Zeichen entsprechend die Codewörter, Sie sehen die

39:58.100 --> 40:02.420
9 mit der kleinsten Wahrscheinlichkeit hat hier also 5 Einsen

40:02.420 --> 40:10.420
abgekriegt, sitzt ganz rechts und die 0 hatte die größte

40:10.420 --> 40:15.020
Wahrscheinlichkeit, die 0 und die 1 haben beide gleich viele Zeichen

40:15.020 --> 40:16.840
abbekommen, liegen beide links.

40:17.540 --> 40:25.700
Und was Sie feststellen ist, dass dieser Code die Fahnenbedingungen

40:25.700 --> 40:26.120
erfüllt.

40:26.980 --> 40:31.120
Es ist kein Codewort, Anfangsstück eines anderen Codeworts.

40:33.560 --> 40:34.420
Woran liegt das?

40:36.120 --> 40:42.860
Das liegt einfach daran, dass wir ja jeweils, wenn wir hier

40:42.860 --> 40:47.360
durchlaufen, immer von der Wurzel zu einem Blatt gehen.

40:49.380 --> 40:55.740
Und das heißt, auf diesem Weg von der Wurzel aus zu einem Blatt, hat

40:55.740 --> 40:58.180
es immer irgendwann einen Unterschied gegeben.

40:59.080 --> 41:02.120
Also auch hier, dieser Weg ist sehr identisch, aber in dem Augenblick

41:02.120 --> 41:03.140
verzweige ich mich.

41:04.180 --> 41:07.380
Und dann ist natürlich dieser Weg kein Anfangsstück eines anderen

41:07.380 --> 41:07.980
Codeworts.

41:08.840 --> 41:11.900
Sie erinnern sich bei der Morse-Codierung.

41:12.560 --> 41:17.720
Da hatten wir einen Baum, der war auch ein binärer Baum, da hatten wir

41:17.720 --> 41:20.640
immer einen Punkt gehabt, und hier stand ein E und da stand irgendein

41:20.640 --> 41:21.320
anderes Zeichen.

41:21.980 --> 41:29.660
Da ist das Codewort für das E ein Anfangsstück für das Zeichen, das an

41:29.660 --> 41:31.480
diesem Knoten dran ist.

41:32.720 --> 41:36.220
Das hatte keine Fahnenbedingungen, also das war die Morse-Codierung.

41:37.060 --> 41:39.980
Jetzt könnte man ja sagen, naja, ich kann ja auch genauso gut einfach

41:39.980 --> 41:42.260
das Ganze umkehren.

41:42.320 --> 41:44.440
Ich könnte ja sagen, ich gehe einfach von...

41:44.440 --> 41:46.600
Es wäre einfacher, wenn ich hier bei einem Zeichen bin.

41:48.040 --> 41:53.060
Warum suche ich mir die Folge der Zeichen von der Wurzel zu dem

41:53.060 --> 41:53.760
Zeichen?

41:54.100 --> 41:57.420
Ich kann ja genauso von dem Zeichen ausgehen, einfach den Weg hier bis

41:57.420 --> 41:58.180
zur Wurzel nehmen.

42:01.640 --> 42:09.780
Und da ist es natürlich so, dass auf einmal es sein kann, dass ein

42:09.780 --> 42:16.000
Codewort Anfangsstück ist für ein anderes Codewort.

42:17.260 --> 42:19.800
Ich suche hier gerade nach einem Beispiel.

42:20.140 --> 42:24.220
In diesem Fall haben wir hier ein solches Beispiel.

42:27.900 --> 42:30.880
Natürlich, wenn wir hier in der Richtung gehen...

42:30.880 --> 42:32.880
Natürlich, wenn wir andersrum gehen würden.

42:33.240 --> 42:38.000
Ich würde hier die Codierung für die 1 zum Beispiel, wenn ich mir die

42:38.000 --> 42:41.280
anschaue und ich würde jetzt in dieser Richtung hier durchlaufen,

42:41.340 --> 42:42.160
hätte ich 0,1.

42:43.800 --> 42:49.040
Ich hätte aber für das Zeichen 6 zum Beispiel, hätte ich ja auch 0,1

42:49.040 --> 42:51.060
als Anfangsstück.

42:52.820 --> 42:58.740
Also der Weg von dem Blatt zur Wurzel, wenn er kurz ist, kann

42:58.740 --> 43:04.220
natürlich ein Anfangsstück sein für den Weg von einem anderen Blatt zu

43:04.220 --> 43:04.740
der Wurzel.

43:06.060 --> 43:08.700
Dann hätte ich auf einmal nicht diese Eigenschaft, diese

43:08.700 --> 43:14.500
Präfixeigenschaft, dass ich kein Präfix eines Codeworts finde, der

43:14.500 --> 43:16.360
selbst ein Codewort ist.

43:17.120 --> 43:23.280
Deswegen muss man das so machen, dass man immer von der Wurzel zu den

43:23.280 --> 43:23.940
Blättern geht.

43:24.800 --> 43:26.600
Können Sie sich gerne selbst nochmal überlegen.

43:27.360 --> 43:28.820
Das ist eine ganz wichtige Eigenschaft.

43:30.640 --> 43:34.620
Diese Huffman-Codierung ist eines der Standardverfahren zur

43:34.620 --> 43:35.360
Datenkompression.

43:35.560 --> 43:39.760
Wenn Sie einen Pfeil zippen, wird zum Beispiel dieses Verfahren

43:39.760 --> 43:40.320
eingesetzt.

43:40.540 --> 43:44.120
Man geht aber manchmal auch noch, macht man noch ein bisschen mehr.

43:44.120 --> 43:48.240
Es gibt noch sowas, das heißt Lempel-Ziff.

43:49.420 --> 43:53.200
Die schauen sich noch an, wie irgendwelche Folgen, also irgendwelche

43:53.200 --> 43:57.620
Buchstabenfolgen vorkommen, wie häufig die sind und dadurch kann das

43:57.620 --> 44:00.420
Ganze dann noch mehr komprimiert werden.

44:01.620 --> 44:05.040
Also das ist das, was Sie machen, wenn Sie eine Datei komprimieren.

44:05.880 --> 44:11.640
Manchmal können die drastisch komprimiert werden, sodass Sie wirklich

44:11.640 --> 44:17.540
nur einen Bruchteil der Größe brauchen und Sie können eindeutig

44:17.540 --> 44:21.540
dekodieren auf das Dokument, das Sie ursprünglich mal gehabt haben.

44:22.740 --> 44:24.600
Damit ist auch dieses Thema schon vorbei.

44:25.640 --> 44:28.360
Wir kommen zu einem weiteren Thema, nämlich der Darstellung von

44:28.360 --> 44:29.640
Zeichen und Ziffern.

44:29.900 --> 44:32.400
Bisher war das etwas allgemein, überhaupt Codierungen.

44:32.400 --> 44:37.000
Und jetzt kommen wir dazu, wie wir eigentlich irgendwelche Texte und

44:37.000 --> 44:39.920
Ziffern darstellen wollen im Rechner.

44:40.840 --> 44:43.920
Das Ganze muss natürlich einige Eigenschaften erfüllen.

44:44.020 --> 44:48.480
Es soll möglichst billig sein, preiswert, nicht billig, preiswert,

44:49.320 --> 44:51.160
kostengünstig.

44:51.880 --> 44:54.360
Also Binär-Codierung, wissen wir, können wir mit Transistoren

44:54.360 --> 44:55.740
darstellen, ist relativ einfach.

44:57.380 --> 44:59.240
Dekodierung muss schnell und einfach sein.

44:59.240 --> 45:02.660
Ich hatte Ihnen mal dargestellt, dass wir zum Beispiel Zahlen auch

45:02.660 --> 45:10.080
durch Carry-Safe-Darstellungen darstellen konnten oder wir konnten

45:10.080 --> 45:15.660
Zahlen durch redundante Zahlendarstellungen darstellen.

45:16.100 --> 45:19.280
Da hatte ich Sie darauf hingewiesen, wenn man dann in die normale

45:19.280 --> 45:22.040
Darstellung geht, ist das relativ aufwendig.

45:22.700 --> 45:27.580
Es ist noch immer maximal linear, aber es ist immer noch etwas, was

45:27.580 --> 45:28.640
ein bisschen Aufwand erfordert.

45:28.640 --> 45:31.840
Codierung und Dekodierung müssen schnell und einfach sein und

45:31.840 --> 45:35.840
Operationen auf den kodierten Wörtern sollen natürlich auch möglichst

45:35.840 --> 45:36.520
einfach sein.

45:36.600 --> 45:40.820
Ich möchte ja addieren, modifizieren, dividieren können, aber sind die

45:40.820 --> 45:42.700
Zahlen irgendwie intern dargestellt?

45:42.840 --> 45:47.180
Operationen darauf müssen schnell und kostengünstig sein.

45:48.220 --> 45:49.660
Und das schauen wir uns dann genauer an.

45:50.180 --> 45:55.740
Was wir darstellen müssen, sind einerseits Texte, zum Beispiel auf

45:55.740 --> 45:58.680
dieser Folie, die wir ziffern und zeichnen.

45:59.540 --> 46:01.800
Wir haben aber manchmal auch irgendwelche Sonderzeichen, wir haben

46:01.800 --> 46:02.720
auch Steuerzeichen.

46:03.540 --> 46:07.220
Wenn ich das hier kodiere, muss ich darstellen, dass ich hier in die

46:07.220 --> 46:08.140
nächste Zeile gehe.

46:08.700 --> 46:12.340
Und zwar hier ganz nach vorne, da nicht ganz nach vorne.

46:13.520 --> 46:15.480
Solche Dinge muss ich auch angeben können.

46:17.900 --> 46:19.440
Also Steuerzeichen sind auch wichtig.

46:19.720 --> 46:22.700
Oder ich muss mal auf eine neue Seite übergehen und so weiter.

46:24.040 --> 46:29.360
Ich mache normalerweise die Darstellung über N-Bit-Codes, also feste

46:29.360 --> 46:30.260
Länge pro Zeichen.

46:31.440 --> 46:36.980
Also nicht häufigkeitsabhängig minimal, sondern ich habe hier eine

46:36.980 --> 46:40.060
redundante Darstellung über N-Bit-Codes.

46:41.320 --> 46:46.440
Und der Zeichenvorrat ist natürlich dann kleiner gleich der Anzahl der

46:46.440 --> 46:52.340
darstellbaren Zeichen über diese Blocklänge N.

46:52.340 --> 46:54.060
Also kleiner gleich 2 hoch N.

46:54.580 --> 46:55.440
Mehr kann ich nicht darstellen.

46:56.240 --> 46:58.760
Jetzt gibt es hier eine ganze Reihe von verschiedenen Kodierungen.

47:00.920 --> 47:03.080
Irgendwelche Zeichen darzustellen, ich hatte Ihnen das schon mal

47:03.080 --> 47:03.500
erwähnt.

47:03.660 --> 47:06.380
Das ist der ASCII-Code, American Standard Code for Information

47:06.380 --> 47:07.100
Interchange.

47:07.620 --> 47:08.840
Das ist ein 7-Bit-Code.

47:11.060 --> 47:14.560
Wenn ich einen 7-Bit-Code betrachte, ist ein Paritäts-Bit noch extra

47:14.560 --> 47:14.840
drin.

47:15.520 --> 47:18.140
Ich kann ihn auch als 8-Bit-Code verwenden.

47:18.890 --> 47:24.140
Dann habe ich 256-Bit darstellbar, genau die doppelte Menge Anzahl.

47:24.580 --> 47:27.340
Wenn wir den 7-Bit-Code nehmen, dann können wir die Zeichen hier in

47:27.340 --> 47:28.480
dieser Tabelle darstellen.

47:29.480 --> 47:34.560
Also zum Beispiel das Zeichen T, das Aufmerksamkeit erreichte, weil

47:34.560 --> 47:39.060
ich zu Beginn auf der Anfangsfolie dieses Kapitels das Zeichen T in

47:39.060 --> 47:43.480
dem Wort Otto mit zwei unterschiedlichen ASCII-Zeichen dort aufgeführt

47:43.480 --> 47:43.760
hatte.

47:43.760 --> 47:49.900
Das muss also beide Male das 101 sein, gefolgt von 0100.

47:50.360 --> 47:56.300
Also die ersten drei Bits, X, geben die Spalte an und die nächsten

47:56.300 --> 48:00.520
vier Bits geben die Zeile an in dieser Darstellung.

48:01.760 --> 48:04.620
Und damit habe ich die Möglichkeit, meine Zeichen darzustellen.

48:04.680 --> 48:05.580
Was sehe ich hier für Zeichen?

48:06.560 --> 48:12.320
Hier in den Spalten 0 und 1 sehe ich nur irgendwelche Steuerzeichen.

48:14.260 --> 48:15.800
Null ist also gar nichts.

48:17.220 --> 48:21.620
Dann habe ich hier zum Beispiel Acknowledgement oder ich habe die

48:21.620 --> 48:26.680
Klingel oder ich habe Line Feed oder ich habe Carriage Return Line

48:26.680 --> 48:30.740
Feed oder ich habe Delete oder was immer Sie hier sehen.

48:30.880 --> 48:35.240
Oder Negative Acknowledge oder ein Synchronize, also verschiedene

48:35.240 --> 48:36.200
Steuerzeichen.

48:37.240 --> 48:40.360
Dann geht es hier los mit den eigentlichen darstellbaren Zeichen.

48:41.060 --> 48:45.560
Mit dem Leerzeichen und dann folgen eine ganze Reihe von auch wieder

48:45.560 --> 48:49.360
Sonderzeichen, die ich brauche, also Interpunktionszeichen, Klammern

48:49.360 --> 48:50.120
und ähnliches.

48:50.620 --> 48:55.200
Dann folgen hier die Ziffern 0 bis 9, danach wieder so ein paar

48:55.200 --> 48:57.520
Vergleichszeichen und ähnliches.

48:58.880 --> 49:06.760
Dann folgen die großen Buchstaben A bis Z und es folgen die kleinen

49:06.760 --> 49:08.660
Buchstaben, auch A bis Z.

49:08.660 --> 49:15.240
Wenn Sie sich das anschauen, dann sehen Sie, Sie haben hier eine feste

49:15.240 --> 49:19.760
Distanz zwischen den Großbuchstaben und den Kleinbuchstaben.

49:20.740 --> 49:26.580
Wenn Sie also ein Codewort haben, eine Ziffernfolge, ein 7-Bit-Zeichen

49:26.580 --> 49:35.400
haben, das ein großes A darstellt, dann addieren Sie einfach 32 und

49:35.400 --> 49:38.980
Sie bekommen daraus eine Zeichenfolge, das ist das kleine A.

49:41.120 --> 49:43.340
Einfach 32 drauf addiert.

49:44.080 --> 49:47.300
Und das geht für alle Zeichen des Alphabets.

49:48.660 --> 49:54.540
Sie können also Folgendes machen, Sie können sagen, ich gehe von A

49:54.540 --> 49:59.180
über B, C bis nach Z durch.

49:59.500 --> 50:02.480
Eine Schleife, die 26 Buchstaben durchläuft.

50:02.480 --> 50:07.620
Das wäre hier einfach, das wären das 26 aufeinanderfolgende Positionen

50:07.620 --> 50:08.120
im Code.

50:08.780 --> 50:14.740
Sie brauchen nur jeweils auf die Darstellung des Zeichens A eins drauf

50:14.740 --> 50:15.160
zu addieren.

50:15.280 --> 50:17.200
Sie sind beim B, C und so weiter.

50:18.620 --> 50:21.220
Sie könnten also diese Zeichen als Laufvariablen nehmen.

50:21.620 --> 50:24.420
Wird in Java nicht gemacht, in Pascal war das alles möglich.

50:25.280 --> 50:28.380
Und da kommt man also über CharacterSets iterieren.

50:29.980 --> 50:31.180
Kein Problem, geht.

50:32.300 --> 50:34.240
Und Sie sehen dann hier noch so ein paar andere Zeichen.

50:34.340 --> 50:39.720
Das sind also die Zeichen, 128 Zeichen, die man mindestens braucht, um

50:39.720 --> 50:44.800
vernünftig Kommunikation zwischen Rechnern machen zu können.

50:46.780 --> 50:48.740
Jetzt gibt es noch einen anderen Code, auch den hatte ich schon

50:48.740 --> 50:54.380
erwähnt, den sogenannten EPSILIC Code, den Extended Binary Coded

50:54.380 --> 50:56.840
Decimal Interchange Code.

50:57.780 --> 51:05.620
Binary Coded Decimal bezieht sich auf diese Zeichen, diese

51:05.620 --> 51:07.360
Dezimalziffern 0 bis 9.

51:08.060 --> 51:09.220
Ganz rechts.

51:10.560 --> 51:12.060
Was hat das F zu bedeuten?

51:12.160 --> 51:17.480
Das ist einfach nur ein Hexadezimal, Abkürzungen für 4-Bit von 0000

51:17.480 --> 51:19.000
bis 1111.

51:19.000 --> 51:26.960
Wenn ich also 1111 habe und dahinter irgendeine 4-Bit-Folge, sind die

51:26.960 --> 51:30.800
4 Bits dahinter die Binärdarstellungen der Ziffern 0 bis 9.

51:32.060 --> 51:33.320
Das ist hier angegeben.

51:34.500 --> 51:42.560
Ich habe also 1111 und dann den Binary Coded Decimal Code für die

51:42.560 --> 51:43.540
Ziffern 0 bis 9.

51:44.060 --> 51:47.320
Die Ziffern oder Zahlen 0 bis 9 einfach binär codiert.

51:48.120 --> 51:50.580
Und die anderen Zeichen sind dann entsprechend angeordnet.

51:50.680 --> 51:55.620
Ich habe hier vorne mit ein paar Lücken wieder die Steuerzeichen drin.

51:56.580 --> 51:59.620
Ich habe dann, Sie sehen, viele Lücken da drin, die gar nicht gefüllt

51:59.620 --> 52:00.000
sind.

52:00.520 --> 52:01.940
Und dann die anderen Zeichen.

52:02.840 --> 52:09.980
Das Interessante ist, wenn Sie hier auf die Codierung von A32

52:09.980 --> 52:12.900
addieren, dann sind Sie dort.

52:14.120 --> 52:15.240
Kein kleines A.

52:16.240 --> 52:23.860
Wenn Sie hier codieren, müssten Sie von dem großen A 4 mal 16

52:23.860 --> 52:24.500
abziehen.

52:27.060 --> 52:28.380
Völlig andere Operation.

52:29.460 --> 52:35.540
Und wenn Sie eine Schleife machen von A bis Z, haben Sie in Ihrem

52:35.540 --> 52:39.520
Programm so geschrieben, dann würden Sie hier alle Codewörter

52:39.520 --> 52:42.760
durchlaufen in dieser Liste.

52:45.240 --> 52:50.360
Also alle Zeichen, alle folgen, wenn Sie immer nur eins addieren, weil

52:50.360 --> 52:53.380
Sie hier keine aufeinanderfolgenden Darstellungen haben.

52:54.340 --> 52:59.820
Das I und das J haben als Codewort einen ziemlichen Abstand.

53:02.180 --> 53:04.640
Bei dem ASCII-Code war der Abstand 1.

53:05.260 --> 53:09.400
Hier ist er 1, 2, 3, 4, 5, 6, 7, 8.

53:10.360 --> 53:12.140
Dann geht es wieder mit Abstand 1 weiter.

53:13.140 --> 53:18.380
Das heißt, man muss wissen, wie die Zeichen in einem Rechner

53:18.380 --> 53:22.720
dargestellt werden, wie sie intern dargestellt werden, um vernünftig

53:22.720 --> 53:25.800
Operationen auf Zeichen ausführen zu können.

53:26.860 --> 53:32.580
Das Dumme ist, dass EBCDIC über langen Zeitraum in IBM-Rechnern

53:32.580 --> 53:33.320
verwendet wurde.

53:34.620 --> 53:38.080
Die meisten anderen Rechnerhersteller haben ASCII verwendet.

53:39.020 --> 53:43.400
Das heißt, Sie müssen dann in Ihren Programmen abfragen, welche Art

53:43.400 --> 53:46.760
Codierung vorgenommen ist, weil Sie dann unterschiedlich Ihre

53:46.760 --> 53:50.960
Funktionen ausführen müssen, sofern die auf Zeichenfolgen arbeiten.

53:52.240 --> 53:55.580
Dass Sie sehen, man muss aufpassen, man muss wissen, wie werden

53:55.580 --> 53:59.920
Zeichen intern dargestellt, weil das halt die Art verändern wird, in

53:59.920 --> 54:01.980
der Sie auf solchen Zeichen arbeiten.

54:03.240 --> 54:08.040
Jetzt möchte man natürlich nicht nur die Zeichen darstellen, die wir

54:08.040 --> 54:10.060
im lateinischen Alphabet haben.

54:11.020 --> 54:14.040
Es gibt ja viele verschiedene Zeichensätze, es gibt die ganzen

54:14.040 --> 54:17.380
asiatischen Zeichensätze, die arabischen Zeichen, es gibt die

54:17.380 --> 54:20.580
chinesischen Zeichen und so weiter, ganz viele.

54:21.920 --> 54:26.800
Jetzt macht man das so, dass man 16 Bit pro Zeichen verwendet in einem

54:26.800 --> 54:32.640
Unicode oder in der Version Unicode 5 oder ab der Version Unicode 5.0

54:32.640 --> 54:39.460
sogar 16 weitere 16-Bit-Bereiche prinzipiell.

54:40.460 --> 54:43.800
Das heißt, Sie können lange Zeichenfolgen verwenden, um die

54:43.800 --> 54:45.260
verschiedenen Zeichen darzustellen.

54:47.080 --> 54:51.660
Und Sie haben hier bis zu eine Million Zeichen zur Verfügung.

54:53.280 --> 54:54.300
Wozu braucht man die?

54:54.980 --> 54:58.940
Ich muss halt Vereinbarungen haben, wie ich die einzelnen Zeichen

54:58.940 --> 54:59.480
darstelle.

54:59.640 --> 55:04.680
Also zum Beispiel habe ich hier vorne irgendwo, da habe ich die

55:04.680 --> 55:08.060
lateinischen Zeichen, also der ASCII-Code ist hier mit eingebettet.

55:09.240 --> 55:13.140
Aber ich habe eben auch einen Bereich, da sind dann irgendwelche

55:13.140 --> 55:15.360
chinesischen Zeichensätze und Ähnliches.

55:15.360 --> 55:22.240
Und wenn ich diesen Code kenne, kann ich also bis auf diesen Code

55:22.240 --> 55:24.720
einzelne Zeichen in andere übersetzen.

55:24.840 --> 55:25.860
Das ist eine Standardisierung.

55:26.560 --> 55:31.440
Auf die Art und Weise kann ich einen chinesischen Text übersetzen in

55:31.440 --> 55:33.380
einen, der in lateinischen Zeichen geschrieben ist.

55:33.440 --> 55:36.260
Ich weiß ja genau, wie die Zeichen jeweils zugeordnet sind.

55:36.880 --> 55:39.100
Natürlich kann ich ihn nicht übersetzen, ich kann aber nur die Zeichen

55:39.100 --> 55:39.780
anders darstellen.

55:39.900 --> 55:43.640
Ich kann kyrillische Buchstaben oder lateinische Buchstaben verwenden.

55:43.640 --> 55:46.800
Ich kenne genau die Darstellung in diesem Code, der ist international

55:46.800 --> 55:47.640
standardisiert.

55:48.000 --> 55:52.240
Auf die Art und Weise kann man global kommunizieren, in verschiedene

55:52.240 --> 55:53.080
Zeichen setzen.

55:54.220 --> 55:58.000
Also das hier war die anfängliche Aufteilung bei nur 16 Bit mit

55:58.000 --> 56:01.200
maximal 2 hoch 16 verschiedenen Zeichen.

56:01.440 --> 56:05.200
Erweitert mittlerweile auf über eine Million Zeichen, sodass man hier

56:05.200 --> 56:10.640
wirklich in der Lage ist, flexibel, unterschiedlich zu kommunizieren.

56:10.640 --> 56:14.960
Wenn Sie mehr darüber wissen wollen, gehen Sie rein in die

56:14.960 --> 56:20.020
entsprechenden Webseiten, www.unicode.org oder auch bei Wikipedia,

56:20.340 --> 56:21.940
finden Sie viele Informationen zu Unicode.

56:24.320 --> 56:25.820
Das zu den Zeichensätzen.

56:27.220 --> 56:29.940
Jetzt wollen wir aber nicht nur Zeichensätze darstellen, wir wollen

56:29.940 --> 56:33.280
nicht nur Textverarbeitung machen, wir wollen rechnen können.

56:33.800 --> 56:34.900
Dazu brauchen wir Ziffern.

56:34.900 --> 56:40.160
Ziffern kann ich darstellen mit ASCII oder EBCDIC, wäre aber etwas

56:40.160 --> 56:46.720
aufwendig, wenn ich 7 oder 8 Bit verwenden müsste, um Ziffern

56:46.720 --> 56:49.480
darzustellen, die ich eigentlich nur 4 Bit maximal brauche.

56:50.580 --> 56:52.720
Also eine 4-Bit-Darstellung reicht aus.

56:53.620 --> 56:56.380
Es gibt deshalb unterschiedliche Codierungen, eine ganze Reihe

56:56.380 --> 56:58.120
verschiedener Ansätze hat man da gemacht.

56:58.120 --> 57:03.220
Der BCD-Code ist der, den ich Ihnen jetzt schon vorgestellt habe, als

57:03.220 --> 57:07.780
Teil von dem EBCDIC-Code, einfach binär dargestellt, 0 bis 9.

57:09.000 --> 57:12.360
Dann gibt es etwas, nennt sich der XS3-Code.

57:12.920 --> 57:18.740
Da addiere ich einfach auf die Codewörter eine 3 drauf, dann geht es

57:18.740 --> 57:25.380
halt von 3 bis binär 12, aber das sind jetzt meine Codewörter für 0

57:25.380 --> 57:25.780
bis 9.

57:28.120 --> 57:32.400
Oder ich verwende noch einen anderen Code, den sogenannten Icon-Code.

57:33.460 --> 57:34.500
Was sehe ich da?

57:36.580 --> 57:42.840
Da habe ich hier noch das gleiche, 0, 1, 2, 3, 4, 5.

57:44.120 --> 57:46.300
Und dann geht es auf einmal anders weiter.

57:46.720 --> 57:51.640
Dann zähle ich zurück, das ist hier die 9, die 8, die 7, die 6.

57:54.820 --> 57:57.780
Hier, da habe ich zurückgezählt, 6 und 5.

57:57.900 --> 58:01.500
Also 0 bis 4, das ist der eine Teil, da geht es in diese Richtung und

58:01.500 --> 58:03.140
hier zähle ich runter.

58:05.340 --> 58:06.900
Vom maximalen Codewort.

58:07.940 --> 58:11.880
Wenn Sie jetzt natürlich irgendwelche Codewörter hier addieren,

58:13.360 --> 58:18.520
numerisch, als Binärzahlen addieren, also wenn Sie jetzt 2 und 3

58:18.520 --> 58:20.980
addieren, müsste 5 rauskommen.

58:20.980 --> 58:25.280
Aber das codierte Wort für die 5 sieht halt anders aus.

58:26.420 --> 58:30.200
Das heißt, da muss man aufpassen mit den Operationen, die ausgeführt

58:30.200 --> 58:30.460
werden.

58:31.180 --> 58:33.260
Dann gibt es noch andere Codierungen, bei denen man jetzt sagt, ich

58:33.260 --> 58:34.080
mache das redundant.

58:35.020 --> 58:37.280
Ein sogenannter 2-aus-5-Code, 5-Bit.

58:38.020 --> 58:41.080
Da habe ich also die Möglichkeit, Fehler zu erkennen oder zu

58:41.080 --> 58:41.660
korrigieren.

58:42.260 --> 58:47.000
Hier sind in jeder 5-Bit-Folge 2 Bits, gerade gleich 1.

58:48.660 --> 58:57.400
Und damit können Sie jetzt die 10 verschiedenen Ziffern eindeutig

58:57.400 --> 58:57.860
darstellen.

58:57.940 --> 59:01.120
Auch hier muss man aufpassen, wie geht das eigentlich da mit der

59:01.120 --> 59:01.820
Arithmetik.

59:02.660 --> 59:06.140
Das ist hier nochmal ein bisschen weiter dargestellt.

59:06.260 --> 59:09.080
BCD-Codierung habe ich Ihnen schon gesagt, die Eigenschaften habe ich

59:09.080 --> 59:10.380
Ihnen alle dargestellt.

59:10.720 --> 59:14.680
Ich habe hier eine einfache Stellenwertigkeit, 2 hoch 0, 2 hoch 1 bis

59:14.680 --> 59:15.360
2 hoch 3.

59:16.260 --> 59:17.700
Bei X ist 3.

59:18.560 --> 59:22.520
Ebenfalls relativ einfach, schöne Eigenschaften.

59:22.600 --> 59:28.100
Also ich kann natürlich hier problemlos arithmetische Operationen

59:28.100 --> 59:28.540
ausführen.

59:28.640 --> 59:32.180
Ich muss ja nur dieses plus 3 jeweils dort berücksichtigen.

59:33.000 --> 59:37.060
Ich weiß zum Beispiel, wenn ich einen sogenannten Burstfehler habe,

59:38.000 --> 59:41.840
dass ich eine Folge habe von nur Nullen oder nur Einsen, wenn ich 4

59:41.840 --> 59:44.360
Nullen habe oder 4 Einsen, das sind keine gültigen Ziffern.

59:44.360 --> 59:47.220
Das heißt, ich kann solche Burstfehler sofort erkennen.

59:48.120 --> 59:51.680
Die treten also häufig als Fehler auf in der Realität.

59:52.200 --> 59:56.620
Ich habe aber keine Stellenwertigkeit, muss also aufpassen, wie ich

59:56.620 --> 59:58.260
hier mit umgehe.

59:59.180 --> 01:00:03.040
Aber so Vergleichseigenschaften, wenn ich nur wissen will, ob ein Wort

01:00:03.040 --> 01:00:06.400
größer oder eine Ziffer größer ist als die andere, kann ich mit der

01:00:06.400 --> 01:00:08.380
XS3 -Codierung ganz einfach machen.

01:00:09.260 --> 01:00:15.900
Icon-Codierung hat eine etwas erstaunliche Stellenwertigkeit, 2, 4, 2,

01:00:16.040 --> 01:00:21.660
1 und ist also auch interessant, ist symmetrisch, aber Sie hatten

01:00:21.660 --> 01:00:25.560
gesehen, für die Ziffern von 5 bis 9 haben wir hier die Werte

01:00:26.640 --> 01:00:30.860
Binärdarstellung plus 6, nur für die ersten 0 bis 4 habe ich genau die

01:00:30.860 --> 01:00:31.500
Binärdarstellung.

01:00:32.400 --> 01:00:36.880
Und bei der 2 aus 5-Codierung, da habe ich halt genau die 10

01:00:36.880 --> 01:00:40.750
verschiedenen Codewörter, wenn ich 2 aus 5 Bits auf 1 setze,

01:00:40.990 --> 01:00:41.910
ausgenutzt.

01:00:42.590 --> 01:00:45.430
Hier auf eine Art und Weise gemacht, sodass Sie durchaus eine

01:00:45.430 --> 01:00:46.670
Stellenwertigkeit haben.

01:00:47.590 --> 01:00:51.690
7, 4, 2, 1, 0, also keine Zweierpotenzen, beziehungsweise nur hier

01:00:51.690 --> 01:00:55.450
keine Zweierpotenz und da auch noch eine 0 als Stellenwertigkeit, das

01:00:55.450 --> 01:00:56.550
heißt dieses Bit ist redundant.

01:00:58.350 --> 01:00:59.630
Aber eben nicht vollständig.

01:01:00.830 --> 01:01:03.890
Hat für Fehlereigenschaften Vorteile, für die Arithmetik ist es nicht

01:01:03.890 --> 01:01:04.550
ganz so günstig.

01:01:05.610 --> 01:01:08.370
Und damit sind wir auch durch die Zifferndarstellung durch und jetzt

01:01:08.370 --> 01:01:12.430
kommen wir schon zu dem nächsten Teil, dass wir uns mit Zahlen,

01:01:12.690 --> 01:01:13.970
Zahlendarstellung beschäftigen.

01:01:14.010 --> 01:01:15.350
Wie können wir eigentlich Zahlen darstellen?

01:01:16.170 --> 01:01:18.310
Wir haben das gerade eben schon gemerkt, wir wissen, wie wir

01:01:18.310 --> 01:01:19.990
Dualzahlen verwenden können.

01:01:20.470 --> 01:01:24.310
Das kennen Sie alles aus der Grundschule oder aus der vielleicht

01:01:24.310 --> 01:01:26.110
ersten Klassen der weiterführenden Schule.

01:01:29.810 --> 01:01:32.710
Das Dezimalsystem ist halt nicht immer gut geeignet, weil wir da zu

01:01:32.710 --> 01:01:34.590
viele verschiedene Ziffern darstellen müssen.

01:01:35.670 --> 01:01:39.010
Und es gibt diese binärdezimale Codierung, Binary Coded Decimal, das

01:01:39.010 --> 01:01:40.050
habe ich Ihnen schon vorgestellt.

01:01:42.330 --> 01:01:46.770
Hierbei ist es so, dass die Eigenschaften, die ich gesagt habe, die

01:01:46.770 --> 01:01:49.710
sind hier erfüllt, das ist technisch einfach zu realisieren.

01:01:51.630 --> 01:01:56.290
Die sind nah zum Dezimalsystem, sind aber eben leider etwas redundant,

01:01:56.530 --> 01:01:58.530
ich brauche mehr Bits als unbedingt erforderlich.

01:01:59.750 --> 01:02:04.630
Und Arithmetik ist relativ leicht, wir werden aber diese spezielle

01:02:04.630 --> 01:02:05.830
Codierung nicht weiterverwenden.

01:02:06.310 --> 01:02:11.250
Wir nehmen allgemein das Dualsystem mit gewissen Varianten.

01:02:11.250 --> 01:02:15.670
Und die Frage ist, was ich eigentlich darstellen möchte.

01:02:16.350 --> 01:02:22.510
Habe ich ganze Zahlen, natürliche Zahlen, rationale Zahlen, reelle

01:02:22.510 --> 01:02:23.070
Zahlen?

01:02:23.450 --> 01:02:25.930
Kann ich eigentlich beliebige reelle Zahlen darstellen?

01:02:27.330 --> 01:02:29.010
Also wie sieht das aus mit der Genauigkeit?

01:02:29.190 --> 01:02:31.110
Ich habe ja nur eine bestimmte Anzahl von Bits.

01:02:31.110 --> 01:02:38.850
Sie kennen Zahl Pi oder viele verschiedene Zahlen, Zahl E oder sowas,

01:02:39.010 --> 01:02:45.050
die zeichnen sich dadurch aus, dass sie nicht rational dargestellt

01:02:45.050 --> 01:02:47.990
werden können, das heißt es sind irrationale Zahlen, jede irrationale

01:02:47.990 --> 01:02:51.870
Zahl ist nur durch eine unendliche Folge von Dezimalziffern

01:02:51.870 --> 01:02:52.510
darstellbar.

01:02:53.710 --> 01:02:56.050
Das heißt, wenn Sie unendlich viele Bits verwenden, können Sie die gar

01:02:56.050 --> 01:02:56.630
nicht darstellen.

01:02:57.450 --> 01:02:59.570
Genauigkeit ist also hier ein wichtiger Punkt.

01:03:00.510 --> 01:03:02.850
Und da muss ich mich damit beschäftigen, wie das aussieht mit

01:03:02.850 --> 01:03:03.730
Rundungsfehlern.

01:03:05.130 --> 01:03:10.030
Eigentlich müsste meine Zahl so viele Bits haben, ich habe aber nur 32

01:03:10.030 --> 01:03:10.770
Bits zur Verfügung.

01:03:11.730 --> 01:03:14.750
Was mache ich hier mit dem ganzen Teil, der da hinten ist, der Rest,

01:03:14.910 --> 01:03:15.870
der nicht berücksichtigt wird?

01:03:16.350 --> 01:03:17.870
Wie beeinflusst das meine Berechnung?

01:03:18.770 --> 01:03:21.710
Damit muss man sich beschäftigen, das muss einem klar sein, wie das

01:03:21.710 --> 01:03:22.170
funktioniert.

01:03:22.810 --> 01:03:26.010
Und ich muss mir anschauen, wie ich Operationen ausführen kann.

01:03:26.010 --> 01:03:31.350
Also ich möchte zwei Zahlen meinetwegen addieren, das kann ich direkt

01:03:31.350 --> 01:03:31.670
machen.

01:03:32.810 --> 01:03:36.230
Und ich kann mir dann anschauen, welche Auswirkungen haben die

01:03:36.230 --> 01:03:36.770
Codierungen.

01:03:37.330 --> 01:03:40.450
Wenn ich im Rechner das mache, muss ich die beiden Zahlen x und y

01:03:40.450 --> 01:03:41.650
intern darstellen.

01:03:42.070 --> 01:03:45.590
Eine Operation ausführen, die an diese interne Darstellung angepasst

01:03:45.590 --> 01:03:45.870
ist.

01:03:46.510 --> 01:03:50.810
Und dann bekomme ich hier einen Wert heraus, der hoffentlich der

01:03:50.810 --> 01:03:54.230
gleiche ist, als wenn ich diesen Weg gegangen wäre.

01:03:54.230 --> 01:03:59.790
Solch ein Diagramm, bei dem ich ein gewünschtes Ziel auf verschiedene

01:03:59.790 --> 01:04:03.050
Art und Weise erreichen kann, nennt man auch ein kommutatives

01:04:03.050 --> 01:04:04.150
Diagramm.

01:04:04.530 --> 01:04:08.690
Also dieses Diagramm soll kommutieren, die Reihenfolge der beiden

01:04:08.690 --> 01:04:12.170
Pfeile hier, erst die Operation und dann die Codierung oder erst

01:04:12.170 --> 01:04:14.930
Codierung und dann die Operation, soll egal sein.

01:04:15.670 --> 01:04:19.850
Das muss ich für alle relevanten Funktionen oder Operationen hier

01:04:19.850 --> 01:04:23.850
gewährleisten, dass mein Code das erfüllt, beziehungsweise ich muss

01:04:23.850 --> 01:04:28.470
wissen, für welche Werte ich hier Probleme kriegen würde.

01:04:29.710 --> 01:04:33.510
Also wie muss diese Operation gestaltet werden, sodass das Diagramm

01:04:33.510 --> 01:04:34.130
kommutiert?

01:04:34.550 --> 01:04:36.350
Und das schauen wir uns im Weiteren genauer an.

01:04:37.090 --> 01:04:39.730
Das Einfachste sind die natürlichen Zahlen, die kann ich als

01:04:39.730 --> 01:04:40.930
Dualzahlen darstellen.

01:04:41.450 --> 01:04:46.370
Also mit n bits kann ich eine sogenannte C2n-Darstellung wählen, eine

01:04:46.370 --> 01:04:49.670
Darstellung zur Basis 2 mit n bits.

01:04:49.670 --> 01:04:54.050
Das ist genau die Dualdarstellung, stellenwertig hingeschrieben.

01:04:54.570 --> 01:05:08.990
Also hier die Zahl 17 wäre in dem Fall die 16 plus 1 und die Zahl 7

01:05:08.990 --> 01:05:13.230
ist gerade 4 plus 2 plus 1.

01:05:13.990 --> 01:05:19.230
Wenn ich die beiden addiere, kommt hier entsprechend 0, 1, 1, 0, 1

01:05:19.230 --> 01:05:19.630
raus.

01:05:20.570 --> 01:05:26.210
Und das ist natürlich auch wieder eine Zahl, Entschuldigung, ich

01:05:26.210 --> 01:05:28.350
addiere hier nicht, ich subtrahiere.

01:05:29.810 --> 01:05:36.810
1 minus 1 ist 0, dann habe ich einen Übertrag, 0 bis 0 ist, nochmal, 1

01:05:36.810 --> 01:05:39.210
bis 1 ist 0, kein Übertrag.

01:05:39.210 --> 01:05:49.750
1 bis 0 ist 1, Übertrag ist 1, also 0 bis 0 ist 0, Übertrag 1

01:05:49.750 --> 01:05:50.430
rübergenommen.

01:05:51.670 --> 01:05:57.470
1 bis 0 ist 1, Übertrag 1, 1 bis 1 ist 0.

01:05:58.390 --> 01:06:02.110
Das war also die Subtraktion der 7 von der 17, es kommt eine Zahl

01:06:02.110 --> 01:06:03.850
raus, das ist gerade die Zahl 10.

01:06:06.430 --> 01:06:11.970
Wenn ich die Zahl multipliziere, hier angegeben, da fehlt noch ein

01:06:11.970 --> 01:06:12.410
bisschen was.

01:06:13.650 --> 01:06:20.070
Hier habe ich, da war in der Folie, die Sie wahrscheinlich vor sich

01:06:20.070 --> 01:06:22.370
liegen haben, ein kleiner Fehler, ich weiß nicht, wie das passiert

01:06:22.370 --> 01:06:22.690
ist.

01:06:22.690 --> 01:06:28.130
Hier gehe ich mal davon aus, dass ich diese Bits verwende, um

01:06:28.130 --> 01:06:36.390
festzustellen, also einmal dieser Wert, einmal der Wert um 1

01:06:36.390 --> 01:06:39.550
verschoben und dann dreimal mit der 0 multipliziert.

01:06:40.150 --> 01:06:45.250
Wenn ich die jetzt aufaddiere, in dieser üblichen Art, wie man jetzt

01:06:45.250 --> 01:06:50.710
eine solche Multiplikation hinschreiben kann, dann habe ich hier ein

01:06:50.710 --> 01:07:00.790
Ergebnis und dieses Ergebnis hat natürlich nicht nur 5 Bit, sondern es

01:07:00.790 --> 01:07:03.190
hat entsprechend mehr, es müsste 10 Bits haben.

01:07:05.310 --> 01:07:09.390
1, 2, 3, 4, 5, 6, 7, 8, hat 9 Bit.

01:07:09.910 --> 01:07:11.510
Das habe ich mir irgendwo verzählt, ist egal.

01:07:11.510 --> 01:07:17.170
Also ich habe jedenfalls diese einfache Art und Weise, wie ich diese

01:07:17.170 --> 01:07:27.510
Zahlen multipliziere und ich habe aber eben als Ergebnis, jetzt eine

01:07:27.510 --> 01:07:32.190
Zahl in dem Fall, habe ich natürlich hier ein Ergebnis, das ich noch

01:07:32.190 --> 01:07:33.530
mit 5 Bit darstellen kann.

01:07:34.490 --> 01:07:38.550
Aber wenn ich größere Zahlen gehabt hätte, dann wäre das Ergebnis

01:07:38.550 --> 01:07:40.430
nicht mehr mit 5 Bit darstellbar gewesen.

01:07:40.430 --> 01:07:43.750
Das heißt, der Zahlenbereich kann überschritten werden, das muss ich

01:07:43.750 --> 01:07:48.610
beachten, wenn ich mit solchen Zahlen im Rechner arbeite.

01:07:49.050 --> 01:07:55.110
Bereichsüberschreitungen können zu Fehlern führen und damit muss man

01:07:55.110 --> 01:07:55.790
darauf aufpassen.

01:07:56.850 --> 01:08:01.450
Jetzt will ich im Rechner nicht nur natürliche Zahlen darstellen,

01:08:02.270 --> 01:08:05.610
sondern auch ganze Zahlen, bei denen ich negative Werte habe.

01:08:06.350 --> 01:08:09.170
Gerade eben waren nur positive Werte da, aber jetzt will ich auch mal

01:08:09.170 --> 01:08:10.650
negative Werte darstellen können.

01:08:11.170 --> 01:08:14.770
Also ich brauche einen Zahlenbereich mit negativen Werten und mit

01:08:14.770 --> 01:08:15.610
positiven Werten.

01:08:16.550 --> 01:08:18.470
Und die Frage ist, wie teile ich das auf?

01:08:18.710 --> 01:08:21.830
Es ist naheliegend, ich möchte jede positive Zahl einfach negieren

01:08:21.830 --> 01:08:23.910
können, negativ machen können.

01:08:24.970 --> 01:08:29.890
Das heißt, es sollen möglichst gleich viele negative wie positive

01:08:29.890 --> 01:08:30.890
Zahlen da sein.

01:08:32.210 --> 01:08:38.950
Das heißt, ich kann genau die Hälfte der verfügbaren Zahlen als

01:08:38.950 --> 01:08:40.450
positive Zahlen darstellen.

01:08:41.610 --> 01:08:44.930
Deswegen fordern wir normalerweise, dass das Ganze symmetrisch zum

01:08:44.930 --> 01:08:45.730
Nullpunkt ist.

01:08:47.310 --> 01:08:51.170
Wir haben aber eine gerade Zahl von Werten normalerweise.

01:08:51.170 --> 01:08:56.510
Wenn wir eine N-Bit-Darstellung haben, hätten wir zwei Hoch-N-Werte.

01:08:58.210 --> 01:09:02.990
Wir haben aber die Null und dann einen bestimmten Anteil positiver,

01:09:03.270 --> 01:09:04.390
also Nicht-Null-Werte.

01:09:05.110 --> 01:09:07.330
Und dann haben wir noch eine Reihe negative Werte.

01:09:09.090 --> 01:09:12.290
Und wir haben offensichtlich nicht genau zum Nullpunkt symmetrisch

01:09:12.290 --> 01:09:18.130
hier unsere Darstellung, sondern es wird wahrscheinlich eine Zahl

01:09:18.130 --> 01:09:21.990
vielleicht mehr positiv sein als negativ oder umgekehrt.

01:09:22.890 --> 01:09:26.070
Und ich muss erreichen, dass arithmetische Operationen auf den

01:09:26.070 --> 01:09:28.070
codierten Zahlen leicht zu realisieren sind.

01:09:28.710 --> 01:09:30.890
Das kann man auf viele verschiedene Arten machen.

01:09:31.450 --> 01:09:37.730
Die einfachste Art ist, hier vorne ein Vorzeichen zu nehmen, Null oder

01:09:37.730 --> 01:09:38.130
Eins.

01:09:38.130 --> 01:09:42.230
Und ich nehme einfach dieses Bit mal Minus Eins.

01:09:43.270 --> 01:09:44.790
Null mal Minus Eins ist Null.

01:09:46.990 --> 01:09:59.730
Einmal Minus Eins ist Minus Eins.

01:09:59.730 --> 01:10:06.390
Ich habe dann hier das Vorzeichen dargestellt, also Null entspricht

01:10:06.390 --> 01:10:10.710
positiv, Eins entspricht negativen Zeichen.

01:10:10.970 --> 01:10:15.110
Ich sage auch Minus Eins hoch Null oder Minus Eins hoch Eins.

01:10:16.910 --> 01:10:18.730
So, der Betrag der Zahl.

01:10:19.390 --> 01:10:21.750
Dann kann ich eine sogenannte XSQ-Darstellung nehmen.

01:10:21.850 --> 01:10:24.750
Was habe ich bei der XSQ-Darstellung, wenn ich mir das jetzt anschaue?

01:10:24.750 --> 01:10:26.910
Wir hatten noch unseren Zahlenstrahl.

01:10:28.170 --> 01:10:32.350
Jetzt würde also bei der XSQ-Darstellung, wir haben hier den

01:10:32.350 --> 01:10:35.330
Zahlenstrahl, die Null und dann haben wir hier unseren Zahlenbereich.

01:10:36.290 --> 01:10:39.750
Da können wir mit einer XSQ-Darstellung zum Beispiel dafür sorgen,

01:10:40.330 --> 01:10:44.690
wenn das hier die Null war, dass dieser ganze Bereich einfach nach

01:10:44.690 --> 01:10:47.250
rechts geschoben wird, wenn hier die Null ist.

01:10:47.250 --> 01:10:50.930
Dann nehme ich einfach die ganzen Zahlen hier, diese Zahlen und habe

01:10:50.930 --> 01:10:58.870
jetzt nur noch Codewörter von Null bis doppelte Größe bei diesem

01:10:58.870 --> 01:10:59.570
Bereich hier.

01:11:00.270 --> 01:11:04.090
Und ich habe jetzt hier die negativen und da die positiven Zahlen.

01:11:07.210 --> 01:11:10.650
Das ist also eine Art, wie ich jetzt sagen kann, mit den

01:11:10.650 --> 01:11:17.810
Zeichenfolgen, mit dem geringsten Wert nur die Null bis zu dem größten

01:11:17.810 --> 01:11:23.570
Wert 2 hoch N, stelle ich gerade 2 hoch N halbe negative und 2 hoch N

01:11:23.570 --> 01:11:24.970
halbe positive Zahlen dar.

01:11:25.550 --> 01:11:27.970
Und die negativen sind kleiner als die positiven.

01:11:31.010 --> 01:11:33.870
Und es gibt eine Möglichkeit, eine Komplementdarstellung zu wählen.

01:11:33.930 --> 01:11:34.430
Was ist das?

01:11:34.830 --> 01:11:35.870
Eine Komplementdarstellung.

01:11:37.330 --> 01:11:41.970
Da verwende ich natürlich auch wieder die Hälfte der Codewörter für

01:11:41.970 --> 01:11:45.430
die Darstellung von negativen Zahlen, die andere Hälfte für positive

01:11:45.430 --> 01:11:45.930
Zahlen.

01:11:46.630 --> 01:11:51.410
Und ich mache folgendes, dass ich sage, zu einer Zahl X, die hier

01:11:51.410 --> 01:11:57.090
binär dargestellt wird, als Dualzahl, ist die negative Zahl, gerade

01:11:57.090 --> 01:12:03.750
das Komplement, bezüglich einer größeren Zahl K und ich subtrahiere

01:12:03.750 --> 01:12:06.090
einfach das X von diesem K.

01:12:07.570 --> 01:12:14.390
Im Prinzip war die Darstellung in dem Icon-Code genau das für die

01:12:14.390 --> 01:12:15.670
Dezimalziffern.

01:12:17.270 --> 01:12:20.890
So ähnlich, auch eine Art Komplementdarstellung.

01:12:21.370 --> 01:12:25.830
Die ersten 5, die letzten 5, so artkomplementär dargestellt.

01:12:26.570 --> 01:12:32.510
Hier haben wir die Hälfte, da wäre also in der Regel K halbe und hier

01:12:32.510 --> 01:12:37.510
würden wir also alle Zeichen von 0 bis K halbe positiv darstellen,

01:12:37.510 --> 01:12:40.870
dann haben wir hier die positiven Zahlen und hier die negativen.

01:12:42.090 --> 01:12:48.670
Wenn Sie jetzt in der Dualdarstellung einer Zahl vergleichen, den

01:12:48.670 --> 01:12:53.350
Dualwert einer Zahl, die hier liegt, mit einer Zahl, die da liegt, ist

01:12:53.350 --> 01:12:55.910
einmal die negative größer als die positive.

01:12:56.070 --> 01:12:58.390
Das darf natürlich nicht sein, das muss man beachten.

01:12:58.390 --> 01:13:01.930
Ich muss also aufpassen, welche Darstellung ich nehme.

01:13:02.530 --> 01:13:05.530
Die Komplementdarstellung, werden wir gleich sehen, hat durchaus

01:13:05.530 --> 01:13:07.390
einige interessante Eigenschaften.

01:13:10.050 --> 01:13:14.010
Also hier haben wir, ach, ich habe K halbe nicht genau getroffen, wie

01:13:14.010 --> 01:13:14.350
Sie sehen.

01:13:15.610 --> 01:13:20.210
So, positiv, negativ und deswegen haben wir hier eine grundsätzlich

01:13:20.210 --> 01:13:22.790
andere Darstellung als bei der XSQ-Darstellung.

01:13:25.130 --> 01:13:28.890
Sie werden gleich sehen, welche Folgen das hat für die Verwendung

01:13:28.890 --> 01:13:29.610
solcher Zahl.

01:13:29.690 --> 01:13:33.630
Eine wichtige Folge ist halt, wenn ich nur Werte vergleichen möchte,

01:13:34.670 --> 01:13:37.010
hat die XSQ-Darstellung deutliche Vorteile.

01:13:38.850 --> 01:13:42.450
Ansonsten werden Sie feststellen, dass hier die Komplementdarstellung

01:13:42.450 --> 01:13:43.770
auch einige Vorteile hat.

01:13:44.670 --> 01:13:46.890
Wir werden uns die jetzt genauer angucken, die sogenannte

01:13:46.890 --> 01:13:50.470
Zweikomplementdarstellung und die Einskomplementdarstellung.

01:13:51.470 --> 01:13:55.710
Bei der Zweikomplementdarstellung ist das Komplement K nicht K,

01:13:55.810 --> 01:13:57.050
sondern 2 hoch N.

01:13:58.630 --> 01:14:08.350
Also, ich habe eine N-Bit-Darstellung und ich stelle meine Zahlen

01:14:08.350 --> 01:14:16.090
jetzt entweder da als positive Zahl oder als Komplement zu 2 hoch N.

01:14:20.930 --> 01:14:28.650
Also, der Wert von X für eine negative Zahl, wenn die Zahl also

01:14:28.650 --> 01:14:33.110
negativ ist, addiere ich sie zu 2 hoch N, das heißt, ich ziehe den

01:14:33.110 --> 01:14:38.790
Betrag von X ab, also die Darstellung der negativen Zahlen und

01:14:38.790 --> 01:14:40.630
ansonsten ist es einfach die Dualdarstellung.

01:14:43.250 --> 01:14:49.070
Das heißt, wenn wir uns jetzt hier K-Halbe anschauen, K-Halbe ist dann

01:14:49.070 --> 01:14:56.010
ja gerade 2 hoch N-1 und 2 hoch N-1 ist eine Zahl, bei der das

01:14:56.010 --> 01:14:57.530
führende Bit eine 1 ist.

01:14:58.190 --> 01:15:02.930
Das heißt, alle Zahlen, die negativ sind, haben hier vorne eine 1

01:15:02.930 --> 01:15:03.190
stehen.

01:15:03.190 --> 01:15:09.050
Das war das Gleiche wie bei der Darstellung mit Vorzeichenbetrag, aber

01:15:09.050 --> 01:15:12.650
hier eben etwas anders.

01:15:13.930 --> 01:15:19.030
Hier bezieht sich das auf diese Arten der Komplementdarstellung.

01:15:21.710 --> 01:15:27.010
Und für die positiven Zahlen ist natürlich das Bit N-1 gleich 0, für

01:15:27.010 --> 01:15:31.710
die negativen Zahlen ist es gleich 1 und jetzt können Sie problemlos

01:15:31.710 --> 01:15:33.770
sich einen Wert ausrechnen.

01:15:34.350 --> 01:15:41.910
Sie brauchen also nur das erste Bit zu nehmen, BN-1, multiplizieren

01:15:41.910 --> 01:15:44.450
das mit 2 hoch N-1 und ziehen den Wert ab.

01:15:45.950 --> 01:15:52.710
Und das, was dahinter steht, ist dann gerade der restliche Wert, BI

01:15:52.710 --> 01:15:58.110
mal 2 hoch I ergibt Ihnen gerade dann insgesamt den Wert Ihrer Zahl X.

01:15:58.110 --> 01:16:01.650
Das ist entweder negativ, wenn Sie das hier vorne abgezogen haben,

01:16:01.950 --> 01:16:03.190
oder es ist ein positiver Wert.

01:16:03.830 --> 01:16:05.630
Das folgt einfach sofort aus dieser Darstellung.

01:16:07.570 --> 01:16:12.150
Hier haben wir ein Beispiel, für N gleich 4 haben wir 16 verschiedene

01:16:12.150 --> 01:16:13.930
Zahlen, die wir darstellen können.

01:16:14.850 --> 01:16:19.530
Also 8 Zahlen können wir darstellen positiv und 8 negativ.

01:16:19.530 --> 01:16:28.190
Wir haben für die Zahlen 0 bis 7, in dem Fall von 0,0,0 bis 0,1,1,1.

01:16:28.590 --> 01:16:33.650
Und dann kommt die minus 1, minus 2 bis minus 8, gehen entsprechend so

01:16:33.650 --> 01:16:33.970
weiter.

01:16:34.550 --> 01:16:42.350
Also die minus 1 ist halt 2 hoch 4 minus 1.

01:16:43.370 --> 01:16:48.250
Das ist 2 hoch 3 plus 2 hoch 2 plus 2 hoch 1 plus 2 hoch 0.

01:16:49.690 --> 01:16:53.070
Und entsprechend geht es hier weiter runter, minus 1, minus 2 bis

01:16:53.070 --> 01:16:53.590
minus 8.

01:16:54.890 --> 01:17:03.350
Also in dem Fall haben Sie hier die 0, 1, 2 und so weiter bis 7.

01:17:04.850 --> 01:17:10.070
Und dann geht es hier weiter mit, da haben Sie die minus 1, minus 2

01:17:10.070 --> 01:17:12.230
und so weiter bis minus 8.

01:17:13.070 --> 01:17:17.330
Das heißt, das Folgen hier auf die 7 folgt die minus 8 in der

01:17:17.330 --> 01:17:18.470
Dualdarstellung.

01:17:20.910 --> 01:17:23.290
Jetzt schauen wir uns das nochmal genauer an, wie die Beziehungen

01:17:23.290 --> 01:17:23.930
eigentlich aussehen.

01:17:24.010 --> 01:17:29.250
Wie finde ich zu einer Zahl die Darstellung der negativen Zahl?

01:17:29.690 --> 01:17:36.530
Ich möchte also das Komplement bilden und jetzt mache ich einen

01:17:36.530 --> 01:17:39.310
kleinen Trick.

01:17:40.410 --> 01:17:43.950
Ich schreibe hier, also das Komplement wird hier gebildet durch 2 hoch

01:17:43.950 --> 01:17:46.590
n minus x, wenn x ein positiver Wert ist.

01:17:47.890 --> 01:17:51.710
Jetzt schreibe ich einfach 2 hoch n minus 1 minus x plus 1.

01:17:52.370 --> 01:17:54.250
Das ist der gleiche Wert am Ende.

01:17:55.430 --> 01:17:59.810
Wenn ich das jetzt einfach hinschreibe in binärer Kodierung, dann

01:17:59.810 --> 01:18:05.030
steht hier die binäre Kodierung von 2 hoch n minus 1, davon ziehe ich

01:18:05.030 --> 01:18:10.630
die binäre Kodierung von x ab und darauf addiere ich die binäre

01:18:10.630 --> 01:18:11.730
Kodierung von 1.

01:18:13.810 --> 01:18:17.630
Das heißt, die binäre Kodierung von 2 hoch n minus 1 ist gerade eine

01:18:17.630 --> 01:18:18.570
Folge von Einsen.

01:18:19.530 --> 01:18:24.470
Davon ziehe ich, das heißt ich habe hier eine Folge von Einsen und

01:18:24.470 --> 01:18:33.490
davon ziehe ich jetzt bn minus 1, bn minus 2 und so weiter b1, b0 ab.

01:18:35.930 --> 01:18:41.990
Das heißt, wenn ich das abziehe, dann kippt praktisch jedes Bit.

01:18:42.250 --> 01:18:48.470
1 minus 1 gibt 0, 1 minus 0 gibt 1.

01:18:49.250 --> 01:18:56.570
Das heißt, ich habe hier einfach nur alle Bits meiner Zahl x zu kippen

01:18:56.570 --> 01:19:00.170
und anschließend addiere ich eine 1.

01:19:01.710 --> 01:19:07.710
Das ist also eine sehr einfache Art, wie ich das ausführen kann.

01:19:09.470 --> 01:19:12.850
Also ich brauche nur am Ende nochmal eine 1 drauf zu addieren.

01:19:12.950 --> 01:19:14.570
Ich kippe die Bits und addiere eine 1.

01:19:15.950 --> 01:19:21.570
Nur zur klaren Aussage, die Definition des Zweierkomplements ist

01:19:21.570 --> 01:19:26.010
nicht, alle Bits kippen und eine 1 addieren, sondern die Definition

01:19:26.010 --> 01:19:29.990
des Zweierkomplements ist, ich habe hier meinen Zahlenstrahl, mache

01:19:29.990 --> 01:19:32.870
ein Komplement und das k ist gerade 2 hoch n.

01:19:33.990 --> 01:19:40.130
Und zu einem x habe ich hier also k minus x als Komplement.

01:19:40.710 --> 01:19:41.710
Das ist das Zweierkomplement.

01:19:42.010 --> 01:19:48.630
Und die Eigenschaften dieser Zahl 2 hoch n führen dazu, wenn ich von 2

01:19:48.630 --> 01:19:51.270
hoch n den Wert abziehe, ist es das Gleiche, als wenn ich einfach nur

01:19:51.270 --> 01:19:52.830
alle Bits kippe und eine 1 addiere.

01:19:53.750 --> 01:19:58.770
Dann kann ich die ganzen Code-Wörter, ich könnte Code-Wörter sagen,

01:19:58.870 --> 01:20:02.390
man redet aber hier einfach von dem Zahlenraum, oder den codierten

01:20:02.390 --> 01:20:04.910
Zahlen, die ich bekomme, die kann ich jetzt in so einem Ring

01:20:04.910 --> 01:20:11.150
darstellen und damit habe ich jetzt eine Reihe schöner Eigenschaften.

01:20:11.630 --> 01:20:15.270
Man stellt sofort fest, wenn ich zweimal Komplement bilde, dann habe

01:20:15.270 --> 01:20:16.730
ich wieder die Zahl, die ich haben möchte.

01:20:16.790 --> 01:20:20.010
Das muss natürlich eine Eigenschaft sein, die erfüllt sein muss.

01:20:20.010 --> 01:20:22.490
Doppelt negiert gibt wieder den gleichen Wert.

01:20:24.090 --> 01:20:27.530
Und wenn ich meinetwegen hier irgendetwas addiere, gehe ich immer in

01:20:27.530 --> 01:20:28.150
diese Richtung.

01:20:28.690 --> 01:20:30.790
Wenn ich subtrahiere, gehe ich in diese Richtung.

01:20:31.950 --> 01:20:36.610
Und jetzt gibt es noch eine Reihe weiterer Eigenschaften, die aber

01:20:36.610 --> 01:20:42.230
jetzt, die kann ich Ihnen vielleicht gerade noch darstellen, wenn ich

01:20:42.230 --> 01:20:44.350
Ihnen hier diese Beispiele gebe.

01:20:44.350 --> 01:20:49.470
Also addiert, eine positive Zahl addiert geht in die Richtung.

01:20:50.930 --> 01:20:55.370
Eine negative Zahl addiert geht in die Richtung, im Uhrzeigersinn.

01:20:56.110 --> 01:20:59.210
Wenn ich jetzt zwei Zahlen addiere, zum Beispiel diese beiden hier, 0

01:20:59.210 --> 01:21:06.850
und 1 ist 1, 1 und 1 ist 0, 1 und Übertrag 1 ist 0, 1 und Übertrag 1

01:21:06.850 --> 01:21:11.930
ist 0 und hier kommt dann eine 1 raus.

01:21:14.590 --> 01:21:16.450
1, 0, 0, 0, 1.

01:21:19.870 --> 01:21:21.070
Rauskommen muss eine 1.

01:21:21.450 --> 01:21:22.850
Die 1 hat diese Darstellung.

01:21:23.710 --> 01:21:26.070
Das ist genau diese Darstellung.

01:21:27.270 --> 01:21:29.550
Das heißt, ich kann den Überlauf einfach ignorieren.

01:21:31.330 --> 01:21:33.230
Minus 2, minus 3, was kommt denn daraus?

01:21:33.290 --> 01:21:34.490
Es müsste minus 5 rauskommen.

01:21:35.910 --> 01:21:47.870
1, 1, 0, 1, 1, 0, 1, 1.

01:21:48.630 --> 01:21:57.150
Und Sie sehen, 1, 0, 0, 1, 1, 0, 1, 1, das hier ist die minus 5.

01:21:58.070 --> 01:22:02.470
Überlauf wird einfach ignoriert, das heißt, ich bin hier, wenn ich die

01:22:02.470 --> 01:22:06.110
addiere, laufe ich im Prinzip über das K hinaus und ich kann das

01:22:06.110 --> 01:22:08.190
einfach nochmal dann abziehen.

01:22:08.790 --> 01:22:14.330
Das heißt, diese Darstellung macht eine Reduktion, Modulo 2 hoch N.

01:22:15.370 --> 01:22:18.430
Und dann gibt es noch eine weitere Eigenschaft, die man sich anschauen

01:22:18.430 --> 01:22:18.750
muss.

01:22:20.810 --> 01:22:23.770
Ich kann also subtrahieren, da addiere ich einfach das Komplement,

01:22:24.890 --> 01:22:27.710
multiplizieren, dividieren, kann man einfach auf die Addition

01:22:27.710 --> 01:22:29.450
zurückführen, man kann das auch besser machen.

01:22:30.450 --> 01:22:31.730
Bereichsüberschreitung, was ist denn damit?

01:22:31.970 --> 01:22:34.570
Ich addiere 7 und 3, was kommt denn dann raus?

01:22:35.730 --> 01:22:38.770
Es gibt 10, 10 habe ich nicht im Zahlenring mit drin.

01:22:40.150 --> 01:22:45.150
0, 1, 0, 1.

01:22:48.560 --> 01:22:55.740
Jetzt habe ich hier eine Zahl, bei der unterscheidet sich das führende

01:22:55.740 --> 01:22:59.680
Bit von beiden führenden Bits der beiden Zahlen.

01:23:00.880 --> 01:23:05.160
Das heißt, ich habe zum Beispiel zwei positive Zahlen addiert und es

01:23:05.160 --> 01:23:10.600
kommt eine Zahl raus, die sieht ja hier aus wie eine negative Zahl.

01:23:11.340 --> 01:23:13.000
Das ist eine Bereichsüberschreitung.

01:23:13.940 --> 01:23:18.300
Das heißt, wenn sich das Vorzeichen der Summe von beiden Vorzeichen

01:23:18.300 --> 01:23:23.300
der Summanden unterscheidet, das ist hier auch der Fall, 0, 1, 1, 0,

01:23:23.540 --> 01:23:23.980
1.

01:23:25.560 --> 01:23:30.000
Hier haben Sie, das wird ja ignoriert, 0 und Sie hatten hier zwei

01:23:30.000 --> 01:23:30.880
negative Zahlen.

01:23:32.320 --> 01:23:37.060
Weiß ich, der Zahlenbereich wurde überschritten, ich muss das Ganze so

01:23:37.060 --> 01:23:38.580
deklarieren, ich habe einen Fehler.

01:23:39.780 --> 01:23:42.220
Und damit haben wir alle Eigenschaften dieses Zweierkomplements.

01:23:42.980 --> 01:23:47.960
Wenn Sie noch einen kleinen Augenblick warten, dann dürfen Sie aber

01:23:47.960 --> 01:23:49.900
zumindest hier noch einen kleinen Weihnachtsmann abholen.

01:23:50.600 --> 01:23:51.920
Den dürfen Sie noch mitnehmen.

01:23:51.920 --> 01:23:56.760
Den kriegen nämlich alle, die ausgehalten haben heute in dieser

01:23:56.760 --> 01:23:57.280
Vorlesung.

01:23:57.460 --> 01:23:58.660
Den gebe ich Ihnen noch in die Hand.

01:23:59.380 --> 01:24:00.520
Dann wünsche ich Ihnen frohe Weihnachten.

01:24:01.920 --> 01:24:02.780
So, tschüss.

01:24:03.140 --> 01:24:09.000
Jetzt kommt in den letzten fünf Minuten noch etwas, was sich nicht mit

01:24:09.000 --> 01:24:12.360
der Vorlesung beschäftigt, sondern etwas anderes, ganz kurz.

01:24:12.900 --> 01:24:15.580
Die Eigenschaften waren hier, die hatte ich Ihnen ja gerade alle

01:24:15.580 --> 01:24:16.120
dargestellt.

01:24:16.600 --> 01:24:20.320
Jetzt höre ich mit diesem Teil hier auf.

01:24:20.320 --> 01:24:24.100
Ich will also Präsentationen beenden und alles beibehalten.

01:24:25.040 --> 01:24:30.100
Und jetzt gehe ich auf ein anderes Programm.

01:24:34.600 --> 01:24:40.900
Auf ein Programm, das ich vor Jahren einmal entdeckt habe, als ich mir

01:24:40.900 --> 01:24:42.920
einen Tablet-PC gekauft habe.

01:24:43.340 --> 01:24:46.860
Also die Tablets sind ja keine Sache, die erst in den letzten Jahren

01:24:46.860 --> 01:24:49.780
mit dem iPad auf den Markt kam, sondern Tablet-PCs gibt es schon

01:24:49.780 --> 01:24:50.060
immer.

01:24:51.020 --> 01:24:53.160
Notebooks mit einem Touchscreen, also mit einem

01:24:53.160 --> 01:24:56.880
berührungsempfindlichen Bildschirm, auf dem man malen kann.

01:24:57.900 --> 01:25:01.300
Und hier habe ich also eine Möglichkeit, dass ich malen kann.

01:25:01.360 --> 01:25:02.860
Ich habe hier den Stift ausgewählt.

01:25:03.440 --> 01:25:08.680
Jetzt kann ich hier zum Beispiel irgendein Gegenstand malen.

01:25:08.980 --> 01:25:09.740
Der wird jetzt hier so...

01:25:09.740 --> 01:25:13.660
Ich könnte auch, wenn ich ein sauberes Kreis mache, wird er immer noch

01:25:13.660 --> 01:25:14.120
nicht sauber.

01:25:14.120 --> 01:25:15.820
Ich kann auch versuchen, das ganz sauber zu machen.

01:25:15.940 --> 01:25:17.240
Jetzt habe ich einen Kreis gemalt.

01:25:18.500 --> 01:25:23.820
Und jetzt kann ich hier auf Animation drücken und es passiert gar

01:25:23.820 --> 01:25:24.160
nichts.

01:25:25.360 --> 01:25:27.400
Jetzt gehe ich dann wieder zurück.

01:25:29.060 --> 01:25:31.520
Jetzt sage ich, ich füge eine Schwerkraft hinzu.

01:25:33.220 --> 01:25:35.100
Und Sie sehen, die fallen runter.

01:25:37.900 --> 01:25:39.740
Jetzt füge ich noch was hinzu.

01:25:39.900 --> 01:25:42.800
Ich sage, dieses Teil soll in die Richtung laufen.

01:25:42.800 --> 01:25:44.880
Das soll in die Richtung laufen.

01:25:46.060 --> 01:25:50.540
Und ich mache nur ganz bisschen Schwerkraft.

01:25:51.100 --> 01:25:52.160
Was passiert dann?

01:25:52.760 --> 01:25:58.200
Die laufen aufeinander zu und jetzt stoßen sie sich ab, entsprechend

01:25:58.200 --> 01:26:01.520
der Schwerkraft, die hier angegeben wurde und den Kräften, die hier

01:26:01.520 --> 01:26:02.380
drauf wirken.

01:26:03.060 --> 01:26:08.200
Oder ich sage, das Teil soll sich aber noch mit einer bestimmten Kraft

01:26:08.200 --> 01:26:10.760
in die Richtung bewegen.

01:26:10.760 --> 01:26:13.160
Mal sehen, was dann passiert.

01:26:14.000 --> 01:26:15.900
Dann dreht sich das auf einmal.

01:26:19.480 --> 01:26:22.760
Das heißt, hier habe ich eine Möglichkeit, wie ich irgendwelche

01:26:22.760 --> 01:26:24.160
Gegenstände zeichnen kann.

01:26:24.800 --> 01:26:28.980
Und das Interessante ist, ich kann also zum Beispiel sagen, ich möchte

01:26:28.980 --> 01:26:32.280
gerne die Eigenschaften verändern.

01:26:32.980 --> 01:26:37.440
Das Ganze kann Gummi sein oder Stahl oder Holz oder Eis oder Plastik

01:26:37.440 --> 01:26:38.580
oder Ton.

01:26:39.320 --> 01:26:44.720
Untersprechend den Eigenschaften dieser Materialien verändert sich das

01:26:44.720 --> 01:26:45.820
physikalische Verhalten.

01:26:45.940 --> 01:26:48.960
Die werden also einfach unterschiedlich dann interpretiert.

01:26:49.740 --> 01:26:52.420
Jetzt will ich Ihre Zeit nicht zu sehr in Anspruch nehmen.

01:26:52.580 --> 01:26:55.460
Ich möchte Ihnen einfach schöne vorgefertigte Beispiele zeigen.

01:26:57.440 --> 01:27:07.680
Zum Beispiel hier dieses Offroader, also ein Fahrzeug, das soll diese

01:27:07.680 --> 01:27:08.800
Strecke hochfahren.

01:27:09.000 --> 01:27:12.460
Sie sehen, wir haben hier irgendwelche Kräfte eingezeichnet.

01:27:13.180 --> 01:27:15.340
Das sind Räder, die verbunden mit dem dahinterliegenden.

01:27:15.400 --> 01:27:20.300
Hier unten dieses mit so mauerähnlich ausgefüllten Teil, das bedeutet,

01:27:20.440 --> 01:27:22.520
dieses verändert sich durch die Schwerkraft nicht, das ist fest

01:27:22.520 --> 01:27:23.440
gebunden an den Ort.

01:27:23.440 --> 01:27:25.000
Die Schwerkraft ist ziemlich hoch.

01:27:25.700 --> 01:27:28.100
Und hier habe ich noch etwas dazu gemalt, was sich bewegt.

01:27:28.400 --> 01:27:31.740
Also lassen wir das jetzt mal loslaufen, wird animiert.

01:27:31.900 --> 01:27:36.180
Dann sehen Sie, jetzt bewegen die sich entsprechend den dargestellten

01:27:36.180 --> 01:27:36.620
Kräften.

01:27:37.440 --> 01:27:41.020
Und das Teil versucht da hochzukommen und schafft es tatsächlich und

01:27:41.020 --> 01:27:43.040
fällt dann in den bitteren Abgrund.

01:27:43.040 --> 01:27:51.040
Ein ähnliches Beispiel schauen wir uns mal an, hier zum Beispiel ein

01:27:51.040 --> 01:27:51.860
Katapult.

01:27:55.500 --> 01:27:59.680
Auch nett vorher gemalt, nicht von mir, habe ich übernommen.

01:28:00.720 --> 01:28:02.360
Und jetzt schauen wir uns an, was hier passiert.

01:28:03.160 --> 01:28:07.880
Schwerkraft wirkt und Sie sehen, es wird hier dieser Haufen von

01:28:07.880 --> 01:28:12.660
irgendwelchen Quadraten hier einfach umgeworfen.

01:28:13.400 --> 01:28:15.340
Könnte natürlich die Schwerkraft auch verändern.

01:28:16.140 --> 01:28:16.920
Was passiert dann?

01:28:17.940 --> 01:28:21.900
Naja, dann rauscht das da einfach irgendwo anders durch die Gegend.

01:28:21.900 --> 01:28:29.240
Also das ist erstaunlich, wie einfach hier diese Gegenstände sich

01:28:29.240 --> 01:28:35.140
verändern können, in der Art, wie sie sich in der realen Welt bewegen.

01:28:35.820 --> 01:28:39.020
Schauen wir uns hier noch mal an den Domino-Effekt.

01:28:39.100 --> 01:28:40.820
Auch das ist nett, dieses Teil.

01:28:44.680 --> 01:28:47.800
Hier sehen Sie eine nette Anordnung.

01:28:47.800 --> 01:28:50.980
Wenn ich das einfach animiere, passiert folgendes.

01:28:51.060 --> 01:28:54.780
Sie sehen, das hier vorne wird bewegt, da sind die einzelnen Kräfte

01:28:54.780 --> 01:28:55.100
dran.

01:28:55.620 --> 01:28:57.700
Alles andere sind jetzt Folgewirkungen.

01:28:58.500 --> 01:29:00.900
Sie sehen, da werden also einige Objekte bewegt.

01:29:01.960 --> 01:29:04.260
Und da wird jetzt also das bewegt.

01:29:04.880 --> 01:29:08.340
Sie sehen, das war ganz wichtig, dadurch kann nämlich hier diese Kugel

01:29:08.340 --> 01:29:09.580
bewegt werden.

01:29:10.460 --> 01:29:14.080
Und das Teil hier hat eine Feder, ja auch das kann man darstellen.

01:29:14.080 --> 01:29:16.260
Sie sehen, dadurch, dass das sich jetzt angestoßen hat, genau in dem

01:29:16.260 --> 01:29:18.500
Augenblick ist diese Kugel auch weggelaufen.

01:29:19.620 --> 01:29:22.200
Ich könnte natürlich hier auch die Schwerkraft ein bisschen verändern.

01:29:23.080 --> 01:29:28.740
Ich könnte hier irgendwas dazu malen, da irgendein Zeichen reinmalen,

01:29:28.780 --> 01:29:29.560
was passiert dann?

01:29:30.020 --> 01:29:31.540
Dann würde es natürlich ganz anders ablaufen.

01:29:33.820 --> 01:29:39.560
Sie sehen, das ist jetzt leider durch die kleine Störung alles völlig

01:29:39.560 --> 01:29:40.100
verdorben.

01:29:40.860 --> 01:29:42.660
Hat leider nicht so funktioniert.

01:29:42.660 --> 01:29:45.260
Ach, ein bisschen putze ich doch noch hier.

01:29:47.180 --> 01:29:52.500
So, und als letztes wollte ich Ihnen jetzt noch ein Beispiel zeigen

01:29:52.500 --> 01:29:54.980
für das hier.

01:29:55.580 --> 01:29:58.340
Das will ich nicht aufbewahren.

01:29:59.400 --> 01:30:05.260
Da machen wir jetzt noch ganz kurz eine Darstellung eines anderen

01:30:05.260 --> 01:30:10.360
Objektes, nämlich dieses Bild, Frohe Weihnachten, was ich Ihnen sehr

01:30:10.360 --> 01:30:11.060
herzlich wünsche.

01:30:11.060 --> 01:30:15.160
Ich danke Ihnen, dass Sie ausgehalten haben heute bis 13 Uhr.

01:30:15.940 --> 01:30:17.440
Ich freue mich, dass Sie noch hier gewesen sind.

01:30:17.560 --> 01:30:21.020
Es macht viel mehr Spaß, in die Augen von interessierten Studentinnen

01:30:21.020 --> 01:30:24.300
und Studenten zu gucken, als wenn ich das hier alleine gemacht hätte

01:30:24.300 --> 01:30:25.900
oder nur mit meinem Mitarbeiter zusammen.

01:30:26.420 --> 01:30:27.800
Ich hätte es auch dann aufgezeichnet.

01:30:27.980 --> 01:30:30.880
Die Aufzeichnung wird heute gleich nachmittags bereitgestellt.

01:30:31.760 --> 01:30:34.860
Und auch das hier kann man natürlich bewegt machen, bewegte

01:30:34.860 --> 01:30:35.400
Weihnachten.

01:30:35.400 --> 01:30:38.420
Die sehen dann so aus, dass alles sich entsprechend den

01:30:38.420 --> 01:30:41.960
eingezeichneten Kräften hier etwas hin und her bewegt.

01:30:43.760 --> 01:30:46.320
Hauptsache, dass Ihre ganzen Wünsche zu Weihnachten nicht auf diese

01:30:46.320 --> 01:30:47.760
Art und Weise zusammenfallen.

01:30:48.020 --> 01:30:49.740
Also, ich wünsche Ihnen schöne Weihnachten.

01:30:49.900 --> 01:30:51.260
Genießen Sie die paar ruhigen Tage.

01:30:51.760 --> 01:30:53.020
Kommen Sie frisch gestärkt zurück.

01:30:53.160 --> 01:30:54.800
Wir sehen uns wieder am 8.

01:30:54.920 --> 01:30:57.560
Januar im Hörsaal am Fasanengarten.

01:30:58.160 --> 01:30:59.360
Vielen Dank für die Aufmerksamkeit.