Exercise 2.12: Run–Length Coding and Run–Length Limited Coding
Wir betrachten eine Binärquelle mit dem Symbolvorrat $\rm A$ und $\rm B$, wobei $\rm 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 Codebitfolge 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
- $$\rm ABAABAAAABBAAB\text{...}$$
die entsprechende Ausgabe von Run–Lenght Coding:
- $$ 2; \ 3; \ 5; \ 1; \ 3; \text{...}$$
- Natürlich muss man die Längen $L_1 = 2$, $L_2 = 3$, ... der einzelnen, jeweils durch $\rm 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\hspace{0.05cm}\text{'}\hspace{0.05cm}011\hspace{0.05cm}\text{'}\hspace{0.05cm}101\hspace{0.05cm}\text{'}\hspace{0.05cm}001\hspace{0.05cm}\text{'}\hspace{0.05cm}011\hspace{0.05cm}\text{'}\hspace{0.05cm}\text{...}$$
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.
Hinweise:
- Die Aufgabe gehört zum Kapitel Weitere Quellencodierverfahren.
- Insbesondere wird Bezug genommen auf die Seite Lauflängencodierung – Run-Length Coding.
$\text{RLLC-Beispiel 2}$: Wir gehen wieder von obiger Folge und dem Parameter $D = 2$ aus:
- Quellensymbolfolge: $\rm 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) $\rm A$–Symbole.
Fragebogen
Musterlösung
- $$N_\text{Bit}\hspace{0.15cm}\underline{== 1250}.$$
(2) Die gesamte Symbolfolge der Länge $N = 1250$ beinhaltet $N_{\rm B} = 25$ Symbole ${\rm B}$ und somit $N_{\rm A} = 1225$ Symbole ${\rm A}$. Damit gilt für die relative Häufigkeit von ${\rm 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 ${\rm B}$–Symbolen mit 8 Bit dargestellt wird $(D = 8)$. Damit ergibt sich mit $N_{\rm B} = 25$:
- $$N_{\rm Bit} = N_{\rm B} \cdot 8 \hspace{0.15cm}\underline{= 200} \hspace{0.05cm}.$$
(4) Run–Length Coding mit $D = 7$ erlaubt für $L_i$ nur Werte zwischen $1$ und $2^7-1 =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 $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 sieben 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 sechs Bit:
- $$N_{\rm Bit} = 34 \cdot 6 \hspace{0.15cm}\underline{= 204} \hspace{0.05cm},$$
also ein schlechteres Ergebnis als mit sieben Bit gemäß Teilaufgabe (5).