Exercise 2.2Z: Average Code Word Length

Tabellen zur Quellencodierung

Ziel von Datenkomprimierung ist es, die Nachricht einer Quelle mit möglichst wenigen Binärzeichen darzustellen.

Wir betrachten hier eine wertdiskrete Nachrichtenquelle mit dem Symbolvorrat $\rm \{ A, B, C, D\}$ ⇒ Symbolumfang $M = 4$ und den Auftrittswahrscheinlichkeiten

$p_{\rm A} = p_{\rm B} = p_{\rm C} = p_{\rm D} = 1/4$ (Teilaufgabe 1),
$p_{\rm A} = 1/2, \, p_{\rm B} = 1/4, \, p_{\rm C} = p_{\rm D} = 1/8$ (ab Teilaufgabe 2).

Vorausgesetzt wird, dass es zwischen den einzelnen Quellensymbolen keine statistischen Bindungen gibt.

Ein Maß für die Güte eines Komprimierungsverfahrens ist die mittlere Codewortlänge $L_{\rm M}$ mit der Zusatzeinheit „bit/Quellensymbol”.

Vorgegeben sind drei Zuordnungen. Anzumerken ist:

Jeder dieser Binärcodes $\rm C1$, $\rm C2$ und $\rm C3$ ist für eine spezielle Quellenstatistik ausgelegt.
Alle Codes sind präfixfrei und somit ohne weitere Angabe sofort decodierbar.

Hinweis:

Die Aufgabe gehört zum Kapitel Allgemeine Beschreibung der Quellencodierung.

Fragebogen

$\text{C1:}\ \ L_{\rm M} \ = \ $

$\ \rm bit/Quellensymbol$

$\text{C2:}\ \ L_{\rm M} \ = \ $

$\ \rm bit/Quellensymbol$

$\text{C3:}\ \ L_{\rm M} \ = \ $

$\ \rm bit/Quellensymbol$

$\text{C1:}\ \ L_{\rm M} \ = \ $

$\ \rm bit/Quellensymbol$

$\text{C2:}\ \ L_{\rm M} \ = \ $

$\ \rm bit/Quellensymbol$

$\text{C3:}\ \ L_{\rm M} \ = \ $

$\ \rm bit/Quellensymbol$

	Kein Codewort ist der Beginn eines anderen Codewortes.
	Alle Codeworte haben gleiche Länge.

	der Code $\rm C1$,
	der Code $\rm C2$.

	$\rm AACDBACABADAAA$ ...
	$\rm ACBCCCACAACCD$ ...

Musterlösung

Solution

(1) Die mittlere Codewortlänge ergibt sich allgemein zu

$$L_{\rm M} = p_{\rm A} \cdot L_{\rm A} + p_{\rm B} \cdot L_{\rm B}+ p_{\rm C} \cdot L_{\rm C} + p_{\rm D} \cdot L_{\rm D} \hspace{0.05cm}.$$

Sind die vier Quellensymbole gleichwahrscheinlich (alle Wahrscheinlichkeiten genau $1/4$), so kann dafür auch geschrieben werden:

$$L_{\rm M} = 1/4 \cdot ( L_{\rm A} + L_{\rm B}+ L_{\rm C} + L_{\rm D}) \hspace{0.05cm}.$$

$\text{Code C1:}$ $L_{\rm M} \hspace{0.15cm}\underline{= 2.00}\ \rm bit/Quellensymbol$,
$\text{Code C2:}$ $L_{\rm M} \hspace{0.15cm}\underline{= 2.25}\ \rm bit/Quellensymbol$
$\text{Code C3:}$ $L_{\rm M} \hspace{0.15cm}\underline{= 2.25}\ \rm bit/Quellensymbol$.

(2) Mit der Codetabelle $\text{C1}$ ergibt sich unabhängig von den Symbolwahrscheinlichkeiten stets die mittlere Codewortlänge $L_{\rm M} \hspace{0.15cm}\underline{= 2}\ \rm bit/Quellensymbol$.

Für die beiden anderen Codes erhält man:

$\text{Code C2:}$ $L_{\rm M} = 1/2 \cdot 1 + 1/4 \cdot 2 + 1/8 \cdot 3 + 1/8 \cdot 3 \hspace{0.15cm}\underline{= 1.75}\ \rm bit/Quellensymbol$,
$\text{Code C3:}$ $L_{\rm M} = 1/2 \cdot 3 + 1/4 \cdot 2 + 1/8 \cdot 1 + 1/8 \cdot 3 \hspace{0.15cm}\underline{= 2.50}\ \rm bit/Quellensymbol$.

Man erkennt aus dem Beispiel das Prinzip:

Wahrscheinliche Symbole werden durch wenige Binärsymbole dargestellt und unwahrscheinliche durch mehr.
Bei gleichwahrscheinlichen Symbolen wählt man am besten auch die Codewortlängen gleich.

(3) Richtig ist Lösungsvorschlag 1:

Der Code $\text{C1}$ mit einheitlicher Länge aller Codeworte ist präfixfrei,
aber auch andere Codes können präfixfrei sein, zum Beispiel die Codes $\text{C2}$ und $\text{C3}$.

(4) Richtig ist Lösungsvorschlag 1:

Bereits aus „00” am Anfang erkennt man, dass der Code $\text{C2}$ hier nicht in Frage kommt, da sonst die Quellensymbolfolge mit „AA” beginnen müsste.
Tatsächlich wurde der Code $\text{C1}$ verwendet.

(5) Richtig ist der Lösungsvorschlag 2:

Der erste Lösungsvorschlag gibt dagegen die Quellensymbolfolge für den Code $\text{C2}$ an, wenn die Codesymbolfolge $\rm 001101111001100100111000$ lauten würde.