Grundlagen der Informatik
Kapitel 1: Grundbegriffe

1.1 Grundbegriffe

Die Codierung- und Informationstheorie beschreibt Algorithmen, mit derern Hilfe es uns gelingt, Informationen über eine Datenleitung oder in einen Datenspeicher zu übertrragen. Dabei werden die Daten in möglichst effienziente Einheiten verpackt. Effizient heißt hier: So kompakt wie möglich und gleichzeitig sicher. Jede Datenübertragung erzeugt zunächst Fehler in der übertragenen Information. Diese soll der Algorithmus erkennen und korrigieren können. Darüberhinaus sollen Daten so kurz wie möglich codiert werden, um nicht unnötig Kapazitäten zu verschwenden.

Das Modell der Codierungstheorie sieht dabei wie folgt aus: Am Anfang steht eine Nachrichtenquelle, die verschiedene Daten aussendet. Dabei tritt jedes Datum mit einer gewissen Wahrscheinlichkeit p <= 1 auf. Ein Beispiel wäre ein Würfel, der mit einer Wahrscheinlichkeit von 1/6 auf eine bestimmte Seite fällt.

Der Quelle folgt der Quellcodierer, der jedem Datum ein Codewort so zuordnet, das die durchschnittliche Codewortlänge minimal ist. Nach dem Quellcodierer folgt der Kanalcodierer, der jedes Codewort so umwandelt, dass auch nach einer fehlerhaften Datenübertragung noch die Originalnachricht restauriert oder zumindest ein Fehler in der Übertragung erkannt werden kann.

Nach dem Kanalcodierer geht die Nachricht in den Kanal, der wie gesagt eine Störquelle darstellt. Nach dem Kanal folgt analog zuerst der Kanaldecodierer, der Quelldecodierer und schließlich die Nachrichtensenke, also der Empfängrer der Nachricht.

Grundlagen der Informatik
Kapitel 2: Quellcodierung

2.1 Grundlegende Definitionen

Im folgenden sei X ein Alphabet ( zum Beispiel die Menge der Buchstaben {a, b, c, d, . . . , x, y, z} oder binär {0, 1} ) und x(i) sei ein Symbol aus diesem Alphabet. Eine Nachricht x setzt sich dann zusammen aus verschiedenen Symbolen x(i) mit i = 1, ...,n .Lies: Die Nachricht (oder das Wort) x besteht aus n Symbolen aus dem Alphabet x, wobei x(i) das Symbol an der Stelle i bezeichnet. Die Menge aller Nachrichten, die aus X entnommen werden, bezeichnen wir mit X*. Dies müssen nicht zwangsweise ALLE möglichen Nachrichten aus X sein, sondern nur eine Teilmenge: X* = { x | x sei ein Wort über X }.

Xn sei dann die Menge der Nachrichten aus X*, deren Länge genau n beträgt. Xn = { x aus X* | |x| = n }. Dabei ist eben der Betrag von x ( |x| ) die Länge des Wortes x.

Wir betrachten nun eine Nachrichtenquelle ( X, P ). P sei dabei die Menge der Wahrscheinlichkeiten, mit der die Quelle ein Zeichen aus dem Alphabet sendet. Dabei wird jedem x(i) genau eine Wahrscheinlichkeit p(i) zugeordnet. Die Summe aller p(i) für i = 1, . . . , n ist dabei stehts 1, will heißen, dass die Quelle, wenn Sie ein Zeichen sendet, auf jeden Fall eines senden muss, das auch in ihrem Alphabet vorliegt. ( X, P ) entspricht einem Stichprobenraum.

Bei der Quellcodierung muss nun jeder Nachricht ein Codewort zugeordnet werden. Dazu benötigen wir ein zweites Alphabet Y, das solche Symbole enthält, die wir auch durch den Kanal schicken können. In der digitalen Signalverarbeitung entspricht Y = { 0, 1 }. Die Codierung selbst ist nun eine injektive Abblidung, die jeder Nachricht genau ein Codewort eindeutig zuordnet. Die Abbildung heiße C: X ---> Y*\{}. Das leere Element wird also aus der Menge der Codewörter entfernt. y(i) = C( x(i) ).

Beispiel: ( X, P ) sei eine Quelle ( {a, b, c, d }, ( 0.9, 0.02, 0.05, 0.03 ) ). Y = { 0, 1 }. Eine Codierungsmöglichkeit wäre dann zum Beispiel: a ---> 0; b ---> 110; c ---> 111; d ---> 101; oder aber: a ---> 00; b ---> 01; c ---> 10; d ---> 11;

