Aufgaben:Aufgabe 2.12: Run–Length Coding & RLLC

Wir betrachten eine Binärquelle mit dem Symbolvorrat A und B, wobei B allerdings nur sehr selten auftritt.

Ohne Quellencodierung würde man pro Quellensymbol genau ein Bit benötigen, und dementsprechend würde bei einer Quellensymbolfolge der Länge $N$ für die Codebit folge folge ebenfalls $N_\text{Bit} = N$gelten.
Entropiecodierung macht hier ohne weitere Maßnahme (Zusammenfassen mehrerer Symbole zu einem Tupel) wegen der ungünstigen Symbolwahrscheinlichkeiten wenig Sinn.
Abhilfe schafft Run-Length Coding (RLC), das unter dem genannten Link im Theorieteil beschrieben ist. Zum Beispiel ergibt sich für die Quellensymbolfolge: ABAABAAAABBAAB ... die entsprechende Ausgabe von Run–Lenght Coding: 2; 3; 5; 1; 3; ...
Natürlich muss man die Längen $L_1 = 2$, $L_2 = 3$, ... der einzelnen, jeweils durch B getrennten Substrings vor der Übertragung binär darstellen. Verwendet man für alle $L_i$ jeweils $D = 3$ (Bit), so erhält man die RLC–Binärfolge 010′011′101′001′011′...

Die Grafik zeigt das das zu analysierende RLC–Ergebnis. In Spalte 2 und 3 sind die Substringlängen $L_i$ binär bzw. dezimal angegeben und in Spalte 4 in kumulierter Form (Werte von Spalte 3 aufsummiert).

Ein Problem von Run-Length Coding (RLC) ist der unbegrenzte Wertebereich der Größen $L_i$. Mit $D = 3$ kann kein Wert $L_i > 7$ dargestellt werden und mit $D = 2$ lautet die Beschränkung $1 \le L_i \le 3$.

Das Problem umgeht man mit Run–Length Limited Coding (RLLC). Ist ein Wert $L_i \ge 2^D$, so ersetzt man $L_i$ durch ein Sonderzeichen S und die Differenz $L_i - 2^D +1$. Beim RLLC–Decoder wird dieses Sonderzeichen S wieder expandiert.

RLLC–Beispiel 2: Wir gehen wieder von obiger Folge und dem Parameter $D = 2$ aus:

Quellensymbolfolge: ABAABAAAABBAAB ...
RLC–Dezimalfolge: 2; 3; 5; 1; 3; ...
RLLC–Dezimalfolge: 2; 3; S;2; 1; 3; ...
RLLC–Binärfolge: 01′11′ 00′10′01′11′...

Man erkennt:

Das Sonderzeichen S ist hier als 00 binär–codiert. Dies ist nur ein Beispiel – es muss nicht so sein.
Da mit $D = 2$ für alle echten RLC–Werte $1 \le L_i \le 3$ gilt, erkennt der Decoder das Sonderzeichen 00.
Er ersetzt dieses wieder durch $2^D -1$ (im Beispiel drei) A–Symbole.

Hinweise:

Die Aufgabe gehört zum Kapitel Weitere Quellencodierverfahren.
Insbesondere wird Bezug genommen auf die Seite Lauflängencodierung – Run-Length Coding.
Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.

Fragebogen

$\text{ohne Codierung:} \ N_\text{Bit} \ = \ $

$h_{\rm B}\ = \ $

$\text{RLC mit } D = 8\text{:} \ N_\text{Bit} \ = \ $

	Ja.
	Nein.

$\text{RLLC mit } D = 7\text{:} \ N_\text{Bit} \ = \ $

$\text{RLLC mit } D = 6\text{:} \ N_\text{Bit} \ = \ $

Musterlösung

1. Die Binärfolge besteht aus insgesamt N = 1250 Binärsymbolen (ablesbar aus der letzten Spalte in der Tabelle). Damit benötigt man ohne Codierung ebenso viele Bit: N_Bit = 1250.

2. Die gesamte Symbolfolge der Länge N = 1250 beinhaltet N_B = 25 Symbole B und N_A = 1225 Symbole A. Damit gilt für die relative Häufigkeit von B:

$$h_{\rm B} = \frac{N_{\rm B}}{N} = \frac{25}{1250} \hspace{0.15cm}\underline{= 0.02} = 2\%\hspace{0.05cm}. $$

3. Wir betrachten nun Run–Length Coding (RLC), wobei jeder Abstand zwischen zwei B–Symbolen mit 8 Bit dargestellt wird (D = 8). Damit ergibt sich mit N_B = 25:

$$N_{\rm Bit} = N_{\rm B} \cdot 8 \hspace{0.15cm}\underline{= 200} \hspace{0.05cm}.$$

4. Run–Length Coding mit 7 Bit pro Codewort erlaubt für L_i nur Werte zwischen 0 und 127. Der Eintrag „226” in Zeile 19 ist aber größer ⇒ NEIN.

5. Auch bei Run–Length Limited Coding (RLLC) sind für die „echten” Abstände L_i mit D = 7 nur Werte zwischen 1 und 2⁷ – 1 = 127 zulässig. Der Eintrag „226” in Zeile 19 wird bei RLLC ersetzt durch

Zeile 19a: S = 0000000 ⇒ Sonderzeichen, steht für „+ 127”,

Zeile 19b: 1100011 ⇒ Dezimal 99.

Damit erhält man insgesamt 26 Worte zu je 7 Bit:

$$N_{\rm Bit} = 26 \cdot 7 \hspace{0.15cm}\underline{= 182} \hspace{0.05cm}.$$

6. Nun müssen bei RLLC gegenüber RLC (siehe Tabelle) folgende Änderungen vorgenommen werden:

Zeile 1: 122 = 1 · 63 + 59 (ein Wort mehr),

Zeile 6: 70 = 1 · 63 + 7 (ein Wort mehr),

Zeile 7: 80 = 1 · 63 + 17 (ein Wort mehr),

Zeile 12: 79 = 1 · 63 + 18 (ein Wort mehr),

Zeile 13: 93 = 1 · 63 + 30 (ein Wort mehr),

Zeile 19: 226 = 3 · 63 + 37 (drei Worte mehr),

Zeile 25: 97 = 1 · 63 + 34 (ein Wort mehr).

Damit erhält man insgesamt 34 Worte zu je 6 Bit:

$$N_{\rm Bit} = 34 \cdot 6 \hspace{0.15cm}\underline{= 204} \hspace{0.05cm},$$

also ein schlechteres Ergebnis als mit 7 Bit gemäß Teilaufgabe (5).