WEBVTT

00:13.600 --> 00:14.940
Da ist noch nichts.

00:15.580 --> 00:16.460
Hört man nichts.

00:16.640 --> 00:18.040
1, 2, 3, 4.

00:18.220 --> 00:19.200
Jetzt hören Sie es auch hinten.

00:19.740 --> 00:20.260
Vielen Dank.

00:20.400 --> 00:20.840
Sehr gut.

00:21.020 --> 00:26.820
Ich habe jetzt gar nicht kontrolliert, inwieweit das hier richtig

00:26.820 --> 00:27.720
eingestellt ist.

00:27.940 --> 00:31.960
Ich denke, das kann ein bisschen stärker eingestellt werden.

00:33.820 --> 00:34.660
1, 2...

00:35.600 --> 00:36.980
1, 2, 3, 4.

00:37.020 --> 00:39.240
Jetzt hören endlich auch mal die Leute, bei denen es aufgezeichnet

00:39.240 --> 00:42.160
wird, was ich jetzt zu Anfang immer als Tonprobe mache.

00:42.160 --> 00:44.780
Das scheint so aber in Ordnung zu sein.

00:45.800 --> 00:46.100
Gut.

00:46.340 --> 00:48.880
Und das jetzt wieder zurück.

00:49.160 --> 00:49.280
Genau.

00:49.940 --> 00:54.320
Also, ich begrüße Sie zur vorletzten Vorlesung Grundlageninformatik 2

00:54.320 --> 00:55.080
in diesem Jahr.

00:55.960 --> 00:57.720
Nicht in diesem Semester, da kommt noch ein bisschen mehr.

00:59.000 --> 01:02.760
Und ganz kurz wieder zur Erinnerung, Anmeldung zur Bonusklausur ist

01:02.760 --> 01:03.280
noch offen.

01:03.640 --> 01:05.600
Bis Ende des Jahres dürfen Sie das noch machen.

01:05.780 --> 01:07.560
Stoff wissen Sie, wie der aussieht.

01:08.700 --> 01:10.700
Und was haben wir letztes Mal gemacht?

01:10.700 --> 01:16.680
Da haben wir uns noch weiter beschäftigt mit den Hardware-Geschichten.

01:16.940 --> 01:22.700
Wir haben uns also beschäftigt mit den verschiedenen Gattern.

01:23.400 --> 01:25.480
Wir hatten Transistoren uns angeschaut.

01:25.580 --> 01:30.920
Ich hatte Ihnen etwas erzählt über einfache Schaltungen, über den

01:30.920 --> 01:33.520
Inverter, über NAND und NORD.

01:33.540 --> 01:35.200
Das war alles schon das Mal davor gewesen.

01:35.800 --> 01:37.900
Dann kamen die Transfergatter dazu.

01:37.900 --> 01:41.080
Ich habe Ihnen was erzählt über Verzögerungsglied.

01:41.740 --> 01:44.920
Und darüber, wie man solche Schaltungen tatsächlich baut.

01:45.440 --> 01:50.340
Geometrisch so aufgemalt mit den entsprechenden Entwurfswerkzeugen.

01:51.100 --> 01:53.120
Und ich habe Ihnen dazu auch einiges zur Technologie erzählt.

01:53.760 --> 01:56.800
Wir haben uns kurz angeschaut, wie das aussieht mit den Entwicklungen.

01:57.340 --> 01:59.500
Das Moorsche Gesetz ist ein ganz wichtiges Gesetz.

01:59.620 --> 02:02.620
Wissen Sie, wir wissen nicht, wie lange das noch wohl Gültigkeit haben

02:02.620 --> 02:02.860
wird.

02:02.980 --> 02:04.980
Beziehungsweise, wie lange die Technologie sich so entwickelt.

02:04.980 --> 02:10.340
Aber wir sind schon relativ weit rangekommen an das voraussichtliche

02:10.340 --> 02:11.480
Ende dieser Entwicklung.

02:11.880 --> 02:14.860
Und das hängt halt daran, dass man irgendwann auf einer atomaren Ebene

02:14.860 --> 02:16.240
ist und nicht mal weitermachen kann.

02:17.260 --> 02:20.240
Ich habe Ihnen dann etwas erzählt über den Hardware-Entwurf, über

02:20.240 --> 02:22.040
Hardware -Software-Codesign.

02:23.140 --> 02:26.800
Darüber, wie man Systeme entwickelt auf verschiedenen Ebenen.

02:26.900 --> 02:30.280
Wir haben uns VHDL angeschaut und ich habe Ihnen dazu Beispiele

02:30.280 --> 02:33.960
gegeben, wie man einen Halbadierer beschreibt, wie man entsprechend

02:33.960 --> 02:37.340
einen Volladierer beschreibt.

02:37.680 --> 02:42.300
Erstmal als Komponente abstrakt, dann beschrieben durch die einzelnen

02:42.300 --> 02:45.620
Komponenten, die man braucht, Halbadierer oder Gatter, interne

02:45.620 --> 02:47.300
Signale, wie man das alles beschreibt.

02:47.420 --> 02:49.160
Also die Struktur und auch das Verhalten.

02:49.980 --> 02:55.540
Und wir haben dann gesehen, dass man verschiedene Arten der

02:55.540 --> 02:56.820
Realisierung von Systemen hat.

02:56.820 --> 03:00.840
Ich habe Ihnen etwas erzählt zum FPGAs.

03:01.000 --> 03:04.500
Wichtige Technologie, die Sie immer stärker auch in technischen

03:04.500 --> 03:08.700
Anwendungen finden, die eben zur Laufzeit noch programmierbar ist,

03:08.760 --> 03:11.360
wenn Sie dynamisch konfigurierbare FPGAs haben.

03:12.260 --> 03:15.200
Und wir hatten dann, das war eigentlich das Wesentliche gewesen in dem

03:15.200 --> 03:18.240
Kapitel, noch eine kurze Übersicht über die verschiedenen

03:18.240 --> 03:19.420
Einsatzbereiche.

03:20.080 --> 03:22.760
Und dann kamen wir zum nächsten Kapitel, nämlich zur Codierung und der

03:22.760 --> 03:23.440
Zahlendarstellung.

03:23.440 --> 03:26.420
Und ich habe Ihnen etwas erzählt darüber, wie wir Zahlen darstellen im

03:26.420 --> 03:30.180
Rechner, dass wir zunächst mal uns mit Codierung beschäftigen müssen.

03:30.480 --> 03:33.300
Da hatten wir einfacher angeschaut, Telefon-Codierung, Morse

03:33.300 --> 03:35.940
-Codierung, hatten gesehen, dass es dort unterschiedliche

03:35.940 --> 03:40.680
Eigenschaften gibt, insbesondere bei der Morse-Codierung, das Problem

03:40.680 --> 03:41.780
der Dekodierung.

03:42.120 --> 03:48.400
Wir haben zwar eine injektive Abbildung, aber keine Abbildung, die bei

03:48.400 --> 03:51.360
der Verlängerung auf Wörter dann noch dekodierbar ist.

03:51.360 --> 03:53.860
Und das heißt, da haben wir ein Problem.

03:54.460 --> 03:57.120
Deswegen haben wir gesagt, wenn wir das etwas anders machen, wenn wir

03:57.120 --> 04:00.980
also dafür sorgen, dass kein Codewort Präfix eines anderen Codeworts

04:00.980 --> 04:04.720
ist, wenn die Funktion dann noch injektiv ist, dann haben wir auf

04:04.720 --> 04:08.440
jeden Fall, kann man zumindest zeigen, dann eine dekodierbare

04:08.440 --> 04:11.820
Abbildung, eben wegen dieser Bedingung, kein Codewort ist Anfang eines

04:11.820 --> 04:12.660
anderen Codeworts.

04:13.400 --> 04:15.920
Und das ist eben in der Fano-Bedingung formuliert.

04:15.920 --> 04:19.180
Fano, mal wieder irgendein Wissenschaftler, der in dem Bereich

04:19.180 --> 04:20.000
gearbeitet hat.

04:20.640 --> 04:24.580
Und so kann man dann eben zum Beispiel die Morse-Codierung verändern,

04:24.700 --> 04:26.880
indem man dort ein Trennzeichen einführt.

04:26.960 --> 04:30.860
Und dann kann man natürlich alles wieder geeignet dekodieren.

04:31.740 --> 04:33.740
Das waren die Bemerkungen dazu.

04:34.260 --> 04:37.140
Und dann kommen wir genau zum Abschnitt 7.3.

04:37.280 --> 04:38.860
Das ist die erste Folie für heute.

04:38.860 --> 04:46.720
Und da gehen wir jetzt zum Thema über Fehlererkennung und

04:46.720 --> 04:47.720
Fehlerkorrektur.

04:48.200 --> 04:50.680
Warum muss man sich mit Fehlererkennung und Korrektur beschäftigen?

04:50.800 --> 04:54.660
Ich hatte Ihnen schon bei dem, was ich Ihnen zur Hardwareentwicklung

04:54.660 --> 04:58.660
erzählte, bemerkt, dass man zukünftig immer stärker damit rechnen

04:58.660 --> 05:00.020
muss, dass auch mal Fehler auftreten.

05:00.540 --> 05:01.660
Das ist ein altes Problem.

05:01.920 --> 05:06.920
Wenn Sie Daten zwischen Speicher und Recheneinheit hin- und

05:06.920 --> 05:10.220
herschieben, können auf dem Übertragungsweg Fehler auftreten, dass

05:10.220 --> 05:14.700
Bits ausgelöscht werden, dass eine 0 zu einer 1 wird und eine 1 zu

05:14.700 --> 05:15.080
einer 0.

05:15.620 --> 05:17.160
Und damit muss man geeignet umgehen können.

05:18.140 --> 05:23.500
Wir wollen ja nicht solche Daten fehlerhaft weiterverwenden.

05:24.120 --> 05:26.260
Wir müssen also einerseits erkennen können, dass ein Fehler

05:26.260 --> 05:29.900
aufgetreten ist, andererseits wollen wir gerne korrigieren können.

05:30.080 --> 05:32.400
Das wäre natürlich noch toller, wenn man einen Fehler, der aufgetreten

05:32.400 --> 05:33.660
ist, wieder korrigieren kann.

05:34.500 --> 05:39.100
Wie man das hinbekommen kann, das werden wir uns angucken.

05:39.300 --> 05:42.760
In diesem Fall beschränkt auf Block-Codierungen, also zum Beispiel 32

05:42.760 --> 05:46.940
-Bit oder 64-Bit-Wörter oder eben irgendwelche N-Bit-Codierungen.

05:48.060 --> 05:53.640
Was wir hier definieren, ist ein Maß, das wir eigentlich schon kennen.

05:55.120 --> 05:57.040
Dazu hatte ich Ihnen hier noch nichts erzählt.

05:57.160 --> 06:00.980
Das ist hier gar nicht gewesen in dieser Vorlesung.

06:00.980 --> 06:03.740
Ich habe Ihnen hier noch nichts erzählt zum Hemming-Abstand.

06:03.940 --> 06:07.140
Der Hemming-Abstand geht folgendermaßen vor.

06:07.240 --> 06:14.580
Wir haben also hier zwei Wörter, zwei Codes, zwei Codewörter und legen

06:14.580 --> 06:15.620
die praktisch übereinander.

06:15.720 --> 06:16.680
Die haben ja gleiche Länge.

06:17.380 --> 06:23.120
Und jetzt vergleichen wir für jede einzelne Position, ob die Elemente

06:23.120 --> 06:24.460
identisch sind oder nicht.

06:25.600 --> 06:30.500
Dieses H von XIYI, H für Hemming, Hemming also auch ein

06:30.500 --> 06:35.520
Wissenschaftler, dieses H von XYI ist gleich 1, wenn die beiden

06:35.520 --> 06:37.820
unterschiedlich sind, und 0 sonst.

06:37.920 --> 06:42.620
Wenn hier also eine 0 und 1 steht, dann würde hier bei der Hemming

06:42.620 --> 06:45.240
-Distanz unten drunter eine 1 stehen.

06:45.380 --> 06:47.780
Wenn die identisch sind, dann steht dort eine 0.

06:48.900 --> 06:51.160
Auch wenn hier 1,1 steht, steht dort auch eine 0.

06:51.880 --> 06:56.840
Und wenn dort 1,0 steht, würde da eine 1 stehen.

06:56.840 --> 07:00.800
Also, im Prinzip bilden Sie hier das XOR von den beiden Elementen und

07:00.800 --> 07:05.120
das ist der Hemming-Abstand in dem Fall.

07:05.760 --> 07:09.180
Also man guckt sich an, die Anzahl der Stellen, an denen sich die

07:09.180 --> 07:10.400
beiden Wörter unterscheiden.

07:10.920 --> 07:14.840
Und wenn ich mir das angeguckt habe, habe ich etwas über die Distanz.

07:15.480 --> 07:20.240
Dann weiß ich nämlich, wie viele Veränderungen vorgenommen werden

07:20.240 --> 07:27.280
müssen von einem Wort X zu einem Wort Y, damit aus X ein Y wird.

07:28.480 --> 07:31.420
Wieso will man aus einem Wort X ein Wort Y machen?

07:32.360 --> 07:33.440
Die Idee ist andersrum.

07:34.040 --> 07:39.380
Wenn jetzt nur der Abstand 5 ist zwischen X und Y.

07:40.380 --> 07:44.360
Und ich habe jetzt ein anderes Wort, das einen Abstand 1 hat.

07:44.960 --> 07:48.400
Dann weiß ich, dieses Wort ist sicherlich nicht gleich Y, ist nicht

07:48.400 --> 07:49.000
gleich X.

07:49.600 --> 07:54.040
Und wenn jetzt kein anderes Codewort einen Abstand 1 von X hat, dann

07:54.040 --> 07:57.400
weiß ich, das ist ein offensichtlicher Fehler, weil da ein Wort

07:57.400 --> 07:59.220
entstanden ist, das nicht zum Code gehört.

08:00.000 --> 08:02.100
Und das ist das, was man sich jetzt im Weiteren anguckt.

08:02.760 --> 08:06.640
Wir wollen uns anschauen, die Hemming-Zahl eines Codes.

08:07.280 --> 08:10.820
Und die Hemming-Zahl eines Codes gibt gerade an, den minimalen Abstand

08:10.820 --> 08:12.560
zwischen zwei beliebigen Codewörtern.

08:13.460 --> 08:17.260
Wir schauen uns alle Codewörter an, also alle Bilder von Zeichen, die

08:17.260 --> 08:19.840
abgebildet werden durch die Codierung.

08:20.680 --> 08:26.040
Und schauen uns also alle diese Abstände an zwischen zwei beliebigen

08:26.040 --> 08:26.760
Codewörtern.

08:28.460 --> 08:32.800
Und der minimale Abstand, das ist das, was wir als Hemming-Zahl

08:32.800 --> 08:33.660
bezeichnen.

08:35.040 --> 08:39.720
Das heißt, wenn ich mir jetzt die einzelnen Codes anschaue, wir machen

08:39.720 --> 08:41.500
das gleich noch etwas grafisch.

08:41.500 --> 08:45.720
Was wir uns hier anschauen, ist zum Beispiel diese 1 aus 10-Codierung

08:45.720 --> 08:46.820
für Dezimalziffern.

08:47.540 --> 08:48.980
Wie groß ist hier der Abstand?

08:49.540 --> 08:53.720
Schauen wir uns hier zwei nebeneinander liegende Wörter an.

08:54.200 --> 08:57.340
Also 1 aus 10-Codierung heißt, ich habe 10 Bit.

08:58.100 --> 09:00.740
Ein Bit ist eine Eins, alle anderen sind Null.

09:01.380 --> 09:04.980
Das heißt, die Position, an der eine Eins steht, beschreibt praktisch

09:04.980 --> 09:06.620
genau den Wert dieser Ziffer.

09:06.620 --> 09:10.580
Also hier, das ist halt die Codierung der Null, an der 0.

09:10.700 --> 09:13.380
Stelle, von rechts gerechnet, 1.

09:13.500 --> 09:13.980
Stelle, 2.

09:14.140 --> 09:14.840
Stelle und so weiter.

09:15.360 --> 09:21.360
Und der Abstand von je 2 aus diesem Code ist ziemlich offensichtlich.

09:21.540 --> 09:22.840
Da ist immer nur eine Eins drin.

09:25.600 --> 09:28.100
Und die Einsen sind alle an verschiedenen Stellen.

09:29.120 --> 09:32.980
Das heißt, wenn ich mir hier zwei Wörter anschaue, dann haben die

09:32.980 --> 09:34.100
jeweils eine Eins.

09:34.100 --> 09:37.000
Und das andere Wort hat jeweils an den Stellen eine Null.

09:37.720 --> 09:41.100
Das heißt, es gibt genau zwei Positionen, an denen diese beiden

09:41.100 --> 09:42.380
Codewörter sich unterscheiden.

09:42.940 --> 09:48.160
Und deswegen ist in dem Fall der Hemming-Abstand gleich 2 für je zwei

09:48.160 --> 09:49.040
verschiedene Wörter.

09:49.700 --> 09:52.000
Weil die beiden Einsen an verschiedenen Stellen stehen, in diesen

09:52.000 --> 09:52.600
Codewörtern.

09:53.040 --> 09:55.560
Wie hier ganz deutlich zu sehen, da sind das halt diese beiden

09:55.560 --> 09:58.940
Stellen, wo ich Unterschiede habe oder ansonsten irgendwelche anderen

09:58.940 --> 10:01.660
Stellen, wo gerade die beiden Einsen sind.

10:01.660 --> 10:05.740
Und da für alle verschiedenen Wörter diese Differenz gerade gleich,

10:06.980 --> 10:09.700
oder dieser Abstand gleich 2 ist, also die Hemming-Zahl in dem Fall

10:09.700 --> 10:10.380
auch gleich 2.