Forderung: Bei der Codierung muss für die Codewörter eine minimale mittlere Codewortlänge |x(i)| * p(i) entstehen. Ein solcher Code heißt dann effizient! Der erste Code im oberen Beispiel wäre mit 0.9 * 1 + 0.02 * 3 + 0.05 * 3 + 0.03 * 3 = 1.2 effizienter als der untere. Die mittlere Codewortlänge l(C) lässt sich errechnen:

mit ( X = { x1, . . . , xn}, P = (p1, . . . pn ) )

Beispiel: X = { a, b, c, d }, Y = { 0, 1}. Wir codieren a---> 0; b ---> 01; c ---> 11; d ---> 00; Ersichtlich werden die Folgen dc (0011) und aac (0011) auf das selbe Codewort abgebildet. Die ursprüngliche Nachricht kann nicht zurückgewonnen werden. Wird fordern also einen eindeutig decodierbaren Code!

Eindeutig decodierbare Codes

Ein Code ist eindeutig decodierbar, wenn kein Codewort c(i) Präfix eines zweiten Codewortes c(j) ist für c(i) <> c(j). Im obigen Beispiel wäre c(1) Präfix von c(2) und c(4). Eine Decodierung war nicht möglich. Einen solchen präfixfreien Code nennen wir Präfixcode. ....... qed

Hinweis: Um einen Präfixcode zu gewinnen, bendienen wir uns eines Codebaums. Die Wurzel ist das leere Element. Von der Wurzel aus gehen wir nach links, indem wir dem Vorgänger eine 0 anhängen und nach rechts, indem wir eine 1 anhängen. Dabei betrachten wir jeweils die Enden des Codebaumes als Blätter und den Vorgänger zweier Elemente wieder als deren Wurzel. Wenn wir jetzt ausschließlich solche Elemente als Codewörter betrachten, die an den Blättern hängen, haben wir einen Präfixcode erzeugt.

2.2 Die Ungleichungen von Kraft und McMillan

Wir betrachten ein Alphabet Y und dessen Elementzahl |Y| = n. l(1), . . . , l(n) seinen die Längen der Codewörter 1 bis n. Wenn dafür die Gleichung gilt, so kann man sagen, es existiert ein Präfixcode C über Y mit den geforderten Längen. (Ungleichung von Kraft )

Die Ungleichung von McMillan dagegen sagt aus, dass wenn erfüllt ist, auch ein eindeutig decodierbarer Code existiert. Es lässt sich aber nicht umgekehrt schließen, das der Code eindeutig sein muss. Es heißt nur: Wenn diese Gleichung nicht gilt, ist der Code nicht eindeutig decodierbar!

Folgerung: Zu jedem eindeutig decodierbaren Code gibt es einen Präfixcode mit gleicher Codewortlänge.

2.3 Huffman - Codes

Huffman-Codes sind kompakte Codes, die nach dem Huffman-Verfahren gewonnen wurden. Dabei wird nach folgendem Algorithmus verfahren (wir betrachten Y={0,1}):

1. Schreibe alle Auftretenten Wahrscheinlichkeiten der Nachrichten x in absteigender Reihenfolge auf
2. Fasse die beiden Wahrscheinlichkeiten, die am Ende der Reihe stehen, zusammen (Addition!)
3. Soritiere diese Summe wieder in aufsteigender Reihenfolge in die Liste ein und merke den Weg, durch den die Summe gebildet wurde zur späteren Rückverfolgung
4. Wiederhole Schritt 1 - 3 solange, bis die Reihe nur noch aus zwei Werten besteht
5. Ordne jedem der beiden Werte beliebig einem 0, dem anderen 1 zu
6. Gehe in die vorherige Liste (mit 3 Werten) und ordne dem Wert, der nicht zusammengefasst wurde, die Zahl zu, die schon in der letzten Liste steht. Ordne den beiden Summanden ihre Zahl der letzten Liste zu und hänge an diese jeweils beliebig eine 0 und eine 1 an
7. Wiederhole Schritt 5 und 6 solange, bis in der Originalliste jede Wahrscheinlichkeit (jede Nachricht) ein Codewort hat.

Wir haben nun einen Präfixcode erhalten.