/ Informationstheorie

Huffman min. Codewortlänge

Untere Schranke der Codewortlänge bei festen Binärcodes: MinLaenge = ⌈log₂(Symbolanzahl)⌉. Huffman erreicht diesen Wert bei Gleichverteilung.

01 · Eingabe

Huffman min. Codewortlänge berechnen

Untere Schranke der Codewortlänge bei festen Binärcodes: MinLaenge = ⌈log₂(Symbolanzahl)⌉. Huffman erreicht diesen Wert bei Gleichverteilung.

Lösen für

MinLaenge = ⌈log₂(Symbolanzahl)⌉

Symbolanzahl Symbolanzahl

Worum geht es?

Die minimale Codewortlänge eines Festlängen-Binärcodes für n verschiedene Symbole ist ⌈log₂(n)⌉. Kürzer geht es nicht — bei einem Bit weniger wären nicht genug Codeworte verfügbar.

Bei Gleichverteilung der Symbole erreicht ein Huffman-Code genau diese Länge. Bei schiefen Verteilungen kann er im Mittel sogar kürzer werden, weil häufige Symbole kürzere Codes bekommen.

Die Formel

Formel Min. Codewortlänge

MinLänge = ⌈log₂(Symbolanzahl)⌉

Umstellung:
    Symbolanzahl = 2^MinLänge

Die Variablen

Symbol	Bedeutung	Einheit	Erklärung
Symbolanzahl	Symbolanzahl	—	Anzahl verschiedener zu kodierender Symbole.
MinLaenge	Min. Codewortlänge	Bit	Minimale Codewortlänge bei Festlängencode.

Minimal-Beispiel

Acht Symbole:

Rechnung 8 Symbole

MinLänge = ⌈log₂(8)⌉
         = 3 Bit

Praxis-Beispiele

Beispiel 1 — ASCII-Buchstaben

26 Großbuchstaben:

Rechnung Alphabet

MinLänge = ⌈log₂(26)⌉
         = ⌈4,7⌉
         = 5 Bit

Beispiel 2 — Dezimalziffern

10 Ziffern:

Rechnung Dezimalziffer

MinLänge = ⌈log₂(10)⌉
         = ⌈3,32⌉
         = 4 Bit

Beispiel 3 — Anzahl Symbole aus Codelänge

Bei einer Codewortlänge von 7 Bit:

Rechnung Symbolraum

Symbolanzahl = 2^7
             = 128