10:11.460 --> 10:14.740
Nun muss das nicht immer so sein, dass die Codewörter alle den

10:14.740 --> 10:16.060
gleichen Abstand haben.

10:16.180 --> 10:17.580
Die können auch unterschiedliche Abstände haben.

10:17.660 --> 10:21.700
Hier ist das der Fall, dass je zwei Codewörter den Abstand 2 haben.

10:23.460 --> 10:26.940
Die Frage ist jetzt, wie kann ich hier Fehler erkennen?

10:28.360 --> 10:32.200
Nun immer dann, wenn ich ein Wort bekomme, ein Codewort bekomme, das

10:32.200 --> 10:34.620
nicht in dem Code enthalten ist.

10:35.360 --> 10:38.860
Das heißt, nehmen wir mal an, wir hätten ein Codewort, das einen

10:38.860 --> 10:43.280
Hemming -Abstand von 1 hat, also nur Nullen, kommt hier nicht vor,

10:43.420 --> 10:46.040
sehe ich sofort Hemming-Abstand 1, das kann ich offensichtlich

10:46.040 --> 10:46.500
erkennen.

10:47.620 --> 10:52.800
Also wann immer ich mir irgendein Codewort hernehme und ein anderes

10:52.800 --> 10:55.420
Codewort betrachte, das den Hemming-Abstand 1 hat.

10:55.800 --> 11:03.100
Das heißt, keine 1 wäre Hemming-Abstand 1 oder 2 Einsen wäre auch

11:03.100 --> 11:04.060
Hemming -Abstand 1.

11:06.200 --> 11:11.820
Dann wäre ich sicher, Hemming-Abstand 1, das ist ein Wort, das

11:11.820 --> 11:17.080
entstanden ist aus einem Codewort, dadurch das ein Bit gekippt ist.

11:17.500 --> 11:18.620
Das heißt, da kann ich einen Fehler erkennen.

11:20.540 --> 11:23.620
Und die Frage ist, wann kann ich einen Fehler korrigieren?

11:24.920 --> 11:29.480
Wenn ich dadurch, dass ich ein Codewort betrachte, ich habe also hier

11:29.480 --> 11:34.920
mein Codewort X und ich habe irgendwie ein Codewort Y und jetzt

11:34.920 --> 11:38.540
betrachte ich ein fehlerhaftes Codewort, nennen wir das mal Z.

11:40.040 --> 11:44.720
Und wenn dieses Codewort Z, das seien jetzt hier die Distanzen, dieses

11:44.720 --> 11:49.400
Z ist nicht im Code, ist also ein fehlerhaftes Wort, das kann ich ja

11:49.400 --> 11:51.600
feststellen, ob das Z drin ist.

11:53.100 --> 12:01.960
Also Z nicht aus C von A in dem Fall, also nicht aus unserer

12:01.960 --> 12:03.300
Codierung, kein Codewort.

12:04.280 --> 12:08.580
Wenn das irgendwo dazwischen liegt, dann schaue ich mir die Distanzen

12:08.580 --> 12:13.060
an, das wäre hier also der Abstand zu X, das wäre der Abstand zu Y und

12:13.060 --> 12:16.100
natürlich kann ich dann erwarten, naja, nehmen wir mal an, ich habe

12:16.100 --> 12:22.860
diese Situation, dann wäre das Z, sofern also das DX kleiner als die Y

12:22.860 --> 12:25.920
ist, wahrscheinlich aus dem X entstanden.

12:27.640 --> 12:31.040
Zumindest ist es näher an dem X und ich gehe dann einfach davon aus,

12:31.520 --> 12:38.520
wenn ich ein Wort bekomme, das näher an X liegt als an Y, dann ist es

12:38.520 --> 12:41.500
von X gekommen, wenn es näher an Y liegt, dann ist es wahrscheinlich

12:41.500 --> 12:42.460
aus Y entstanden.

12:43.740 --> 12:45.320
Das vermute ich einfach.

12:45.580 --> 12:48.500
Natürlich kann es sein, dass da viel mehr Bits gekippt sind, sodass es

12:48.500 --> 12:50.080
zufällig an die Position gekommen ist.

12:50.500 --> 12:54.000
Das könnte natürlich aus X entstanden sein und durch eine Anzahl von

12:54.000 --> 12:56.740
Fehlern irgendwie hierhin gelandet sein, dann ist es ganz nah bei Y.

12:57.620 --> 12:59.700
Dann würde ich sagen, das liegt jetzt bei Y.

13:00.680 --> 13:04.700
Aber wenn ich jetzt mir einfach angucke, Situation, wie viele Fehler

13:04.700 --> 13:11.840
dürfen auftreten, damit ich die Fehler erkennen kann und auch

13:11.840 --> 13:15.640
korrigieren kann, dann ist es doch offensichtlich, dass ich etwas so

13:15.640 --> 13:22.020
lange, wenn das hier der gesamte Abstand ist von D, X, Y, wenn ich

13:22.020 --> 13:25.240
also den Abstand D, X, Y halber habe,

13:29.720 --> 13:34.340
wenn der Abstand kleiner ist als D, X, Y halber, wenn ich also so

13:34.340 --> 13:39.600
viele Fehler drin habe, dass ich maximal den Abstand D, X, Y halber

13:39.600 --> 13:44.800
erreiche, dann weiß ich, dieses Codewort ist zwar fehlerhaft, aber es

13:44.800 --> 13:45.700
ist aus X entstanden.

13:46.540 --> 13:52.140
Entsprechend, wenn ich von Y durch Fehler nur maximal die Entfernung

13:52.140 --> 13:56.000
D, X, Y halber wegkomme, kann ich auch sagen, dann bin ich

13:56.000 --> 13:57.600
offensichtlich von Y gekommen.

13:58.840 --> 14:02.360
Wenn ich mehr Fehler habe, die mich also über diese Grenze hinweg

14:02.360 --> 14:08.180
bringen, dann kann ich diese höheren Fehleranzahlen nicht mehr

14:08.180 --> 14:09.520
geeignet korrigieren.

14:09.620 --> 14:11.860
Dann würde ich ja vermuten, dass es, wenn es meinetwegen aus X

14:11.860 --> 14:17.780
entstanden war, mit mehr als D, X, Y halben Fehlern, dann würde ich

14:17.780 --> 14:20.320
vermuten, das ist aus Y entstanden, das wäre falsch.

14:20.440 --> 14:23.380
Also ich ordne praktisch immer das fehlerhafte Codewort dem

14:23.380 --> 14:28.840
nächstliegenden Codewort zu und das heißt, dass ich so lange Fehler

14:28.840 --> 14:33.100
korrigieren kann, wie ich weniger Fehler habe, als der halbe Abstand

14:33.100 --> 14:34.960
zwischen diesen beiden Codewörtern angeht.

14:35.440 --> 14:38.100
Ich glaube, das ist ziemlich intuitiv und das gucken wir uns jetzt ein

14:38.100 --> 14:38.700
bisschen genauer an.

14:39.120 --> 14:41.380
Hier nochmal ein kleines Beispiel.

14:41.380 --> 14:45.000
Hier haben wir die drei Codewörter.

14:46.660 --> 14:51.220
Also hier haben wir C von 0, C von 1, C von 2.

14:51.900 --> 14:53.440
Wie ist der Abstand zwischen diesen beiden?

14:53.540 --> 14:58.520
Wir haben hier einen Unterschied, dort einen, dort einen, dort einen,

14:58.580 --> 15:01.120
dort einen, dort einen, 1, 2, 3, 4, 5, 6.

15:02.280 --> 15:04.360
Schauen wir uns die anderen beiden an.

15:04.560 --> 15:10.880
Hier sind es, da ist ein Unterschied, da, dort, dort, dort und dort.

15:10.880 --> 15:11.640
Auch 6.

15:12.080 --> 15:17.840
Schauen wir uns den großen Unterschied an, zwischen C von 2, also

15:17.840 --> 15:18.780
zwischen Z und X.

15:19.380 --> 15:25.660
Dann sehen wir, da ist ein Unterschied, da ist ein Unterschied, da ist

15:25.660 --> 15:28.620
einer, da ist einer, da ist einer, da ist einer.

15:29.000 --> 15:29.620
Auch wieder 6.

15:30.220 --> 15:34.860
Also hier haben wir zwischen diesen drei Codewörtern, X, Y, Z, jeweils

15:34.860 --> 15:36.060
einen Abstand von 6.

15:36.440 --> 15:37.260
Hier auch angegeben.

15:38.240 --> 15:38.960
Das ist dieses Bild.

15:38.960 --> 15:44.960
Wir haben also 6 Bits zu verändern, bevor wir von einem Codewort zum

15:44.960 --> 15:45.600
anderen kommen.

15:46.960 --> 15:49.680
Und jetzt kann man sich überlegen, offensichtlich werde ich, wenn das

15:49.680 --> 15:53.280
die einzelnen Codewörter sind, alle Wörter, die dazwischen liegen,

15:53.360 --> 15:54.740
sofort als fehlerhaft erkennen.

15:55.680 --> 15:59.580
Und wenn ich also jetzt hier rübergehe, von mit einem Bit, 2 Bit

15:59.580 --> 16:03.040
verändert, 3 Bit verändert, 4 Bit verändert, hier habe ich von der

16:03.040 --> 16:07.180
anderen Seite, eins verändert von Y, noch eins verändert von Y.

16:07.180 --> 16:12.160
Jetzt habe ich also den vollständigen Weg von Z nach Y durch eine

16:12.160 --> 16:12.980
Reihe von Veränderungen.

16:13.040 --> 16:15.960
Sie können hier verschiedene Wege natürlich gehen, von Z nach Y.

16:16.580 --> 16:21.140
Das wäre eine solche sukzessive Veränderung von Bits, sodass Sie aus Z

16:21.140 --> 16:22.320
das Y produzieren.

16:24.920 --> 16:29.300
Und offensichtlich ist es so, der Abstand ist 6, also halber Abstand

16:29.300 --> 16:29.920
ist 3.

16:31.080 --> 16:36.020
Wenn ich den Abstand 3 habe, weiß ich natürlich nicht, wohin ich gehen

16:36.020 --> 16:36.380
soll.

16:37.720 --> 16:41.640
Wenn ich Abstand 3 habe, dann ist der Abstand zu beiden gleich.

16:43.040 --> 16:45.120
Dann weiß ich nicht, was richtig ist.

16:45.560 --> 16:48.860
Das heißt, ich muss dann schon kleiner als den halben Abstand haben.

16:49.700 --> 16:52.800
In diesem Fall ist also HC gleich 6.

16:53.600 --> 16:57.340
Der halbe Abstand ist, hier sind nochmal diese Umgebungen angegeben,

16:57.460 --> 16:59.260
in denen die einzelnen Bereiche liegen.

17:00.020 --> 17:05.300
Und sobald wir also 3 überschritten haben oder auf dem Abstand 3 sind,

17:05.380 --> 17:09.680
können wir nicht mehr eindeutig zuordnen, woher das gekommen ist.

17:10.140 --> 17:15.440
Das heißt, in dem Fall hätten wir, Bezug auf, gehen wir nochmal

17:15.440 --> 17:18.880
zurück, das sind also die verschiedenen Umgebungen so eines Wortes,

17:19.040 --> 17:23.680
hier etwas naheliegend visualisiert durch solche Kringel da dringend

17:23.680 --> 17:23.960
herum.

17:24.760 --> 17:27.100
Und Sie können sich also um jedes Codewort solche Umgebungen

17:27.100 --> 17:27.560
vorstellen.

17:28.140 --> 17:30.920
Und dann sehen Sie, welche Codewörter dort jeweils noch drin liegen

17:30.920 --> 17:31.260
können.

17:32.120 --> 17:34.940
Wenn wir uns jetzt angucken, die Erkennungs- und

17:34.940 --> 17:38.940
Korrekturmöglichkeiten, dann ist es offensichtlich so, dass wir eben

17:38.940 --> 17:40.400
Fehler erkennen können.

17:40.740 --> 17:45.040
Solange wir Codewörter bekommen, die hier irgendwo dazwischen liegen,

17:45.180 --> 17:47.980
also alle diese Codewörter dazwischen, können wir selbstverständlich

17:47.980 --> 17:53.200
als fehlerhaft identifizieren, weil sie Abstand haben von den anderen,

17:53.500 --> 17:55.280
der ungleich 0 ist.

17:56.420 --> 18:04.360
Das heißt, wir können in dem Fall K-Fachfehler erkennen, entsprechend

18:04.360 --> 18:05.420
der Hemming-Distanz.

18:06.280 --> 18:10.820
Also, wenn der Hemming...

18:11.600 --> 18:13.240
Ups, für alle x, was steht hier?

18:13.320 --> 18:14.900
h von x, y, kleiner gleich k,

18:25.480 --> 18:26.060
folgt...

18:26.060 --> 18:27.280
und kleiner gleich...

18:27.920 --> 18:29.440
Das ist hier genau gemeint.

18:29.740 --> 18:33.800
Also die Definition sagt Folgendes aus.

18:34.860 --> 18:38.280
Wenn ich einen Cod-K-Fachfehler erkennbar habe,

18:41.520 --> 18:48.500
dann ist jedes Codewort, das einen Abstand hat von dem, also den

18:48.500 --> 18:54.200
Abstand haben von weniger als k, bei denen ist gewährleistet, dass y

18:54.200 --> 18:56.840
nicht aus dem Code von a ist.

18:57.960 --> 19:04.220
Dann ist ein Cod-K-Fehler erkennbar.

19:04.500 --> 19:07.900
Also wann immer der Abstand von zwei Codewörtern kleiner gleich k ist,

19:08.020 --> 19:13.800
muss daraus folgen, dass dieses Wort y nicht aus c von a ist.

19:14.080 --> 19:15.040
Also kein Codewort ist.

19:15.140 --> 19:19.440
Wir haben ein Codewort und irgendein anderes Wort, also x ist ein

19:19.440 --> 19:23.140
Codewort, y ist irgendein Wort und wenn der Abstand von x und y

19:23.140 --> 19:27.340
kleiner gleich k ist, dann ist dieses y kein Codewort.

19:27.660 --> 19:33.600
Wenn diese Bedingung erfüllt ist, dann ist der Cod-K-Fehler erkennbar.

19:33.600 --> 19:38.760
Und jetzt können wir das gleiche machen für K-Fehler-Korrigierbarkeit.

19:39.700 --> 19:45.760
Irgendein Codewort x, irgendein Codewort y, also jetzt zwei Codewörter

19:45.760 --> 19:51.340
und ein Wort, das beliebig ist aus b hoch n, also beliebiges n-Bit

19:51.340 --> 19:52.360
-Wort.

19:55.780 --> 20:05.740
Und wenn x ungleich y ist, also zwei verschiedene Codewörter und h von

20:05.740 --> 20:11.580
x und z kleiner gleich k ist, also der Abstand dieses Wortes z von x

20:11.580 --> 20:14.680
kleiner gleich k, das heißt das liegt in dem Fall zum Beispiel

20:14.680 --> 20:19.800
irgendwo hier in diesem Bereich meinetwegen, dann muss der Abstand zu

20:19.800 --> 20:21.580
y größer als k sein.

20:22.500 --> 20:26.840
Das heißt, wann immer ich ein Wort habe zwischen x und y, in diesem

20:26.840 --> 20:31.260
Fall x und y, wenn ich hier ein Wort habe, das z passt ja zu dem Bild

20:31.260 --> 20:35.400
leider nicht, wenn ich hier irgendein Wort z Strich habe, das näher an

20:35.400 --> 20:43.900
x ist, dann muss daraus folgen, dass der Abstand von z Strich zu y

20:43.900 --> 20:45.820
größer als k ist.

20:46.840 --> 20:48.960
Also dann ist es k-fach korrigierbar.

20:50.060 --> 20:54.680
In dem Fall, wenn also der Abstand drei wäre, kleiner gleich drei,

20:55.180 --> 20:58.620
wäre der Abstand leider zum anderen auch drei, das heißt, dass es in

20:58.620 --> 21:02.380
diesem Fall bei dem Beispiel hier mit einem Hemming Abstand von sechs

21:02.380 --> 21:06.130
ist sicherlich so, dass der Code nicht dreifach fehlerkorrigierbar

21:06.760 --> 21:10.720
wäre oder dreifach fehlerkorrigierbar, weil ich für drei Fehler einen

21:10.720 --> 21:13.600
gleichen Abstand habe zwischen zwei benachbarten Codewörtern.

21:15.140 --> 21:19.300
Und wenn jetzt kommen wir zu der Folgerung aus dieser Definition.

21:19.820 --> 21:26.240
Die Definition war, es ist k-fehler erkennbar, wenn ich aus einem

21:26.240 --> 21:29.900
Codewort mit Abstand k schließen kann oder aus einem Wort mit Abstand

21:29.900 --> 21:32.000
k schließen kann, es gehört nicht zum Code.

21:33.320 --> 21:38.660
Es ist k-fach fehlerkorrigierbar, wenn der Abstand von einem Codewort

21:39.960 --> 21:43.080
eindeutet, also wenn Abstand kleiner gleich k heißt, der Abstand zum

21:43.080 --> 21:45.060
nächsten Codewort ist größer als k.

21:45.720 --> 21:49.320
Diese beiden Bedingungen, dann kann ich über Kenntnis des Hemming

21:49.320 --> 21:54.300
-Codes, der Hemming-Zahl, nicht das Hemming-Code, sondern über

21:54.300 --> 21:58.900
Kenntnis der Hemming-Zahl dieses Codes, sofort sagen, was ich hier

21:58.900 --> 22:01.040
erkennen und korrigieren kann.

22:01.660 --> 22:03.980
Der Hemming-Code gibt den minimalen Abstand an.

22:05.320 --> 22:08.080
Ja, den minimalen Abstand zwischen zwei Codewörtern.

22:09.120 --> 22:14.700
Das heißt, zwei Codewörter, die den Abstand hc haben oder Abstand k

