Exercise 2.2Z: Average Code Word Length

• Return to book

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 {A, B, C, D}   ⇒   Symbolumfang M = 4 und den Auftrittswahrscheinlichkeiten

• p_A = p_B = p_C = p_D = 1/4 (Teilaufgabe 1),

• p_A = 1/2, p_B = 1/4, p_C = p_D = 1/8 (ab Teilaufgabe 2).

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

Ein Maß für die Güte eines Komprimierungsverfahrens ist die mittlere Codewortlänge L_M mit der Zusatzeinheit „bit/Quellensymbol”. Vorgegeben sind drei Zuordnungen. Anzumerken ist:

• Jeder dieser Binärcodes C1, C2 und C3 ist für eine spezielle Quellenstatistik ausgelegt.

• Alle codes sind präfixfrei und somit ohne weitere Angabe sofort decodierbar.

Hinweis: Die Aufgabe bezieht sich auf das Kapitel 2.1.

Fragebogen

1

Bestimmen Sie die mittlere Codewortlänge für p_A = p_B = p_C = p_D = 1/4.

$C1:\ \ L_M$ = $bit/Quellensymbol$

$C2:\ \ L_M$ = $bit/Quellensymbol$

$C3:\ \ L_M$ = $bit/Quellensymbol$

2

Welche Werte ergeben sich für p_A = 1/2, p_B = 1/4, p_C = p_D = 1/8.

$C1:\ \ L_M$ = $bit/Quellensymbol$

$C2:\ \ L_M$ = $bit/Quellensymbol$

$C3:\ \ L_M$ = $bit/Quellensymbol$

3

Woran erkennt man präfixfreie Codes?

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

4

Für die spezielle Quellenfolge ADBDCBCBADCA ergibt sich die Codefolge 001101111001100100111000. Welcher Code wurde verwendet?

	der Code C1,
	der Code C2.

5

Nach Codierung mit C3 erhält man 001101111001100100111000. Wie lautet die zugehörige Quellensymbolfolge?

	AACDBACABADAAA ....
	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}.$$

• Code C1:    L_M = 2.00 bit/Quellensymbol,

• Code C2:    L_M = 2.25 bit/Quellensymbol,

• Code C3:    L_M = 2.25 bit/Quellensymbol.

2.  Mit der Codetabelle C1 ergibt sich unabhängig von den Symbolwahrscheinlichkeiten stets die mittlere Codewortlänge L_M = 2 bit/Quellensymbol. Für die beiden anderen Codes erhält man

• Code C2:    L_M = 1/2 · 1 + 1/4 · 2 + 1/8 · 3 + 1/8 · 3 = 1.75 bit/Quellensymbol,

• Code C3:    L_M = 1/2 · 3 + 1/4 · 2 + 1/8 · 1 + 1/8 · 3 = 2.50 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. Ein Code mit einheitlicher Länge aller Codeworte ist zwar präfixfrei, aber auch andere Codes können präfixfrei sein, zum Beispiel die Codes C2 und C3.

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

5.  Richtig ist der Lösungsvorschlag 2. Der erste Lösungsvorschlag gibt die Quellensymbolfolge für den Code C2 an, wenn die Codesymbolfolge 001101111001100100111000 lauten würde.