View source for Aufgaben:Aufgabe 2.12: Run–Length Coding & RLLC


{{quiz-Header|Buchseite=Informationstheorie und Quellencodierung/Weitere Quellencodierverfahren
}}

[[File:P_ID2474__Inf_A_2_13_neu.png|right|]]
Wir betrachten eine Binärquelle mit dem Symbolvorrat <b>A</b> und <b>B</b>, wobei <b>B</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 <i>N</i> für die Codefolge ebenfalls <i>N</i> 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: &nbsp;&nbsp;<font color="#cc0000"><span style="font-weight: bold;"> ABAABAAAABBAAB ...</span></font>

: Run&ndash;Lenght Coding: &nbsp;&nbsp;<font color="#cc0000"><span style="font-weight: bold;"> 2; 3; 5; 1; 3; ...</span></font>

:* Natürlich muss man die Längen <i>L</i><sub>1</sub> = 2, <i>L</i><sub>2</sub> = 3, ... der einzelnen, jeweils durch <b>B</b> getrennten Substrings vor der Übertragung binär darstellen. Verwendet man für alle <i>L<sub>i</sub></i> jeweils <i>D</i> = 3 Bit, so erhält man die RLC&ndash;Binärfolge <font color="#cc0000"><span style="font-weight: bold;"> 010&prime;011&prime;101&prime;001&prime;011&prime;...</span></font>

:* Ein Problem der RLC ist der  unbegrenzte Wertebereich der Größen <i>L<sub>i</sub></i>. Mit <i>D</i>&nbsp;=&nbsp;3 kann kein Wert <i>L<sub>i</sub></i> > 7 dargestellt werden und mit <i>D</i> = 2 lautet die Beschränkung 1&nbsp;&#8804;&nbsp;<i>L<sub>i</sub></i>&nbsp;&#8804;&nbsp;3.

:* Das Problem umgeht man mit <i>Run&ndash;Length Limited Coding</i> (RLLC). Ist ein Wert <i>L<sub>i</sub></i>&nbsp;&#8805;&nbsp;2<sup><i>D</i></sup>, so ersetzt man <i>L<sub>i</sub></i> durch ein Sonderzeichen <b>S</b> und die Differenz <i>L<sub>i</sub></i>&nbsp;&ndash;&nbsp;2<sup><i>D</i></sup>&nbsp;+&nbsp;1.

:* Beim RLLC&ndash;Decoder wird dieses Sonderzeichen wieder expandiert.

<b>Beispiel:</b>&nbsp;&nbsp; Wir gehen wieder von obiger Binärfolge und dem Parameter <i>D</i> = 2 aus:

:* Quellensymbolfolge: &nbsp;&nbsp;&nbsp;&nbsp;<font color="#cc0000"><span style="font-weight: bold;"> ABAABAAAABBAAB ...</span></font>

:* RLC&ndash;Dezimalfolge: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#cc0000"><span style="font-weight: bold;"> 2; 3; 5; 1; 3; ...</span></font>

:* RLLC&ndash;&bdquo;Dezimalfolge&rdquo;:&nbsp; <font color="#cc0000"><span style="font-weight: bold;"> 2; 3;</span></font><b> S;</b><font color="#cc0000"><span style="font-weight: bold;">  2; 1; 3; ...</span></font>

:* RLLC&ndash;Binärfolge: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#cc0000"><span style="font-weight: bold;"> 01&prime;11&prime;</span></font> <b>00&prime;</b><font color="#cc0000"><span style="font-weight: bold;">10&prime;01&prime;11&prime;...</span></font>

Man erkennt, dass hier das Sonderzeichen <b>S</b> als <b>00</b> binär&ndash;codiert ist (dies ist nur ein Beispiel &ndash; es muss nicht so sein). Da mit <i>D</i> = 2 für alle echten RLC&ndash;Werte 1 &#8804; <i>L<sub>i</sub></i> &#8804; 3 gilt, erkennt der Decoder das Sonderzeichen und ersetzt es wieder durch 2<sup><i>D</i></sup> &ndash; 1 (im Beispiel drei) <b>A</b>&ndash;Symbole.

Die obere Grafik zeigt das  das zu analysierende RLC&ndash;Ergebnis. In Spalte 2 und 3 sind die Substringlängen <i>L<sub>i</sub></i> binär bzw. dezimal angegeben und in Spalte 4 in kumulierter Form (Werte von Spalte 3 aufsummiert).

<b>Hinweis:</b> Die Aufgabe bezieht sich auf die letzte Theorieseite von Kapitel 2.4.


===Fragebogen===

<quiz display=simple>
{Wieviele Bit würde man <i>ohne Quellencodierung</i> benötigen, also mit der Zuordnung <b>A</b>&nbsp;&#8594;&nbsp;<b>0</b> und <b>B</b>&nbsp;=&nbsp;<b>1</b>?
|type="{}"}
uncodiert: $N_\text{Bit}$ = { 1250 3% }


{Wie groß ist die relative Häufigkeit des Symbols <b>B</b>?
|type="{}"}
$h_B$ = { 0.02 3% }