22:14.700 --> 22:22.580
oder Abstand d haben, die sind ja beide im Code.

22:22.740 --> 22:26.500
Und sobald ich einen Abstand habe, der um 1 geringer ist, kann ich

22:26.500 --> 22:27.840
erkennen, dass das ein Fehler ist.

22:28.460 --> 22:36.520
Deswegen, wenn die Codezahl größer gleich k plus 1 ist, also die

22:36.520 --> 22:40.240
Hemming -Zahl größer als k plus 1 ist, ist die Codierung k-Fehler

22:40.240 --> 22:40.800
erkennbar.

22:41.680 --> 22:47.700
Ich kann auch sagen, jeder Code ist hc minus 1

22:51.080 --> 22:54.820
Fehler erkennbar.

22:54.920 --> 22:56.080
Das ist ein bisschen einfacher formuliert.

22:56.380 --> 23:01.240
Also jeder Code ist hc minus 1 Fehler erkennbar.

23:02.680 --> 23:07.320
1 weniger als der Hemming-Abstand oder zwischen beliebigen Codewörtern

23:07.320 --> 23:20.300
und er ist hc minus 1 halbe Fehler korrigierbar.

23:25.600 --> 23:29.320
Damit haben wir diese beiden Fälle.

23:29.580 --> 23:35.540
Also wenn hc größer gleich 2k plus 1 ist, dann ist die Codierung k

23:35.540 --> 23:36.520
-Fehler korrigierbar.

23:37.280 --> 23:43.500
Wenn das hc also eine gerade Zahl ist, dann ist hc minus 1 ungerade

23:43.500 --> 23:50.580
Zahl und also in diesem Fall bei 6 kommt halt das Abstand 2 heraus,

23:50.580 --> 24:00.520
weil ich in dem Fall hc minus 1, also 5 durch 2 und davon demnächst

24:00.520 --> 24:02.680
kleinere ganze Zahlen nehme.

24:04.900 --> 24:09.980
Also weniger als der halbe Abstand, wenn der Abstand eine gerade Zahl

24:09.980 --> 24:13.780
ist, ansonsten ist es gerade dieser Abstand.

24:13.960 --> 24:14.880
Kommt also so gerade hin.

24:17.440 --> 24:21.100
Und damit haben wir jetzt Aussagen darüber, wie ich aus der

24:21.100 --> 24:26.340
Hemmingzahl eines Codes ablesen kann, was ich erkennen kann und was

24:26.340 --> 24:27.200
ich korrigieren kann.

24:28.280 --> 24:32.660
Das ist also ganz einfache Erläuterung aus diesen Definitionen.

24:32.700 --> 24:34.360
Hier ist das nochmal räumlich angeordnet.

24:34.640 --> 24:36.920
Das sind die beiden verschiedenen Situationen.

24:37.000 --> 24:39.990
Sobald ich Codewörter habe, die nur ein...

24:40.720 --> 24:47.060
also sobald ich Wörter habe, nicht Codewörter, Wörter haben irgendein

24:47.060 --> 24:54.780
Wort Z Strich, dort oder dort oder irgendwo, das in einem Umkreis

24:54.780 --> 25:00.240
eines Codewortes liegt, in dem kein anderes Codewort liegt, weiß ich,

25:00.380 --> 25:01.480
ich habe einen Fehler erkannt.

25:02.240 --> 25:03.910
Das ist also die K-Fehlererkennbarkeit.

25:05.180 --> 25:10.180
Jede Codierung ist hc minus 1 Fehler erkennbar.

25:11.720 --> 25:17.180
Und das andere ist die Korrigierbarkeit.

25:18.160 --> 25:21.120
Da sehen Sie, da müssen also diese Umgebungen des Jungs sein.

25:21.420 --> 25:28.160
Das heißt, ich darf nicht, also jede Codierung C ist hc halbe minus 1

25:28.160 --> 25:34.300
Fehler korrigierbar und das heißt weniger, 1 weniger als der halbe

25:34.300 --> 25:34.660
Abstand.

25:37.220 --> 25:44.020
Damit haben wir diese beiden Fälle uns angeguckt, also Erkennbarkeit

25:44.020 --> 25:45.040
und Korrigierbarkeit.

25:45.660 --> 25:49.300
Das sind wichtige Eigenschaften, die man sich anschauen muss für die

25:49.300 --> 25:50.000
verschiedenen Codes.

25:50.040 --> 25:54.120
Hier hatten wir bei der 1 aus 10 Codierung, hatten wir schon gesehen,

25:54.220 --> 25:56.900
da ist die Hemmingzahl gleich 2.

25:57.120 --> 25:59.820
Es haben alle Codewörter den gleichen Abstand 2.

26:01.140 --> 26:06.020
Das heißt, in dem Fall können wir maximal Einfachfehler erkennen und

26:06.020 --> 26:14.520
wir können keine Fehler korrigieren, weil hier eben hc minus 1 halbe

26:14.520 --> 26:15.720
gerade gleich 0 ist.

26:15.960 --> 26:16.700
Wir können nichts erkennen.

26:17.240 --> 26:19.440
Nichts korrigieren, nur Einfachfehler erkennen.

26:20.460 --> 26:23.800
Und hier ist eine Codierung ein bisschen anders aus.

26:23.960 --> 26:28.680
Da haben wir ABCD codiert durch einmal hier 4 Nullen.

26:28.860 --> 26:31.040
Da haben wir also hier einen Abstand von 3.

26:31.780 --> 26:34.120
Dort haben wir einen Abstand von...

26:34.120 --> 26:36.760
Hier sind es 3, da ist der Abstand 4.

26:37.460 --> 26:39.580
Hier ist der Abstand 1, 2, 3.

26:41.320 --> 26:42.240
Stimmt das überhaupt?

26:43.120 --> 26:44.100
Genau, 1, 2, 4.

26:44.300 --> 26:48.940
Hier ist der Abstand zwischen den beiden 1, 2, 3.

26:49.760 --> 26:50.920
Und die anderen können sich angucken.

26:51.260 --> 26:53.280
Jedenfalls ist der minimale Abstand hier 3.

26:53.820 --> 26:56.160
Wir haben in dem Fall also eine Hemmingzahl von 3.

26:56.900 --> 27:02.460
Und in dem Fall bei einer Hemmingzahl von 3 können wir Zweifachfehler

27:02.460 --> 27:04.900
erkennen, also Doppelfehler erkennen.

27:05.740 --> 27:07.600
Und wir können Einfachfehler korrigieren.

27:09.360 --> 27:12.720
Also auch das ist hier damit zu sehen.

27:12.780 --> 27:14.920
Wir können also Codes angeben, bei denen wir Fehler korrigieren

27:14.920 --> 27:15.260
können.

27:15.800 --> 27:18.260
Bei dem mit dem Abstand 6 hatten wir gesehen, da können wir sogar

27:18.260 --> 27:19.440
Doppelfehler korrigieren.

27:21.460 --> 27:23.400
Hier nochmal dieses Beispiel genau.

27:23.500 --> 27:27.320
Das sind also Fünffachfehler erkennbar, Zweifachfehler korrigierbar.

27:28.160 --> 27:33.460
Tatsächlich sind Ihre Zahlen, die Sie im Rechner speichern, die im

27:33.460 --> 27:37.520
Speicher abgelegt sind, Zwischenspeicher und Recheneinheit hin und her

27:37.520 --> 27:41.000
geschoben werden, die sind in der Regel mindestens so abgesichert,

27:41.060 --> 27:42.600
dass Sie Einfachfehler korrigieren können.

27:44.160 --> 27:46.340
Das heißt, Sie haben dort immer irgendwelche redundanten Bits drin,

27:46.460 --> 27:49.280
über die Sie solche Erkennbarkeit und Korrigierbarkeit hinbekommen.

27:50.780 --> 27:55.180
Das also zu diesen Erkennbarkeit und Korrigierbarkeit.

27:55.180 --> 27:59.580
Wie kann ich einem bei einem Code diese Eigenschaften dazufügen?

28:00.040 --> 28:05.160
Eine Möglichkeit ist zum Beispiel, dass ich zu einer Zahl bin, also

28:05.160 --> 28:10.200
hier irgendeine Zahl habe, meinetwegen so etwas, 5 Bit, dann kann ich

28:10.200 --> 28:17.460
ein Bit dranhängen, ein Prüfbit und dieses Prüfbit kann man entweder

28:17.460 --> 28:21.920
als Odd oder Even Parity Check machen, also ich überprüfe, ob die

28:21.920 --> 28:26.220
Anzahl der Bits in meinem Wort ungerade oder gerade ist.

28:26.380 --> 28:32.280
Wenn sie ungerade ist, dann schreibe ich da eine 1 hin und Even wäre,

28:33.140 --> 28:36.800
prüfe, ob die Anzahl der Bits in meinem Codewort, also wenn ich hier

28:36.800 --> 28:40.580
irgendwie sowas hätte, dann würde ich als Prüfbit da eine 0

28:40.580 --> 28:41.940
hinschreiben.

28:42.020 --> 28:45.880
Das heißt, ich habe dann geprüft, ob in dem Wort jetzt eine ungerade

28:45.880 --> 28:49.140
Zahl von 1 sind oder eine gerade Zahl von 1 und schreibe da

28:49.140 --> 28:50.660
entsprechend eine 1 oder eine 0 hin.

28:50.740 --> 28:53.660
Sie wissen, ich kann sowas das gerade durch die XOR-Funktion

28:53.660 --> 28:54.600
hinbekommen.

28:55.760 --> 29:01.820
Das ist praktisch das XOR der Bits, die in dem Wort drinstehen.

29:02.180 --> 29:05.460
Wenn ich eine solche Veränderung gemacht habe oder solch eine

29:05.460 --> 29:11.840
Ergänzung gemacht habe, kann man sich leicht überlegen, dann ist der

29:11.840 --> 29:15.060
Hemming -Abstand zwischen je zwei Codewörtern gleich 2.

29:15.840 --> 29:16.280
Warum?

29:17.840 --> 29:24.200
Es haben ja dann alle meine Codewörter, wenn ich also dieses hier mir

29:24.200 --> 29:31.240
anschaue, da prüfe ich auf ungerade Anzahl von Bits und füge da eine 1

29:31.240 --> 29:33.180
hinzu, wenn es ungerade ist.

29:33.380 --> 29:37.420
Das heißt, dann habe ich insgesamt eine gerade Zahl von Bits, wenn ich

29:37.420 --> 29:38.760
das Parität-Bit mitzähle.

29:40.340 --> 29:44.280
Das heißt aber, dass zwei verschiedene Codewörter in so einem

29:44.280 --> 29:47.600
abgesicherten Code immer eine gerade Zahl von Einsen haben.

29:48.480 --> 29:53.760
Wenn ich immer eine gerade Anzahl von Einsen habe, in diesem Fall dann

29:53.760 --> 29:58.720
6 -Bit-Zahlen, dann ist ein Einfachfehler sofort zu erkennen, weil ich

29:58.720 --> 30:00.840
dadurch auf eine ungerade Anzahl von Einsen komme.

30:00.980 --> 30:03.420
Es wird entweder eine 0 zu 1 oder eine 1 zu einer 0.

30:04.040 --> 30:08.000
Dadurch verändern sich auf jeden Fall die Anzahl der Einsen.

30:08.520 --> 30:12.060
Damit erkenne ich sofort, dass ein Einfachfehler erkannt wurde.

30:12.160 --> 30:14.360
Ich habe also einen Mindestabstand von 2.

30:14.880 --> 30:17.560
Muss ja mindestens an zwei Stellen etwas verändern, damit ich von

30:17.560 --> 30:19.940
einer geraden Zahl wieder zu einer geraden Zahl komme.

30:21.400 --> 30:22.960
Jetzt kann man das ergänzen.

30:23.060 --> 30:27.920
Man kann noch weitere Prüfbits anhängen und kann dadurch die Abstände

30:27.920 --> 30:30.960
zwischen benachbarten Wörtern erhöhen.

30:32.000 --> 30:33.440
Und das macht man auch.

30:34.060 --> 30:39.300
Man kann das machen für jedes einzelne, wie hier, für jedes einzelne

30:39.300 --> 30:42.720
Codewort ein Bit dranhängen und kann dadurch den Abstand erhöhen.

30:43.260 --> 30:46.580
Ich kann aber auch folgendes machen, dass ich hier eine Reihe von

30:46.580 --> 30:51.240
Wörtern betrachte und dann habe ich hier am Ende ein Prüf.

30:51.620 --> 30:55.580
Das wäre jetzt also mein Prüfbereich.

30:55.720 --> 31:00.540
Da hätte ich jetzt mehrere Bits und jedes Bit prüft unterschiedliche

31:00.540 --> 31:01.760
Eigenschaften dieses Codes.

31:02.920 --> 31:07.440
Dazu gibt es einiges an Theorie, wie man sowas machen kann, dass man

31:07.440 --> 31:10.760
durch verschiedene Bits unterschiedliche Eigenschaften dieses Codes

31:10.760 --> 31:11.380
absichert.

31:11.920 --> 31:14.720
Man kann also Parität an verschiedenen Stellen absichern oder noch

31:14.720 --> 31:18.620
andere Eigenschaften überprüfen und kann dadurch eventuell einen

31:18.620 --> 31:20.680
ganzen Block absichern.

31:21.080 --> 31:27.020
Auch das wird gemacht, wird häufig, da der Zugriff auf Daten in der

31:27.020 --> 31:30.380
Regel blockweise passiert im Speicher und nicht auf der Ebene

31:30.380 --> 31:35.080
einzelner Register, ist es so, dass man häufig einen ganzen Block

31:35.080 --> 31:38.980
absichert und dadurch auch überprüft, ob der gesamte Block ein Fehler

31:38.980 --> 31:39.740
enthält oder nicht.

31:40.460 --> 31:45.560
Deswegen diese unterschiedlichen Arten der Bits, die man hier als

31:45.560 --> 31:46.620
Prüfbits dazufügt.

31:47.480 --> 31:49.820
Sie kennen das auch von der Matrikelnummer.

31:50.000 --> 31:51.220
Sie kennen alle ihre Matrikelnummer.

31:51.440 --> 31:53.100
Da sind auch Kontrollziffern drin.

31:53.500 --> 31:55.560
Das heißt, nicht jede Matrikelnummer ist gültig.

31:56.060 --> 31:59.320
Da ist ein Algorithmus dahinter, der überprüfen kann, ob das eine

31:59.320 --> 32:01.660
korrekte Matrikelnummer ist oder nicht.

32:02.440 --> 32:10.120
Und damit hat man also dann eine Möglichkeit, da auch Eingabefehler zu

32:10.120 --> 32:12.720
erkennen, beziehungsweise etwas zu korrigieren.

32:13.660 --> 32:15.380
Und bei Kontonummern ist es ähnlich.

32:15.580 --> 32:17.980
Da sind auch nicht jede Kontonummer ist gültig, sondern die haben auch

32:17.980 --> 32:20.120
gewisse Fehlererkennungs- und Korrektureigenschaften.

32:21.540 --> 32:27.380
Es gibt eine sehr umfangreiche Theorie für diesen ganzen Arten der

32:27.380 --> 32:27.920
Codierung.

32:28.680 --> 32:31.520
Hier noch ganz kurz diese Theorie.

32:32.120 --> 32:35.800
Es gibt dicke Bücher über Codierungstheorie, es gibt algebraische

32:36.520 --> 32:40.380
Codes, es gibt lineare Codes, es gibt unterschiedlichste Arten, wie

32:40.380 --> 32:42.220
man solche Codes entwickeln kann.

32:42.820 --> 32:46.260
Ich habe Ihnen im Prinzip nur die einfachsten Grundlagen jetzt

32:46.260 --> 32:46.860
dargestellt.

32:47.020 --> 32:50.920
Nur gesagt, dass man überhaupt sich beschäftigt mit der Frage, ist

32:50.920 --> 32:54.460
etwas fehlererkennbar oder fehlerkorrigierbar?

32:55.340 --> 32:59.240
Und wie man dann diese Eigenschaften erreicht, das ist jetzt eine

32:59.240 --> 33:01.060
andere Sache.

33:01.180 --> 33:04.320
Da muss man wesentlich stärker in die Codierungstheorie hineingehen.

33:04.380 --> 33:08.880
Dazu fehlt mir die Zeit, aber ich musste Ihnen diese Aspekt einmal

33:08.880 --> 33:13.920
darstellen und für einfache Arten der Ergänzung von Codes habe ich

33:13.920 --> 33:18.440
Ihnen hier ein Beispiel genannt, über eben diese Paritätsabsicherung

33:18.440 --> 33:23.380
oder Sie werden an den Übungsaufgaben da noch ein bisschen mehr machen

33:23.380 --> 33:23.760
können.

33:24.520 --> 33:26.420
Das also zur Fehlererkennung und Fehlerkorrektur.

33:27.200 --> 33:30.400
Es kommt noch eine andere Codierung, nämlich die häufigkeitsabhängige

33:30.400 --> 33:30.840
Codierung.

33:31.440 --> 33:36.060
Da geht es um ein völlig anderes Problem, weil eben hatten wir eine

33:36.060 --> 33:38.960
Codierung, bei der alle Wörter gleich viele Bits hatten.

33:40.440 --> 33:44.630
Alle Wörter gleich viele Bits heißt natürlich, wenn ich jetzt oder

33:45.000 --> 33:48.180
alle Zeichen gleich viele Wörter, alle Codewörter haben gleich viele

33:48.180 --> 33:51.140
Bits, also alle Zeichen werden auf Wörter gleicher Länge abgebildet.

33:51.900 --> 33:55.700
Wenn ich jetzt einen Text codieren möchte, also zum Beispiel hier

33:55.700 --> 34:00.380
dieses Wort häufigkeitsabhängige Codierungen, könnte ich mir

