Datenkompression: AufgabenLösungen

Aus Wikibooks

zurück

Kapitel 1[Bearbeiten]

Kapitel 2[Bearbeiten]

Kapitel 3[Bearbeiten]

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 4[Bearbeiten]

Kapitel 5[Bearbeiten]

Kapitel 6[Bearbeiten]

Kapitel 7[Bearbeiten]