Der Bildungsserver Berlin-Brandenburg ist ein Service des Landesinstituts für Schule und Medien Berlin-Brandenburg
im Auftrag der Senatsverwaltung für Bildung, Jugend und Wissenschaft
und des Ministeriums für Bildung,
Jugend und Sport Land Brandenburg
Partner:
und die Bildungsserver der Länder
Unterricht
Informatik
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)
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.
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.)
weitere Aufgaben: Arbeitsblatt 5 (pdf, 53 kB)
Redaktionell verantwortlich: Ralf Punkenburg, LISUM