34:00.380 --> 34:03.780
überlegen, jedes Zeichen auf meinetwegen einen Byte, damit kann ich

34:03.780 --> 34:04.780
jedes Zeichen darstellen.

34:04.860 --> 34:11.000
Mit einem Byte kann ich die codieren und dann hätte ich sofort so

34:11.000 --> 34:13.000
viele Bytes, wie ich hier Zeichen habe.

34:13.100 --> 34:13.660
Ganz einfach.

34:14.760 --> 34:17.280
Das Interessante ist aber, wenn sich hier dieses Wort angucken,

34:18.060 --> 34:23.020
häufigkeitsabhängige Codierungen, da finden sie zum Beispiel hier mal

34:23.020 --> 34:23.900
ein E.

34:24.920 --> 34:28.580
Wir finden 1, 2, 3, 4 mal ein G.

34:28.580 --> 34:32.680
Wir finden ein N dreimal.

34:33.400 --> 34:35.540
Also einige Zeichen kommen häufiger vor als andere.

34:37.220 --> 34:42.020
Und wenn sie jetzt bei der Codierung ihrer Wörter oder ihrer Zeichen

34:42.020 --> 34:46.540
berücksichtigen, dass einige Zeichen häufiger vorkommen, dann kann man

34:46.540 --> 34:49.400
natürlich auf die Idee kommen, diese Zeichen, die häufig vorkommen,

34:49.980 --> 34:53.260
die codiere ich einfach mit weniger Bits als solche, die seltener

34:53.260 --> 34:53.680
vorkommen.

34:54.640 --> 34:58.060
Das steckt übrigens so ein bisschen hinter der Morse-Codierung.

34:58.940 --> 35:01.220
Da ist das E mit einem Zeichen codiert.

35:02.840 --> 35:05.620
Ein Zeichen heißt, das E taucht ganz oft auf.

35:06.460 --> 35:08.560
Deswegen habe ich das in einem Zeichen erledigt.

35:09.960 --> 35:13.040
Und andere Zeichen, wenn Sie sich den Morsebaum anschauen, werden Sie

35:13.040 --> 35:16.140
feststellen, dass Zeichen, die nicht so häufig vorkommen in unserem

35:16.140 --> 35:20.280
normalen Text, die haben deutlich mehr Zeichen.

35:20.600 --> 35:23.200
Also mehr einzelne Bits und Dats.

35:25.040 --> 35:29.560
Das heißt, wir verkürzen einfach die Nachrichten durch Wahl von kurzen

35:29.560 --> 35:32.380
Codewörtern für häufige Zeichen und langen Codewörtern für seltene

35:32.380 --> 35:32.820
Zeichen.

35:33.840 --> 35:37.600
Genau das setzen Sie ein, wenn Sie eine Komprimierung einer Datei

35:37.600 --> 35:37.860
machen.

35:37.940 --> 35:42.340
Wenn ich sage, ich zippe diese Datei, dann verändern Sie die Codierung

35:42.340 --> 35:48.040
dieser Datei dadurch, dass Sie die Informationen in der Datei

35:48.040 --> 35:50.080
häufigkeitsabhängig neu codieren.

35:52.080 --> 35:56.780
Also häufig auftretende Informationen mit weniger Bits, seltener

35:56.780 --> 35:58.100
auftretende mit mehr Bits.

35:58.980 --> 36:03.260
Dann haben Sie eine das sparende Codierung Ihrer Originaldatei.

36:04.100 --> 36:07.140
Das kann erheblich Platz einsparen.

36:07.620 --> 36:10.520
Ich brauche dann natürlich eine Häufigkeitsverteilung.

36:11.440 --> 36:13.680
Die kann ich für jede Datei berechnen.

36:14.500 --> 36:17.880
Ich könnte also hier die Zeichen auf dieser Seite einmal kurz

36:17.880 --> 36:21.760
durchzählen, die Häufigkeit der einzelnen Zeichen bestimmen und für

36:21.760 --> 36:23.860
diese Seite eine optimale Codierung machen.

36:24.380 --> 36:28.860
Wenn Sie also eine Datei zippen, dann wird im Prinzip genau das

36:28.860 --> 36:31.900
gemacht, allerdings nicht bezogen auf einzelne Zeichen, sondern

36:31.900 --> 36:34.340
bezogen auf kleinere Zeichenfolgen.

36:35.200 --> 36:37.040
Da steckt also noch ein bisschen mehr dahinter, als nur einzelne

36:37.040 --> 36:38.200
Zeichen anzuschauen.

36:38.600 --> 36:42.800
Ich werde Ihnen jetzt zeigen, wie man eine Codierung machen kann, bei

36:42.800 --> 36:48.440
der man nur die Häufigkeit der einzelnen Zeichen sich anschaut und

36:48.440 --> 36:49.680
entsprechend codiert.

36:50.680 --> 36:54.440
Wir brauchen dafür also die beiden Zeichenvorräte A und B.

36:54.600 --> 36:58.080
A das Ausgangsalphabet, das wir codieren wollen, B das Bildalphabet

36:58.080 --> 37:03.020
und wir brauchen eine Wahrscheinlichkeitsverteilung auf unseren

37:03.020 --> 37:03.820
Zeichen.

37:04.440 --> 37:07.000
Wir müssen wissen, wie oft die vorkommen und dann machen wir eine

37:07.000 --> 37:08.960
Häufigkeitsabhängige Codierung.

37:09.760 --> 37:13.540
Und diese Wahrscheinlichkeitsfunktion, die kommt halt einfach aus

37:13.540 --> 37:14.940
einer Analyse eines Textes.

37:15.380 --> 37:17.260
Dann habe ich diese Verteilung.

37:17.260 --> 37:20.840
Natürlich muss die Codierung injektiv sein und die Fahnenbedingungen

37:20.840 --> 37:22.920
erfüllen, damit ich es wieder rückgängig machen kann.

37:23.880 --> 37:28.320
Und dann habe ich also hier eine injektive Codierung, die das erfüllt.

37:29.300 --> 37:32.800
Und zunächst mal schaut man sich für eine beliebige injektive

37:32.800 --> 37:36.180
Codierung, die die Fahnenbedingungen erfüllt, folgende Eigenschaft an.

37:36.640 --> 37:38.880
Ich schaue mir die sogenannte Codlänge an.

37:39.300 --> 37:44.960
Und die Codlänge bekomme ich dadurch, dass ich von allen Codwörtern

37:44.960 --> 37:52.180
die Länge betrachte und die Wahrscheinlichkeit des Auftretens dieses

37:52.180 --> 37:56.840
Zeichens, also die Länge des Codeworts, das A zugeordnet ist,

37:56.940 --> 38:02.400
multipliziert mit der Wahrscheinlichkeit von A, gibt mir aufsummiert

38:02.400 --> 38:05.680
über alle Zeichen des Alphabets die Codlänge.

38:07.560 --> 38:12.260
Und die Codlänge charakterisiert natürlich, wie gut ich mit diesem

38:12.260 --> 38:16.760
Code etwas abbilden kann oder etwas codieren kann.

38:17.720 --> 38:22.440
Und das Ganze ist optimal, wenn diese Codlänge minimal ist bezüglich

38:22.440 --> 38:26.760
aller möglichen Codierungen mit diesen Eigenschaften, also injektiv

38:26.760 --> 38:27.580
und Fahnenbedingungen.

38:28.460 --> 38:31.920
Da schauen wir, dass möglichst wenig Zeichen zu machen.

38:33.200 --> 38:38.500
Kurze Überlegung, wenn Sie nur die Dezimalziffern sich anschauen.

38:39.800 --> 38:43.180
Dezimalziffern, da haben Sie zehn verschiedene, normalerweise sind wir

38:43.180 --> 38:44.120
vier Bits dafür.

38:45.100 --> 38:50.520
Vier Bits für zehn Zeichen, das heißt wir hätten dann eine Codlänge

38:50.520 --> 38:54.800
von, wenn wir also vier Bits nehmen jeweils, dann hätten wir eine

38:54.800 --> 38:55.900
Codlänge von 40.

38:57.260 --> 38:58.260
Zehn mal vier Bit.

38:59.440 --> 39:03.800
Wenn Sie alle, egal wie wahrscheinlich die jetzt sind, nehmen wir alle

39:03.800 --> 39:05.580
gleich wahrscheinlich, wäre 40.

39:06.120 --> 39:09.500
Wenn die unterschiedlich wahrscheinlich sind, dann wäre das

39:09.500 --> 39:12.380
entsprechend, nicht Quatsch, nicht 40, sondern vier.

39:12.560 --> 39:15.080
Wenn Sie gleich wahrscheinlich wären, würden Sie jeweils ein Zehntel

39:15.080 --> 39:19.820
nehmen und dann hätten Sie also die Summe der Codlänge, die Summe der

39:19.820 --> 39:22.940
Längen der Codwörter durch zehn dividiert, wäre also gerade vier.

39:23.540 --> 39:28.660
Das wäre die Codlänge bei einem Blockcode mit gleiche Länge für alle

39:28.660 --> 39:29.160
Codwörter.

39:29.280 --> 39:33.420
Da wäre also gleiche Wahrscheinlichkeit, wäre also dann die, die

39:33.420 --> 39:36.360
Codlänge wäre dann immer gerade gleich dieser Anzahl von Bits.

39:36.420 --> 39:40.120
Wenn Sie unterschiedliche Wortlängen haben, dann kann die Zahl kleiner

39:40.120 --> 39:43.440
oder auch größer sein und dann sucht man sich halt die Codierung, die

39:43.440 --> 39:45.020
die kleinste Länge hat.

39:45.840 --> 39:50.860
Also nochmal Codlänge, Produkt aus Wahrscheinlichkeiten mal Wortlänge,

39:51.240 --> 39:53.360
gibt Ihnen die Codlänge an, für das Alphabet.

39:54.300 --> 39:57.200
Und jetzt schauen wir uns an, mal kurz hier so eine Tabelle.

39:58.640 --> 40:03.160
Interessanterweise haben wir in der deutschen Sprache gewisse Zeichen

40:03.160 --> 40:05.940
häufiger, gewisse Zeichen weniger häufig, das wissen Sie aber auch.

40:06.240 --> 40:11.340
In der deutschen Sprache ist das Zeichen, das am häufigsten vorkommt,

40:11.820 --> 40:19.080
hier nach dieser Tabelle, die hier herkommt aus einem Buch von Bauer,

40:19.500 --> 40:20.800
über effiziente Geheimnisse.

40:22.060 --> 40:27.060
Entzifferte Geheimnisse, nicht entzifferte Geheimnisse von Bauer, der

40:27.060 --> 40:29.860
hat das mal hier auch zitiert.

40:31.380 --> 40:35.400
Da steht also, dass das A demnach bei uns, das häufigste Zeichen wäre.

40:35.620 --> 40:38.020
Ich dachte, das wäre das E, aber es ist, nein, Quatsch.

40:38.980 --> 40:41.460
Ich bin ja hier, das E, selbstverständlich, danke sehr.

40:41.980 --> 40:44.640
Mit 17 Prozent, ich war völlig verrutscht hier, das sind ja zwei

40:44.640 --> 40:47.640
verschiedene, zwei Tabellen nebeneinander.

40:48.540 --> 40:52.700
Also, selbstverständlich ist es die 17 hier, im Deutschen und im

40:52.700 --> 40:55.420
Englischen ist es auch das E, aber die anderen Wahrscheinlichkeiten

40:55.420 --> 40:56.560
sind ein bisschen unterschiedlich.

40:57.080 --> 41:03.000
Also zum Beispiel das Z kommt im Englischen mit 0,09 vor, im Deutschen

41:03.000 --> 41:12.100
mit 1,14 und das Y kommt hier im Englischen vor mit 1,73 und im

41:12.100 --> 41:13.300
Deutschen mit 0,08.

41:14.200 --> 41:17.080
Sie werden vielleicht bemerkt haben, dass auf Tastaturen Plätze von Y

41:17.080 --> 41:20.100
und Z häufig gerade vertauscht sind, das hängt damit zusammen.

41:20.700 --> 41:24.440
Also auch die Anordnung auf der Fingertastatur hängt auch mit den

41:24.440 --> 41:26.060
Wahrscheinlichkeiten der Zeichen zusammen.

41:27.540 --> 41:29.500
Deswegen spielt das auch da eine Rolle.

41:30.480 --> 41:33.300
Das sind also die Wahrscheinlichkeiten für das Auftreten in deutschen

41:33.300 --> 41:34.360
oder englischen Texten.

41:35.540 --> 41:38.940
Sie können sagen, ich möchte generell deutsche Texte kodieren, dann

41:38.940 --> 41:42.040
mache ich das so, dass ich hier diese Wahrscheinlichkeitsverteilung

41:42.040 --> 41:46.300
dieser Zeichen im Deutschen hernehme.

41:46.680 --> 41:50.200
Sie können aber auch sagen, ich nehme mir ein Dokument her und

41:50.200 --> 42:00.140
extrahiere daraus die Anzahl der Zeichen, Anzahl A, Anzahl B und so

42:00.140 --> 42:00.480
weiter.

42:00.780 --> 42:05.420
Die Anzahl aller Zeichen da drin und dann habe ich die Anteile der

42:05.420 --> 42:10.840
einzelnen Zeichen in diesem Dokument und kann dann bezogen auf die

42:10.840 --> 42:13.980
Häufigkeiten in dem realen Dokument diese Verteilung machen.

42:16.120 --> 42:19.560
Üblicherweise ist eine optimale Kodierung nicht eindeutig bestimmt und

42:19.560 --> 42:22.860
ich werde jetzt ein Verfahren vorführen, mit dem man eine optimale

42:22.860 --> 42:27.960
Verteilung hinbekommen kann und die Idee läuft jetzt wie folgt.

42:28.680 --> 42:32.840
Wir schauen uns einfach an, die Wahrscheinlichkeiten.

42:33.040 --> 42:38.960
Nehmen wir einfach mal hier dieses Wort Wahrscheinlichkeiten.

42:39.920 --> 42:45.380
Das fängt an mit, ich hoffe ich kriege das hier einigermaßen hin, geht

42:45.380 --> 42:58.400
los mit einem B, danach kommt ein A, ein H, ein R, ein S, ein C, das H

42:58.400 --> 43:10.720
hatten wir schon, da kommt ein E, ein I, ein N, ein L, das I war schon

43:10.720 --> 43:16.460
da, das C war schon da, das H war schon da, ein K, ein E war da, ein I

43:16.460 --> 43:24.020
war da, ein P, das E war schon da und das N war schon da.

43:25.500 --> 43:26.880
So, wie oft kommt das vor?

43:27.020 --> 43:33.460
Das kommt einmal vor, das W, das A kommt einmal vor, das H kommt 1, 2,

43:33.700 --> 43:45.700
3 mal vor, das R in dem Fall kommt einmal vor, das S kommt einmal

43:45.700 --> 43:55.300
einmal, das C kam zweimal vor, das E kam dreimal vor, I kam dreimal

43:55.300 --> 44:02.080
vor, N zweimal, L einmal, K einmal, T einmal.

44:02.840 --> 44:06.420
So, das sind die Häufigkeiten der Zeichen in dem Wort

44:06.420 --> 44:07.180
Wahrscheinlichkeiten.

44:08.540 --> 44:11.660
Kurzes Wort, was machen wir jetzt?

44:11.740 --> 44:14.840
Wir bilden einfach, ich habe jetzt hier nicht Wahrscheinlichkeiten

44:14.840 --> 44:16.040
stehen, ich habe Häufigkeiten stehen.

44:16.340 --> 44:17.740
Ich kann es aber auch über Häufigkeiten machen.

44:18.280 --> 44:20.420
Ich müsste Wahrscheinlichkeiten kriegen, indem ich einfach durch die

44:20.420 --> 44:21.500
Länge des Wortes dividiere.

44:23.040 --> 44:25.440
Jetzt bilde ich einfach Knoten.

44:26.400 --> 44:30.120
Ich tue also so, als wären diese Zeichen jetzt Knoten und hier der

44:30.120 --> 44:32.420
Knoten ist markiert mit der Wahrscheinlichkeit.

44:33.440 --> 44:36.240
Also ich habe das jetzt praktisch gerade gemacht.

44:36.640 --> 44:40.580
Ich habe also hier praktisch jetzt einen solchen Knoten gebildet.

44:41.160 --> 44:45.700
B mit der Wahrscheinlichkeit 1, A mit der Wahrscheinlichkeit 1, H mit

44:45.700 --> 44:47.080
der Wahrscheinlichkeit 3 und so weiter.

44:47.700 --> 44:50.420
Und dann läuft folgenden Algorithmus ab.

44:51.800 --> 44:54.360
Ich zeige Ihnen jetzt hier den ganzen Algorithmus.

44:55.800 --> 44:57.020
Was machen wir?

44:59.020 --> 45:01.360
Solange ich in der...

45:02.020 --> 45:05.300
Also L ist jetzt hier die Menge aller dieser Knoten zu Anfang.

45:05.900 --> 45:10.220
Das wäre also die gesamte Menge von W bis T, beziehungsweise dieses

45:10.220 --> 45:13.880
hier wären die ganzen Knoten, die ich jetzt zur Verfügung habe.

45:13.980 --> 45:15.860
Die Zeichen, die ich dort kodieren muss.

45:16.840 --> 45:18.740
Jetzt nehme ich sukzessive Zeichen raus.

45:19.500 --> 45:24.540
Ich nehme also zwei Knoten raus, KL und KR, die die geringsten

45:24.540 --> 45:25.460
Bewertungen haben.

45:26.620 --> 45:28.460
Zwei Zeichen mit den geringsten Bewertungen.

45:28.540 --> 45:31.520
Ich male jetzt gleich hier über diesen Code rüber.

45:31.680 --> 45:32.820
Das ist aber nicht weiter schlimm, denke ich.

