Grundlagen der Informatik
Kapitel 3: Entropie und Quellcodierung

3.1 Modell der Information / Informationsgehalt einer Nachricht

Sehen wir uns eine Nachrichtenquelle an, zum Beispiel einen sechsseitigen Würfel, der zunächst unverfälscht würfelt. Wir können also die Quelle ( X, P ) beschreiben mit X = { 1, 2, 3, 4, 5, 6 }, P = { 1/6, 1/6, 1/6, 1/6, 1/6, 1/6 . Jede Zahl tritt mit einer Wahrscheinlichkeit von 1/6 auf. Wir können jedem Wurfergebnis den gleichen Informationsgehalt abgewinnen. Oder anders: wir wären nicht mehr überascht über eine gewürfelte 6 als wäre eine 1 gefallen, beides war ja gleich wahrscheinlich.

Wir verfälschen nun die Quelle so, dass die 6 mit erhöter Wahrscheinlichkeit auftritt: P = { 0.1, 01, 0.1, 0.1, 0.1, 0.5 }. Der Informationsgehalt der 1, 2, 3, 4 und 5 sind höher als der der 6, da wir ja nicht so überrascht sind über eine 6.

Eine Quelle mit P = { 1, 0, 0, . . ., 0 } wiederum würde bedeuten, das auf jeden Fall eine 1 fällt. Wir können der 1 allerdings keine Information abgewinnen, wir rechnen ja damit, das sie fällt.

Der Informationsgehalt einer Nachricht entspricht also der Überaschung, die wir erfahren, wenn ein bestimmtes Ereignis (eine bestimmte Information) von unserer Quelle ausgeht!

Aus verschiedenen überlegungen heraus, die ich hier nicht näher erläutern werde, kann man eine Funktion gewinnen, mit der sich der Informationsgehalt einer Nachricht x(i) gewinnen lässt: f = - log

In der Quelle ( X, P ) sein p(x) <> 0 die Wahrscheinlichkeit, dass die Nachricht x auftritt. Wir wählen eine Basis a so, dass a = |X|, also der Zeichenvorrat, mit dem wir eine Stelle der Nachricht besetzen können ( bei einem Würfel wäre das z.B. 6, es sind ja 6 Seiten ) mit a > 1. Dann errechnet sich der Informationsgehalt I für die Nachricht x durch:

Die Entropie einer Quelle lässt sich dann als mittlerer Informationsgehalt der Quelle ausdrücken, also der durchschnittliche Grad der Überaschung über alle möglichen Nachrichten aus ( X, P ):

3.2 Eigenschaften der Entropiefunktion

Wir können nun die Entropie einer Quelle dazu verwenden, um die minimale mittlere Codelänge zur Quellcodierung zu berechnen. Dazu muss ein wenig formale mathematische Vorarbeit geleistet werden, die ich mir hier wieder erspare. Am Ende steht der Quellencodierungssatz von Shannon, die besagt, das für jeden eindeutig decodierbaren Code gilt:

Dabei sei n = |Y| >= 2.

Der Quellencodierungssatz lässt nun also Aussagen über die kleinste mittlere Codelänge zu, die man erreichen kann, damit C: X --->Y* \ {} gerade noch eindeutig decodierbar ist. Ist obige Formel nicht erfüllt, so ist der Code nicht eindeutig decodierbar. Ein Umkehrschluss ist jedoch nicht möglich!

Bei einer gegebenen Codierung C kann man nun leicht auch deren Abweichung vom Idealwert errechnen. Diese Abweichung nennen wir Redundanz von C und bezeichnet sozusagen die Anzahl der Stellen, die wir in C zuviel haben (um die unsere Codewörter y zu lang sind):

3.3 Blockcodierung

Unser Ziel ist es, die Redundanz so gering wie möglich zu halten, um möglichst wenig Platz für den Code zu brauchen. Dazu fassen wir Nachrichten zu Blöcken zusammen und Codieren dann jeweils die Blöcke:

Beispiel: X = { a, b}, P = ( 3/4, 1/4 ), Y = { 0, 1}, H(X) = 0.811 C = { 0, 1 }, l(C) = 1
im Block: X` = { aa, ab, ba, bb } P` = ( 9/16, 3/16, 3/16, 1/16 ), C = { 0, 11, 100, 101 } ---> l(C) = 0.85