Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

So, guten Morgen zur Informationstheorie. Ja, ich gehe nochmal zurück, wo wir momentan stehen,

im Kapitel 3 Quellenkodierung. Und wir haben uns beschäftigt mit Codes mit variable Wortlänge.

Und die wollen wir kommafrei dekodierbar haben. In einem Code mit variable Wortlänge ist ja

eigentlich schwierig zu wissen, wo ein Kotwort aufhört, wo geht das nächste an. Wenn man dazu

kein Trennzeichen, kein Komma verwenden will, dann kann man das mit sogenannten Präfix-freien

Codes machen, wo kein kürzeres Kotwort am Anfang eines Längeren als Vorsilbe, als Präfix

Präfix drin steckt. Weil dann kann man immer schauen von Anfang bis zum Ende und dann

hat man das Codewort und dann geht das nächste. Und das kann man sich in einem Baum anschaulichen.

Also im Binären geht man zum Beispiel für eine Null nach oben, für eine Eins nach unten

und dann darf in einem präfixfreien Codewort nur den Endknoten im Baum ein Codewort zugeordnet

werden, nicht aber den Zwischenknoten, weil bei einem Zwischenknoten weiß ich nicht,

ist es jetzt aus, ist das Codewort fertig oder geht es weiter.

Wenn bei einem Endknoten weiß ich 100% es ist aus und ich gehe zurück zur Wurzel.

Einfach schon?

So, das ist also der Trick von den präfixfreien Codes.

Wir haben dann einen Satz bewiesen, das Theorem von Macmillan, nein, Entschuldigung, die

kraftige Ungleichung zunächst, Macmillan kommt gleich.

Der besagt, wenn ich einen Code habe mit K verschiedenen Codewörtern, Groß K, das ist

die Mächtigkeit des Codes, also die Menge der Codewörter ist der Code, über das haben

wir diskutiert, dass das ein bisschen anders ist als in der Umgangssprache.

Und diese Codewörter haben unterschiedliche Längen.

Das erste Codewörter hat die Länge N1, die zweite hat die Länge N2, also wie viele Symbole,

dass das Codewörter halt lang ist.

Damit es einen präfixfreien Code geben kann, muss diese Ungleichung existieren.

Da sehen Sie, wenn die Codewörter länger werden, dann tut sich die Ungleichung leichter,

weil eine Zahl hoch Minus was Größeres, was Kleineres ist.

Verstanden?

Und wenn die Codewörter zu kurz sind, dann geht es nicht mehr.

Aber diese Gleichung ist nicht nur notwendig, sie ist auch hinreichend.

Wenn diese Ungleichung erfüllt ist, dann gibt es einen präfixfreien Code, der eindeutig

dekodierbar ist.

Also dieser Satz besteht aus zwei Sätzen, nämlich dann und nur dann.

Und wie kann man das beweisen?

Die Beweistechnik ist, dass man immer vom ursprünglich vollständigen Baum ausgeht für

die maximale Tiefe und schaut, wie viele Knoten aus dem ursprünglich vollständigen Baum gehen,

verloren, wenn man einen Knoten mit einem Codewort besetzt.

Wenn ich sage, das ist ein Codewort, also nur die Null, dann darf ich die alle anderen nicht

mehr verwenden, weil nur Endknoten dürfen Codewörter repräsentieren, sonst sind wir

nicht präfixfrei.

Und dann zähle ich einfach ab, wie viele Knoten von dem ursprünglich vollständigen Baum verbrauche

ich.

Und solange ich nicht genügend freie Knoten habe, geht es halt nicht.

Und wenn ich noch welche habe, geht es.

Und das ist also zweiseitig, man kann auch, der existiert dann, der hinreichend Beweis,

der ist auch ein Konstruktionsverfahren, nämlich wir nehmen einen ursprünglich vollständigen

Baum, so wie es hier ist, und setzen einfach die Codewörter rein, also ist es vorausgesetzt,

die Kraftschirmgleichung existiert, und wir setzen die einfach rein und es muss immer

ein noch freier Knoten auf der richtigen Tiefe, also anderer Codewortlänge existieren, wenn

die Kraftschirmgleichung erfüllt ist.