Aufgaben:Aufgabe 2.12: Run–Length Coding & RLLC - Versionsgeschichte

Guenter am 2. Oktober 2018 um 12:49 Uhr

2018-10-02T12:49:55Z

Mwiki-lnt: Textersetzung - „*Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.“ durch „ “

2018-05-29T12:02:41Z

Textersetzung - „*Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.“ durch „ “

Guenter: Guenter verschob die Seite Aufgaben:2.12 Run–Length Coding & RLLC nach Aufgaben:Aufgabe 2.12: Run–Length Coding & RLLC

2018-01-03T14:01:41Z

Guenter verschob die Seite 2.12 Run–Length Coding & RLLC nach Aufgabe 2.12: Run–Length Coding & RLLC

Guenter am 27. Mai 2017 um 15:24 Uhr

2017-05-27T15:24:12Z

Guenter am 27. Mai 2017 um 15:12 Uhr

2017-05-27T15:12:27Z

Guenter am 27. Mai 2017 um 15:11 Uhr

2017-05-27T15:11:26Z

Guenter am 27. Mai 2017 um 15:11 Uhr

2017-05-27T15:11:00Z

Guenter am 27. Mai 2017 um 15:09 Uhr

2017-05-27T15:09:49Z

Guenter: Guenter verschob die Seite Aufgaben:2.13 Run–Length Coding & RLLC nach Aufgaben:2.12 Run–Length Coding & RLLC

2017-05-27T13:15:26Z

Guenter verschob die Seite 2.13 Run–Length Coding & RLLC nach 2.12 Run–Length Coding & RLLC

Guenter: Guenter verschob die Seite Aufgaben:2.13 Run–Length Coding und RLLC nach Aufgaben:2.13 Run–Length Coding & RLLC

2017-05-26T11:37:18Z

Guenter verschob die Seite 2.13 Run–Length Coding und RLLC nach 2.13 Run–Length Coding & RLLC

← Nächstältere Version		Version vom 2. Oktober 2018, 12:49 Uhr
Zeile 118:		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^]]~~

@@ Zeile 21: / Zeile 21: @@
 *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]].
-*Sollte die Eingabe des Zahlenwertes &bdquo;0&rdquo; erforderlich sein, so geben Sie bitte &bdquo;0.&rdquo; ein.

@@ Zeile 77: / Zeile 77: @@
 ===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>.
+'''(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}. $$
-<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}.$$
-<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;,
 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:
+'''(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;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).
 Damit erhält man insgesamt 34 Worte zu je 6 Bit:

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

@@ Zeile 22: / Zeile 22: @@
 *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]].
 *Sollte die Eingabe des Zahlenwertes &bdquo;0&rdquo; erforderlich sein, so geben Sie bitte &bdquo;0.&rdquo; ein.
 {{GraueBox|

@@ Zeile 16: / Zeile 16: @@
 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.
 {{GraueBox|
@@ Zeile 29: / Zeile 35: @@
 *Er  ersetzt dieses wieder durch $2^D -1$ (im Beispiel drei) <b>A</b>&ndash;Symbole.}}

@@ 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.
+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>
+{{GraueBox|
-:* 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>
+Man erkennt:
-:* 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.
+''Hinweise:''
+*Die Aufgabe gehört zum  Kapitel [[Informationstheorie/Weitere_Quellencodierverfahren|Weitere Quellencodierverfahren]].
-:* Beim RLLC&ndash;Decoder wird dieses Sonderzeichen wieder expandiert.
+*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]].
+*Sollte die Eingabe des Zahlenwertes &bdquo;0&rdquo; erforderlich sein, so geben Sie bitte &bdquo;0.&rdquo; ein.
@@ Zeile 44: / Zeile 39: @@
 <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="{}"}
-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>?
 |type="{}"}
-$h_B$ = { 0.02 3% }
+$h_{\rm B}\ = \ $ { 0.02 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="{}"}
-$RLC,\ D = 8:\ N_\text{Bit}$ = { 200 3% } Bit
+$\text{RLC mit } D = 8\text{:} \ N_\text{Bit} \ = \ $ { 200 3% }
@@ Zeile 67: / Zeile 62: @@
 {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% }
+$\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="{}"}
-$RLLC,\ D = 6:\ N_\text{Bit}$ = { 204 3% }
+$\text{RLLC mit } D = 6\text{:} \ N_\text{Bit} \ = \ ${ 204 3% }