Aufgaben:Aufgabe 2.12: Run–Length Coding & RLLC: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(7 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 3: Zeile 3:
 
}}
 
}}
  
[[Datei:P_ID2474__Inf_A_2_13_neu.png|right|]]
+
[[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> nur sehr selten auftritt.
+
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 bei einer Quellensymbolfolge der Länge <i>N</i> für die Codefolge ebenfalls <i>N</i> Bit.
+
* 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;'''...
  
:* Entropiecodierung macht hier ohne weitere Maßnahme (Zusammenfassen mehrerer Symbole zu einem Tupel) wegen der ungünstigen Symbolwahrscheinlichkeiten wenig Sinn.
+
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).
  
:* Abhilfe schafft Run-Length Coding (RLC), das unter dem genannten Link im Theorieteil beschrieben ist. Zum Beispiel:
+
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$.
  
: Quellensymbolfolge: &nbsp;&nbsp;<font color="#cc0000"><span style="font-weight: bold;"> ABAABAAAABBAAB ...</span></font>
+
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.
  
: 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>
+
''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]].
 +
  
:* 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.
+
{{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;'''...
  
:* Beim RLLC&ndash;Decoder wird dieses Sonderzeichen wieder expandiert.
+
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.}}
  
<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.
 
  
  
Zeile 44: Zeile 41:
  
 
<quiz display=simple>
 
<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>?
+
{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="{}"}
 
|type="{}"}
uncodiert: $N_\text{Bit}$ = { 1250 3% }
+
$\text{ohne Codierung:} \ N_\text{Bit} \ = \ $ { 1250 3% }
  
  
 
{Wie groß ist die relative Häufigkeit des Symbols <b>B</b>?
 
{Wie groß ist die relative Häufigkeit des Symbols <b>B</b>?
 
|type="{}"}
 
|type="{}"}
$h_B$ = { 0.02 3% }
+
$h_{\rm B}\ = \ $ { 2 3% } $\ \%$
  
  
{Wie viele Bit benötigt man für <i>Run&ndash;Length Coding</i> (RLC) entsprechend der angegebenen Tabelle?
+
{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="{}"}
 
|type="{}"}
$RLC,\ D = 8:\ N_\text{Bit}$ = { 200 3% } Bit
+
$\text{RLC mit } D = 8\text{:} \ N_\text{Bit} \ = \ $ { 200 3% }  
  
  
Zeile 67: Zeile 64:
 
{Wie viele Bit benötigt man mit <i>Run&ndash;Length Limited Coding</i> (RLLC) mit 7 Bit pro Codewort?
 
{Wie viele Bit benötigt man mit <i>Run&ndash;Length Limited Coding</i> (RLLC) mit 7 Bit pro Codewort?
 
|type="{}"}
 
|type="{}"}
$RLLC,\ D = 7:\ N_\text{Bit}$ = { 182 3% }
+
$\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?
 
{Wie viele Bit benötigt man mit <i>Run&ndash;Length Limited Coding</i> (RLLC) mit 6 Bit pro Codewort?
 
|type="{}"}
 
|type="{}"}
$RLLC,\ D = 6:\ N_\text{Bit}$ = { 204 3% }
+
$\text{RLLC mit } D = 6\text{:} \ N_\text{Bit} \ = \ ${ 204 3% }
  
  
Zeile 80: Zeile 77:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{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>.
+
'''(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>.
  
<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>:
+
'''(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}. $$
 
:$$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:
+
'''(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}.$$
 
:$$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>.
+
'''(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>.
  
<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
+
'''(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 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.
  
:* Zeile 19b: <b>1100011</b> &nbsp;&nbsp;&#8658;&nbsp;&nbsp; Dezimal 99.
 
  
 
Damit erhält man insgesamt 26 Worte zu je 7 Bit:
 
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}.$$
 
:$$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:
+
'''(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;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;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 &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 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 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 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).
  
:* 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:
 
Damit erhält man insgesamt 34 Worte zu je 6 Bit:
Zeile 119: Zeile 118:
 
also ein schlechteres Ergebnis als mit 7 Bit gemäß Teilaufgabe (5).
 
also ein schlechteres Ergebnis als mit 7 Bit gemäß Teilaufgabe (5).
 
{{ML-Fuß}}
 
{{ML-Fuß}}
 
 
 
[[Category:Aufgaben zu Informationstheorie|^2.4 Weitere Quellencodierverfahren^]]
 

Aktuelle Version vom 2. Oktober 2018, 13:49 Uhr

Tabelle zu Run–Length Coding

Wir betrachten eine Binärquelle mit dem Symbolvorrat A und B, wobei 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 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–Lenght Coding:    2; 3; 5; 1; 3; ...
  • Natürlich muss man die Längen $L_1 = 2$, $L_2 = 3$, ... der einzelnen, jeweils durch 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′011′101′001′011′...

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:


RLLC–Beispiel 2:  Wir gehen wieder von obiger Folge 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:

  • 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) A–Symbole.


Fragebogen

1

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

$\text{ohne Codierung:} \ N_\text{Bit} \ = \ $

2

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

$h_{\rm B}\ = \ $

$\ \%$

3

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

$\text{RLC mit } D = 8\text{:} \ N_\text{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?

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

6

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

$\text{RLLC mit } D = 6\text{:} \ 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 somit 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 D = 7 erlaubt für Li nur Werte zwischen 1 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).