Deutsch
Menü

Was ist Mittlere Codewortlänge?

Der mit den Auftrittswahrscheinlichkeiten der Symbole gewichtete Mittelwert der Codewortlängen. Mit der Wahrscheinlichkeit pᵢ des Symbols i und der Länge lᵢ seines Codeworts ist L = Σ pᵢ lᵢ (Bit pro Symbol). Sie wird klein, wenn häufige Symbole kurze Codewörter erhalten, und ist bei einem verlustfreien Code mindestens so groß wie die Entropie. Die Entropie geteilt durch die mittlere Codewortlänge heißt Effizienz der Kodierung. Kodiert man zum Beispiel 4 Symbole mit den Wahrscheinlichkeiten 0,4; 0,3; 0,2 und 0,1 mit einem Huffman-Code, beträgt die mittlere Codewortlänge 1,9 Bit.

Japanische Bezeichnung: 平均符号長

„Mittlere Codewortlänge“ kommt in 6 Übungsfragen aus 1 Themen vor, z. B. Grundlagen der Informationstheorie und Kodierung.

Fachgebiet: Grundlagen der Informationstheorie und Kodierung

Jetzt üben: Fragen zu Mittlere Codewortlänge

Eine Quelle gibt die Symbole A, B, C und D unabhängig voneinander mit den Wahrscheinlichkeiten 0,4; 0,3; 0,2 und 0,1 aus und wird mit einem Huffman-Code kodiert. Wie groß ist die mittlere Codewortlänge pro Symbol?

  1. AEtwa 1,85 Bit
  2. B1,9 Bit
  3. C2 Bit
Antwort und Erläuterung anzeigen

Antwort: B. 1,9 Bit

Bei der Huffman-Kodierung werden wiederholt die beiden kleinsten Wahrscheinlichkeiten zusammengefasst: 0,1 und 0,2 ergeben 0,3, dann 0,3 und 0,3 ergeben 0,6, und zuletzt werden 0,6 und 0,4 zusammengefasst. Die Codewortlängen sind also 1 für A, 2 für B und 3 Bit für C und D. Die mittlere Codewortlänge beträgt 0,4 × 1 + 0,3 × 2 + 0,2 × 3 + 0,1 × 3 = 1,9 Bit.

Eine Quelle gibt die Symbole A bis E unabhängig voneinander mit den Wahrscheinlichkeiten 0,3; 0,25; 0,2; 0,15 und 0,1 aus und wird mit einem Huffman-Code kodiert. Je nachdem, welche von zwei gleichen Wahrscheinlichkeiten zuerst gewählt wird, können sich die Codewörter ändern, die mittlere Codewortlänge jedoch nicht. Wie groß ist die mittlere Codewortlänge pro Symbol?

  1. A2,25 Bit
  2. B2,4 Bit
  3. C3 Bit
Antwort und Erläuterung anzeigen

Antwort: A. 2,25 Bit

Zuerst werden 0,1 und 0,15 zu 0,25 zusammengefasst, dann 0,2 und 0,25 zu 0,45, dann die übrigen 0,25 und 0,3 zu 0,55 und zuletzt 0,45 und 0,55. Die Codewortlängen sind 2 Bit für A, B und C und 3 Bit für D und E, und die mittlere Codewortlänge beträgt (0,3 + 0,25 + 0,2) × 2 + (0,15 + 0,1) × 3 = 1,5 + 0,75 = 2,25 Bit. Bei einer Quelle mit wenig ungleichmäßigen Wahrscheinlichkeiten ist ein Code mit gleichmäßigen Längen kürzer als gestufte Codewortlängen wie 1, 2, 3, 4, 4.

„Mittlere Codewortlänge“ in den Erläuterungen

Fragen mit „Mittlere Codewortlänge“ (6)

  1. Eine Quelle gibt die Symbole A, B, C und D unabhängig voneinander mit den Wahrscheinlichkeiten 0,4; 0,3; 0,2 und 0,1 aus und wird mit einem Huffman-Code kodiert. Wie groß ist die mittlere Codewortlänge pro Symbol?
  2. Eine Quelle gibt die Symbole A bis E unabhängig voneinander mit den Wahrscheinlichkeiten 0,3; 0,25; 0,2; 0,15 und 0,1 aus und wird mit einem Huffman-Code kodiert. Je nachdem, welche von zwei gleichen Wahrscheinlichkeiten zuerst gewählt wird, können sich die Codewörter ändern, die mittlere Codewortlänge jedoch nicht. Wie groß ist die mittlere Codewortlänge pro Symbol?
  3. Eine Quelle gibt die Symbole A, B und C unabhängig voneinander mit den Wahrscheinlichkeiten 0,6; 0,3 und 0,1 aus; ihre Entropie beträgt etwa 1,30 Bit. Welcher Wert liegt der Effizienz (Entropie ÷ mittlere Codewortlänge) am nächsten, wenn diese Quelle mit einem Huffman-Code kodiert wird?
  4. Eine binäre Quelle gibt unabhängig voneinander 0 mit der Wahrscheinlichkeit 0,8 und 1 mit der Wahrscheinlichkeit 0,2 aus. Je 2 Symbole werden zusammengefasst; die 4 Kombinationen 00, 01, 10 und 11 werden jeweils als ein Symbol betrachtet und mit einem Huffman-Code kodiert. Wie groß ist die mittlere Codewortlänge pro ursprünglichem Symbol?
  5. Welche Aussage über Codes variabler Länge im Vergleich zu Codes fester Länge ist richtig?
  6. Welche Aussage über den Zusammenhang zwischen verlustfreier Kompression und der Entropie einer Quelle ist richtig?

Verwandte Begriffe

Huffman-Kodierung Informationsentropie Präfixcode Verlustfreie Kompression Binärer symmetrischer Kanal Hamming-Abstand Hamming-Code Informationsgehalt Kraft-Ungleichung Lauflängenkodierung

Zur Glossarübersicht