Zum Inhalt springen

Huffman-Codierung

Huffman-Codierung

Du hast erkannt, dass man beim Morsen in Wirklichkeit ein drittes Symbol benötigt, um die einzelnen Codewörter voneinander zu trennen. Die Funker haben dies mit einer etwas längeren Pause gekennzeichnet.

 So geht es ganz einfach: 0000-00-11-01-0100-01-1011-01

 Drei Basissymbole sind nun überaus unpraktisch. Kann man Codes mit veränderlicher Codelänge auch aus zwei Symbolen aufbauen?

 Die Huffman-Codierung

 Die amerikanischen Mathematiker David A. Huffman und Claude Shannon haben diese Frage untersucht und solche Codes entwickelt. Die Idee ist wiederum nicht schwer zu verstehen: Man muss der Codierung ansehen können, wo Codewörter enden. Also darf kein Codewort so aussehen wie das "Anfangsstück" eines anderen Codewortes. Solche Codes werden "präfixfrei" genannt.

 Beispiel (mit vier Codewörtern)

Hamming-Codierung

 Damit können wir jetzt auch Bilddateien codieren. Dabei müssen wir die Bilddatei aber zunächst untersuchen, damit wir die Codierung so einrichten können, dass sie sich "lohnt".

1. Aufgabe:

Nimm das Bild mit dem Pfeil. Betrachte immer Paare von zwei (aufeinander folgenden) Pixeln und erstelle eine Häufigkeitstabelle.

Aufgabe zur Hamming-Codierung 

Ordne nun die vier Code-Wörter möglichst geschickt den "Pixelpaaren" zu. Wie viele Bits benötigt man, wenn man die Bilddatei so codiert? (Hinweis: Das kannst Du ausrechnen, ohne die Bilddatei zu codieren.)

2. Aufgabe:

Finde zwei verschiedene Beispiele für einen präfixfreien Code mit 5 Codewörtern.

3. Aufgabe:

Was hältst Du von der Idee, mit einem solchen Code eine Bilddatei wie den Pfeil mit Hilfe der folgenden Tabelle zu codieren:

 

4. Aufgabe:

Warum wäre es nicht sinnvoll, das folgende Bild mit der Codierung aus Aufgabe 1 zu codieren? Welche Alternative schlägst Du vor?

5. Aufgabe:

Jemand benutzt eine Huffman-Codierung, um eine Datei komprimiert zu speichern. Auf die komprimierte Datei wendet er die Huffman-Codierung noch einmal an und auf die dabei entstehende Datei dann noch einmal. Kann man vorhersagen, was dabei passiert?

6. Aufgabe:

Eigentlich benötigt jedes Bild seine eigene Huffman-Codetabelle. Wie kann man beim Decodieren wissen, wie die Codetabelle aussah, mit der die Originaldaten codiert wurden?

Die Aufgaben 2. - 6. als Arbeitsblatt (pdf).

Redaktionell verantwortlich: Frank Oppermann