Exercise 2.5: Residual Redundancy with LZW Coding

Restredundanz r(N) und Näherung r ′(N) dreier Quellen

Wir gehen hier von einer binären Eingangsfolge der Länge N aus und betrachten drei verschiedene binäre Nachrichtenquellen BQ1, BQ2 und BQ3:

BQ1: mit den Symbolwahrscheinlichkeiten p_A = 0.89, p_B = 0.11, also unterschiedlich
⇒ Entropie H = 0.5 bit/Quellensymbol
⇒ Quelle ist redundand.

BQ2: p_A = p_B = 0.5 (gleichwahrscheinlich)
⇒ Entropie H = 1 bit/Quellensymbol
⇒ Quelle ist redundanzfrei.

BQ3: Hier gibt es keine konkreten Angaben zur Statistik. In der Teilaufgabe (f) sollen Sie die Entropie H dieser Quelle abschätzen.

Für diese drei Quellen wurden per Simulation die jeweilige Restredundanz r(N) ermittelt, die nach der Lempel–Ziv–Welch–Codierung in der Binärfolge verbleibt. Die Ergebnisse sind in der jeweils ersten Spalte obiger Tabelle für die Quellen

BQ1 (gelbe Hinterlegung),

BQ2 (grüne Hinterlegung),

BQ3 (blaue Hinterlegung)

eingetragen, wobei wir uns bei der Simulation auf Folgenlängen N ≤ 50000 beschränkt haben.

Die relative Redundanz der Ausgangsfolge – vereinfachend Restredundanz genannt – kann aus

der Länge N der Eingangsfolge,

der Länge L(N) der Ausgangsfolge und

der Quellenentropie H

in folgender Weise berechnet werden:

$$r(N) = \frac{L(N) - N \cdot H}{L(N)}= 1 - \frac{ N \cdot H}{L(N)}\hspace{0.05cm}.$$

Hierbei ist berücksichtigt, dass bei perfekter Quellencodierung die Länge der Ausgangsfolge bis auf den Wert L_min = N · H herabgesenkt werden könnte. Bei nichtperfekter Quellencodierung gibt L(N) – N · H die verbleibende Redundanz (mit der Pseudo–Einheit „bit”) an. Nach Division durch L(N) erhält man die relative Redundanz r(N) mit dem Wertebereich zwischen 0 und 1; r(N) sollte möglichst klein sein.

Eine zweite Kenngröße zur Effizienzmessung der LZW–Codierung ist der Komprimierungsfaktor

$$K(N) = {L(N) }/{N} \hspace{0.05cm},$$

der ebenfalls klein sein sollte. Hinweis: K(N) und r(N) hängen deterministisch zusammen.

Im Theorieteil wurde gezeigt, dass die Restredundanz r(N) durch die Funktion

$$r'(N) ={A}/{{\rm lg}\hspace{0.1cm}(N)} \hspace{0.5cm}{\rm mit}\hspace{0.5cm} A = 4 \cdot {r(N = 10000)} \hspace{0.05cm}.$$

oft gut angenähert wird. Die Näherung r′(N) ist für BQ1 in der zweiten Spalte obiger Tabelle angegeben. In den Teilaufgaben (d) und (e) sollen Sie die Approximation für die Quellen BQ2 und BQ3 vornehmen.

Hinweise:

Die Aufgabe gehört zum Kapitel Komprimierung nach Lempel, Ziv und Welch.
Insbesondere wird Bezug genommen auf die Seiten LZ77 – die Grundform der Lempel-Ziv-Algorithmen, Lempel-Ziv-Codierung mit variabler Indexbitlänge sowie Decodierung des LZW-Agorithmus.
Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.
Die Aufgabe 2.3 sowie die Zusatzaufgabe 2.3Z behandeln andere LZ-Verfahren in ähnlicher Weise.

Hinweis: Die Aufgabe bezieht sich auf Seite 7 und Seite 8 von Kapitel 2.2.

Fragebogen

$BQ1:\ A$ =

$BQ1:\ N_b$ =

$\cdot 10^{21}$

$BQ1:\ N_c$ =

$\cdot 10^{6}$

$BQ2:\ r'(N = 50000)$ =

$r'(N = 10^6)$ =

$r'(N = 10^12)$ =

$BQ2:\ r'(N = 50000)$ =

$r'(N = 10^6)$ =

