Datenkompression: AufgabenLösungen

zurück

Kapitel 1Bearbeiten

Kapitel 2Bearbeiten

Kapitel 3Bearbeiten

Lösungen Huffman

1.) Die Entropie kann mit der Formel   berechnet werden. Für   und   ergeben sich  . Es ergibt sich eine Entropie   [Bit/Symbol]. Bei einem Huffmancode mit der Länge 1 für jedes der beiden Symbole ergibt sich eine Redundanz von   [Bit/Symbol].

Eine Redundanz   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]

  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   und  .

 

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   auf, wäre sie statistisch unabhängig voneinander, würde sie mit der Wahrscheinlichkeit von   auftreten.

Kapitel 4Bearbeiten

Kapitel 5Bearbeiten

Kapitel 6Bearbeiten

Kapitel 7Bearbeiten