45:32.840 --> 45:33.980
Das kann man trotzdem noch hinbekommen.

45:34.700 --> 45:36.380
Ich nehme also zum Beispiel diese beiden hier.

45:36.540 --> 45:37.580
Die haben Einsen.

45:38.320 --> 45:39.660
Und male hier eine Zwei hin.

45:39.940 --> 45:42.900
Das ist die Summe der beiden Bewertungen.

45:43.680 --> 45:46.740
Ich habe zwei Knoten rausgenommen mit den geringsten Bewertungen.

45:47.360 --> 45:48.660
Da habe ich viele zur Auswahl.

45:49.520 --> 45:53.760
Und schreibe die Summe der beiden Bewertungen an den neuen Knoten ran.

45:54.680 --> 45:57.280
Zwei rausgenommen, einen neuen hinzugefügt.

45:57.980 --> 46:00.380
Also, ich füge die Kanten.

46:00.680 --> 46:02.680
KO, KL und KO, KR.

46:03.000 --> 46:04.620
Der neue Knoten war das KO.

46:06.940 --> 46:08.620
Füge ich in den Graphen ein.

46:09.800 --> 46:12.760
Und nehme also dieses KL und KR raus.

46:12.960 --> 46:14.140
Und KO füge ich hinzu.

46:15.180 --> 46:16.620
Dann mache ich das weiter so.

46:16.620 --> 46:18.800
Wieder zwei Knoten mit den geringsten Bewertungen.

46:18.920 --> 46:19.980
Zum Beispiel diese hier.

46:20.560 --> 46:21.600
Kommt auch eine Zwei hin.

46:22.380 --> 46:25.080
Dann habe ich noch, meinetwegen, diese beiden.

46:25.940 --> 46:26.900
Kommt auch eine Zwei hin.

46:28.160 --> 46:29.180
Jetzt geht das weiter.

46:30.200 --> 46:32.300
Da habe ich einmal noch eine Eins.

46:33.560 --> 46:35.040
Und ansonsten habe ich eine ganze Reihe.

46:35.200 --> 46:36.060
Das sind Zweien.

46:36.680 --> 46:39.520
Dann würde ich zum Beispiel diese beiden zusammenfügen.

46:39.640 --> 46:40.620
Und dann eine Drei hinschreiben.

46:42.060 --> 46:44.840
Dann habe ich jetzt einige, das sind Zweien.

46:44.840 --> 46:47.460
Ich habe Zweien und Dreien jetzt noch drin.

46:47.540 --> 46:49.100
Wenn ich das richtig gemacht habe.

46:49.720 --> 46:53.220
Dann kann ich jetzt irgendwelche Knoten kombinieren, die mit einer

46:53.220 --> 46:59.640
Zwei beschriftet sind.

46:59.820 --> 47:01.760
Zum Beispiel diese beiden.

47:01.860 --> 47:03.040
Dann kommt da eine Vier raus.

47:05.360 --> 47:11.760
Oder ich füge diese Zwei zusammen mit der Zwei.

47:11.760 --> 47:14.020
Dann kommt da auch eine Vier raus.

47:16.200 --> 47:19.780
Und jetzt habe ich hier, die Zweien sind ja rausgegangen.

47:20.920 --> 47:22.060
Was habe ich hier noch übrig?

47:24.280 --> 47:26.140
Dreien und Vieren.

47:26.320 --> 47:27.980
Dann muss ich die Dreien zusammenfügen.

47:28.900 --> 47:34.240
Zum Beispiel diese Drei und die Drei.

47:34.560 --> 47:36.060
Das gibt sechs.

47:37.140 --> 47:39.420
Dann muss ich noch zusammenfügen.

47:39.520 --> 47:40.880
Dann bleibt diese Drei noch übrig.

47:41.760 --> 47:46.280
Also meinetwegen die Drei und die Drei.

47:46.700 --> 47:47.880
Das gibt auch eine Sechs.

47:49.560 --> 47:54.520
Und jetzt habe ich hier oben, passen Sie auf, ob ich alles richtig

47:54.520 --> 47:56.980
mache, dürfte keine Drei mehr übrig sein.

47:57.080 --> 48:00.660
Ich habe hier noch die Vieren, die Zwei und die Sechsen.

48:01.460 --> 48:05.100
Jetzt müsste ich die beiden Vieren zusammen basteln.

48:05.960 --> 48:08.340
Daraus, Vier plus Vier gibt Acht.

48:09.540 --> 48:11.360
Und jetzt habe ich hier noch zwei Sechsen.

48:12.120 --> 48:13.520
Die beiden bastel ich zusammen.

48:13.640 --> 48:14.940
Dann kommt da eine Zwölf raus.

48:16.200 --> 48:17.500
Das sollte eine Zwölf sein.

48:18.040 --> 48:19.920
Dann muss ich die beiden noch zusammen basteln.

48:20.040 --> 48:21.320
Und es kommt eine Zwanzig raus.

48:22.100 --> 48:24.760
Es müssten gerade Zwanzig Zeichen in dem Wort Wahrscheinlichkeiten

48:24.760 --> 48:25.220
gewesen sein.

48:26.020 --> 48:26.180
So.

48:27.020 --> 48:30.120
Jetzt habe ich genau das gemacht, was hier steht, in diesem Teil zwei.

48:31.100 --> 48:34.740
Ich habe jeweils die Knoten mit den kleinsten Beschriftungen genommen.

48:35.820 --> 48:36.700
Die zusammengenommen.

48:36.700 --> 48:39.800
Die Summe der beiden Bewertungen dort in die neuen Knoten

48:39.800 --> 48:40.400
reingeschrieben.

48:41.040 --> 48:41.980
Und jetzt bin ich fertig.

48:42.040 --> 48:43.260
Ich habe hier die Zahl Zwanzig drin.

48:43.320 --> 48:46.900
Wenn da Wahrscheinlichkeiten stehen, dann müssten am Ende dort eine

48:46.900 --> 48:47.860
Eins rauskommen.

48:48.040 --> 48:48.480
Eins Null.

48:48.560 --> 48:51.700
In diesem Fall ist das gerade die Anzahl der Zeichen in dem Wort

48:51.700 --> 48:52.500
Wahrscheinlichkeiten.

48:53.540 --> 48:56.480
Und jetzt habe ich einen Baum.

48:57.640 --> 49:01.640
Und den Baum verwende ich jetzt, um meinen Co zu erzeugen.

49:01.640 --> 49:08.320
Ich beschrifte jede nach links verlaufende Kante im Baum mit O und

49:08.320 --> 49:10.800
jede nach rechts verlaufende Kante mit 1.

49:11.360 --> 49:16.000
Also nach links, nach links, nach links, nach links.

49:17.400 --> 49:18.740
Da geht eine nach rechts.

49:19.620 --> 49:20.700
Da ging eine nach rechts.

49:21.060 --> 49:22.000
Da ging eine nach rechts.

49:23.720 --> 49:25.040
Die geht nach rechts.

49:25.360 --> 49:26.500
Die geht nach links.

49:27.920 --> 49:28.910
Nach links.

49:28.910 --> 49:29.290
Die geht nach links.

49:30.110 --> 49:30.870
Die ging da oben hin.

49:32.470 --> 49:34.450
Hier geht eine nach rechts.

49:35.170 --> 49:35.630
Eine Eins.

49:36.130 --> 49:37.670
Die ging gleich da ganz oben hin.

49:37.890 --> 49:39.430
Hier male ich eine Eins hin.

49:39.970 --> 49:44.170
Da eine Null.

49:45.490 --> 49:46.970
Jetzt muss ich aufpassen.

49:47.030 --> 49:48.210
Ich hatte hier die mit Null.

49:48.310 --> 49:49.410
Da muss da auch noch eine Null.

49:49.550 --> 49:51.850
Da oben muss eine Eins ran.

49:52.030 --> 49:53.510
Da auch eine Eins.

49:53.630 --> 49:54.930
Da müssen Nullen hin.

49:54.930 --> 49:56.250
Eine Null, eine Eins.

49:57.030 --> 49:58.230
Ich hoffe, ich habe sie alle beschriftet.

49:58.390 --> 49:59.290
Da fehlt noch eine Eins dran.

50:00.810 --> 50:05.070
Jedes Mal, wenn ich nach links gehe, eine Null, nach rechts eine Eins.

50:06.150 --> 50:07.590
Und jetzt erzeuge ich den Code.

50:08.650 --> 50:13.510
Indem ich nämlich jedem Blatt, da stehen die einzelnen Zeichen.

50:14.290 --> 50:15.790
T, L und so weiter.

50:16.550 --> 50:21.770
Ordne ich jetzt die Bits zu auf dem Pfad von der Wurzel zu diesem

50:21.770 --> 50:22.090
Blatt.

50:23.370 --> 50:25.090
Also, ich gehe jetzt hier durch.

50:26.730 --> 50:31.990
Zum Beispiel, wenn ich zu dem L hier laufen möchte, müssen wir uns

50:31.990 --> 50:32.710
hier durchhangeln.

50:33.430 --> 50:37.510
Dann steht da also rückwärts eins.

50:39.230 --> 50:40.710
Das hier ist auch eine Eins.

50:42.330 --> 50:43.350
Noch eine Eins.

50:44.210 --> 50:44.890
Noch eine Eins.

50:45.030 --> 50:48.490
Das wäre also C von L.

50:49.770 --> 50:52.050
Schauen wir uns mal ein anderes Zeichen an.

50:52.150 --> 50:54.030
Meinetwegen die Codierung von dem E.

50:56.510 --> 50:58.270
Dann haben wir hier eine Null.

51:00.870 --> 51:01.790
C von E.

51:01.910 --> 51:02.730
Das wäre eine Null.

51:02.970 --> 51:04.710
Dann wären wir da, da, da, da.

51:04.790 --> 51:06.890
Laufen wir...

51:06.890 --> 51:07.650
Nein, das stimmt ja gar nicht.

51:08.150 --> 51:08.930
Das ist ja falsch.

51:14.090 --> 51:15.410
Wir waren hier bei dem E.

51:15.590 --> 51:17.770
Auf das E kommen wir über diese Kante.

51:18.570 --> 51:20.390
Die hat hier eine Eins.

51:20.870 --> 51:24.870
Diese Kante, da war eine Drei dran, führt direkt zu der Sechs.

51:24.970 --> 51:25.750
Das ist eine Eins.

51:26.350 --> 51:27.190
Dann haben wir hier eine Null.

51:28.630 --> 51:30.530
Und wir haben da unten nochmal eine Eins.

51:31.830 --> 51:35.510
Das wäre also C von E.

51:35.770 --> 51:37.170
Das hier sollte ein L sein.

51:38.890 --> 51:40.390
Entsprechend können Sie hier durchlaufen.

51:41.010 --> 51:42.610
Und können sich die ganzen Codes anschauen.

51:42.710 --> 51:45.950
Sie werden sehen, hier sind die Unterschiede nicht so sehr groß

51:45.950 --> 51:47.670
zwischen den einzelnen Häufigkeiten.

51:47.670 --> 51:53.470
Das heißt, hier werden Sie entweder drei oder vier Bits haben.

51:54.070 --> 51:57.110
Für die Darstellung der einzelnen Zeichen.

51:57.550 --> 52:01.150
Auf jeden Fall unterschiedlich viele Bits pro Zeichen.

52:02.270 --> 52:03.610
Ich gebe Ihnen ein anderes Beispiel.

52:04.730 --> 52:05.350
Dieses hier.

52:06.010 --> 52:07.430
Wenn wir hier jetzt suchen.

52:09.270 --> 52:11.150
Diejenigen mit der kleinsten Wahrscheinlichkeit.

52:11.290 --> 52:12.670
Hier sind also wirklich die Wahrscheinlichkeiten.

52:12.730 --> 52:14.510
Ich hatte Ihnen das eben vorgeführt mit Häufigkeiten.

52:14.510 --> 52:16.190
Hier sind die Wahrscheinlichkeiten.

52:16.250 --> 52:18.310
Schauen wir uns an, welche haben hier die niedrigsten

52:18.310 --> 52:19.250
Wahrscheinlichkeiten.

52:19.890 --> 52:23.010
Das sind also zum Beispiel 0,05 und 0,04.

52:23.730 --> 52:27.410
0,04 ist die kleinste Wahrscheinlichkeit.

52:27.510 --> 52:30.050
Dann habe ich mehrere mit 0,05 hier zur Verfügung.

52:31.610 --> 52:33.510
Die Kombination ist 0,09.

52:33.790 --> 52:36.330
Dann habe ich hier zweimal 0,05, das gibt 0,1.

52:36.470 --> 52:39.790
Ich habe zweimal 0,07 und 0,06.

52:39.910 --> 52:42.570
Das gibt 0,13 als Kombination.

52:43.170 --> 52:44.850
Wenn Sie sich die anderen anschauen.

52:44.950 --> 52:47.450
Dann habe ich hier 0,08 und 0,09.

52:47.630 --> 52:49.270
Diese beiden, die kombiniert werden müssen.

52:49.830 --> 52:52.370
Als nächstes habe ich dann zur Verfügung.

52:52.590 --> 52:56.230
Hier sehen Sie, da ist übrig noch 1,5, 2,5, 2.

52:56.530 --> 52:58.390
Hier steht 0,1.

52:59.190 --> 53:01.390
Das heißt, die beiden muss ich erstmal kombinieren.

53:01.490 --> 53:02.410
Das gibt 0,23.

53:03.630 --> 53:08.110
Und so weiter bekomme ich 0,32, 0,43, 0,57.

53:08.430 --> 53:10.710
Und wenn ich die kombiniere, komme ich auf die 1,0.

53:10.710 --> 53:15.530
Das ist also einfach hier jeweils die beiden Elemente oder zwei

53:15.530 --> 53:19.530
Elemente mit den minimalen Bewertungen hergenommen.

53:20.010 --> 53:24.250
Dann komme ich hier auf die jeweiligen Wahrscheinlichkeiten in den

53:24.250 --> 53:24.750
Knoten.

53:25.510 --> 53:28.710
Und jetzt kommen hier bei den nach links laufenden Kanten überall

53:28.710 --> 53:31.130
Nullen hin, bei den nach rechts laufenden überall Einsen.

53:32.250 --> 53:35.770
Und wenn ich jetzt mir anschaue, wie sehen die Codierungen aus.

53:35.890 --> 53:37.310
Zum Beispiel die Codierung der 6.

53:37.310 --> 53:42.770
Da laufe ich halt von der Wurzel zu dem Blatt.

53:43.530 --> 53:47.170
Also habe ich hier einmal nach links, nach rechts, nach rechts, nach

53:47.170 --> 53:47.550
links.

53:47.810 --> 53:50.130
Entsprechend habe ich hier dieses als Codierung.

53:51.890 --> 53:57.050
Jetzt ist die Frage, warum laufe ich hier eigentlich von der Wurzel

53:57.050 --> 53:57.850
zum Blatt?

53:58.310 --> 53:59.990
Bei dem Codewort wäre es ja völlig egal.

54:00.150 --> 54:01.210
Könnte ich auch andersherum laufen.

54:02.030 --> 54:02.950
Es gibt das gleiche.

54:03.570 --> 54:08.690
Wenn Sie sich anschauen, hier meinetwegen die Codierung der 1.

54:09.570 --> 54:11.010
Das ist nicht egal.

54:11.470 --> 54:16.090
Wenn Sie von der Wurzel, wenn Sie hier rüber laufen von der Wurzel zum

54:16.090 --> 54:21.530
Blatt, dann kommen Sie also bei der C von 1, ist in dem Fall also

54:21.530 --> 54:23.270
gerade gleich 1 0.

54:23.810 --> 54:26.730
Wenn Sie andersherum laufen würden, hätten Sie 0 1 daraus bekommen.

54:28.050 --> 54:31.590
Warum macht man das von der Wurzel und nicht vom Blatt?

54:33.550 --> 54:36.710
Was würde passieren, wenn wir hier bei den Blättern anfangen?

54:38.390 --> 54:41.950
Hätten wir hier 0 0, 0 1 als ein Wort.

54:42.150 --> 54:44.470
Wir hätten 0, also 0 1.

54:45.030 --> 54:52.330
Wir hätten hier zum Beispiel 0 1 1.

54:53.850 --> 54:56.650
Wir hätten hier zum Beispiel...

54:57.850 --> 54:59.390
Was hätten wir denn hier für Wörter?

54:59.390 --> 55:03.830
Wenn wir bei den Blättern anfangen, hätten wir 0 0.

55:04.570 --> 55:07.410
Wir hätten dann hier 0 1.

55:08.590 --> 55:10.910
Wir hätten 0 1 1.

55:12.210 --> 55:15.710
Wir hätten 0 1 1 1.

55:17.790 --> 55:21.550
Wir hätten 0 0 1 0.

55:23.350 --> 55:24.530
Und so weiter.

55:25.150 --> 55:29.150
Fällt Ihnen daran irgendwas auf, wenn ich diese Kodierung nehme?

55:29.970 --> 55:32.290
Können wir also ein bisschen entsprechend fortsetzen.

55:32.410 --> 55:35.810
Das wären jetzt unsere Kodwörter, wenn wir bei den Blättern anfangen.

55:36.970 --> 55:40.090
Ich habe Ihnen einiges erzählt über Kodwörter, über Kodierungen und

55:40.090 --> 55:41.430
den Eigenschaften von Kodierungen.

55:42.250 --> 55:45.850
Fällt Ihnen an diesen Kodierungen etwas auf, wenn man die nehmen

55:45.850 --> 55:46.250
würde?

55:46.630 --> 55:48.230
Diese einzelnen Kodierungen.

55:51.360 --> 55:55.280
Hat irgendeiner von Ihnen eine Idee, warum man das so nicht machen

55:55.280 --> 55:55.760
sollte?

56:00.110 --> 56:01.470
Ja, genau.

56:01.650 --> 56:03.450
Ganz leise kamen gerade eben die Fano-Bedingungen.

