Willkommen zur vorletzten Vorlesung.
Wir fangen heute ein neues Thema an, nämlich Informationstheorie.
Das wird keine Bezüge zu dem haben, was wir davor gemacht haben mit
Berechenbarkeit und Automaten, sondern ziemlich losgelöst sein.
Informationstheorie ist quasi das Beschäftigen mit der Verarbeitung
von Informationen über Kanäle oder Darstellung von Informationen im
Computer.
Da gibt es ganz grob die drei Gebiete Quell-Codierung, Kanal-Codierung
und Kryptographie.
Quell-Codierung ist also, wenn wir Daten haben und wir wollen die
jetzt speichern, möglichst clever, meistens platzsparend, dann reden
wir davon Quell-Codierung.
Kanal-Codierung geht darum, dass wir Daten transferieren wollen über
einen Kanal und dieser Kanal eventuell fehleranfällig ist.
Und Kryptographie ist, wenn auch beim übermitteln von Daten oder auch
beim Abspeichern von Daten, dass die verschlüsselt werden.
Okay, ein bisschen genauer.
Bei der Quell-Codierung wollen wir die Redundanz oder Irrelevanz in
der Information, die dort in der Quelle vorliegt, reduzieren.
Also wenn wir wissen, wir haben Informationen und dabei sind irgendwie
1000 Nullen und 500 Einsen, dann statt uns 0 0 0 0 0 0 0 0 zu
speichern, dann speichern wir uns sowas wie 1000 Nullen.
Also wir wollen die Redundanz verringern, ohne Informationen zu
verlieren.
Das soll vor allen Dingen helfen, platzsparend zu agieren, also die
Daten zu komprimieren.
Das wird verwendet in allen Standard-Dateiformaten zum Beispiel, die
Sie so kennen.
MP3 für Musik oder was weiß ich.
So, genau.
Ich sage gleich, wir werden hier nur verlustfreie Kompressionen
betrachten.
Es gibt auch verlusthafte Kompressionen, gerade Stichwort MP3 oder
JPEG, wenn eigentlich in dem Bild oder in der Musik sehr viel mehr
Informationen drin ist, die durchaus verloren gehen darf, weil das
menschliche Auge oder Ohr nicht genügend aufnehmen kann.
Hier geht es eher darum, dass wir verlustfreie Kompressionen haben
wollen.
Wir wollen exakt die Informationen aus der Quelle wiedergeben.
Das hat eine hohe wirtschaftliche Bedeutung, das können Sie sich
denken.
Kanalkodierung, wie schon gesagt, es geht um die Übertragung von
digitalen Daten, sei es zwischen verschiedenen Computern oder
Netzwerken oder innerhalb eines Computers.
Und diese Kanäle, die könnten eventuell gestört sein.
Also es könnten Fehler übertragen werden.
Es kann auch die Übertragung sein zwischen dem Signal, das Sie in der
Tastatur eingeben, bis es dann im Prozessor ankommt oder so.
Und wir wollen diese Störungen zum einen erkennen und nach Möglichkeit
sogar korrigieren.
Also wir wollen wenigstens das Mindeste ist, zu merken, dass das
Signal gestört ist.
Und da ist es dann so ein bisschen andersherum.
Wir können das machen, indem wir die Daten redundant machen.
Das ist sozusagen das Gegenteil von der Kompression davor.
Wir fügen zusätzlich Redundanz in die Daten ein, um die Fehler zu
erkennen.
Zum Beispiel können wir sagen, wenn auf der Tastatur ein Buchstabe
gedrückt wird, dann wird dieses Signal nicht nur, also meinetwegen
binär kodiert oder sowas, dann wird es nicht nur einmal an den
Prozessor gesendet, sondern fünfmal.
Und dann sehen wir, wenn jetzt irgendwie von den fünfmalen irgendwie
beim dritten und beim vierten irgendwie das anders aussieht, als bei
dem ersten und zweiten und fünften, dann ist da ein Fehler drin.
Und dann haben wir den Fehler schon mal erkannt.
Wenn aber drei von den fünf irgendwie übereinstimmen, dann würden wir
auch wissen, da ist bestimmt diese Taste mit gemeint gewesen sein.
Dann haben wir den Fehler sogar korrigiert.
Darum geht es bei der Kanalkodierung.
Und das letzte Thema ist Kryptographie.
Da geht es um Sicherheit, dass die Daten verschlüsselt werden und dass
es widerstandsfähig gegen unbefugtes Lesen oder sogar Ändern sein
soll.
Da gibt es die Kryptoanalyse und die Kryptologie und das werden wir
hier alles aber nicht behandeln.
Also Kryptographie wird hier kein Thema sein.
Es geht nur um Quellkodierung und Kanalkodierung.
Wer mag, also wir haben jetzt zwei Vorlesungen Zeit, darüber zu
sprechen.
Wir werden also alles im Prinzip nur ein bisschen anreißen können und
Sie merken schon, dass ich die Kryptographie komplett rauslassen muss.
Wer mag und sich mehr Material dazu angucken möchte, den empfehlen wir
das TGI-Skript von Professor Müller-Quade.
Das ist auf der Homepage auch verlinkt.
Ich glaube, also hier steht noch, dass es zehn Jahre mittlerweile alt
sein soll.
Ich glaube so 13, 14 hat Müller-Quade auch die TGI gehalten und
vielleicht hat er da das Skript auch aktualisiert.
Aber das ist wirklich gut und quasi ist diese zwei Vorlesungen, die
wir jetzt hier haben werden, sind ein Excerpt aus dem Skript, aus dem
entsprechenden Kapitel von Professor Müller-Quade.
Außerdem könnte man noch ein Buch empfehlen, das Information und
Codierung heißt, von Martin Werner, wenn Sie weiter daran interessiert
sind.
Gut, fangen wir an.
Also wir formalisieren erstmal, was ist Information.
Wie immer gehen wir hier von einer Zeichenmenge aus, einer endlichen
Zeichenmenge, die wir mit Sigma bezeichnen, unser Alphabet und
meistens, um irgendwie so Doppelindizes zu vermeiden, sind unsere
Zeichen jetzt einfach 1 bis N.
Manchmal nicht, aber okay, meistens.
Und jetzt, wir könnten vielleicht als Information mal nehmen, die
deutsche Sprache.
Die hat irgendwie 26 Zeichen.
Gehen wir mal davon aus, ohne die ganzen Sonderzeichen und Umlaute,
also dann hätten wir 26 Zeichen, aber nicht jedes von diesen Zeichen
taucht gleich häufig auf in der deutschen Sprache.
Also das X taucht sehr viel seltener auf als das E zum Beispiel.
Und das formalisieren wir, indem wir sagen, okay, jedes Zeichen hat
eine Wahrscheinlichkeit.
Also das Zeichen I hat die Wahrscheinlichkeit Pi, mit der es an dieser
Informationsquelle auftaucht.
Das war jetzt das Beispiel mit der deutschen Sprache oder Sie können
sich vorstellen, dass die Zeichen vielleicht Farben sind für
Bildpunkte in einem Bild und dann gibt es auch Farben, die häufiger
auftauchen als andere Farben.
Auf einem Faxgerät wird Schwarz sehr viel weniger auftauchen als Weiß,
wenn es Schwarz-Weiß-Fax ist.
Gut, also das sind so die Wahrscheinlichkeiten, die mit den Zeichen
assoziiert sind.
Und die Informationsquelle generiert jetzt diese Informationen nach
diesen Wahrscheinlichkeiten.
Also da kommt etwas, das ist einfach ein zufälliger String von
Zeichen, der dort generiert wird.
Und dann können wir auch sagen, dass das X, was das Zeichen I mit
Wahrscheinlichkeit P von I liefert, eine Zufallsvariable ist, eine
diskrete Zufallsvariable.
Also mit einer Wahrscheinlichkeit von P von 3 wird das Zeichen 3
generiert an der Informationsquelle X.
Andere Beispiele, die Informationsquelle könnte einfach ein Würfel
sein, weil das irgendwie nah an Wahrscheinlichkeiten dran liegt und
dann hätte der Würfel also sechs Zeichen, das sind 1 bis 6 Augen und
die Wahrscheinlichkeit für jedes Zeichen wäre gleich ein Sechstel,
wenn es ein fairer Würfel ist und dann wäre das also durch diesen
Wahrscheinlichkeitsvektor hier dargestellt, die Information.
Dann können wir mal darüber reden, wie viel Information oder
Erkenntnis wir kriegen durch die Informationsquelle.
Also wir können mal gucken, wie einfach es ist vorherzusagen, was das
nächste Zeichen sein wird.
Wenn die Informationsquelle jetzt ein Würfel ist, dann ist das
Ergebnis ziemlich schwer vorherzusagen, weil wir einfach alles, jeder
der sechs Ausgänge ist gleich wahrscheinlich.
Also der Erkenntnisgewinn von dem nächsten Zeichen ist sehr hoch.
Wir haben einen hohen Erkenntnisgewinn.
Ein anderes Beispiel wäre ein gezinkter Würfel, der irgendwie mit
Wahrscheinlichkeit 1,5 immer auf der 6 landet und die anderen fünf
Flächen nur mit Wahrscheinlichkeit von 10 Prozent ergibt.
Der ist irgendwie ein bisschen unförmig oder gezinkt worden durch
Gewichte oder wie auch immer.
Dann könnten wir wagen, vorherzusagen, was das nächste Zeichen sein
wird.
Nämlich es wird mit ziemlich hoher Wahrscheinlichkeit eine 6 sein und
dann in der Hälfte der Fälle hätten wir damit recht erwartet.
Das heißt, wenn wir dann ein Zeichen kriegen, dann ist der
Erkenntnisgewinn kleiner.
Wenn es dann wirklich eine 6 wird, dann sagen wir, okay, war ja klar.
Und das ist jetzt ein Maß für den Erkenntnisgewinn, der in dieser
Information drin steckt.
Also für uns ist Information eine Menge von Zeichen und jedes Zeichen
mit einer Wahrscheinlichkeit.
Sie können das als Zufallsexperiment sehen, wie mit dem Würfel.
Sie haben aber auch im Kopf zum Beispiel die deutsche Sprache.
Da gibt es Zeichen, Buchstaben und die kommen mit gewissen
Häufigkeiten und dann ist die Frage, wie groß ist der
Erkenntnisgewinn, wenn wir jetzt so einen zufälligen Buchstaben aus
der deutschen Sprache kriegen.
Also quasi die Informationsquelle schüttet einfach so deutsche Wörter
Zeichen für Zeichen aus und wenn wir dann ein E sehen, dann war der
Erkenntnisgewinn nicht so groß.
Aber wenn wir ein X sehen, dann sind wir da ein bisschen überrascht.
Gut, also das ist der Erkenntnisgewinn und der wird als Information
bezeichnet.
Wir wollen diese Information, wir wollen das irgendwie formalisieren.
Wir wollen uns überlegen, wann viel Information da ist und wann wenig
Information da ist.
Also was wir wollen, sind erstmal ein paar Wünsche und danach werden
wir die formale Definition tatsächlich sehen.
Ich will Ihnen nicht einfach die Formel zeigen und dann erklären,
sondern irgendwie das von hinten aufzäumen.
Also zum einen die Information I und ein PI, das ist also jetzt für
eine gewisse Wahrscheinlichkeit, das ist die Wahrscheinlichkeit von
einem Zeichen und wenn man dann dieses Zeichen sehen, dann haben wir
einen Erkenntnisgewinn und der soll nicht negativ sein.
Also wir wollen immer ein bisschen was dadurch erkennen.
Außerdem ein sicheres Ereignis, also wo die Wahrscheinlichkeit 100%
ist, eins, was auf jeden Fall auftritt, soll keine Information
liefern.
Also je höher die Wahrscheinlichkeit ist, desto geringer ist der
Erkenntnisgewinn.
Achso, hier sollte ich vielleicht sagen, also in der ganzen Vorlesung,
auch wenn ich es nicht explizit hingeschrieben habe, alle
Wahrscheinlichkeiten, also Wahrscheinlichkeit 0 ist nicht erlaubt.
Wahrscheinlichkeit 1 erlauben wir, sichere Ereignisse, aber
Wahrscheinlichkeit 0 ist nicht erlaubt, sonst teilen wir hier ein paar
mal durch 0 und so.
Also dann ist es einfach, wenn ein Zeichen Wahrscheinlichkeit 0 ist,
dann schmeißen wir es raus aus unserem Alphabet, dann taucht es ja
daran nicht auf.
Gut, und außerdem, wenn sich jetzt die, wenn Wahrscheinlichkeiten nah
beieinander liegen, dann sollen die entsprechenden Informationen auch
nah beieinander liegen.
Oder kleine Änderungen in der Wahrscheinlichkeit sollen kleine
Änderungen in der Information hervorrufen oder mathematisch
ausgedrückt, die Information als Abbildung soll stetig sein.
So, außerdem wollen wir, wenn wir jetzt diese Informationen kriegen,
durch das Auswerten dieses Experimentes, dann soll die Information von
einem doppelt so langen Experiment auch doppelt so hoch sein.
Und deshalb wollen wir, wenn ein Experiment doppelt so lang ist, dann
ist die Wahrscheinlichkeit für diesen Ausgang, dieses längeren
Experiments, wenn die unabhängig sind, wovon wir ausgehen, immer das
Produkt der Wahrscheinlichkeiten der einzelnen Experimente.
Die Information, dass der Würfel eine 1 und danach eine 2 gewürfelt
hat, da ist die Wahrscheinlichkeit 1 sechste für die 1 mal 1 sechste
für die 2 danach.
Also für eine doppelt so lange Zeichenkette, da multiplizieren sich
die Wahrscheinlichkeiten und die Information soll sich aber addieren.
Wir wollen aus einer doppelt so langen Beobachtungsfenster doppelt so
viel Information rausholen.
Okay, das heißt, das hier ist jetzt wirklich die erste nicht-triviale
Eigenschaft, die die Information erfüllen soll.
Also die soll nicht negativ sein, die soll bei einem sicheren Ereignis
null Erkenntnisgewinn haben und dann soll diese Gleichung gelten.
Gut, und jetzt ist gar nicht mehr so viel möglich, das zu machen.
Die ist quasi dadurch festgelegt, bis auf Faktoren, und zwar als die
folgende Funktion.
Wir müssen die so wählen.
Die Information zur Wahrscheinlichkeit p ist der Logarithmus,
irgendeiner Basis b, wir werden immer den binären Logarithmus machen,
von 1 durch p.
Also es ist das gleiche, wenn man Logarithmen-Gesetze kennt, wie Minus
der Logarithmus zur Basis b von p.
Diese Funktion erfüllt diese Eigenschaften, die wir uns gewünscht
haben, und egal welche Basis wir einsetzen, weil ein Basiswechsel
einfach ein Faktor Änderung da drin ist.
Okay, aber wir machen hier wirklich nur Basis 2.
Vielleicht noch mal ganz kurz die Wiederholung, falls sie den
Logarithmus lange nicht mehr gesehen haben.
Was ist so die kennzeichnenden Eigenschaften?
Das hier ist die die wichtige Eigenschaft für uns.
Also egal welche Basis wir haben, multiplizieren wir die Argumente,
addieren sich die Werte.
Okay, das ist genau das, was wir wollten.
Wenn das Argument, das war die Wahrscheinlichkeit, multipliziert wird,
dann werden die entsprechenden Werte addiert.
Und der Logarithmus von 1 durch x, also wir hatten gerade 1 durch p,
für eine positive Zahl ist Minus der Logarithmus von p.
Also in diesem Graphen hier, wir sind, wir handeln, bei uns geht es um
Wahrscheinlichkeiten, die sind ja also zwischen 0 und 1.
1 ist erlaubt, 0 ist nicht erlaubt.
Das heißt, wir gucken uns nicht, wenn wir uns den Logarithmus von
einer Zahl angucken, die zwischen 0 und 1 liegt, dann liegt es, der
Logarithmus davon, bei 1 ist er 0 und bei 0 geht es hier gegen Minus
unendlich.
Ja, da ist er nicht definiert, der Logarithmus von 0.
Und je kleiner die Wahrscheinlichkeit ist, desto tiefer geht es hier.
Mit dem Minus, also desto höher ist der Erkenntnisgewinn.
Basiswechsel, habe ich schon gesagt, das ist quasi, wenn ich jetzt von
der Basis A auf die Basis B wechseln möchte, dann ist es einfach
dieser Faktor hier, das ist eine konstante Zahl, die hängt nicht mehr
von x ab.
Einfach nur, wenn ich dieses Bild strecke oder stauche, dann bleiben
die oberen Eigenschaften erhalten.
Gut.
So, also das ist die Definition für Information für uns.
Wir haben eine Quelle, die Wahrscheinlichkeiten und Zeichen hat, also
Zeichen mit zugeordneten Wahrscheinlichkeiten und dann eine
Wahrscheinlichkeit hat eine gewisse Informationswert für uns.
Also wir hatten schon ein Beispiel des Würfels, jetzt machen wir mal
das Beispiel einer Münze, die hat also nur zwei Zeichen, Kopf und Zahl
oder hier heißen die 0 und 1 und die Wahrscheinlichkeit, wenn das eine
faire Münze ist, dann sind die jeweils 1,5.
Das heißt, was ist die Information eines Münzwurfs?
Das ist die Information von der Wahrscheinlichkeit 1,5, also setzen
wir das da ein, Logarithmus zur Basis 2 jetzt, von 1 durch 1,5, also
Logarithmus von 2 und das ist genau 1, weil es die Basis 2 ist.
Das heißt, ein Münzwurf, das ist ja für uns das Wichtige, wir sind ja
hier immer binär unterwegs, wenn wir eine binäre Zufallsvariable haben
zwischen 0 und 1, die gleich wahrscheinlich eine 0 oder eine 1 liegt,
dann ist der Informationsgewinn genau 1.
Das ist so unsere Normierung.
Wenn wir die Münze jetzt K mal werfen und die ist immer noch eine
faire Münze, dann ist also für einen bestimmten Ausgang, also der
bestimmte Ausgang heißt zum Beispiel Kopf, Kopf, Zahl, Zahl, Kopf,
Kopf, für K-Würfel ist es halt die Multiplikation der entsprechenden
Wahrscheinlichkeiten, das hat dann 1,5 1,5, 1,5, 1,5 und so weiter,
also 1 durch 2 hoch K.
Und das setzen wir jetzt ein in die Information und wir kriegen also,
jetzt setze ich mal einfach hier drüben ein, P ist 1 durch 2 hoch K,
also Minus der Logarithmus von 1 durch 2 hoch K, oder es ist das
Gleiche wie, wenn ich das hier 1 durchnehme und das Minus wegnehme,
also der Logarithmus von 2 hoch K zur Basis 2, das ist also genau K.
Also ein Münzwurf gibt uns Information 1 und K-Münzwürfe Information
K.
So, jetzt, warum machen wir das?
Also wir haben jetzt, denken Sie wieder vielleicht an die deutsche
Sprache, wo wir die 26 Buchstaben haben und jeder Buchstabe hat eine
gewisse Wahrscheinlichkeit und jetzt ist die Frage, wie viel
Information steckt in der deutschen Sprache, okay?
Oder, also wenn wir jetzt, wenn die deutsche Sprache zum Beispiel sehr
redundant wäre, dann würde sie weniger Informationen enthalten.
Stellen Sie sich vor, irgendwie die deutsche Sprache wird reformiert
und wir schreiben jetzt alles genauso wie vorher, bloß dass wir jeden
Buchstaben verdoppeln.
Dann sind die Wörter sehr viel länger, da ist sehr viel Redundanz drin
und wir haben sehr viel weniger Informationen, okay?
Gut, und das soll jetzt sozusagen über die ganze Sprache, nicht nur
für ein einzelnes Zeichen, soll gemessen werden über die sogenannte
Entropie, okay?
Also die Entropie ist quasi der mittlere Informationsgehalt pro
Zeichen.
Anders ausgedrückt, warum ist das für uns eigentlich auch interessant?
Das ist, wenn jedes Zeichen sozusagen maximale Informationen hat, dann
ist so anschaulich gesehen, ist jedes Zeichen wichtig.
Aus jedem Zeichen konnten wir nicht vorhersehen, dass das jetzt kommt
und was als nächstes kommt, ist immer wichtig für die Quelle.
Das heißt, wenn wir jetzt wollen, wir wollen, wir sind bei Quellen
-Codierung, wir wollen das jetzt irgendwie anders codieren und
komprimieren, wir wollen die gleiche Information mit weniger Zeichen
oder mit weniger Länge eines Strings hinkriegen, dann, wenn da so viel
Information drin steckt, dann werden wir das nicht schaffen.
Also die Entropie ist so ein Maß, eine untere Schranke, an die, wie
gut wir das komprimieren können, das Signal an der Quelle, okay?
Dann gibt es noch, ich will die einfach, die werde ich jetzt einmal
nur erwähnen, die Kolmogorov-Komplexität, die vielleicht so noch den
besten Zusammenhang zu Automaten hat.
Von einem String, beliebiger String, ist die Kolmogorov-Komplexität
die Länge eines kürzesten Programms, das den String ausgibt.
Okay?
Und einfach, damit Sie es mal gesehen haben und Entropie zum Beispiel
muss, also die ist eine untere Schranke an diese Komplexität, also
diese, ich könnte ja, statt den String zu speichern, könnte ich mir
das Programm speichern, was den String ausgibt.
Denken Sie wieder an den String der 1000 Nullen und dann 501 Naht.
Das Programm, was den String ausgibt, ist sehr viel kürzer.
Und Kolmogorov-Komplexität ist die Länge eines kürzesten Programms.
Da werde ich mir das Programm, das den String ausgibt, speichern,
statt den String selber und das kann natürlich nicht kürzer sein als
die Entropie.
So, jetzt kommen wir endlich zur Entropie.
Wie gesagt, wir bleiben bei Basis 2.
Wir haben eine Zufallsvariable x und die Ergebnisse, die sind in, das
sind unsere Zeichen, die sind in Sigma, in dem endlichen Alphabet und
wir haben positive Wahrscheinlichkeit für jedes Zeichen.
Dann ist die Entropie h von x und das ist die Summe über alle Zeichen,
die Wahrscheinlichkeit des Zeichens mal die Information des Zeichens.
Also mal die Wahrscheinlichkeit des Zeichens mal die Information von
dieser Wahrscheinlichkeit des Zeichens.
Die Information ist an Wahrscheinlichkeiten gekoppelt.
Okay, also p von a mal Logarithmus zur Basis 2 von 1 durch p von a.
Also etwas, was häufig auftaucht, hat eine hohe Wahrscheinlichkeit,
allerdings eine niedrige Information.
Aber die Information, das geht halt nur logarithmisch.
Eine kleine Beobachtung, diese Entropie ist immer positiv, weil wir
jetzt diesen Fall nicht haben, dass Zeichen Null Wahrscheinlichkeit
haben, dann wüssten wir auch gar nicht, was das hier sein soll.
Also der erste Term ist positiv und der zweite Term ist auch positiv
oder nicht negativ zumindest.
Also die Entropie, stochastisch gesehen, ist für eine diskrete,
endliche Zufallsvariable, ist einfach ein Wert für diese
Zufallsvariable.
Und hohe Entropie soll heißen, schlechte Komprimierbarkeit.
Und was ist denn die höchste Entropie, die wir erreichen können?
Na ja, wenn die Anzahl der Zeichen N ist, dann wird das hier maximal,
wenn alle Zeichen gleichwahrscheinlich sind.
Das ist auch irgendwie intuitiv klar, weil dann irgendwie der
Erkenntnisgewinn bei jedem Zeichen maximal wird.
Wir können nicht vorhersehen, was als nächstes kommt.
Also in diesem Fall, wenn alle Zeichen gleichwahrscheinlich sind, dann
haben die also die Wahrscheinlichkeit 1 durch N, dann können wir uns
das ja auch einmal ausrechnen, diese Summe hier.
Also wir haben N-Terme, die sind alle jetzt gleich, weil P von A
gleich ist.
Und was ist ein Term?
Ein Term ist 1 durch N für die Wahrscheinlichkeit mal den Logarithmus
zur Basis 2 von 1 durch 1 durch N, also von N.
Das heißt, die Ns vorne kürzen sich weg und wir haben da einfach den
Logarithmus zur Basis 2 von N.
Also in Abhängigkeit von der Anzahl der Zeichen ist der Logarithmus
zur Basis 2 eine obere Schranke an die Entropie.
Okay, gut.
Machen wir das mal mit der deutschen Sprache.
Die deutsche Sprache hat 26 Buchstaben.
Das heißt, was ist Log 2 von 26?
Ich muss jetzt also zählen, wie oft muss ich 26 durch 2 teilen, bis
ich bei 1 bin?
Also ich kann das, wenn ich, was ist denn die nächste, ach machen wir
es so, wenn ich einmal durch 2 teile, dann bin ich bei 13, dann sagen
wir mal, ist das 12.
Wenn ich nochmal durch 2 teile, bin ich bei 6.
Nochmal durch 2 teilen, bin ich bei 3.
Nochmal durch 2 teilen, sagen wir mal, ich bin nicht bei 3, sondern
bei 4.
Nochmal durch 2, nochmal durch 2, 5, ungefähr, quasi.
Da steht es ein bisschen genauer.
Log 2 von 26 ist ungefähr 4,7.
Okay.
Und 4,7 ist sozusagen das höchste, was wir erwarten können.
Das ist, wenn quasi maximaler Informationsgehalt in jedem Zeichen der
deutschen Sprache drinstecken würde.
Und wenn man das mal sich ausrechnet, einfach den Duden nimmt und die
Häufigkeiten zählt und dann entsprechend das auswertet hier, dann
landet man bei 4,1, was schon gar nicht so schlecht ist.
Okay, also die deutsche Sprache ist nicht besonders redundant in
dieser Hinsicht.
Jetzt wäre es natürlich super, noch andere Sprachen hier zu haben,
aber ich würde mal schätzen, dass Französisch zum Beispiel redundanter
ist.
Allein schon, weil irgendwie jedes Wort auf dem Konsonanten endet oder
so.
Egal.
Gut, hier ist nochmal der Graph von dieser Funktion aufgezeichnet.
Wenn wir eine Münze haben mit Wahrscheinlichkeit p, also das ist, wir
haben nur zwei Zeichen, Nullen und Einsen.
Die Nullen kommen mit Wahrscheinlichkeit p, was auch immer, und die
Einsen mit Wahrscheinlichkeit halt 1-p.
Dann ist die Entropie, diese Formel, die hat jetzt nur zwei Terme,
nämlich einmal p mal log 1 durch p und der andere Term ist 1-p für die
zweite Wahrscheinlichkeit mal log 1 durch 1-p.
Und wenn ich das jetzt auftrage, dann kriege ich diesen
Funktionsgrafen und dann sehen sie also, wenn die Münze fair ist, wenn
p, also die Wahrscheinlichkeit für Kopf, genau 1,5 ist, dann hat es
die höchste Entropie.
Und wenn die Münze gezinkt ist und irgendwie die Wahrscheinlichkeit
für Kopf irgendwie größer wird, dann geht es halt in die eine Richtung
runter oder wenn sie kleiner wird, geht es in die andere Richtung
entsprechend runter, die Entropie.
Gut,
so jetzt machen wir das, was wir eigentlich machen wollen, nämlich wir
wollen ja eigentlich platzsparend kodieren an der Quelle.
Wir haben so eine Informationsquelle und statt einfach diese Zeichen
so hinzuschreiben, wie sie sind, wollen wir das jetzt komprimieren.
Gut, also nochmal, wir haben eine Informationsquelle X, die liefert
Zeichen i aus einem festgelegten Alphabet mit Häufigkeit oder
Wahrscheinlichkeit p, i.
Und wir kodieren jetzt die Zeichen und wir wollen die binär kodieren.
Das ist irgendwie wahrscheinlich für uns das sinnvollste.
Also wir kodieren die als 0 1 Strings, als Worte.
Jedes Zeichen wird übersetzt in ein Wort aus 0 1 Hochstern.
Und wir wollen jetzt ohne Informationsverlust kodieren und wir wollen
die erwartete Länge der Ausgabe möglichst klein machen.
Also wir überlegen uns jetzt, wie würde man zum Beispiel die deutsche
Sprache kodieren, wenn da eingegeben wird über die Tastatur, wenn
lauter Buchstaben eingegeben und das soll irgendwo in der Datei
abgespeichert werden und wir wissen, das wird irgendwie deutsche
Sprache.
Dann wissen wir also, die triviale Möglichkeit ist zu machen, einfach
binär zu kodieren.
Wir nummerieren die Buchstaben durch, von 1 bis 26.
Wir reservieren uns fünf Bits für jeden Buchstaben und gehen die
einfach durch.
Buchstabe 1 kriegt 0 0 0 0 0, also fünfmal.
Buchstabe 2 kriegt 0 0 0 0 1 und so weiter.
Das ist aber unter Umständen zu lang.
Wir können sparen, indem wir Zeichen, die häufiger kommen, kürzere
Wörter geben.
Und Zeichen, die seltener kommen, dafür längere Wörter geben.
Und dann spielt sich das so gegeneinander auf, dass wir unterm Strich
gespart haben.
Und das ist das, was wir meinen mit der mittleren oder der erwarteten
Länge der Ausgabe.
Und die wollen wir minimieren.
Also formal ordnen wir jedem Zeichen ein Codewort zu.
CI aus 0 1 Stern.
Und wir verwenden jetzt erst mal keine Trennzeichen, um zu trennen.
Also zum Beispiel, ich könnte das A kodieren als 0 0, könnte das H
kodieren als 1 1 0, weil es irgendwie seltener vorkommt, kann ich mir
da mehr Bits erlauben.
Das L als 1 0 und das O als 0 1.
Und dann würde ich zum Beispiel so, das wäre jetzt abgespeichert
worden.
Das ist einfach ein String durch hintereinander schreiben von diesen
Codewörtern.
Und jetzt wollen wir, da soll die ganze Information drin stecken und
wir müssen die Information aber natürlich auch noch rauskriegen, also
dekodieren.
Und jetzt können wir uns mal fragen, was heißt denn das hier?
Naja, jetzt ist es gar nicht so trivial, wenn die unterschiedliche
Länge haben.
Wenn die alle gleiche Länge hätten, dann würden wir einfach so eine
Tabelle uns aufschreiben und sagen, das heißt das und das heißt das.
Wenn die unterschiedliche Länge haben, dann könnten wir Probleme
kriegen.
Hier kriegen wir aber kein Problem.
Also wir wissen, die 1 ist nicht selber ein Codewort.
Wir kennen diese Tabelle.
Wir wissen auch 1 1 taucht hier nicht auf, aber 1 1 0 taucht hier auf.
Das muss ein H sein.
Das kann auch nichts anderes sein, wenn nichts anderes irgendwie mit 1
1 0 anfängt.
Okay, also das ist ein H und dann geht es hier weiter mit 0 0 und 0 0
muss ein A sein.
Das kann nichts anderes werden, wenn nichts mit 0 0 anfängt und so
weiter.
Dann müssen das hier zwei Ls sein und ein O.
Das heißt, das ist eine Folge von fünf Codewörtern und steht für
Hallo.
So, jetzt haben wir schon einen wichtigen Punkt schon ein bisschen
gesehen und besprochen.
Wichtig ist, dass wir das ohne Trennzeichen machen wollen und auch
effizient oder verlustfrei wieder dekodieren können müssen.
Und dafür ist es wichtig, dass kein Codewort ein Beginn von einem
anderen Codewort ist.
Damit wir sehen, okay, wir lesen ein Zeichen bis irgendwann der
String, den wir jetzt gelesen haben, in unserer Tabelle drin steht und
dann wissen wir, das ist das Zeichen.
Wenn es jetzt der Anfang wäre von einem anderen Eintrag in der
Tabelle, wüssten wir nicht, ob wir jetzt schon abschließen, ob das
schon ein X ist oder ob wir noch weiter lesen müssen und es vielleicht
auch ein T wird.
Und die Idee, Codewörter zu benutzen, wo kein Codewort ein Anfang
eines anderen Codeworts ist, das ist dann die Idee des sogenannten
Prefixcodes.
Also wir haben Code, wir haben variable Länge, das heißt über die
Länge können wir nicht entscheiden, wann das Codewort zu Ende ist.
Wir wollen keine Trennzeichen benutzen.
Und dann brauchen wir ein Prefixcode, okay.
So, und diese Prefixcodes, die sind schön und gut, weil sie
mathematisch gesehen relativ einfach sind und auch, weil sie relativ
gute Kompressionsraten haben, ja.
Wir werden jetzt Prefixcodes darstellen als eine Baumstruktur, okay.
Das sieht so aus.
Also wir machen das alles nur für Binär.
Wir können auch leicht auf größere Codierungselfabete gehen, aber wir
bleiben bei Nullen und Einzen, okay.
So, nochmal, unser Alphabet ist irgendwie 1 bis N und der Prefixcode
sind Codewörter C1 bis Cn.
Jedes Ci ist also ein String aus Nullen und Einzen.
Und der entsprechende Codierungsbaum ist jetzt ein gerichteter, also
gewurzelter binärer Baum.
Informatikbäume haben die Wurzeln oben und die Blätter unten.
Also hier ist die Wurzel und die Richtung geht sozusagen abwärts in
den Baum von Wurzel zu Blatt.
Und jede Kante hat eine 0 oder eine 1 dran zu stehen.
Und von einem Knoten gibt es nur eine Kante, oder höchstens eine
Kante, die mit 0 runter geht und höchstens eine Kante, die mit 1
runter geht, okay.
Also nach unten sozusagen gesehen, jeder Knoten hat höchstens zwei
Kinder.
Und dann die Blätter, die sind gelabelt mit den Zeichen unseres
Alphabets.
Zum Beispiel hier einfach von links nach rechts, das ist ein sehr
triviales Beispiel von A bis H, okay.
Und dann das Codewort ist jetzt hier drin versteckt, nämlich so wie
die Kanten gelabelt sind und wie die Blätter da verteilt wurden.
Also das Codewort hier für A wäre zum Beispiel 0 0 0.
Also das ist der Weg von der Wurzel zum Blatt mit dem entsprechenden
Zeichen.
Also das Codewort für D ist 0 1 1, okay.
Hier ist nochmal ganz konkret, Zeichen B hat also den Code oder das
Codewort 0 0 1 und E hat das 1 0 0 und so weiter, okay.
Diesen Baum kann man immer hinschreiben, wenn der Code Präfix frei
ist.
Überlegen Sie sich, wenn jetzt ein Codewort ein Anfang von einem
anderen Codewort wäre, dann wäre sozusagen etwas hier in der Mitte,
was nicht ein Blatt ist, irgendwie gelabelt mit einem Zeichen und das
wollen wir nicht.
Dadurch, dass die Zeichen an den Blättern steht, ist das Präfix frei.
Gut.
Und hier steckt sozusagen die ganze Information drin, wie der Code
aussieht, wie der Präfixcode aussieht.
Es gibt, das geht eins zu eins zu übersetzen.
Ich führe das alles nicht im Detail aus, aber das ist auch in dem Fall
noch nicht schwierig.
Also jede Präfix-Codierung gehört zu einem Baum, jeder Baum gehört zu
einer Präfix-Codierung.
Dann noch ein kleiner Begriff, die Tiefe eines Knotens in einem Baum,
also V ist ein Knoten, T ist ein Baum, dann ist die Tiefe die Anzahl
der Kanten auf dem kürzesten Weg zur Wurzel.
Also die Wurzel hat Tiefe 0, die Kinder der Wurzel haben Tiefe 1 und
so weiter.
Hier hätten jetzt beispielsweise alle Blätter die Tiefe 3, aber es
muss nicht sein, es können auch Blätter geringere oder höhere Tiefe
haben.
Und an dem Baum können wir jetzt auch ablesen, die mittlere Codewort
-Länge.
Also wir sehen ja für jedes Zeichen, wie lang das Codewort ist.
Das ist nämlich genau die Tiefe von dem entsprechenden Blatt.
Und die mittlere Codewort-Länge ist jetzt, wenn wir diese Tiefe
multiplizieren, mit der Wahrscheinlichkeit des Zeichens.
Also wir wollen hohe Wahrscheinlichkeiten hoch in dem Baum haben,
geringe Tiefe.
Das hier wäre jetzt sozusagen ein Beispiel für eine
Informationsquelle, die halt diese acht Zeichen hat.
Und wenn die Wahrscheinlichkeiten alle wirklich ein Achtel wären, dann
wäre das wirklich das Beste, was man da machen könnte.
Alle Blätter auf die gleiche Höhe legen, weil die alle die gleiche
Wahrscheinlichkeit haben.
Und es hätte dann die kürzeste mittlere Codewort-Länge.
Alle Codeworte haben Länge 3, also ist die mittlere Codewort-Länge
auch 3 und natürlich geht es nicht kürzer.
Also intuitiv ist es klar.
Wir können natürlich, wir brauchen erstmal genügend Blätter, um
überhaupt die ganzen Zeichen darzustellen.
Und natürlich jedes Mal, wenn wir einen Level weiter runter gehen,
dann verdoppelt sich die Anzahl der Blätter oder anders ausgedrückt,
mit jedem Bit, was wir spendieren in der Codewort-Länge, verdoppelt
sich die Größe des darstellbaren Alphabets, die Anzahl der
darstellbaren Zeichen.
Also wenn das Alphabet Sigma ist und mit Wörtern gleicher Länge
kodiert werden soll, dann brauchen wir pro Codewort so viele Blitz.
Das ist jetzt wieder genau der Logarithmus zur Basis 2 von der Anzahl
der Zeichen.
Es ist gegeben, dass das hier acht Zeichen ist.
Wie oft muss ich durch zwei teilen, bis ich bei eins angekommen bin?
Also wie viele Levels brauche ich in diesem Baum?
Es gibt noch dieses Beispiel des Morse-Alphabets, was Sie vielleicht
jetzt auch schon im Kopf hatten.
Das hat auch zwei Zeichen, ja, kurz und lang.
Ich weiß nicht, ob die einen besseren Namen haben.
Die haben auch unterschiedliche Länge und Sie sehen hier ganz gut,
dass häufige Buchstaben, sowas wie das E, sehr kurze Codewörter
kriegen und seltene Buchstaben, sowas wie das Q, lange Codewörter
kriegen.
Allerdings ist das hier kein Präfix-Code, weil zum Beispiel das
Codewort von E ist ein Anfang von dem Codewort von A oder das, was
wiederum Anfang von W ist und so weiter.
Deswegen hat der Code tatsächlich drei Zeichen, nämlich Trennzeichen,
wann ein Buchstabe aufhört und wann der nächste Buchstabe anfängt.
Okay, es gibt also, wenn Sie morsen, dann gibt es drei Zustände, kurz,
lang und Pause.
Und wenn Sie jetzt sozusagen an jedes Zeichen hinten noch ein drittes,
das Pausezeichen hinten ransetzen, dann ist es ein Präfix-Code.
Jetzt gibt es das Shannons Quellen-Codierungstheorem, was uns angibt,
Schranken, obere und untere Schranken an diese mittlere Codewort-
länge.
Und das hängt jetzt mit der Entropie zusammen, die wir am Anfang kurz
angeguckt haben.
Je höher die Entropie ist, desto mehr, desto länger müssen die
Codewörter sein.
Also, wenn x eine diskrete Zufallsvariable ist, Entropie h von x hat
und wir einen Präfix-Code für x haben, das Alphabet hat D-Zeichen, das
Code -Alphabet, also für uns ist D gleich 2.
Dann ist die kleinstmögliche mittlere Codewort-Länge n-quer, dann
liegt die zwischen Entropie durch, naja, für uns ist D gleich 2, also
log 2 von 2 ist 1, also zwischen Entropie und Entropie plus 1.
Okay, also wir haben es ziemlich genau festgelegt.
Ja, die mittlere Codewort-Länge, vergewissern Sie sich noch mal, das
ist also die Länge mal die Wahrscheinlichkeit eines Zeichens, also die
kann nicht ganzzahlig sein.
Wir können sowas wie mittlere Codewort-Länge von 3,5 haben.
Wenn zum Beispiel irgendwie 50 Prozent der Zeichen oder mit
Wahrscheinlichkeit 50 Prozent ein Zeichen mit 3 und mit
Wahrscheinlichkeit 50 Prozent ein Zeichen mit 4 Codewort-Länge gemacht
wird, dann hat es eine mittlere Codewort-Länge von 3,5.
Okay, also es ist mindestens die Entropie, aber echt kleiner als die
Entropie plus 1.
Okay, also die Entropie und die mittlere Codewort-Länge, die
Komprimierbarkeit hängen direkt zusammen.
Dann, das ist Shannons Quellen-Codierungstheorem, auch Shannon, der
Name wird ziemlich oft auftauchen.
Ich weiß nicht, wie oft heute, aber zumindest, wenn Sie sich weiter
informieren wollen.
Es gibt jetzt auch die Shannon-Farnow-Codierung.
Also wie würde man das hier beweisen?
Man würde, naja, man muss erst mal zeigen, dass es nicht besser geht
und dann muss man hier zeigen, dass man ein Code hat, dessen mittlere
Codewort -Länge echt kleiner ist als die Entropie plus 1.
Da hat Shannon also ein Code angegeben und das ist der sogenannte
Shannon -Farnow-Code oder die Shannon-Farnow-Codierung.
Und die stelle ich Ihnen jetzt vor.
Wir machen das erst an einem Beispiel und danach exakt.
Angenommen, das hier sind unsere Zeichen, die wir an der Quelle haben
und die entsprechenden Wahrscheinlichkeiten, dass dieses Zeichen an
der Quelle auftritt.
Also wir haben hier Zeichen von 0 bis 12, vielleicht mehr, weiß ich
nicht, ob sich das hier schon verwundert.
Und die Wahrscheinlichkeiten sind schon, die Zeichen sind schon so
sortiert, dass sie mit absteigenden Wahrscheinlichkeiten in der Liste
auftauchen.
Also die 0 ist das häufigste Zeichen und die 12 hier in der Liste das
seltenste Zeichen mit 15 Prozent oder fast 16 Prozent
Wahrscheinlichkeit auch die 0 auf und die 12 nur mit einer
Wahrscheinlichkeit von ungefähr 2 Prozent.
Gut, so was macht jetzt Shannon-Farnow?
Wir suchen also für jedes Zeichen suchen wir ein Codewort und die Idee
ist, für häufige Zeichen kurze Wörter zu benutzen.
Aber die Frage ist, wie genau machen wir das?
Und Shannon-Farnow macht es jetzt hier in dem binären Teil so, dass
wir uns angucken, von, sagen wir mal, von oben gesehen, was ungefähr
50 Prozent der Wahrscheinlichkeit ausmacht.
Also die ersten vier Zeichen zusammengenommen nehmen ungefähr 50
Prozent, tauchen in ungefähr 50 Prozent der Fälle auf, das ist hier
irgendwie ein bisschen weniger als 50 Prozent und dann entsprechend
sind die die weiteren Zeichen tauchen auch ungefähr 50 Prozent der
Fälle auf.
Also wir suchen uns den Punkt, wo sozusagen den Cut, den wir da setzen
wollen, wo die ungefähr gleich verteilt sind.
Und dann fangen wir schon mal an, die Codewörter anzufangen.
Das sind jetzt natürlich noch nicht die finalen Codewörter, sondern es
ist die erste Stelle in dem Codewort.
Also die ersten vier Zeichen kriegen als erste Stelle eine 0 und der
Rest kriegt als erste Stelle eine 1.
Und dann iterieren wir das einfach rekursiv.
Das heißt, wir gucken in den ersten Block, was taucht jetzt die Hälfte
der Zeit auf.
Also die zusammen haben ungefähr 50 Prozent oder genau irgendwie sowas
wie 48 Prozent und jetzt gucken wir also was 24 und 24.
Also eine möglichst gute Aufteilung in gleich große
Wahrscheinlichkeiten und das ist jetzt hier die ersten beiden und die
letzten beiden.
Und dann machen wir es wieder so, die hier oben kriegen als zweite
Stelle 0 und die anderen kriegen als zweite Stelle 1 und wir gehen
rekursiv wieder in die kleineren Blöcke rein.
Das heißt, wir gucken dort und da ist die Aufteilung einfach die 1 zu
1 Aufteilung und wir sind jetzt fertig.
Das Codewort für das Zeichen 0 wird 0 0 0 sein.
Das Codewort für das Zeichen 1 wird 0 0 1 sein.
Jetzt gehen wir noch Rekursion in diesen Teil rein, sortieren die
wieder so und haben jetzt das Codewort gefunden für das 2 und für die
3.
Und hier unten müssen wir auch noch den Block rekursiv durchmachen,
den dann wieder rekursiv durchmachen.
Immer oben die Nullen und unten die Einsen ranhängen und nach einer
Weile sieht es dann vielleicht so aus.
Und dann merken sie, dass ganz automatisch die weniger häufigen
Zeichen öfter in die Rekursion reingeschoben werden und dadurch
längere Codewörter kriegen.
Und das wird automatisch ein Präfixcode werden.
Und der ist sogar ziemlich gut.
Also hier ist es ganz formal als Funktion geschrieben.
Die Shannon-Fano-Codierung von einer Zeichenliste z, also wir haben
eine Zeichenliste z mit Zeichen z1 bis zk und Wahrscheinlichkeiten p1
bis pk und der Output ist die Codewörter c1 bis ck.
Gut, also wenn k gleich 1 ist, also wenn wir nur ein Zeichen zu machen
haben, dann geben wir hier das leere Codewort aus.
Das ist so die Terminierung der Rekursion.
Andernfalls sortieren wir uns die Zeichen nach absteigenden
Wahrscheinlichkeiten oder nicht aufsteigenden Wahrscheinlichkeiten und
suchen dann diese Trennung.
Also wir trennen z an einem Index i und das heißt, also wir gucken uns
z1 bis zi an und die anderen zi plus 1 bis zk.
Und wir wählen den Index so, dass wenn wir die Wahrscheinlichkeiten
aus dem ersten Teil nehmen und die Wahrscheinlichkeiten zusammen
addiert aus dem zweiten Teil nehmen, dass die möglichst nah
beieinander liegen.
Also quasi in der Hälfte, so gut wie möglich.
Das kann man leicht machen.
Und dann rufen wir Rekursionen für die entsprechenden Teilinstanzen
auf.
Also wir machen z1, das ist jetzt nur die erste Menge mit den
Wahrscheinlichkeiten, wie sie da oben kommen und kriegen da jetzt ein
Codewort dafür und wir hängen an alle diese Codewörter vorne die 0
ran.
Und für z2 rufen wir auch Rekursiv auf und hängen an alle diese
Codewörter vorne eine 1 an.
Okay, das sind die Codewörter, die wir machen.
Das kann man sich auch wieder in dem Baum vorstellen.
Ich habe gesagt, dass Präfixcodes und Codierungsbäume quasi das
gleiche sind.
Das wäre jetzt hier der Baum von dem Beispiel davor.
Es sieht jetzt so aus, als ob die Blätter auf der gleichen Höhe sind,
aber sie merken, dass da ein paar Kanten länger sind als andere
Kanten.
Also die Blätter hier sind tatsächlich höher in dem Baum, mit
geringerer Tiefe höher in dem Baum.
Und das Blatt hier, das hat schon eine Tiefe von 5, weil das Codewort
schon 5 lang ist.
Das ist 1 1 0 1 1.
Und Sie müssen sich das so vorstellen, dass Shannon Fano diesen Baum
von oben nach unten aufbaut.
Shannon Fano sagt, okay, wir fangen an bei der Wurzel.
Wir machen diese zwei Kinder mit 0 und mit 1 und dann sagt es nur
noch, okay, welche Blätter kommen in den linken Teilbaum und welche
Blätter kommen in den rechten Teilbaum.
Also der Baum wird von oben nach unten gebaut.
Die mittlere Codewortlänge der Shannon Fano Codierung ist gut.
Die ist höchstens optimal plus 1 oder sogar echt weniger als optimal
plus 1.
Also im Schnitt brauchen wir höchstens ein Bit mehr als die Entropie.
Aber muss nicht unbedingt optimal sein.
Es gibt Beispiele, wo Shannon Fano nicht optimale mittlere
Codewortlängen gibt.
Deswegen wird sie auch nicht gemacht.
Weil man kann es optimal machen mit der sogenannten Huffman Codierung,
die wir jetzt gleich machen werden.
Und der große Unterschied ist, Huffman baut den Baum von unten nach
oben auf.
Also von den Blättern zur Wurzel statt von der Wurzel zu den Blättern.
Gut.
Machen wir wieder die Huffman Codierung erst an einem Beispiel und
danach formal.
Meine Zeichen sind jetzt hier diese Zeichen von sechs Stück und die
sind wieder schon sortiert nach ihren Wahrscheinlichkeiten, die
dahinter stehen.
Und ich weiß ja, die werden die Blätter in meinem Baum sein.
Und jetzt ist nun die Frage, welche Blätter füge ich zusammen?
Welche kriegen sozusagen in einer Stufe höher?
Wer sind Geschwister?
Welches Paar hat einen gemeinsamen Vater?
Und die Idee ist, dass wir die beiden unwahrscheinlichsten Zeichen,
also die beiden seltensten Zeichen mit den geringsten
Wahrscheinlichkeiten oder Häufigkeiten nehmen und sagen, die beiden
kriegen einen gemeinsamen Vater.
Und dann sehen wir diesen Vater an, dem geben wir auch eine
Wahrscheinlichkeit, nämlich die Summe der Kinder.
Also mit Wahrscheinlichkeit 10% sind wir dann sozusagen in diesem
Teilbaum.
Und jetzt sehen wir das als unsere neue Instanz an, dass wir immer
noch diese vier Zeichen hier haben und wir haben dieses Ding.
Und die Frage ist jetzt, wer kommt zusammen und kriegt einen
gemeinsamen Vater?
Das könnten jetzt wieder zwei Originalzeichen sein oder ein
Originalzeichen und ein Teilbaum.
Und wieder, wir machen das wieder so, wir nehmen uns die beiden mit
den geringsten Wahrscheinlichkeit und fügen die zusammen.
Also das wären hier die unteren beiden.
Und jetzt merken Sie, was im nächsten Schritt passieren wird, ist
nämlich nicht, dass dieser Unterbaum, der hat jetzt eine
Wahrscheinlichkeit von 25% schon bekommen, weil es die Summe der
Wahrscheinlichkeiten in diesen Blättern sind.
Und die beiden unwahrscheinlichsten sind jetzt die beiden und die
werden zusammengefügt erst mal.
Und dann entsprechend sind jetzt die beiden unwahrscheinlichsten 25
und 35, die werden zusammengefügt und am Ende die zusammengefügt.
Und das ist der Baum.
Das ist der Codierungsbaum und jetzt geben wir einfach tatsächlich
willkürlich diese Nullen und Einsen.
Einfach nur darauf achten, dass ein Kind 0 und das andere Kind 1
kriegt und dann ist das auch ein Präfixcode.
Und der ist tatsächlich optimal.
Hier als Beispiel am Ende das Zeichen d, das war so häufig, das hat
eine Häufigkeit von 40%, dass es sich tatsächlich gelohnt hat, ein
Codewort der Länge 1 zu geben für das d, weil wir damit so viel sparen
können.
Und dadurch müssen notgedrungen, um die Präfixeigenschaft zu haben,
alle anderen Codewörter mit einer 0 anfangen, damit wir nicht denken,
das könnte vielleicht ein d sein.
Und so hat e zum Beispiel das Codewort 0 1 0 und c hat das Codewort 0
1 1 1.
Gut, hier ist es wieder formal.
Also als Eingabe haben wir wieder eine Menge von Zeichen, n bis n, und
Wahrscheinlichkeiten p1 bis pn und als Ausgabe geben wir den Code aus
und am besten mittels des Baumes.
Also t ist der Baum, der zu dem Code gehört.
Wir erhalten uns die Menge q, das sind die Sachen, die sozusagen zur
Verfügung stehen, um zusammengefügt zu werden.
Am Anfang sind es einfach unsere Zeichen und später sind es dann so
Teilbäume, schon zusammengefügte Sachen.
Und für alle diese Zeichen am Anfang sind es Blätter in dem Baum und
dann gehen wir jetzt in genau, in jedem Schritt wird die Menge q 1
kleiner, weil wir zwei zusammengefügt haben zu einem Teil.
Also wir wissen, es sind genau n minus 1 Schritte zu gehen und in
jedem Schritt wird ein neuer Knoten kreiert in dem Baum und der Knoten
heißt jetzt mal z.
Und z kriegt als Kinder oder Nachfolger die beiden
unwahrscheinlichsten Elemente aus q.
Also u ist das Element aus q mit der entsprechenden Wahrscheinlichkeit
minimal, das wird der linke Nachfolger und v ist jetzt aus dem Rest
mit Wahrscheinlichkeit minimal und das wird der rechte Nachfolger.
Wir haben die Nachfolger gesetzt und wir setzen jetzt die
Wahrscheinlichkeit von z einfach als die Summe der
Wahrscheinlichkeiten und fügen z in q ein.
Wir wissen dann, was die die Wurzel ist.
Genau, den Baum speichern wir ab.
Jedes Element kennt seine Nachfolger, linken und rechten Nachfolger
und wir müssen auch die Wurzel kennen.
Das ist das, was zuletzt in q eingefügt wurde und das können wir dann
zurückgeben.
Gut.
Ich habe es schon erwähnt, der Huffman-Algorithmus berechnet den
Codierungsbaum mit optimaler mittlerer Codewortlänge.
Also bestmögliche mittlere Codewortlänge zu dieser Zufallsvariable.
Das wollen wir auch beweisen und um das zu beweisen, brauchen wir ein
Lemma, wo wir im Prinzip Großteil der Arbeit drin steckt.
Das Lemma ist jetzt ein bisschen länglicher formuliert.
Ich lese es einmal vor.
Sigma ist unser Alphabet, Zeichen von 1 bis n und die
Wahrscheinlichkeiten p1 bis pn oder die Wahrscheinlichkeitsmenge dann
als groß p.
Und für zwei verschiedene Zeichen in dem Alphabet x und y, x und
gleich y, mit den unwahrscheinlichsten Wahrscheinlichkeiten, also mit
den geringsten Wahrscheinlichkeiten.
Das sind die, die wir in dem Huffman-Algorithmus einem gemeinsamen
Vater geben.
Und wir wollen, dass das kein Fehler war, wenn wir über
Codierungsbäume mit optimaler mittlerer Codewortlänge reden.
Das heißt, was wir brauchen ist, dass mindestens ein optimaler
Codierungsbaum, also optimal im Sinne von minimale mittlere
Codewortlänge, existiert, der diese beiden in einem gemeinsamen
Elternknoten gibt.
Nicht unbedingt alle optimalen, erinnern Sie sich an das Beispiel, wo
alle Zeichen gleichwahrscheinlich sind.
Da nimmt man den Baum, der komplett balanciert ist und dann ist es
ziemlich willkürlich, wie wir die Zeichen da unten machen.
Also wir können nicht verlangen, dass die beiden unwahrscheinlichsten
immer zusammenkommen, aber wir brauchen mindestens einen optimalen,
der den gemeinsamen Elternknoten gibt.
Das ist zumindest notwendig und tatsächlich dann auch hinreichend,
wenn wir das gezeigt haben.
Gut, also zeigen wir das.
Nochmal das Setup.
X und Y sind verschiedene Zeichen, die haben kleinstmögliche
Wahrscheinlichkeiten in dieser Wahrscheinlichkeitsmenge.
Und wir haben einen Codierungsbaum, der minimale mittlere
Codewortlänge hat.
Irgendeinen.
Wir wissen eigentlich nichts darüber, außer dass er minimale mittlere
Codewortlänge hat.
Und was wir zeigen wollen ist, dass es einen gibt, wo das X und Y
gemeinsam Elternknoten haben.
Das heißt, wir gucken uns jetzt in diesem beliebigen Codierungsbaum T'
an, gucken uns an, wo liegen X und Y.
Und OBDA hat, X ist nicht geringerer Tiefe als Y.
Also die Tiefe von X ist mindestens die Tiefe von Y.
Und Z sei der Elternknoten von X.
Das ist jetzt ein Elternknoten, also es ist nicht Y.
Die X und Y sind ja Blätter in den Bäumen.
Gut, jetzt unterscheiden wir Fälle, wie dieser Baum aussehen könnte.
Also es könnte sein, dass Z gar keinen anderen Nachkommen hat, nur X.
Das ist aber Quatsch.
Sie haben vielleicht schon gemerkt, dass jeder Knoten in so einem
Codierungsbaum, den wir bisher gesehen haben, immer genau zwei Kinder
hat.
Und das ist tatsächlich auch immer sinnvoll, genau zwei Kinder zu
haben.
Weil, wenn Z nur ein Kind hat, dann heißt es, jedes Codewort, wenn ich
von oben runter gekommen bin bis hier, dann habe ich null
Erkenntnisgewinn, wenn ich hier noch das Codewort um eins verlängere.
Dann kann ich einfach das abschneiden und Z als X nehmen als neues
Blatt.
Und dann hat X ein kürzeres Codewort.
Das heißt, der Baum hätte insgesamt mittlere Codewortlänge, weniger.
Also das passiert nicht.
Also Z hat noch einen Nachbarn.
Und dieser Nachbar, der heißt jetzt mal Q, in dem Bild zumindest.
Aber was wir uns angucken, ist W, das ist ein tiefster Nachfolger von
Z, der nicht X ist.
Also Z hat einen Nachbarn, das heißt zwei Nachkommen, also gibt es
mindestens zwei.
Es gibt einen, der nicht X ist und von den anderen nehmen wir uns ein
Blatt, was am tiefsten hängt.
Und das sei jetzt mal W.
Und jetzt ist die Frage, wo liegt W?
Was ist die Tiefe von W?
Wir wissen, dass die Wahrscheinlichkeit, die Häufigkeit von W,
höchstens die Häufigkeit, das ist, wenn man zu kurz die Beweise
aufschreibt, also aus der Optimalität von T.
Wir wissen, T' ist optimal.
Das heißt, was steht hier im Raum?
Es steht im Raum, X und W zu tauschen.
Wir könnten den gleichen Baum nehmen, nur die Labels X und W tauschen,
also die Codewörter für X und W ändern.
Wenn wir das tun, weil T' optimal war, kann es nicht strikt besser
werden.
Wenn die Tiefe von W tiefer ist als die Tiefe von X, dann würde der
Tausch heißen, dass W ein kürzeres Codewort kriegt.
Ein kürzeres Codewort darf ich, das ist so einfach, aber ich stolpere.
Die Quintessenz ist klar.
Wenn W weiter unten liegt in dem Baum, dann muss einfach die
Wahrscheinlichkeit von W, die Häufigkeit von W, geringer sein, weil es
einfach nicht lohnt, die Codewörter zu tauschen.
Wir können nicht häufigeren Zeichen längere, kürzere Codewörter geben.
Sonst wäre ganz klar, der Tausch einfach besser.
Bessere und mittlere Codewortlänge.
Lass es jetzt einfach so stehen.
Okay, das heißt, W hat ja eine Tiefe, die ist mindestens die von X und
damit auch mindestens die von Y.
Das heißt, wir können aber davon ausgehen, dass W eine
Wahrscheinlichkeit hat, die mindestens die von X und von Y ist, weil X
und Y die geringsten Wahrscheinlichkeiten haben.
Also hat W die gleiche Wahrscheinlichkeit und wir machen weiter,
genau, die einzige Möglichkeit, dass W hier runter liegt, ist, dass
sie die gleiche Wahrscheinlichkeit haben.
Und dann machen wir statt mit dem XY-Paar, machen wir weiter mit dem
XW -Paar im Fall 3.
Im Fall 3 ist es jetzt so, es gibt also, X ist das Blatt, Z ist der
Elternknoten und es gibt nur noch ein Blatt da drunter, Q, und nichts
mehr da drunter.
Das ist echt ein Blatt, jetzt.
Und jetzt ist es wieder so, jetzt machen wir den Tausch zwischen Q und
Y.
Warum ist der Tausch gut?
Wieder Y wird nicht ein längeres Codewort kriegen.
Q hat eine Wahrscheinlichkeit, die ist mindestens höchstens die von Y,
weil es tiefer oder mindestens so tief liegt wie Y, wegen der
Optimalität des Baumes.
Das heißt, hier rumtauschen ist erlaubt, weil wenn der optimal war,
dann hatten die die gleiche Wahrscheinlichkeit.
Entschuldigung.
Gut, also das ist ein Austauschargument und wir haben dann einen Baum
gefunden, der ist immer noch optimal und X und Y haben jetzt einen
gemeinsamen Elternknoten.
Das heißt, in diesem Schritt, in diesem Huffman-Codierungsschritt, wo
wir den ersten Schritt, wo wir die ersten beiden Zeichen nehmen mit
den geringsten Wahrscheinlichkeiten und denen gemeinsam Elternknoten
geben, da haben wir schon mal nichts falsch gemacht.
Es ist immer noch möglich, das optimal zu ergänzen.
Und was jetzt noch fehlt, ist, diesen Beweis komplett auszurollen.
Was wir dann tun, nämlich wir identifizieren diesen neuen Elternknoten
als ein neues Element.
Wir behandeln das wie ein neues Zeichen mit der Wahrscheinlichkeit der
Summe der entsprechenden Wahrscheinlichkeiten und dass wir da keinen
Fehler machen.
Und dann machen wir jetzt Induktionen nach der Anzahl der Zeichen, die
noch zu machen sind und beweisen also, dass der Huffman-Algorithmus
einen Codierungsbaum mit minimaler mittlerer Codewortlänge gibt und
der Induktionsanfang ist irgendwie ein Zeichen oder zwei Zeichen und
das ist trivialerweise erfüllt.
Also wir wissen jetzt, wenn wir für ein bestimmtes n für jedes
Alphabet mit höchstens n Zeichen und für alle Möglichkeiten, wie da
die Wahrscheinlichkeiten darauf verteilt sind, macht Huffman das
Richtige.
Und jetzt sind wir aber bei einem Alphabet mit n plus 1 Zeichen und
müssen es reduzieren, auf den Fall mit n Zeichen.
Was macht der Huffman-Algorithmus Der Huffman-Algorithmus gibt uns
einen Baum, den wir jetzt thuff nennen, für unsere Instanz.
Und diese mittlere Codewortlänge, die bezeichnen wir jetzt als f von
t.
Das ist einfach die mittlere Codewortlänge von dem Baum.
Und wir müssen uns wieder vergleichen mit einem optimalen Baum, also
topt ist ein optimaler Codierungsbaum für diese Instanz und wir haben
Angst davor, dass es einen so dass diese Ungleichung hier gilt, dass f
topt echt kleiner ist als f thuff.
Jetzt haben wir die Zeichen, die von Huffman-Algorithmus zuerst
zusammengewasst wurden.
Wir wissen, es gibt einen optimalen Baum nach dem vorherigen Lemma, wo
x und y wirklich zusammen einen gemeinsamen Elternknoten haben, so wie
in thuff.
Also wir nehmen uns ein topt her, wo das gleiche Zeichen den gleichen
Elternknoten haben.
Jetzt machen wir das, was wir in dem Huffman-Algorithmus machen,
nämlich wir entfernen diese beiden Zeichen aus dem Alphabet, wir fügen
das zusätzliche Zeichen z ein für den Elternknoten und geben ihm die
Wahrscheinlichkeit, was die Summe aus den vorherigen
Wahrscheinlichkeiten ist.
Jetzt können wir das tun auch in den Bäumen.
In den Bäumen heißt es einfach, wir schneiden diese Blätter ab und
kriegen jetzt als Set ein neues Blatt.
Und das sind jetzt topt Strich und thuff Strich, die abgeschnittenen,
kleineren Bäume.
Und wir wissen, thuff Strich ist ein Huffman-Baum für die Instanz
Sigma Strich mit den entsprechenden neuen Wahrscheinlichkeiten, weil
wir einfach in dem Huffman-Algorithmus das Ding jetzt so behandelt
haben, wie eine eigene neue Instanz.
Das heißt, wir können davon ausgehen, dass ab jetzt der Huffman
-Algorithmus nach Induktionsvoraussetzung auf dem kleineren Alphabet
etwas Optimales tut, nämlich einen optimalen Codierungsbaum findet.
Und topt Strich ist ein möglicher Codierungsbaum für diese Instanz mit
den neuen Wahrscheinlichkeiten.
Das heißt,
thuff Strich hat eine mittlere Codierungslänge, die sich ergibt aus
der Codierungslänge von dem thuff.
Nämlich, wir müssen abziehen die Wahrscheinlichkeit von dem Zeichen X
und die Tiefe von dem Zeichen X, die Wahrscheinlichkeit von dem
Zeichen Y und die Tiefe von dem Zeichen Y und dafür drauf addieren die
Wahrscheinlichkeit von dem Zeichen Z und die Tiefe von dem Zeichen Z.
Aber wir wissen ja genau, wie sich das alles zusammensetzt, wie die
hier hinten gegeben sind, nämlich die Wahrscheinlichkeit von dem
Zeichen Z ist gerade die Summe aus den beiden.
Die Tiefen von X und Y sind gleich, irgendeine Zahl, 5, und die Tiefe
von Z ist dann genau 1 weniger.
Das heißt, wenn man das ausrechnet, dann kriegt man raus, dass dort
genau die mittlere Codewortlänge von dem thuff minus PX minus PY ist.
Das ist die mittlere Codewortlänge von dem abgeschnittenen Huffman
-Baum.
Jetzt, die mittlere Codewortlänge von dem abgeschnittenen optimalen
Baum, das ist irgendein Codierungsbaum, der war optimal, als X und Y
noch da waren, muss nicht unbedingt optimal sein, wenn es
abgeschnitten wurde.
Aber es ist eine mögliche Codierung.
Wir können aber auch wieder uns sagen, dadurch, dass X und Y hier das
gleiche Level hatten, können wir genau die gleiche Rechnung machen.
Wir wissen genau, wie sich die Wahrscheinlichkeit von Z verhält zu den
Wahrscheinlichkeiten von X und Y, die haben wir so festgelegt.
Wir wissen genau, wie sich die Höhe von Z verhält zu der Höhe von Y, X
und Y.
Und auch wenn die auf unterschiedlichen Höhen waren, alles was
rauskommt ist, dass die mittlere Codewortlänge von dem beschnittenen
Baum genau PX plus PY weniger ist, als die mittlere Codewortlänge von
dem Originalbaum.
Das heißt, der Term hier oben ist bestmöglich, wenn PX und PY sind
konstanten, wenn das hier vorne bestmöglich ist.
Und das vorne bestmöglich,
genau, wir wissen, die, was, habe ich noch eine Folge?
Ja, gut.
Dann, T-Obstrich wäre jetzt besser als T-Haftstrich.
Wir haben hier leider das nicht hingeschrieben, ich muss ganz kurz
zurückgehen hier unten.
Ja, ich setze diese Ungleichung hier ein, wir sind davon ausgegangen,
wir haben Angst davor, dass der Obstbaum echt besser ist als der
Haftbaum.
Und dieses echt besser geht jetzt in, dass das hier unten echt besser
ist als das hier unten.
Das heißt, der Obststrichbaum wäre echt besser als der Haftstrichbaum,
aber wir wissen, der Haftstrichbaum ist nach Induktion bestmöglich.
Deswegen gilt es auch für den Haftbaum.
So, das ist der Beweis zu der Huffman-Codierung.
Die Huffman-Codierung ist gut, liefert optimale Präfixcodes, aber hat
unterschiedliche Codewortlängen und das hat auch Nachteile.
Also stellen Sie sich vor, wenn wir das jetzt mehr als einen Prozess
ansehen, diese Codierung, als ein Endergebnis.
Wenn Sie die Taste auf der Tastatur drücken und das war irgendwie ein
sehr seltenes Zeichen, sowas wie geschweifte Klammer zu oder so und
die wird jetzt abgespeichert an dem Computer, die kriegt halt ein
relativ langes Codewort, dann wird es sozusagen, das Abspeichern einer
geschweiften Klammer zu braucht sehr viel länger als das Abspeichern
eines Es.
Also das sind die Dekodierungs- oder Codierungsverzögerungen.
Das ist ein Nachteil.
Wir haben sozusagen unterschiedliche Zeiten, um den String zu
dekodieren.
Außerdem wird der dritte Punkt, den mache ich zuerst, wird
vorausgesetzt, dass wir wissen, wie häufig die Zeichen sind.
Also in der deutschen Sprache sind die Häufigkeiten von den einzelnen
Buchstaben anders als in der französischen Sprache, aber wir wollen ja
nicht so wie unsere Wortdokumente abgespeichert werden, dass es
abhängt von der Sprache.
Also wir würden ungerne erstmal irgendwie den Duden-Data meinen
müssen, um die ganzen Häufigkeiten rauszukriegen und daraufhin unsere
Kompression irgendwie zu basieren.
Es gibt Codierungsverfahren, die kein Apriori-Wissen dieser Art
voraussetzen müssen, sondern sozusagen durch die Inputquelle
durchgehen und gucken, was da passiert und sich dynamisch anpassen.
Schaffen wir aber nicht hier in der Vorlesung heute darüber zu reden.
Aber das ist ein Nachteil von der Hafenankodierung.
Man muss genau wissen, was sind die erwarteten Wahrscheinlichkeiten
und dann ist es auch nur erwartet gut, nur wenn sich die
Informationsquelle wirklich an diese Wahrscheinlichkeiten hält,
sozusagen.
Der zweite Punkt ist eigentlich ein genereller Problempunkt, der jetzt
sozusagen schon den Übergang macht zwischen Quellkodierung und
Kanalkodierung.
Wir haben ja in der Quellkodierung sozusagen Redundanz eliminiert.
Wir haben Sachen, die irgendwie häufig vorkommen, wiederholte Zeichen
und so weiter, haben wir diese Redundanz rausgenommen und sehr viel
konziser abgespeichert, sodass jetzt jedes Zeichen in dem kodierten
Ding extrem wichtig ist.
Stellen Sie sich vor, in dem Kodierungsbaum an jedem Schritt ist es
sehr wichtig, ob ich jetzt nach links oder nach rechts gehe, weil wenn
ich da einmal einen Fehler mache irgendwo, dann lande ich auf jeden
Fall woanders.
Und das ist sozusagen genau entgegengesetzt zu dem, was wir in der
Kanalkodierung uns angucken müssen, nämlich es ist sehr
fehleranfällig.
Wenn man einmal einen Fehler macht, also einmal diesen String falsch
ausliest oder falsch schreibt auch, dann wird da wirklich ein Fehler
produziert.
Und wir werden dann als nächstes die Kanalkodierung uns angucken, wo
wir genau das Gegenteil machen, nämlich wir bringen wieder Redundanz
rein, um Fehleranfälligkeit zu minimieren.
Vorher noch, bevor, ja vielleicht noch mal noch ein Beispiel.
Es gibt noch, ich hatte schon mal glaube ich Faxe erwähnt.
Hier ist Faxübertragung.
Also bei einer Faxübertragung ist es ja so, man liest auf der einen
Seite dieses Papier ein.
Es wird im Prinzip binär kodiert.
Es wird einfach nur zu jedem Pixel entschieden, ob er jetzt weiß oder
schwarz ist.
Wir gehen mal davon aus, dass es so ein simples Faxgerät ist.
Und dann soll übermittelt werden, Sie haben das vielleicht auch schon
mal gehört, über akustische Signale oder über sehr einfache
Datenkanäle, einfach der String aus weiß, weiß, weiß, weiß, schwarz,
schwarz, schwarz, weiß, schwarz, weiß, schwarz und so weiter.
Und das andere Faxgerät malt es dann auf, wie das dort so ist.
Da ist jetzt natürlich die Anzahl der weißen Elemente üblicherweise
sehr viel höher als die Anzahl der schwarzen Elemente.
Es fängt wahrscheinlich an, erst mal mit drei Zentimetern weiß.
Und wir wollen, genau, also hier steht so was von 15% Schwerzungsgrad.
Also wenn 15% schwarz ist auf so einem Fax, keine Ahnung, wie
realistisch das ist, dann hätte das eine Entropie von ungefähr 0,61.
Nochmal zur Erinnerung, wir haben hier zwei Zeichen, nur weiß und
schwarz.
Das heißt, die maximal mögliche Entropie ist Logarithmus zu Basis 2
von 2, also genau 1.
Also eine relativ geringe Entropie.
Gut, also wir wollten eine mittlere, kurze, mittlere Kotwortlänge
ungefähr haben.
Also ungefähr eine Kotwortlänge von 0,6 im Mittel.
Das ist jetzt natürlich schwierig, wenn man nur binär kodieren können
und nur schwarz und weiß haben.
Ich meine, sehr viel bleibt uns nicht übrig, als weiß 0 und schwarz 1
zu machen und dann einfach diesen 0,1 String zu machen.
Dann haben wir aber natürlich eine mittlere Kotwortlänge von 1.
Wir wollen aber nur 0,61 haben.
Das heißt, was ist eine Idee, was man hier machen könnte?
Wir könnten Blöcke zusammenfassen.
Wir können statt die einzelnen Bildpunkte als einzelne Zeichen zu
sehen, können wir sagen, okay, wir gucken uns jetzt einfach mal fünf
Bildpunkte an und sagen, das ist ein Zeichen.
Also k ist die Anzahl der Zeichen, zum Beispiel da unten ist ein
kleines Beispiel.
Wenn wir zwei Zeichen uns angucken, können wir sagen, weiß-weiß oder
weiß -schwarz, schwarz-weiß oder schwarz-schwarz.
Und die haben dann entsprechende Wahrscheinlichkeiten.
Dadurch, dass weiß so häufig auftaucht, ist es ziemlich häufig so,
dass man so ein weiß-weiß-Ding sieht.
Das ist dann also mit Wahrscheinlichkeit 1,5 oder weiß-schwarz ist mit
Wahrscheinlichkeit 20 Prozent und genauso schwarz-weiß und 10 Prozent
für schwarz-schwarz.
Und dann könnten wir wieder ganz normal einen Huffman-Präfixkod machen
und diese Blöcke kodieren.
Dann könnten wir jetzt ein kurzes Wort nehmen für weiß-weiß zum
Beispiel.
Eine andere Möglichkeit ist aber die sogenannte Lauflängenkodierung.
Das wird tatsächlich wohl so verwendet bei Fax- und Videoanwendungen.
Und da haben wir also auch die Idee, dass wir zusammenfassen die
Blöcke, aber uns nicht festlegen auf das k auf die Länge der Blöcke.
Sondern gerade wenn jetzt so wenig Schwarz in dem Weißanteil drin ist,
dann speichern wir uns einfach sozusagen den Abstand zum nächsten
schwarzen Punkt.
Also in dem Beispiel, wenn das jetzt hier irgendwie das, was das Fax
wirklich liest, das liest weiß-weiß-weiß, schwarz-weiß-weiß, schwarz
-schwarz und so weiter, dann würden wir das speichern als drei, für
welche drei Weiße kommen.
Zwei, weil danach zwei Weiße kommen.
Null, weil hier zwischen Null Weiße sind.
Vier und so weiter.
Also wir würden erstmal dieses Ding übersetzen in diese Zahl.
Diese Zahl hat jetzt, die ist dann, weiß ich nicht, vielleicht auch
wieder dezimalkodiert, so wie sie hier steht.
Und dann haben wir die Zeichen von 0 bis 10 und übermitteln nur noch
diese Zahl.
Also wir machen so die Anzahl der Zeichen höher.
Also dann hätten wir jetzt hier 10 Zeichen, die übermittelt werden
können und dann können wir uns eine Binärkodierung überlegen für die 3
und für die 0 und so weiter.
Oder wir kodieren das jetzt nicht dezimal, sondern oder wir machen
einfach ein Codewort für jede natürliche Zahl.
Dafür bräuchten wir jetzt Wahrscheinlichkeiten für die einzelnen
Abstände.
Also wir haben eine Wahrscheinlichkeit, dass jetzt ein Block von K
aufeinanderfolgenden weißen Punkten kommen und die können wir
abschätzen, wenn wir wissen, weiße Zeichen kommen sehr viel häufiger
als schwarze Zeichen, dann kommen also weiße Blöcke, ziemlich lange
weiße Blöcke, noch relativ häufig vor, aber dann irgendwann wird die
Wahrscheinlichkeit immer geringer, dass irgendwann muss ja mal wieder
ein schwarzer Punkt kommen.
Also die Wahrscheinlichkeit, wenn die Wahrscheinlichkeit W, die PK,
ist jetzt die Wahrscheinlichkeit für K aufeinanderfolgende weiße
Punkte, die dann aufhören mit einem schwarzen Punkt.
Wir gehen wieder davon aus, dass das alles unabhängig voneinander ist,
dann ist die Wahrscheinlichkeit dafür einfach die Wahrscheinlichkeit
von weiß, K mal, mal die Wahrscheinlichkeit von schwarz.
Wieder Strings von Ereignissen werden einfach multiplizierte
Wahrscheinlichkeiten.
Also das ist das K-Fache der Wahrscheinlichkeit von weiß mal die
Wahrscheinlichkeit von schwarz.
Und so eine Wahrscheinlichkeitsverteilung, wenn man die hier gegeben
hat als Konstanten und dann jetzt in Abhängigkeit von K sich das
anguckt als Verteilung, das nennt man geometrische Verteilung und die
sieht dann ungefähr so aus.
Mit steigendem K wird es immer unwahrscheinlicher, dass wir einen
Block der Länge K haben.
Also stellen Sie sich vor, wenn Sie würfeln und die fünf von den sechs
Seiten sind weiß und eine Seite ist schwarz, die Wahrscheinlichkeit 20
mal hintereinander nur weiß zu würfeln wird dann irgendwann immer
geringer.
Hier ist ein Beispiel von so einer geometrischen Verteilung.
Also das ist der Abstand zwischen zwei schwarzen Bildpunkten, also das
mit 15 Prozent Wahrscheinlichkeit ist der Abstand 0 zum nächsten
schwarzen Bildpunkt oder dann mit 13 Prozent vielleicht 1 und so
weiter und irgendwie immerhin noch mit 2 Prozent ist der Abstand 12.
Das ist tatsächlich das Beispiel, was wir schon hatten am Anfang, was
wir mit Shannon-Fano codiert haben und dann könnten wir diese Abstände
übermitteln, indem wir die zum Beispiel jetzt Huffman oder Shannon
-Fano codieren.
Und so würde man das machen bei Fax-Übertragung oder sowas.
Gut, das ist jetzt das letzte Bild, was ich Ihnen heute zeigen möchte,
wo wir gerade stehen.
Also ich habe schon mal ein bisschen am Anfang darüber geredet, dass
wir eigentlich über Informationen reden und die an einer Quelle
generiert wird und die dort dann erst mal codiert wird, überhaupt
abgespeichert wird und das dann aber natürlich ein interessanter Teil
auch ist, wie diese Information weitergeleitet wird über einen Kanal
und auf dem Kanal muss auch codiert werden.
Zumal dieser Kanal störanfällig sein kann und von einem Kanal, da
können wirklich alles mögliche sein, es kann durch das Internet
geschickt werden oder auch nur von der Tastatur in den Rechner rein.
Und da kümmern wir uns nächstes Mal darum, wie man das macht, wie man
Störanfälligkeit begegnet.
Die Idee ist, Redundanz reinzubringen.
Da ist dann aber auch halt wichtig, wie wir decodieren.
Also ich hatte das Beispiel am Anfang gesagt, wir schicken einfach
jedes Zeichen fünfmal und dann kriegen wir fünf Dinge, die sehen aber
nicht, wir wissen eigentlich, würden wir fünfmal das gleiche Zeichen
erwarten, wir kriegen aber nicht fünfmal das gleiche Zeichen, wir
kriegen irgendwie dreimal ein H und zweimal ein A und jetzt ist die
Frage des Dekodierens, was entscheiden wir jetzt, was die Quelle wohl
gemeint hat.
Und das ist die Kanal-Dekodierung und die Kanal-Codierung und die
Störanfälligkeit und so weiter.
Das ist alles, was wir beim nächsten Mal besprechen, die Quellen
-Dekodierung und den Empfänger, da reden wir gar nicht drüber.
Gut, dann entlasse ich Sie für heute und wünsche Ihnen noch eine
schöne Woche.