$r'(N = 10^12)$ =

	H = 1.00 bit/Quellensymbol,
	H = 0.75 bit/Quellensymbol,
	H = 0.50 bit/Quellensymbol,
	H = 0.25 bit/Quellensymbol.

Musterlösung

Solution

1. Die Näherung r'(N) stimmt definitionsgemäß für die Eingangsfolgenlänge N = 10000 mit der per Simulation ermittelten Restredundanz r(N) = 0.265 exakt überein. Damit ist

$$A = 4 \cdot r(N = 10000) =4 \cdot {0.265} \hspace{0.15cm}\underline{= 1.06} \hspace{0.05cm}. $$

2. Aus der Beziehung A/lg (N) ≤ 0.05 ⇒ A/lg (N_b) = 0.05 folgt:

$${{\rm lg}\hspace{0.1cm}N_{\rm b}} = \frac{A}{0.05} = 21.2 \hspace{0.3cm}\Rightarrow\hspace{0.3cm} N_{\rm b} = 10^{21.2} \hspace{0.15cm}\underline{= 1.58 \cdot 10^{21}} \hspace{0.05cm}.$$

3. Allgemein gilt:

$$r(N) = 1 - \frac{H}{K(N)} \hspace{0.05cm}. $$

BQ1 hat die Entropie H = 0.5 bit/Symbol. Daraus folgt wegen r(N) ≈ r'(N) für K(N_c) = 0.6:

$$r(N_{\rm c}) = 1 - \frac{0.5}{0.6} = 0.167 \hspace{0.1cm}\Rightarrow\hspace{0.1cm} {\rm lg}\hspace{0.1cm}N_{\rm c} = \frac{A}{0.167} = 6.36 \hspace{0.1cm}\Rightarrow\hspace{0.1cm} N_{\rm c} = 10^{6.36} \hspace{0.15cm}\underline{= 2.29 \cdot 10^{6}} \hspace{0.05cm}.$$

4. Für N = 10000 gilt r′(N) = r(N) = 0.190:

$$\frac{A}{{\rm lg}\hspace{0.1cm}10000} = 0.19 \hspace{0.3cm}\Rightarrow\hspace{0.3cm} A = 0.19 \cdot 4 = 0.76 \hspace{0.05cm}. $$

Die Ergebnisse sind in nebenstehender Tabelle zusammengefasst. Man erkennt die sehr gute Übereinstimmung zwischen r(N) und r′(N). Die gesuchten Zahlenwerte sind in der Tabelle rot markiert.

Für den Komprimierungsfaktor gilt (der Apostroph weist darauf hin, dass von der Näherung r′(N) ausgegangen wurde):

$$K'(N) = \frac{1}{1 - r'(N)}\hspace{0.05cm}.$$

Damit gilt für die Länge des LZW–Ausgabestrings:

$$L'(N) = K'(N) \cdot N \hspace{0.05cm}.$$

5. Nach ähnlicher Vorgehensweise wie in der Teilaufgabe d) erhält man für die Binärquelle BQ3 den Anpassungsparameter A = 1.36 und daraus die Ergebnisse gemäß der blau hinterlegten Tabelle.

Hinweis: Die letzte Spalte dieser Tabelle ist nur bei Kenntnis der Teilaufgabe (f) verständlich. Dort wird gezeigt, dass die Quelle BQ3 die Entropie H = 0.25 bit/Quellensymbol besitzt.

In diesem Fall gilt für den Komprimierungsfaktor:

$$K'(N) = \frac{H}{1 - r'(N)} = \frac{0.25}{1 - r'(N)} \hspace{0.05cm}.$$

Für N = 10¹² weicht also der Komprimierungsfaktor (0.282) noch deutlich von der Entropie (0.25) ab, die für N → ∞ erreicht werden kann (Quellencodierungstheorem).

6. Die einzelnen Näherungen r′(N) unterscheiden sich nur durch den Parameter A. Dabei haben wir festgestellt:

Quelle BQ2 (H = 1.00): A = 0.76,

Quelle BQ1 (H = 0.50): A = 1.06,

Quelle BQ3 (H unbekannt): A = 1.36.

Je kleiner die Entropie H ist, um so größer ist offensichtlich der Anpassungsfaktor A. Da genau eine Lösung möglich ist, muss H = 0.25 bit/Quellensymbol richtig sein ⇒ Antwort 4.

Tatsächlich wurden bei der Simulation für die Quelle Q3 die Wahrscheinlichkeiten p_A = 0.96, p_B = 0.04 ⇒ H ≈ 0.25 verwendet.