56:04.350 --> 56:08.450
Wenn ich mir zum Beispiel diese beiden Kodwörter anschaue, dann ist

56:08.450 --> 56:12.910
doch offensichtlich 0 1 ein Präfix von 0 1 1.

56:14.730 --> 56:18.870
Das heißt, wir hätten hier ein Kodwort, das ein Präfix eines anderen

56:18.870 --> 56:19.170
ist.

56:20.310 --> 56:21.670
Das darf nicht sein.

56:22.890 --> 56:25.250
Das heißt, das hier scheidet aus.

56:27.570 --> 56:31.130
Wir wollen erreichen, dass wir immer eine dekodierbare Kodierung

56:31.130 --> 56:31.590
bekommen.

56:32.790 --> 56:34.870
Also Dekodierung, wenn wir das auf Wörter anwenden.

56:35.730 --> 56:38.710
Und wenn wir uns anschauen, die Wege von der Wurzel zu den Blättern,

56:40.210 --> 56:45.830
dann sind die Wege bei Dekodierungen auf den Wegen von der Wurzel zu

56:45.830 --> 56:53.450
den Blättern, die haben alle die Eigenschaft, dass keine Kodierung auf

56:53.450 --> 56:59.050
den Weg von der Wurzel zum Blatt Präfix eines anderen Wortes sein

56:59.050 --> 56:59.310
kann.

56:59.470 --> 57:00.210
Warum nicht?

57:01.830 --> 57:07.950
Das könnte nur dann Präfix sein, wenn ich, sobald ich bei einem Blatt

57:07.950 --> 57:12.570
gelandet bin, also hier zum Beispiel bin ich gelandet bei dem 1 0, das

57:12.570 --> 57:15.430
könnte nur dann Präfix sein, wenn ich dann auch weiterlaufen müsste.

57:16.050 --> 57:18.450
Wenn ich aber hier weiterlaufen müsste, wäre das kein Blatt.

57:20.270 --> 57:24.050
Also, wenn ich diese Baumkodierung mache, immer von der Wurzel zu den

57:24.050 --> 57:27.930
Blättern gehe, habe ich garantiert eine Kodierung, die die Fano

57:27.930 --> 57:28.770
-Bedingungen erfüllt.

57:29.470 --> 57:30.450
Injektiv ist sie sowieso.

57:31.490 --> 57:35.070
Also erfüllt sie die Eigenschaften, die wir normalerweise fordern von

57:35.070 --> 57:35.710
einer Kodierung.

57:37.410 --> 57:41.630
Deswegen, diese Fano-Bedingung erreicht man darüber, dass man von der

57:41.630 --> 57:45.450
Wurzel zu den Blättern etwas abliest und nicht andersrum.

57:47.030 --> 57:50.790
Hier ist also jetzt die Kodierung, die wir aufgrund dieses Beispiels

57:50.790 --> 57:51.790
hier gerade bekommen haben.

57:52.330 --> 57:56.370
Das sind also die Kodes für die neun Ziffern in diesem Fall.

57:56.950 --> 58:02.610
Wenn wir uns jetzt die Kodlänge ausrechnen, nicht die Kodzahl, die

58:02.610 --> 58:07.750
Kodlänge, bei dieser Kodierung der Dezimalziffern mit der

58:07.750 --> 58:11.050
Wahrscheinlichkeit, die dort hinterlegt wurde, bekommen wir eine

58:11.050 --> 58:14.090
Kodlänge von 3,04 raus.

58:15.190 --> 58:24.310
Wenn wir die Kodierung mit 4 Bits nehmen, bekommen wir, egal welche

58:24.310 --> 58:27.330
Wahrscheinlichkeitsfunktion wir nehmen, kriegen wir immer die 4 raus

58:27.330 --> 58:29.510
als Ergebnis, bei einer 4-Bit-Kodierung.

58:29.510 --> 58:34.810
Das heißt, wir haben hier eine deutlich bessere Kodierung, haben also

58:34.810 --> 58:35.690
1 gespart.

58:37.330 --> 58:42.530
Und in dem Fall kann man, oder man kann sogar nachweisen, dass jede

58:42.530 --> 58:46.610
solche Kodierung nach diesem Huffman-Algorithmus eine optimale

58:46.610 --> 58:47.550
Kodierung liefert.

58:48.270 --> 58:54.810
Wir haben also die optimale Anzahl von Bits insgesamt, wenn Sie eine

58:54.810 --> 58:55.870
Huffman -Kodierung nehmen.

58:55.870 --> 59:00.750
Das heißt, wenn Sie eine zeichenweise Kodierung eines Textes vornehmen

59:00.750 --> 59:05.210
und das machen entsprechend der Häufigkeitsverteilung dieser einzelnen

59:05.210 --> 59:10.530
Zeichen, bekommen Sie über diese Huffman-Kodierung eine optimale

59:10.530 --> 59:12.750
Darstellung dieses Textes.

59:12.830 --> 59:17.010
Sie können dann den wieder zurückkodieren in die Ausgangsdarstellung

59:17.010 --> 59:20.510
und das geht eindeutig wegen dieser Fano-Bedingungen.

59:21.570 --> 59:25.270
Also jetzt wissen Sie, wie man auf diese Art und Weise optimal etwas

59:25.270 --> 59:25.890
kodiert.

59:26.330 --> 59:26.850
Redundanzfrei.

59:28.130 --> 59:30.390
Jetzt hatte ich Ihnen gesagt, es gibt noch andere Verfahren.

59:32.490 --> 59:35.970
Also hier ist, das ist eines der, müsste eigentlich, steht hier nicht

59:35.970 --> 59:36.310
dabei.

59:36.910 --> 59:42.230
Es gibt noch die Verfahren zum Beispiel von Lempel-Ziff.

59:43.950 --> 59:48.730
Da wird ein Text nicht in Zeichen unterteilt, sondern in

59:48.730 --> 59:49.950
Zeichenfolgen.

59:49.950 --> 59:53.970
Sie schauen sich an, Zeichen folgen der Länge 2 oder Länge 3 und

59:53.970 --> 59:57.210
schauen auf diese Art und Weise sich an, wie solche Zeichen folgen,

59:57.430 --> 59:59.410
wie oft die vorkommen und kodieren die direkt.

01:00:00.230 --> 01:00:03.830
Natürlich haben Sie dann insgesamt mehr Elemente, die Sie kodieren

01:00:03.830 --> 01:00:04.190
müssen.

01:00:05.530 --> 01:00:10.910
Aber es kann insgesamt dadurch die Kodierung trotzdem besser werden.

01:00:10.990 --> 01:00:13.610
Das heißt, da muss man erst überlegen, wenn ich das so mache, was ist

01:00:13.610 --> 01:00:17.170
eigentlich die optimale Auswahl von Informationseinheiten, die ich

01:00:17.170 --> 01:00:17.770
hier kodiere.

01:00:18.610 --> 01:00:20.770
Und dann mache ich das geeignet häufigkeitsabhängig.

01:00:20.870 --> 01:00:22.430
Das ist also ein aufwendigerer Algorithm.

01:00:23.870 --> 01:00:26.750
Ich habe Ihnen auf jeden Fall jetzt eben gezeigt, es macht durchaus

01:00:26.750 --> 01:00:31.510
manchmal Sinn, etwas redundanzfrei zu kodieren, wenn es darauf

01:00:31.510 --> 01:00:34.950
ankommt, die Größe einer Datei zu reduzieren.

01:00:35.930 --> 01:00:38.030
Das ist manchmal so, dass wir das machen, wenn wir zum Beispiel

01:00:38.030 --> 01:00:40.410
irgendwas per E-Mail verschicken, wollen wir es gerne komprimieren.

01:00:40.870 --> 01:00:43.530
Und das geht halt mit solchen häufigkeitsabhängigen Kodierungen.

01:00:45.110 --> 01:00:47.990
Das waren jetzt einmal Fehlererkennung und Korrektur.

01:00:48.210 --> 01:00:51.770
Und jetzt haben wir die häufigkeitsabhängigen Kodierungen angeschaut.

01:00:52.310 --> 01:00:54.690
Mit beiden werden Sie sich noch intensiver beschäftigen können.

01:00:55.490 --> 01:00:57.670
Jetzt kommen wir schon zum nächsten Abschnitt hier drin, nämlich

01:00:57.670 --> 01:00:59.910
Darstellung von Zeichen und Ziffern.

01:01:00.150 --> 01:01:07.930
Und da geht es darum, also das eine waren vorher irgendwelche Symbole,

01:01:07.970 --> 01:01:09.070
die wir irgendwie kodieren.

01:01:09.210 --> 01:01:11.850
Jetzt geht es darum, für einen bestimmten Zweck etwas zu kodieren.

01:01:11.850 --> 01:01:17.770
Nämlich Zeichen eines Alphabets oder Ziffern geeignet zu kodieren,

01:01:17.870 --> 01:01:20.670
damit die im Rechner einfach dargestellt werden können.

01:01:21.230 --> 01:01:24.090
Natürlich muss man dafür sorgen, dass einerseits die technische

01:01:24.090 --> 01:01:26.130
Realisierung billig ist und einfach ist.

01:01:27.170 --> 01:01:28.430
Kostenoptimal möglichst.

01:01:29.290 --> 01:01:32.010
Kodierung und Dekodierung sollen auch einfach möglich sein.

01:01:32.950 --> 01:01:37.490
Und die zu realisierenden Operationen müssen natürlich auch ausführbar

01:01:37.490 --> 01:01:39.170
sein, in einer vernünftigen Art und Weise.

01:01:39.170 --> 01:01:40.630
Da kommen wir gleich nochmal drauf zurück.

01:01:42.110 --> 01:01:45.570
Ich kann einerseits feste Zeichensätze darstellen.

01:01:46.050 --> 01:01:49.350
Das wären dann zum Beispiel alle Zeichen unserer Schrift.

01:01:49.990 --> 01:01:51.930
Dazu noch irgendwelche Steuerzeichen.

01:01:52.810 --> 01:01:56.270
Und das macht man meistens mit irgendwelchen N-Bit Codes.

01:01:57.050 --> 01:02:02.110
Und hat dann entsprechend der Anzahl der Bits einen Zeichenvorrat

01:02:02.110 --> 01:02:02.430
von...

01:02:02.950 --> 01:02:06.630
also zwei hoch Anzahl der Bits ist dann gerade die Anzahl der Zeichen,

01:02:06.690 --> 01:02:07.470
die Sie darstellen können.

01:02:07.470 --> 01:02:10.370
Da gibt es Standarddarstellungen.

01:02:10.550 --> 01:02:12.670
Gebräuchliche N-Bit Codes hatte ich Ihnen schon mal genannt.

01:02:12.790 --> 01:02:15.530
Der eine war der ASCII-Code.

01:02:16.430 --> 01:02:18.950
American Standard Code for Information Interchange.

01:02:19.610 --> 01:02:24.770
Das ist ein 7-Bit-Code, der meistens noch mit einem Prüfbit erweitert

01:02:24.770 --> 01:02:26.590
wird, damit ich Fehler erkennen kann.

01:02:27.830 --> 01:02:29.590
Korrigieren kann ich sie nicht, aber ich kann sie erkennen.

01:02:30.190 --> 01:02:32.590
Mit 7 Bit kann ich 128 Bit darstellen.

01:02:33.490 --> 01:02:36.090
Manchmal verwendet man einen erweiterten ASCII-Code.

01:02:36.090 --> 01:02:37.970
Das wäre dann mit 8 Bit.

01:02:38.390 --> 01:02:40.970
Da kann ich entsprechend die doppelte Anzahl von Zeichen darstellen.

01:02:41.430 --> 01:02:44.050
Hier ist der einfache 7-Bit-Code dargestellt.

01:02:44.810 --> 01:02:50.250
Und wir stellen hier Zeichen auf eine sehr systematische Art und Weise

01:02:50.250 --> 01:02:50.590
dar.

01:02:51.050 --> 01:02:55.830
Wir trennen einfach unsere 7 Bit auf in einen 3-Bit-Präfix und 4-Bit

01:02:55.830 --> 01:02:56.730
-Suffix.

01:02:57.370 --> 01:03:02.630
Und der Präfix wird gerade genommen, um die Spalten zu adressieren in

01:03:02.630 --> 01:03:03.490
dieser Tabelle.

01:03:03.490 --> 01:03:07.550
Und der Suffix wird genommen, um die Zeilen zu adressieren.

01:03:08.490 --> 01:03:10.890
Also, wir sehen jetzt hier alle möglichen Zeichen.

01:03:10.970 --> 01:03:11.950
Was sehen Sie hier überhaupt?

01:03:12.590 --> 01:03:15.910
Wir sehen zunächst mal in diesem Bereich alle möglichen Steuerzeichen.

01:03:17.150 --> 01:03:22.730
Also zum Beispiel, dass wir anschauen, LF steht für Line Feed.

01:03:24.370 --> 01:03:28.130
Oder, lassen wir mal kurz gucken, CR, Carriage Return.

01:03:28.130 --> 01:03:32.270
Carriage Return bezieht sich also auf das Schreiben mit einer

01:03:32.270 --> 01:03:32.950
Schreibmaschine.

01:03:33.570 --> 01:03:39.970
Da muss also einmal die Schreibwalze einmal zurückgehen an die

01:03:39.970 --> 01:03:40.650
Anfangsposition.

01:03:42.030 --> 01:03:43.150
Das ist also Carriage Return.

01:03:43.990 --> 01:03:46.230
Oder Sie haben hier alle möglichen anderen Sachen noch mit drin.

01:03:46.990 --> 01:03:51.090
NAC, Negative Acknowledge, ist wichtig für TCP, also für

01:03:51.090 --> 01:03:52.050
Internetprotokoll.

01:03:52.610 --> 01:03:53.770
SYN, für Synchronize.

01:03:53.770 --> 01:03:57.270
Also alle möglichen Zeichen, die irgendwelche Steuerfunktionen haben,

01:03:57.350 --> 01:03:59.510
für die Kommunikation zwischen verschiedenen Geräten.

01:04:00.730 --> 01:04:02.530
Die Zeichen wollen Sie in der Regel gar nicht sehen.

01:04:03.250 --> 01:04:07.950
Dann gibt es Zeichen, die wollen Sie sehen, zum Beispiel den

01:04:07.950 --> 01:04:08.650
Zwischenraum.

01:04:09.770 --> 01:04:11.570
Das wäre dieses Zeichen dort.

01:04:12.170 --> 01:04:15.370
Oder Sie wollen ein Ausrufezeichen, Anführungszeichen usw.

01:04:15.490 --> 01:04:15.850
darstellen.

01:04:15.950 --> 01:04:18.570
Also das sind irgendwelche Satzzeichen, die hier stehen.

01:04:19.970 --> 01:04:21.570
Und dann kommen auf einmal die Ziffern.

01:04:21.570 --> 01:04:28.150
Das heißt, wenn wir ein Wort haben, das mit 011 beginnt, dann kommt

01:04:28.150 --> 01:04:31.390
dahinter die Darstellung einer Ziffer.

01:04:32.630 --> 01:04:36.850
Und zwar, wenn Sie sich das anschauen, ist das gerade eine 4-Bit

01:04:36.850 --> 01:04:41.210
-Codierung der Ziffern von 0 bis 9.

01:04:41.810 --> 01:04:42.250
Bis dahin.

01:04:44.310 --> 01:04:50.230
Der Wert dieser 4 Bits, dort ist gerade jeweils der Wert der Ziffer.

01:04:50.610 --> 01:04:54.110
Der Präfix 011 ist beim ASCII-Code da vorgestellt.

01:04:54.690 --> 01:04:57.730
Dahinter kommen dann noch irgendwelche Zeichen, die wir ab und zu mal

01:04:57.730 --> 01:04:58.130
brauchen.

01:04:59.030 --> 01:05:03.270
Und dann kommt hier noch das Add-Zeichen.

01:05:03.870 --> 01:05:08.130
Und dann kommen hier die Buchstaben des lateinischen Alphabetes.

01:05:08.590 --> 01:05:10.790
Erst die Großbuchstaben, dann die Kleinbuchstaben.

01:05:10.790 --> 01:05:17.370
Und Sie sehen, dass die Großbuchstaben und die Kleinbuchstaben sich

01:05:17.370 --> 01:05:20.810
nur in dem Präfix in der Codierung unterscheiden.

01:05:21.890 --> 01:05:29.010
Also die 4 Bit sind für das A gleich, egal ob es ein großer oder ein

01:05:29.010 --> 01:05:29.950
kleiner Buchstabe ist.

01:05:30.070 --> 01:05:32.710
Nur die ersten drei Bits geben diese Unterscheidung an.

01:05:32.710 --> 01:05:39.830
Das heißt aber auch, dass der Abstand zwischen einem Großbuchstaben

01:05:39.830 --> 01:05:42.790
und einem Kleinbuchstaben, egal welchen Buchstaben Sie sich hernehmen,

01:05:43.670 --> 01:05:47.450
identisch ist, sofern Sie die Linie ja anordnen.

01:05:47.570 --> 01:05:49.050
Das hier wäre ja das 0.

01:05:49.190 --> 01:05:51.410
Zeichen, das erste, zweite und so weiter.

01:05:51.870 --> 01:05:53.710
Und da unten sind sie auch durchnummeriert.

01:05:54.290 --> 01:05:59.630
Das heißt, wir haben hier das große B auf Position 50, das kleine B

01:05:59.630 --> 01:06:00.790
auf Position 82.

01:06:00.790 --> 01:06:06.570
Wir sehen es immer gerade, dieser Unterschied von 32 in der Position.

01:06:07.810 --> 01:06:13.330
Und das ist eine wichtige Angelegenheit, wenn Sie auf Zeichen

01:06:13.330 --> 01:06:14.710
-Codierungen arbeiten.

