Datenkompression: AufgabenLösungen

zurück

Kapitel 3

Lösungen Huffman

1.) Die Entropie kann mit der Formel $H(X)=\sum _{k=1}^{N}P_{k}ld({\frac {1}{P_{k}}})$ berechnet werden. Für $P_{1}=0.71$ und $P_{2}=0.29$ ergeben sich $H(X)=0.71\cdot ld({\frac {1}{0.71}})+0.29\cdot ld({\frac {1}{0.29}})$. 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 $P_{XY}=P_{X}\cdot P_{Y}$.

$P_{00}=0.71\cdot 0.71=0.5041$,

$P_{01}=0.71\cdot 0.29=0.2059$,

$P_{10}=0.29\cdot 0.71=0.2059$ und

$P_{11}=0.29\cdot 0.29=0.0841$. Somit ergibt sich eine Entropie von

$H(X)=0.5041\cdot ld({\frac {1}{0.5041}})+2\cdot 0.2059\cdot ld({\frac {1}{0.2059}})+0.0841\cdot ld({\frac {1}{0.0841}})=1.737$ [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.

$1\cdot 0.5041+2\cdot 0.2059+3\cdot 0.2059+3\cdot 0.0841=1.7859$ [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:

$P_{0'}=0.5041\cdot 1+0.2059\cdot 1+0.2059\cdot 1=0.9159$

$P_{1'}=0.2059\cdot 1+0.2059\cdot 2+0.0841\cdot 3=0.87$

Die relative Wahrscheinlichkeit der neuen Ausgabesymbole ist $P_{0'}=0.51285$ und $P_{1'}=0.48715$.

$H(X')=0.51285\cdot 0.963391+0.48715\cdot 1.037562=0.99925$

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 $P_{111}=0.0841$ auf, wäre sie statistisch unabhängig voneinander, würde sie mit der Wahrscheinlichkeit von $P_{1'1'1'}=0.1156$ auftreten.