Aufgaben:Aufgabe 2.12: Run–Length Coding & RLLC

Aus LNTwww
Wechseln zu:Navigation, Suche

P ID2474 Inf A 2 13 neu.png

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

1

Wieviele Bit würde man ohne Quellencodierung benötigen, also mit der Zuordnung A → 0 und B = 1?

uncodiert: $N_\text{Bit}$ =

2

Wie groß ist die relative Häufigkeit des Symbols B?

$h_B$ =

3

Wie viele Bit benötigt man für Run–Length Coding (RLC) entsprechend der angegebenen Tabelle?

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

Bit

4

Ist hier Run–Length Coding mit 7 Bit–Codeworten möglich?

Ja.
Nein.

5

Wie viele Bit benötigt man mit Run–Length Limited Coding (RLLC) mit 7 Bit pro Codewort?

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

6

Wie viele Bit benötigt man mit Run–Length Limited Coding (RLLC) mit 6 Bit pro Codewort?

$RLLC,\ D = 6:\ 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: NBit = 1250.

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).