Betrachten Sie folgende Nachricht:

die puppen puppen mit kleinen puppen,
die kleinen puppen puppen mit winzigen puppen,
die winzigen puppen puppen mit pueppchen,
die pueppchen puppen mit kleinen pueppchen,
die kleinen pueppchen puppen mit winzigen pueppchen,
die winzigen pueppchen puppen,
keiner puppt mit ihr.

(a) Wie lang (in Bits) ist die kodierte Botschaft im ASCII-Code (Zeilenumbruch gilt als 1 Zeichen)? Wie lang wäre die kürzeste mögliche Kodierung der Nachricht (in Bits) bei Codewörtern konstanter Länge? (3 Punkte)

(b) Entwerfen Sie eine effiziente Huffman-Kodierung für die Nachricht! Erstellen Sie einen korrekten Codebaum und ermitteln Sie die Länge (in Bits) der so kodierten Nachricht! Die kodierte Nachricht müssen Sie nicht explizit angeben. (6 Punkte)

(c) Berechnen Sie die Entropie der Nachricht und vergleichen Sie diese mit dem mittleren Speicherplatzbedarf pro Zeichen bei den Kodierungen aus den Aufgabenteilen a) und b)! (3 Punkte)

Approach

Länge (in Zeichen): 276
Größe (in Bit): 276 * 7 = 1932
Anzahl verschiedener Zeichen: 20
Mindestwortlänge für (binäre) Codierung:
2^n >= 20 n >= ln(20)/ln(2)
n >= 4.322
n = 5
Länge der gesamten Botschaft (in Bit): 275 * 5 = 1380
Länge der gesamten Huffman-kodierten Botschaft (in Bit): 1281

digraph G { edge [label=0]; graph [ranksep=0]; P [shape=record, label="{{P|54}|00}"]; Y [shape=record, label="{{\n|6}|01000}"]; DOT [shape=record, label="{{.|1}|0100100}"]; R [shape=record, label="{{R|2}|0100101}"]; G [shape=record, label="{{G|4}|010011}"]; H [shape=record, label="{{H|7}|01010}"]; T [shape=record, label="{{T|7}|01011}"]; SPACE [shape=record, label="{{' '|33}|011}"]; N [shape=record, label="{{N|34}|100}"]; L [shape=record, label="{{L|4}|101000}"]; W [shape=record, label="{{W|4}|101001}"]; Z [shape=record, label="{{Z|4}|101010}"]; K [shape=record, label="{{K|5}|101011}"]; U [shape=record, label="{{U|18}|1011}"]; E [shape=record, label="{{E|43}|110}"]; M [shape=record, label="{{M|6}|111000}"]; COMA [shape=record, label="{{,|6}|111001}"]; C [shape=record, label="{{C|6}|111010}"]; D [shape=record, label="{{D|6}|111011}"]; CD [label=12]; I [shape=record, label="{{I|26}|1111}"]; 276 -> 114 -> P; 60 -> 27 -> 13 -> Y; 7 -> 3 -> DOT; 14 -> H; 162 -> 69 -> N; 35 -> 17 -> 8 -> L; 9 -> Z; 93 -> E; 50 -> 24 -> 12 -> M; CD -> C;3 -> R [label=1]; 13 -> 7 -> G [label=1]; 27 -> 14 -> T [label=1]; 114 -> 60 -> SPACE [label=1]; 8 -> W [label=1]; 17 -> 9 -> K [label=1]; 69 -> 35 -> U [label=1]; 12 -> COMA [label=1]; 24 -> CD -> D [label=1]; 276 -> 162 -> 93 -> 50 -> I [label=1]; }

Entropie der Nachricht:
H(X) = -[(0.12lb0.12) + (0.022lb0.022)``+ (0.004lb0.004) + (0.022lb0.022)``+ (0.022lb0.022) + (0.156lb0.156)``+ (0.014lb0.014) + (0.025lb0.025)``+ (0.094lb0.094) + (0.018lb0.018)``+ (0.014lb0.014) + (0.022lb0.022)``+ (0.123lb0.123) + (0.196lb0.196)``+ (0.007lb0.007) + (0.025lb0.025)``+ (0.065lb0.065) + (0.014lb0.014)``+ (0.022lb0.022) + (0.014lb0.014)]
H(X) = -[(-0.366) + (-0.12) + (-0.029) + (-0.12) + (-0.12)``+ (-0.418) + (-0.089) + (-0.134) + (-0.321) + (-0.105) + (-0.089)``+ (-0.12) + (-0.372) + (-0.46) + (-0.052) + (-0.134) + (-0.257)``+ (-0.089) + (-0.12) + (-0.089)]
H(X) = -[-3.60395]
H(X) = 3.60395

Vergleich (in Bit/Zeichen)
ASCII7
Feste Wortlänge7
Huffman`1281/276` = 4.6413

Die Huffmann-Kodierung ist die effizienteste Kodierung der drei, aber immer noch größer als die Entropie.


  • URL:
  • Language:
  • Subjects: internet-technologies
  • Type: Calculate
  • Duration: 40min
  • Credits: 12
  • Difficulty: 0.7
  • Tags: HPI Internet- und WWW-Technologien
  • Note:
  • Created By: adius
  • Created At:
    2013-05-01 10:58:30 UTC
  • Last Modified:
    2013-05-01 10:58:30 UTC