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
\nGröße (in Bit): 276 * 7 = 1932
\nAnzahl verschiedener Zeichen: 20
\nMindestwortlänge für (binäre) Codierung:
\n2^n >= 20\nn >= ln(20)/ln(2)
\nn >= 4.322
\nn = 5
\nLänge der gesamten Botschaft (in Bit): 275 * 5 = 1380
\nLänge der gesamten Huffman-kodierten Botschaft (in Bit): 1281
\n
\ndigraph G {\n edge [label=0];\n graph [ranksep=0];\n P [shape=record, label="{{P|54}|00}"];\n Y [shape=record, label="{{\\n|6}|01000}"];\n DOT [shape=record, label="{{.|1}|0100100}"];\n R [shape=record, label="{{R|2}|0100101}"];\n G [shape=record, label="{{G|4}|010011}"];\n H [shape=record, label="{{H|7}|01010}"];\n T [shape=record, label="{{T|7}|01011}"];\n SPACE [shape=record, label="{{' '|33}|011}"];\n N [shape=record, label="{{N|34}|100}"];\n L [shape=record, label="{{L|4}|101000}"];\n W [shape=record, label="{{W|4}|101001}"];\n Z [shape=record, label="{{Z|4}|101010}"];\n K [shape=record, label="{{K|5}|101011}"];\n U [shape=record, label="{{U|18}|1011}"];\n E [shape=record, label="{{E|43}|110}"];\n M [shape=record, label="{{M|6}|111000}"];\n COMA [shape=record, label="{{,|6}|111001}"];\n C [shape=record, label="{{C|6}|111010}"];\n D [shape=record, label="{{D|6}|111011}"];\n CD [label=12];\n I [shape=record, label="{{I|26}|1111}"];\n 276 -> 114 -> P;\n 60 -> 27 -> 13 -> Y;\n 7 -> 3 -> DOT;\n 14 -> H;\n 162 -> 69 -> N;\n 35 -> 17 -> 8 -> L;\n 9 -> Z;\n 93 -> E;\n 50 -> 24 -> 12 -> M;\n CD -> C;3 -> R [label=1];\n 13 -> 7 -> G [label=1];\n 27 -> 14 -> T [label=1];\n 114 -> 60 -> SPACE [label=1];\n 8 -> W [label=1];\n 17 -> 9 -> K [label=1];\n 69 -> 35 -> U [label=1];\n 12 -> COMA [label=1];\n 24 -> CD -> D [label=1];\n 276 -> 162 -> 93 -> 50 -> I [label=1];\n}\n

\nEntropie der Nachricht:
\nH(X) = -[(0.12lb0.12) + (0.022lb0.022)``+ (0.004lb0.004) + (0.022lb0.022)``+ (0.022lb0.022) + \t(0.156lb0.156)``+ (0.014lb0.014) + (0.025lb0.025)``+ (0.094lb0.094) + (0.018lb0.018)``+ (0.014lb0.014) + (0.022lb0.022)``+ \t(0.123lb0.123) + (0.196lb0.196)``+ (0.007lb0.007) + \t(0.025lb0.025)``+ (0.065lb0.065) + (0.014lb0.014)``+ (0.022lb0.022) + (0.014lb0.014)]
\nH(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)]
\nH(X) = -[-3.60395]
\nH(X) = 3.60395
\n
\n\n

\n\n\n\n\n\n\n\n\n\n\n
Vergleich (in Bit/Zeichen)
ASCII7
Feste Wortlänge7
Huffman1281/276 = 4.6413
\t\t\n\n

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

\n\n"


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