01:06:15.190 --> 01:06:18.250
Es gibt Programmiersprachen, bei denen Sie als Datentyp Zeichen zur

01:06:18.250 --> 01:06:18.970
Verfügung haben.

01:06:19.650 --> 01:06:22.810
Zum Beispiel können Sie dort direkten Zeichen reinschreiben.

01:06:23.690 --> 01:06:29.230
Dann können Sie das einfach verändern, indem Sie auf die Darstellung

01:06:29.230 --> 01:06:30.810
dieses Zeichens im Prinzip...

01:06:31.850 --> 01:06:33.930
in diesem Fall, wenn Sie etwas drauf addieren, bringt es nichts.

01:06:34.830 --> 01:06:43.370
Wenn Sie hier etwas subtrahieren, wenn Sie hier 32 subtrahieren, dann

01:06:43.370 --> 01:06:45.190
bekommen Sie das große A raus.

01:06:46.110 --> 01:06:49.770
Weil das an der Position steht, die ist um 32 kleiner als die Position

01:06:49.770 --> 01:06:50.530
des kleinen A.

01:06:50.530 --> 01:06:58.350
Sie können also auf einem Datentyp, in der Sprache Pascal ist das so,

01:06:58.450 --> 01:07:00.190
dass Sie ein Datentyp Charakter haben.

01:07:02.390 --> 01:07:06.170
Und Sie können auf einem Datentyp Charakter Operationen ausführen,

01:07:06.250 --> 01:07:07.930
weil Sie die Position der Zeichen kennen.

01:07:09.890 --> 01:07:15.610
Jetzt schauen Sie sich den nächsten Standard-Code an, das ist EBCDIC.

01:07:18.170 --> 01:07:22.430
EBCDIC, Extended Binary Coded Decimal Interchange Code.

01:07:23.150 --> 01:07:25.610
Und hier sehen Sie, ist die Tabelle viel größer.

01:07:26.410 --> 01:07:26.690
Warum?

01:07:26.930 --> 01:07:30.670
Weil wir hier 8-Bit haben, also 256 Zeichen.

01:07:32.350 --> 01:07:39.230
Und hier ist auch wieder die Aufteilung so, dass es aufgeteilt wird in

01:07:39.230 --> 01:07:39.750
X und Y.

01:07:40.550 --> 01:07:43.010
X gibt die Spalte an, Y gibt die Zeile an.

01:07:44.430 --> 01:07:48.310
Und hier sehen Sie einen gravierenden Unterschied zwischen den beiden

01:07:48.310 --> 01:07:48.950
Codierungen.

01:07:50.170 --> 01:07:52.790
Es sind also viele Felder leer gelassen worden.

01:07:53.330 --> 01:07:55.810
Steuerzeichen sind auch wieder hier vorne im unteren Bereich.

01:07:56.750 --> 01:08:00.270
Und dann tauchen hier so einige andere Zeichen noch auf.

01:08:00.330 --> 01:08:03.110
Und hier haben Sie jetzt die Zeichen des lateinischen Alphabets.

01:08:04.030 --> 01:08:08.010
Und hier steht der kleine Buchstabe an einer Position, die ist kleiner

01:08:08.010 --> 01:08:10.010
als die Position des Großbuchstaben.

01:08:11.230 --> 01:08:17.070
Stellen Sie sich mal vor, Sie haben in einem Programm geschrieben A-32

01:08:17.070 --> 01:08:21.330
und wollten daraus eigentlich das große A bekommen.

01:08:23.870 --> 01:08:27.290
Jetzt wird in Ihrem Rechner, in dem einen Rechner, der ASCII-Code

01:08:27.290 --> 01:08:30.350
verwendet, als Grundlage für die Interpretation dieser Zeichen.

01:08:31.190 --> 01:08:32.830
Und im anderen Rechner ist es EBCDIC.

01:08:34.670 --> 01:08:36.010
Dann funktioniert das gar nicht.

01:08:36.070 --> 01:08:39.070
Dann ist ein Programm nicht beliebig von einem zum anderen

01:08:39.070 --> 01:08:39.830
überführbar.

01:08:40.710 --> 01:08:45.250
Das heißt, wenn Sie auf den Codepositionen arbeiten, müssen Sie genau

01:08:45.250 --> 01:08:46.330
aufpassen, was Sie machen.

01:08:46.970 --> 01:08:50.530
Sie müssen auch aufpassen, wenn Sie hier zum Beispiel eine Schleife

01:08:50.530 --> 01:08:51.070
schreiben.

01:08:54.110 --> 01:09:00.850
Zum Beispiel C gleich A zu Z.

01:09:01.490 --> 01:09:07.370
Das ist nicht Java-Syntax, sondern Syntax einer anderen Sprache, zum

01:09:07.370 --> 01:09:08.710
Beispiel Pascal.

01:09:09.710 --> 01:09:13.430
Da können Sie auch solche Zeichenketten iterieren.

01:09:13.430 --> 01:09:19.450
So etwas funktioniert problemlos, läuft von A bis Z, alle Buchstaben

01:09:19.450 --> 01:09:20.450
des Alphabets durch.

01:09:21.290 --> 01:09:26.090
Wenn Sie das aber auf dem EBCDIC-Code machen, dann haben Sie hier

01:09:26.090 --> 01:09:31.690
immer noch Zeichen, die im Code gar nicht belegt sind, aber bei dieser

01:09:31.690 --> 01:09:34.370
Laufvariable alle mitgezählt werden.

01:09:34.790 --> 01:09:37.090
Das heißt, Sie müssten aufpassen, wie Sie eigentlich solche Sachen

01:09:37.090 --> 01:09:40.110
machen, abhängig davon, welcher Zeichensatz zugrunde liegt.

01:09:40.110 --> 01:09:43.570
Und das Dumme war, dass auf allen IBM-Rechnern immer EBCDIC verwendet

01:09:43.570 --> 01:09:45.830
wurde und auf allen anderen Rechnern ASCII.

01:09:46.970 --> 01:09:49.550
Das heißt, je nachdem, auf welchem Rechner Sie arbeiten, haben Sie,

01:09:49.870 --> 01:09:53.250
wenn Sie falsch programmiert haben, unterschiedliche Ausführungen

01:09:53.250 --> 01:09:54.290
Ihrer Programme bekommen.

01:09:55.310 --> 01:09:56.130
Das ist natürlich schlecht.

01:09:57.450 --> 01:10:00.570
Deswegen muss man immer aufpassen, was ist der zugrunde liegende

01:10:00.570 --> 01:10:01.310
Zeichensatz.

01:10:01.470 --> 01:10:04.910
Wenn man Zeichensatzabhängig irgendwelche Berechnungen macht, muss man

01:10:04.910 --> 01:10:08.110
dafür sorgen, dass man sich entsprechend daran anpasst.

01:10:08.770 --> 01:10:13.090
Das also zu diesen Darstellungen von Zeichen.

01:10:13.190 --> 01:10:14.710
Sie sehen, das kann man sehr unterschiedlich machen.

01:10:15.130 --> 01:10:16.750
Das sind die beiden Standarddarstellungen.

01:10:17.110 --> 01:10:19.330
Und inzwischen haben wir sogar noch eine weitere Standarddarstellung,

01:10:19.430 --> 01:10:20.270
das ist der Unicode.

01:10:21.390 --> 01:10:22.350
Universal Code.

01:10:22.470 --> 01:10:26.130
Hier haben wir nicht nur 8-Bit, sondern 16-Bit pro Zeichen zur

01:10:26.130 --> 01:10:26.510
Verfügung.

01:10:27.290 --> 01:10:29.250
Also 65.000 verschiedene Zeichen.

01:10:29.630 --> 01:10:31.470
Wieso brauchen wir 65.000 Zeichen?

01:10:31.570 --> 01:10:35.570
Wir haben doch nur unsere 26 Zeichen im lateinischen Alphabet.

01:10:35.730 --> 01:10:36.370
Das reicht doch.

01:10:37.070 --> 01:10:39.290
Aber wenn Sie aus China kommen, reicht das nicht.

01:10:40.190 --> 01:10:40.970
Da brauchen Sie mehr.

01:10:41.770 --> 01:10:45.250
Das heißt, wir haben viele andere Zeichensätze, die auch dargestellt

01:10:45.250 --> 01:10:45.890
werden müssen.

01:10:46.570 --> 01:10:51.510
Und wenn wir eine Anwendung schreiben, wo wir Zeichen darstellen

01:10:51.510 --> 01:10:56.070
wollen, die in Korea gelesen werden können oder irgendwo in Burundi

01:10:56.070 --> 01:10:58.250
oder sonst irgendwo.

01:10:58.250 --> 01:11:05.250
Oder in USA oder Kanada oder irgendwo in der arabischen Welt oder in

01:11:05.250 --> 01:11:05.810
Israel.

01:11:06.690 --> 01:11:08.290
Die haben alle unterschiedliche Zeichen.

01:11:10.050 --> 01:11:12.790
Auch die sind eindeutig kodiert.

01:11:12.950 --> 01:11:15.570
Man hat sich geeinigt international, wie man die darstellen möchte.

01:11:16.850 --> 01:11:20.530
Hat dafür gesorgt, dass auch das lateinische Alphabet hier vorne im

01:11:20.530 --> 01:11:22.230
kleinen Bereich auch berücksichtigt ist.

01:11:22.690 --> 01:11:25.070
Dann haben wir viele Bereiche, die sind für die ganzen anderen

01:11:25.070 --> 01:11:26.090
Alphabete vorgesehen.

01:11:28.030 --> 01:11:33.170
Das sind also Möglichkeiten, wie man mit 16 Bit eine riesige Anzahl

01:11:33.170 --> 01:11:34.290
von Zeichen darstellen kann.

01:11:34.350 --> 01:11:35.990
Und jetzt habe ich eben einen großen Vorteil.

01:11:36.170 --> 01:11:42.870
Ich kann mit einem Datenformat, einem Zeichenformat mit 16 Bit, kann

01:11:42.870 --> 01:11:46.390
ich also beliebige Zeichen darstellen und ich kann jetzt darauf zum

01:11:46.390 --> 01:11:51.810
Beispiel internationale Anwendungen machen, indem ich gewisse Dinge in

01:11:51.810 --> 01:11:55.310
lateinischen Zeichen darstelle, andere in chinesischen Zeichen oder in

01:11:55.310 --> 01:11:56.690
arabischen Zeichen oder ähnliches.

01:11:57.050 --> 01:12:01.930
Und ich kann das machen im gleichen Code, der hier definiert ist.

01:12:02.690 --> 01:12:04.710
Ich muss nur wissen, wo die einzelnen Zeichen hingehören.

01:12:06.910 --> 01:12:10.310
Inzwischen ist man sogar weitergekommen.

01:12:10.490 --> 01:12:12.930
Das habe ich jetzt hier gar nicht dargestellt.

01:12:13.630 --> 01:12:16.210
Inzwischen gibt es doch, hier steht es, Unicode 5.0.

01:12:17.450 --> 01:12:19.070
Es gibt nun wieder neue Varianten.

01:12:20.170 --> 01:12:24.790
Da hat man inzwischen weitere 16 Bit-Bereiche, also 16 weitere 16 Bit

01:12:24.790 --> 01:12:25.310
-Bereiche.

01:12:25.310 --> 01:12:31.750
Kommt dafür auf insgesamt eine Million Zeichen.

01:12:33.370 --> 01:12:36.770
Also wir brauchen vier weitere Bits, um das entsprechend darzustellen.

01:12:37.510 --> 01:12:41.710
Und hat von dieser möglicherweise bis zu einer Million Zeichen

01:12:41.710 --> 01:12:44.210
mittlerweile 99.000 Zeichen verwendet.

01:12:45.350 --> 01:12:46.470
Also ziemlich viele schon.

01:12:47.290 --> 01:12:50.890
Das ist wichtig für Internationalisierung von Anwendungen, in denen

01:12:50.890 --> 01:12:54.870
man mit einem Code arbeiten möchte.

01:12:56.090 --> 01:13:01.670
Das ist also die Basis für internationalen Dokumentenaustausch.

01:13:03.330 --> 01:13:06.530
Jetzt kommen wir zum wiederum nächsten Teil.

01:13:06.630 --> 01:13:08.390
Wir wollen ja nicht immer beliebige Zeichen darstellen.

01:13:08.530 --> 01:13:10.890
Wir wollen im Endeffekt darauf hinaus, dass wir auch etwas rechnen

01:13:10.890 --> 01:13:11.210
wollen.

01:13:12.070 --> 01:13:15.850
Und dafür brauchen wir Ziffern, die wir darstellen müssen.

01:13:15.850 --> 01:13:18.950
Die können wir in ASCII und in EPSILIC darstellen.

01:13:19.770 --> 01:13:23.530
Bei beiden wird es im Prinzip mit Binary Coded Decimal gemacht.

01:13:24.110 --> 01:13:25.550
Mit noch weiteren Bits dazu.

01:13:26.710 --> 01:13:30.210
Also die einfachste Darstellung von Ziffern ist, diese Tetraden

01:13:30.210 --> 01:13:31.090
-Codierung zu nehmen.

01:13:31.250 --> 01:13:34.310
Vier Bits für eine Ziffer.

01:13:35.050 --> 01:13:36.690
Das geht aber sehr unterschiedlich zu machen.

01:13:37.350 --> 01:13:40.550
Wenn ich vier Bits habe, habe ich 16 verschiedene Code-Möglichkeiten

01:13:40.550 --> 01:13:41.270
oder Code-Wörter.

01:13:41.870 --> 01:13:43.350
Und die kann ich unterschiedlich zuordnen.

01:13:43.350 --> 01:13:44.570
Hier sind einige angegeben.

01:13:45.390 --> 01:13:47.310
Das eine ist dieser Binary Coded Decimal.

01:13:48.230 --> 01:13:51.270
Das andere ist im Prinzip nur eine zyklische Verschiebung.

01:13:52.630 --> 01:13:55.870
Also ich habe hier meine Code-Wörter.

01:13:56.370 --> 01:13:58.290
Das hier wäre also jetzt BCD.

01:13:59.850 --> 01:14:02.110
Dann kann ich das Ganze um drei verschieben.

01:14:02.910 --> 01:14:05.470
Und komme dann hier irgendwo hin.

01:14:05.470 --> 01:14:07.730
Nicht ganz so weit dahinten.

01:14:09.010 --> 01:14:11.970
Ich sage mal einfach BCD plus 3.

01:14:13.050 --> 01:14:15.850
BCD plus 3 ist XS3-Code.

01:14:16.010 --> 01:14:17.690
Also alles oberhalb der 3.

01:14:18.310 --> 01:14:20.330
Neun solche Zeichen werden verwendet.

01:14:20.890 --> 01:14:22.550
Genau um drei Zeichen verschoben.

01:14:24.090 --> 01:14:27.790
Wir werden das später brauchen, dass wir solche Verschiebungen machen

01:14:27.790 --> 01:14:28.090
können.

01:14:29.030 --> 01:14:31.510
Oder wir schauen uns an den sogenannten Icon-Code.

01:14:32.210 --> 01:14:33.230
Was ist hier der Fall?

01:14:33.870 --> 01:14:37.550
Da sehen Sie, sind die ersten verwendet.

01:14:37.590 --> 01:14:40.310
Die ersten 5 und die letzten 5.

01:14:42.270 --> 01:14:47.210
Die hier und die sind gerade jeweils die ersten 5 und die letzten 5.

01:14:48.250 --> 01:14:49.290
Mitfolgen dargestellt.

01:14:51.050 --> 01:14:53.410
Es gibt noch viele andere Möglichkeiten das zu machen.

01:14:53.530 --> 01:14:55.670
Das sind so einige Standard-Codierungen von Ziffern.

01:14:56.370 --> 01:14:58.070
Oder Sie haben ein 2 aus 5-Code.

01:14:58.590 --> 01:15:01.150
Ich hatte Ihnen vorhin ein 1 aus 10-Code dargestellt.

01:15:01.150 --> 01:15:02.530
Das ist ein 2 aus 5-Code.

01:15:02.630 --> 01:15:05.870
2 Bit von 5 Bit sind jeweils 1.

01:15:07.130 --> 01:15:08.670
Dann sehen Sie diese Darstellung.

01:15:10.910 --> 01:15:13.290
Wie beurteilt man eigentlich die Eigenschaften?

01:15:14.570 --> 01:15:17.110
Einfache Darstellung, einfache Codierung und Dekodierung.

01:15:17.250 --> 01:15:18.570
Einfache Arithmetik darauf.

01:15:19.250 --> 01:15:20.610
Das sind hier die Eigenschaften.

01:15:21.410 --> 01:15:23.250
Bei der BCD-Codierung ist es ganz einfach.

01:15:23.350 --> 01:15:25.810
Ich kann den Wert sofort ablesen über die Stellenwertigkeit.

01:15:28.090 --> 01:15:31.810
Also 2 hoch 0, 2 hoch 1, 2 hoch 2, 2 hoch 3 usw.

01:15:32.750 --> 01:15:34.110
Die XS3-Codierung.

01:15:34.670 --> 01:15:39.370
Da habe ich einfach die Dualdarstellung von der Zahl plus 3.

01:15:39.910 --> 01:15:42.970
Ich muss also nur 3 abziehen, um daraus die richtige Zahl zu kriegen.

01:15:45.250 --> 01:15:49.210
Ein Vorteil ist, dass die Nullen, nur Nullen oder nur Einsen nicht als

01:15:49.210 --> 01:15:50.170
Ziffern auftauchen.

01:15:51.870 --> 01:15:53.510
Das hat folgenden Vorteil.

01:15:53.510 --> 01:15:54.910
Das sind häufig Fehler.

01:15:55.010 --> 01:15:55.690
Warum sind das Fehler?

01:15:56.110 --> 01:15:58.630
Ich habe manchmal einen 0-Burst oder einen 1-Burst.

