Quelltext der Seite Aufgabe 2.12: Run–Length Coding und RLLC


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

[[Datei:P_ID2474__Inf_A_2_13_neu.png|right|Tabelle zu Run–Length Coding]]
Wir betrachten eine Binärquelle mit dem Symbolvorrat <b>A</b> und <b>B</b>, wobei <b>B</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 [[Informationstheorie/Weitere_Quellencodierverfahren#Laufl.C3.A4ngencodierung_.E2.80.93_Run.E2.80.93Length_Coding|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&ndash;Lenght Coding'': &nbsp;&nbsp;''' 2; 3; 5; 1; 3;''' ...
* Natürlich muss man die Längen $L_1 = 2$, $L_2 = 3$, ... der einzelnen, jeweils durch <b>B</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&ndash;Binärfolge '''010&prime;011&prime;101&prime;001&prime;011&prime;'''...

Die Grafik zeigt das  das zu analysierende RLC&ndash;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 <i>Run&ndash;Length Limited Coding</i> (RLLC). Ist ein Wert $L_i \ge 2^D$, so ersetzt man $L_i$ durch ein Sonderzeichen <b>S</b> und die Differenz $L_i - 2^D +1$. Beim RLLC&ndash;Decoder wird dieses Sonderzeichen <b>S</b> wieder expandiert.


''Hinweise:'' 
*Die Aufgabe gehört zum  Kapitel [[Informationstheorie/Weitere_Quellencodierverfahren|Weitere Quellencodierverfahren]].
*Insbesondere wird  Bezug genommen auf die Seite [[Informationstheorie/Weitere_Quellencodierverfahren#Laufl.C3.A4ngencodierung_.E2.80.93_Run.E2.80.93Length_Coding|Lauflängencodierung &ndash; Run-Length Coding]].
 


{{GraueBox|
TEXT='''RLLC&ndash;Beispiel 2''':&nbsp; Wir gehen wieder von obiger Folge und dem Parameter $D = 2$ aus:
* Quellensymbolfolge: &nbsp;&nbsp;'''ABAABAAAABBAAB''' ...
* RLC&ndash;Dezimalfolge: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;'''2; 3; 5; 1; 3;''' ...
* RLLC&ndash;Dezimalfolge: &nbsp;&nbsp;&nbsp; '''2; 3;'''<font color="#cc0000"><span style="font-weight: bold;"> S;</span></font>'''2; 1; 3;''' ...
* RLLC&ndash;Binärfolge: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; '''01&prime;11&prime;''' <font color="#cc0000"><span style="font-weight: bold;">00&prime;</span></font>'''10&prime;01&prime;11&prime;'''...

Man erkennt: 
*Das Sonderzeichen <b>S</b> ist hier als <b>00</b> binär&ndash;codiert. Dies ist nur ein Beispiel &ndash; es muss nicht so sein. 
*Da mit $D = 2$ für alle echten RLC&ndash;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) <b>A</b>&ndash;Symbole.}}



===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;&#8594;&nbsp;<b>1</b>?
|type="{}"}
$\text{ohne Codierung:} \ N_\text{Bit} \ = \ $  { 1250 3% }


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


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


{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="{}"}
$\text{RLLC mit } D = 7\text{:} \ 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="{}"}
$\text{RLLC mit } D = 6\text{:} \ N_\text{Bit} \ = \ ${ 204 3% }



</quiz>

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

'''(2)'''&nbsp; Die gesamte Symbolfolge der Länge <i>N</i> = 1250 beinhaltet <i>N</i><sub>B</sub> = 25 Symbole <b>B</b> und somit   <i>N</i><sub>A</sub> = 1225 Symbole <b>A</b>. <br>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}. $$

'''(3)'''&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}.$$

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

'''(5)'''&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}.$$

'''(6)'''&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|^2.4 Weitere Quellencodierverfahren^]]