{Wie viele Bit benötigt man für <i>Run&ndash;Length Coding</i> (RLC) entsprechend der angegebenen Tabelle?
|type="{}"}
$RLC,\ D = 8:\ N_\text{Bit}$ = { 200 3% } Bit


{Ist hier <i>Run&ndash;Length Coding</i> mit 7 Bit&ndash;Codeworten möglich?
|type="[]"}
- Ja.
+ Nein.


{Wie viele Bit benötigt man mit <i>Run&ndash;Length Limited Coding</i> (RLLC) mit 7 Bit pro Codewort?
|type="{}"}
$RLLC,\ D = 7:\ N_\text{Bit}$ = { 182 3% }


{Wie viele Bit benötigt man mit <i>Run&ndash;Length Limited Coding</i> (RLLC) mit 6 Bit pro Codewort?
|type="{}"}
$RLLC,\ D = 6:\ N_\text{Bit}$ = { 204 3% }



</quiz>

===Musterlösung===
{{ML-Kopf}}
<b>1.</b>&nbsp;&nbsp;Die Binärfolge besteht aus insgesamt <i>N</i> = 1250 Binärsymbolen (ablesbar aus der letzten Spalte in der Tabelle). Damit benötigt man ohne Codierung ebenso viele Bit: <i>N</i><sub>Bit</sub> <u>= 1250</u>.

<b>2.</b>&nbsp;&nbsp;Die gesamte Symbolfolge der Länge <i>N</i> = 1250 beinhaltet <i>N</i><sub>B</sub> = 25 Symbole <b>B</b> und  <i>N</i><sub>A</sub> = 1225 Symbole <b>A</b>. Damit gilt für die relative Häufigkeit von <b>B</b>:
:$$h_{\rm B} = \frac{N_{\rm B}}{N} = \frac{25}{1250} \hspace{0.15cm}\underline{= 0.02} = 2\%\hspace{0.05cm}. $$

<b>3.</b>&nbsp;&nbsp;Wir betrachten nun <i>Run&ndash;Length Coding</i> (RLC), wobei jeder Abstand zwischen zwei <b>B</b>&ndash;Symbolen mit 8 Bit dargestellt wird (<i>D</i> = 8). Damit ergibt sich mit <i>N</i><sub>B</sub> = 25:
:$$N_{\rm Bit} = N_{\rm B} \cdot 8 \hspace{0.15cm}\underline{= 200} \hspace{0.05cm}.$$

<b>4.</b>&nbsp;&nbsp;<i>Run&ndash;Length Coding</i> mit 7 Bit pro Codewort erlaubt für <i>L<sub>i</sub></i> nur Werte zwischen 0 und 127. Der Eintrag &bdquo;226&rdquo; in Zeile 19 ist aber größer &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <u>NEIN</u>.

<b>5.</b>&nbsp;&nbsp;Auch bei <i>Run&ndash;Length Limited Coding</i> (RLLC) sind für die &bdquo;echten&rdquo; Abstände <i>L<sub>i</sub></i> mit  <i>D</i> = 7 nur Werte zwischen 1 und 2<sup>7</sup> &ndash; 1 = 127 zulässig. Der Eintrag &bdquo;226&rdquo; in Zeile 19 wird bei RLLC ersetzt durch

:* Zeile 19a: <b>S</b> = <b>0000000</b> &nbsp;&nbsp;&#8658;&nbsp;&nbsp; Sonderzeichen, steht für &bdquo;+ 127&rdquo;,

:* Zeile 19b: <b>1100011</b> &nbsp;&nbsp;&#8658;&nbsp;&nbsp; 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}.$$

<b>6.</b>&nbsp;&nbsp;Nun müssen bei RLLC gegenüber RLC (siehe Tabelle) folgende Änderungen vorgenommen werden:

:* Zeile &nbsp;&nbsp;1: &nbsp;122 = 1 &middot; 63 + 59 &nbsp;&nbsp;(ein Wort mehr),

:* Zeile &nbsp;&nbsp;6: &nbsp;&nbsp;&nbsp;70 = 1 &middot; 63 + 7 &nbsp;&nbsp;&nbsp;&nbsp;(ein Wort mehr),

:* Zeile &nbsp;&nbsp;7: &nbsp;&nbsp;&nbsp;80 = 1 &middot; 63 + 17 &nbsp;&nbsp;(ein Wort mehr),

:* Zeile 12: &nbsp;&nbsp;&nbsp;79 = 1 &middot; 63 + 18 &nbsp;&nbsp;(ein Wort mehr),

:* Zeile 13: &nbsp;&nbsp;&nbsp;93 = 1 &middot; 63 + 30 &nbsp;&nbsp;(ein Wort mehr),

:* Zeile 19: &nbsp;226 = 3 &middot; 63 + 37  &nbsp;&nbsp;(drei Worte mehr),

:* Zeile 25: &nbsp;&nbsp;&nbsp;97 = 1 &middot; 63 + 34  &nbsp;&nbsp;(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).
{{ML-Fuß}}



[[Category:Aufgaben zu Informationstheorie und Quellencodierung|^2.4 Weitere Quellencodierverfahren^]]