<p>Betrachten Sie folgende Nachricht:</p> <p>die puppen puppen mit kleinen puppen,<br> die kleinen puppen puppen mit winzigen puppen,<br> die winzigen puppen puppen mit pueppchen,<br> die pueppchen puppen mit kleinen pueppchen,<br> die kleinen pueppchen puppen mit winzigen pueppchen,<br> die winzigen pueppchen puppen,<br> keiner puppt mit ihr.</p>

(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)<br><br> (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)<br><br> (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)<br><br>

Approach

Länge (in Zeichen): 276<br> Größe (in Bit): 276 * 7 = 1932<br> Anzahl verschiedener Zeichen: 20<br> Mindestwortlänge für (binäre) Codierung:<br> 2^n >= 20 n >= ln(20)/ln(2)<br> n >= 4.322 <br> n = 5<br> Länge der gesamten Botschaft (in Bit): 275 * 5 = 1380<br> Länge der gesamten Huffman-kodierten Botschaft (in Bit): 1281<br> <br> 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]; } <br><br> Entropie der Nachricht:<br> 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)]<br> 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)]<br> H(X) = -[-3.60395]<br> H(X) = 3.60395<br> <br>

<table> <caption>Vergleich (in Bit/Zeichen)</caption> <tr> <td>ASCII</td><td>7</td> </tr> <tr> <td>Feste Wortlänge</td><td>7</td> </tr> <tr> <td>Huffman</td><td>1281/276 = 4.6413</td> </tr> </table>

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


  • 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