Aufgaben:Aufgabe 2.12: Run–Length Coding & RLLC
Wir betrachten eine Binärquelle mit dem Symbolvorrat A und B, wobei B nur sehr selten auftritt.
- Ohne Quellencodierung würde man pro Quellensymbol genau ein Bit benötigen, und dementsprechend bei einer Quellensymbolfolge der Länge N für die Codefolge ebenfalls N Bit.
- 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:
- Quellensymbolfolge: ABAABAAAABBAAB ...
- Run–Lenght Coding: 2; 3; 5; 1; 3; ...
- Natürlich muss man die Längen L1 = 2, L2 = 3, ... der einzelnen, jeweils durch B getrennten Substrings vor der Übertragung binär darstellen. Verwendet man für alle Li jeweils D = 3 Bit, so erhält man die RLC–Binärfolge 010′011′101′001′011′...
- Ein Problem der RLC ist der unbegrenzte Wertebereich der Größen Li. Mit D = 3 kann kein Wert Li > 7 dargestellt werden und mit D = 2 lautet die Beschränkung 1 ≤ Li ≤ 3.
- Das Problem umgeht man mit Run–Length Limited Coding (RLLC). Ist ein Wert Li ≥ 2D, so ersetzt man Li durch ein Sonderzeichen S und die Differenz Li – 2D + 1.
- Beim RLLC–Decoder wird dieses Sonderzeichen wieder expandiert.
Beispiel: Wir gehen wieder von obiger Binärfolge 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, dass hier das Sonderzeichen S als 00 binär–codiert ist (dies ist nur ein Beispiel – es muss nicht so sein). Da mit D = 2 für alle echten RLC–Werte 1 ≤ Li ≤ 3 gilt, erkennt der Decoder das Sonderzeichen und ersetzt es wieder durch 2D – 1 (im Beispiel drei) A–Symbole.
Die obere Grafik zeigt das das zu analysierende RLC–Ergebnis. In Spalte 2 und 3 sind die Substringlängen Li binär bzw. dezimal angegeben und in Spalte 4 in kumulierter Form (Werte von Spalte 3 aufsummiert).
Hinweis: Die Aufgabe bezieht sich auf die letzte Theorieseite von Kapitel 2.4.
Fragebogen
Musterlösung
2. Die gesamte Symbolfolge der Länge N = 1250 beinhaltet NB = 25 Symbole B und NA = 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 NB = 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 Li 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 Li mit D = 7 nur Werte zwischen 1 und 27 – 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).
