Datenkompression: AufgabenLösungen
Aus Wikibooks
Inhaltsverzeichnis |
Kapitel 1
Kapitel 2
Kapitel 3
Lösungen Huffman
1.) Die Entropie kann mit der Formel 
berechnet werden. Für P1 = 0.71 und P2 = 0.29 ergeben sich 
. Es ergibt sich eine Entropie H(X) = 0.869 [Bit/Symbol]. Bei einem Huffmancode mit der Länge 1 für jedes der beiden Symbole ergibt sich eine Redundanz von R(X) = 1 − 0.869 = 0.131 [Bit/Symbol].
Eine Redundanz R(X) > = 0 bedeutet, dass eine größere Datenmenge gespeichert wird, als tatsächlich für Daten mit den angegebenen statistischen Eigenschaften notwendig wäre.
2.) Man kann aus dem Zwei-Symbolcode bspw. ein Vier-Symbolcode erzeugen. Dieser Code ist auf dem ersten Blick nur auf Daten
3.) Für statistisch unabhängige Symbolwahrscheinlichkeiten gilt die Verbundwahrscheinlichkeit bei verbundenen Symbolen 
.
,
,
und
. Somit ergibt sich eine Entropie von
[Bit/2 Symbole] = 0.869 [Bit/Symbol}.
für den Huffmancode mit der Länge 1 für die Symbolfolge 00, die Länge 2 für die Symbolfolge 01, die Länge 3 für die Symbolfolge 10 und die Länge 3 für die Symbolfolge 11.
[Bit/2 Symbole]
0.89295 Bit/Symbol
Durch die Verwendung eines Vier-Symbolcode auf Basis eines Zwei-Symbolcodes kann eine Reduktion der Datenmenge von 1 Bit/Symbol auf 0.89295 Bit/Symbol erreicht werden. Damit reduziert sich die Redundanz von 0.131 auf 0.02395 Bit/Symbol.
Die neuen Wahrscheinlichkeiten für die Symbole 0 und 1 ergeben sich:
Die relative Wahrscheinlichkeit der neuen Ausgabesymbole ist P0' = 0.51285 und P1' = 0.48715.
Die Redundanz beträgt 0.00075 Bit pro Ausgabesymbol.
Die Redundanzen unterscheiden sich aus verschiedenen Gründen:
- Die Redundanz bezieht sich auf die Ausgabesymbole vs. Eingabesymbolen
- Die Ausgabesymbole sind statistisch !NICHT! unabhängig voneinander eine Symbolfolge 111 tritt mit der Wahrscheinlichkeit von P111 = 0.0841 auf, wäre sie statistisch unabhängig voneinander, würde sie mit der Wahrscheinlichkeit von P1'1'1' = 0.1156 auftreten.