01:15:59.510 --> 01:16:04.050
Das heißt, in einem ganzen Bereich treten nur Einsen auf oder nur

01:16:04.050 --> 01:16:04.410
Nullen.

01:16:05.030 --> 01:16:08.150
Dann weiß ich, das sind keine Zahlen, da ist also ein Fehler passiert.

01:16:08.930 --> 01:16:12.970
Deswegen ist das eine günstige Art, diese Folgen von nur Nullen oder

01:16:12.970 --> 01:16:16.090
nur Einsen gar nicht als gültige Codeworte zu akzeptieren.

01:16:16.410 --> 01:16:18.570
Ich habe allerdings da drin keine Stellenwertigkeit.

01:16:18.750 --> 01:16:19.350
Das ist ein Problem.

01:16:19.790 --> 01:16:24.290
Bei der Icon-Codierung habe ich eine interessante Stellenwertigkeit 2,

01:16:24.430 --> 01:16:25.330
4, 2, 1.

01:16:26.290 --> 01:16:27.650
Auch so kann man etwas codieren.

01:16:27.750 --> 01:16:30.290
Sie sehen, es gibt viele verschiedene Möglichkeiten, Codes zu

01:16:30.290 --> 01:16:30.790
definieren.

01:16:31.270 --> 01:16:32.830
Ich will das aber gar nicht weiter vertiefen.

01:16:33.590 --> 01:16:35.750
Hier nochmal der 2 aus 5 Codierung.

01:16:35.930 --> 01:16:37.590
Auch hier einige nette Eigenschaften.

01:16:37.970 --> 01:16:40.770
In dem Fall sogar ein Fehler erkennbar, aber nichts korrigierbar.

01:16:41.370 --> 01:16:46.030
Auch hier eine Stellenwertigkeit 7, 4, 2, 1, 0 mit 5 Bits.

01:16:47.110 --> 01:16:49.470
Aber darauf zu rechnen ist umständlich.

01:16:49.910 --> 01:16:51.190
Es geht, aber es ist umständlich.

01:16:52.950 --> 01:16:54.670
Das war etwas zur Darstellung von Ziffern.

01:16:56.230 --> 01:16:58.590
Kommen wir zum nächsten Punkt, Darstellung von Zahlen.

01:16:59.470 --> 01:17:03.830
Wir kommen also auf diese XS3-Codierung später nochmal zurück oder XSK

01:17:03.830 --> 01:17:04.290
-Codierung.

01:17:05.390 --> 01:17:09.230
Jetzt wollen wir erstmal weiterlaufen und wollen Zahlen darstellen.

01:17:09.610 --> 01:17:11.130
Zahlen bestehen doch aus Ziffern.

01:17:12.230 --> 01:17:15.610
Aber die Frage ist ja, kann ich über die Darstellung von Ziffern

01:17:15.610 --> 01:17:17.970
geeignet darstellen oder muss ich anders darstellen?

01:17:19.550 --> 01:17:23.790
Und ich kann natürlich Zahlen etwas interessanter darstellen, wenn ich

01:17:23.790 --> 01:17:27.030
die Werte betrachte und nicht nur als eine Anreihung von Ziffern.

01:17:27.630 --> 01:17:30.550
Und auch hier ist die Forderung, das muss einfach realisierbar sein.

01:17:30.670 --> 01:17:34.190
Ich muss einfach konvertieren können ins Dezimalsystem, aus dem

01:17:34.190 --> 01:17:34.930
Dezimalsystem.

01:17:35.130 --> 01:17:38.530
Ich brauche eine einfache Arithmetik mit hoher Rechengeschwindigkeit,

01:17:38.650 --> 01:17:39.730
geringem Schaltungsaufwand.

01:17:40.430 --> 01:17:43.030
Möglichkeiten sind viele verschiedene da.

01:17:43.190 --> 01:17:46.650
Ich kann das Dualsystem nehmen, Dezimalsystem, binärdezimale

01:17:46.650 --> 01:17:46.910
Codierung.

01:17:47.530 --> 01:17:49.970
Also viele verschiedene Möglichkeiten, Zahlen zu codieren.

01:17:51.410 --> 01:17:52.970
Zetradenkodierung hatte ich Ihnen gerade dargestellt.

01:17:54.590 --> 01:18:00.510
Und das, was wir machen müssen, ist natürlich, die Codes entsprechend

01:18:00.510 --> 01:18:01.070
habe ich das hier.

01:18:01.830 --> 01:18:03.830
Ja klar, die Fortsetzung ist natürlich klar.

01:18:03.830 --> 01:18:07.830
Wenn ich die binärdezimale Codierung der Ziffern habe, kann ich

01:18:07.830 --> 01:18:11.170
natürlich einfach auf Dezimalzahlen fortsetzen.

01:18:11.310 --> 01:18:12.010
Das kennen wir alles.

01:18:13.190 --> 01:18:19.130
Also insofern wäre dann die Zahl 13 dargestellt durch diese beiden 4

01:18:19.130 --> 01:18:20.310
-Bit -Ziffern.

01:18:20.570 --> 01:18:21.390
Alles sehr einfach.

01:18:22.290 --> 01:18:26.550
Und wir gucken im Weiteren aber nur die Dualdarstellung an.

01:18:27.030 --> 01:18:29.230
Und die Frage ist, was wir überhaupt darstellen wollen.

01:18:30.190 --> 01:18:31.670
Welche Zahlen will ich darstellen?

01:18:33.150 --> 01:18:36.590
Normalerweise, wenn ich mir den Zahlenstrahl angucke, hier irgendwo

01:18:36.590 --> 01:18:41.090
die 0, dann möchte ich natürlich einen zusammenhängenden Bereich

01:18:41.090 --> 01:18:41.730
darstellen können.

01:18:41.810 --> 01:18:42.810
Irgendeinen Ausschnitt.

01:18:43.810 --> 01:18:45.530
Alle diese Zahlen will ich darstellen können.

01:18:45.650 --> 01:18:47.150
Alle diese Zahlen, was sind das für welche?

01:18:47.890 --> 01:18:51.250
Ganze Zahlen, da habe ich nicht alle diese Zahlen, da habe ich nur

01:18:51.250 --> 01:18:52.750
irgendwelche da drin.

01:18:54.690 --> 01:18:55.990
Das sind ganze Zahlen.

01:18:57.250 --> 01:19:00.830
Dann ist die Frage, wie viele brauche ich eigentlich hier, wenn das

01:19:00.830 --> 01:19:02.490
die 0 ist, und wie viele brauche ich da?

01:19:03.170 --> 01:19:05.310
Möglichst doch gleich viele negative wie positive.

01:19:06.430 --> 01:19:07.670
Noch ein wichtiger Punkt.

01:19:09.330 --> 01:19:12.430
Und es sollen natürlich alle ganzen Zahlen zwischen der minimalen und

01:19:12.430 --> 01:19:14.190
der maximalen vorkommen, sonst wird es schwierig.

01:19:15.970 --> 01:19:19.030
Das ist mit rationalen Zahlen, reellen Zahlen.

01:19:19.150 --> 01:19:21.510
Ich hatte schon gesagt, wir haben nur endlich viele Bits zur

01:19:21.510 --> 01:19:22.070
Verfügung.

01:19:22.070 --> 01:19:25.610
Wenn wir endlich viele Bits haben, ist es klar, wir können keine

01:19:25.610 --> 01:19:29.070
beliebig langen Ziffernfolgen darstellen.

01:19:29.210 --> 01:19:31.830
Das heißt, wir haben dann nie die Möglichkeit, reelle Zahlen

01:19:31.830 --> 01:19:32.530
darzustellen.

01:19:32.990 --> 01:19:34.090
Das können wir gleich vergessen.

01:19:34.530 --> 01:19:39.530
Reelle Zahlen kann man nicht darstellen, sofern sie irrational sind.

01:19:39.630 --> 01:19:41.570
Die rationalen Zahlen kann ich alle darstellen.

01:19:44.490 --> 01:19:46.710
Negative Zahlen, hatte ich schon gesagt, müssen wir uns überlegen, wie

01:19:46.710 --> 01:19:48.230
man das macht, wie man die unterscheidet.

01:19:49.310 --> 01:19:53.230
Rationale, reelle Zahlen, das Problem der Genauigkeit, auch mit

01:19:53.230 --> 01:19:53.970
Rundungsfehlern.

01:19:54.030 --> 01:19:55.830
Ich weiß, ich kann nicht beliebig viele darstellen.

01:19:56.530 --> 01:19:59.570
Ich weiß auch nicht, wie genau komme ich denn an eine Zahl ran mit

01:19:59.570 --> 01:20:00.350
endlich vielen Bits.

01:20:00.470 --> 01:20:01.310
Auch das ist also schwierig.

01:20:02.270 --> 01:20:03.490
Da muss ich mich drum kümmern.

01:20:04.050 --> 01:20:06.170
Und ich muss sehen, wie sieht das mit den Operationen aus.

01:20:06.790 --> 01:20:11.310
Wenn ich also zwei Zahlen x und y habe und die Summe der beiden Zahlen

01:20:11.310 --> 01:20:15.110
berechnen möchte, dann kann ich sowohl die beiden Zahlen direkt

01:20:15.110 --> 01:20:19.530
kodieren, also darstellen im Rechner, und darauf eine Operation

01:20:19.530 --> 01:20:20.290
ausführen.

01:20:21.190 --> 01:20:24.010
Und dann kommt dort irgendein Wert raus.

01:20:25.070 --> 01:20:30.750
Das wäre c von x, mit der Operation verknüpft mit c von y.

01:20:31.790 --> 01:20:35.030
Und der Wunsch ist natürlich, dass es egal ist, ob ich den Weg gehe

01:20:35.030 --> 01:20:36.150
oder ob ich den Weg gehe.

01:20:36.690 --> 01:20:39.910
Das heißt, dieses Diagramm muss kommutieren, so nennt man das.

01:20:39.910 --> 01:20:41.870
Kommutatives Diagramm.

01:20:41.970 --> 01:20:44.850
Egal welchen Weg ich gehe, ich muss immer das gleiche Ergebnis

01:20:44.850 --> 01:20:45.230
bekommen.

01:20:45.910 --> 01:20:49.510
Also ob ich erst kodiere oder die Operation ausführe, oder erst die

01:20:49.510 --> 01:20:53.230
Operation ausführe und dann kodiere, diesen Weg gehe, das Ergebnis

01:20:53.230 --> 01:20:54.190
muss gleich sein.

01:20:56.030 --> 01:21:01.110
Ein wichtiger Punkt übrigens im Zusammenhang mit Cloud Computing.

01:21:02.150 --> 01:21:03.450
Ein aktuelles Thema.

01:21:05.030 --> 01:21:08.670
Was hat Cloud Computing mit dieser Darstellung von Zahlen zu tun?

01:21:08.670 --> 01:21:12.730
Cloud Computing hat etwas damit zu tun, dass man Informationen

01:21:12.730 --> 01:21:18.230
kodieren möchte und dass manche dieser Informationen, die man in die

01:21:18.230 --> 01:21:22.730
Cloud schickt, dass die bitte vertraulich bleiben sollen.

01:21:23.670 --> 01:21:25.230
Das heißt, die werden verschlüsselt.

01:21:26.850 --> 01:21:30.570
Und damit die an keiner Stelle außerhalb meines eigenen Rechners

01:21:30.570 --> 01:21:35.010
unverschlüsselt auftauchen, müsste ich natürlich Operationen auf den

01:21:35.010 --> 01:21:37.050
verschlüsselten Zahlen ausführen.

01:21:37.050 --> 01:21:40.230
Der verschlüsselten Werten der Daten.

01:21:41.330 --> 01:21:48.150
Und das, was hier steht, wäre eine Bedingung an eine sogenannte Homo

01:21:48.150 --> 01:21:53.510
-Morphe -Kryptographie.

01:21:57.070 --> 01:22:02.490
Homo-Morphe-Kryptographie ist also eine Verschlüsselung von Daten, so

01:22:02.490 --> 01:22:05.830
dass sich Operationen, die ich eigentlich auf den unverschlüsselten

01:22:05.830 --> 01:22:10.610
Daten ausführen kann, auf den verschlüsselten Daten ausführe und das

01:22:10.610 --> 01:22:11.750
gleiche Ergebnis bekomme.

01:22:12.590 --> 01:22:15.290
Das heißt, wenn ich eine Homo-Morphe-Kryptographie habe, kann ich

01:22:15.290 --> 01:22:19.330
Daten verschlüsseln und kann darauf arbeiten.

01:22:20.270 --> 01:22:23.330
Und es wird an keiner Stelle außerhalb meines Bereichs, wo ich die

01:22:23.330 --> 01:22:26.810
Sachen unverschlüsselt kenne, jemals jemand Kenntnis von den Inhalten

01:22:26.810 --> 01:22:27.190
bekommen.

01:22:27.810 --> 01:22:31.810
Das ist ein ganz heißes Thema in der Kryptographie im Augenblick und

01:22:31.810 --> 01:22:35.210
im Zusammenhang mit der Sicherheit von Anwendungen im Cloud Computing.

01:22:35.210 --> 01:22:38.630
Daran wird gerade sehr intensiv gearbeitet, wie man Homo-Morphe

01:22:38.630 --> 01:22:42.670
-Kryptographische Verfahren entwickeln kann, auf dem man zumindest

01:22:42.670 --> 01:22:45.410
gewisse Operationen effizient ausführen kann.

01:22:45.970 --> 01:22:49.410
Interessantes Thema, ein aktuelles Forschungsthema.

01:22:50.070 --> 01:22:52.490
Das, was ich Ihnen eigentlich darstellen möchte, ist ein ganz altes

01:22:52.490 --> 01:22:57.790
Thema, nämlich für einfache arithmetische Operationen, die einfachen

01:22:57.790 --> 01:23:01.270
Zahlendarstellungen so zu machen, dass Sie das alles effizient machen

01:23:01.270 --> 01:23:01.590
können.

01:23:02.170 --> 01:23:03.590
Und hier steht noch was drunter.

01:23:04.350 --> 01:23:06.570
Wie muss... das kommt wieder weg jetzt hier.

01:23:07.810 --> 01:23:08.690
Wie muss...

01:23:08.690 --> 01:23:09.030
Ups.

01:23:11.070 --> 01:23:12.470
Dieses... es will nicht weg.

01:23:13.010 --> 01:23:13.590
Lassen wir es.

01:23:13.750 --> 01:23:15.270
Jetzt wird er gleich... jetzt ist er am Arbeiten.

01:23:15.430 --> 01:23:17.310
Ich hoffe, ich habe jetzt keinen Unsinn gemacht.

01:23:17.410 --> 01:23:18.810
Er hat das Ganze hin und her erwischen.

01:23:19.350 --> 01:23:21.190
Jetzt hier versucht er auszuführen.

01:23:21.730 --> 01:23:22.790
Dauert anscheinend einen Augenblick.

01:23:22.950 --> 01:23:23.430
Er ist sehr busy.

01:23:24.890 --> 01:23:28.510
Also, wie muss die Operation aussehen, damit das Diagramm kommutativ

01:23:28.510 --> 01:23:28.850
ist?

01:23:28.850 --> 01:23:31.790
Oder wie muss die Kodierung aussehen, damit ich ein kommutatives

01:23:31.790 --> 01:23:32.770
Diagramm machen kann?

01:23:33.870 --> 01:23:37.390
Und jetzt möchte ich gerne auf die nächste Folie gehen, aber er sagt,

01:23:37.510 --> 01:23:38.170
er ist busy.

01:23:39.310 --> 01:23:43.170
Er ist beschäftigt und weiß nicht, wie er weitermachen soll.

01:23:43.990 --> 01:23:44.470
Ärgerlich.

01:23:45.470 --> 01:23:49.150
Auf der nächsten Folie kommt jetzt etwas zu diesen

01:23:49.150 --> 01:23:50.230
Zahlendarstellungen.

01:23:51.250 --> 01:23:54.010
Und ich möchte Ihnen gerne etwas darstellen zu den ganzen Zahlen.

01:23:55.230 --> 01:23:57.350
Also, wie kann ich die negativen Zahlen darstellen?

01:23:57.950 --> 01:24:01.310
Und zu den anderen Zahlen.

01:24:01.430 --> 01:24:04.190
Es macht anscheinend keinen Sinn mehr, das heute fortzuführen, weil

01:24:04.190 --> 01:24:06.010
mein Rechner sagt, er hat keine Lust mehr.

01:24:06.610 --> 01:24:08.390
Er dreht jetzt Däumchen im Hintergrund.

01:24:08.710 --> 01:24:11.290
Beziehungsweise hat entweder ein Deadlock oder ein Livelock.

01:24:11.590 --> 01:24:12.750
Also kann nichts mehr tun.

01:24:12.890 --> 01:24:14.810
Oder hier sieht man, er macht anscheinend irgendetwas.

01:24:15.450 --> 01:24:17.410
Und ich muss jetzt hier warten, bis er damit fertig ist.

01:24:17.890 --> 01:24:19.730
Ansonsten ist unsere schöne Aufzeichnung weg.

01:24:20.410 --> 01:24:21.430
Das wäre natürlich sehr ärgerlich.

01:24:22.270 --> 01:24:25.710
Ich warte jetzt besser einen Augenblick, bis er sich wieder beruhigt

01:24:25.710 --> 01:24:25.950
hat.

01:24:25.950 --> 01:24:30.610
Und ich entlasse Sie nicht in die Weihnachtsferien, sondern bis

01:24:30.610 --> 01:24:31.270
Mittwoch früh.

01:24:31.370 --> 01:24:32.590
Da haben wir noch eine Doppelstunde.

01:24:33.150 --> 01:24:36.030
Und werden dann diesen Teil über Darstellung von Zahlen hoffentlich

01:24:36.030 --> 01:24:37.330
durchgehen können.

01:24:37.850 --> 01:24:39.050
Vielen Dank für die Aufmerksamkeit.