Aufgabe 2.12: Run–Length Coding und RLLC - Versionsgeschichte

Guenter am 12. August 2021 um 15:55 Uhr

2021-08-12T15:55:13Z

Guenter am 12. August 2021 um 15:42 Uhr

2021-08-12T15:42:53Z

Guenter am 28. Januar 2020 um 14:56 Uhr

2020-01-28T14:56:01Z

Guenter am 28. Januar 2020 um 14:29 Uhr

2020-01-28T14:29:03Z

Guenter am 28. Januar 2020 um 13:57 Uhr

2020-01-28T13:57:33Z

Guenter am 2. Oktober 2018 um 14:11 Uhr

2018-10-02T14:11:10Z

Guenter am 2. Oktober 2018 um 13:45 Uhr

2018-10-02T13:45:44Z

Guenter am 2. Oktober 2018 um 13:01 Uhr

2018-10-02T13:01:08Z

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

2018-10-02T12:48:47Z

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

Guenter: Die Seite wurde neu angelegt: „ {{quiz-Header|Buchseite=Informationstheorie/Weitere Quellencodierverfahren }} Tabelle zu Run–Length Coding Wir…“

2018-10-02T12:46:27Z

Die Seite wurde neu angelegt: „ {{quiz-Header|Buchseite=Informationstheorie/Weitere Quellencodierverfahren }} right|Tabelle zu Run–Length Coding Wir…“

Neue Seite

{{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 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 [[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–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:''
*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 – Run-Length Coding]].

{{GraueBox|
TEXT='''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===

<quiz display=simple>
{Wieviele Bit würde man ohne Quellencodierung benötigen, also mit der Zuordnung A → 0 und B → 1?
|type="{}"}
$\text{ohne Codierung:} \ N_\text{Bit} \ = \ $ { 1250 3% }

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

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

{Ist hier Run–Length Coding mit 7 Bit–Codeworten möglich?
|type="[]"}
- Ja.
+ Nein.

{Wie viele Bit benötigt man mit Run–Length Limited Coding (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 Run–Length Limited Coding (RLLC) mit 6 Bit pro Codewort?
|type="{}"}
$\text{RLLC mit } D = 6\text{:} \ N_\text{Bit} \ = \ ${ 204 3% }

</quiz>

===Musterlösung===
{{ML-Kopf}}
'''(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 &bdquo;226” in Zeile 19 ist aber größer   ⇒   NEIN.

'''(5)'''  Auch bei Run–Length Limited Coding (RLLC) sind für die &bdquo;echten” Abstände Li mit D = 7 nur Werte zwischen 1 und 27 – 1 = 127 zulässig. Der Eintrag &bdquo;226” in Zeile 19 wird bei RLLC ersetzt durch

* Zeile 19a: S = 0000000   ⇒   Sonderzeichen, steht für &bdquo;+ 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).
{{ML-Fuß}}

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

@@ Zeile 85: / Zeile 85: @@
 ===Musterlösung===
 {{ML-Kopf}}
-'''(1)'''&nbsp; Die Binärfolge besteht aus&nbsp; $N = 1250$&nbsp; Binärsymbolen (ablesbar aus der letzten Spalte in der Tabelle).&nbsp; Damit benötigt man ohne Codierung ebenso viele Bit:
+'''(1)'''&nbsp; Die Binärfolge besteht aus&nbsp; $N = 1250$&nbsp; Binärsymbolen&nbsp; (ablesbar aus der letzten Spalte in der Tabelle).&nbsp; Damit benötigt man ohne Codierung ebenso viele Bit:
 :$$N_\text{Bit}\hspace{0.15cm}\underline{= 1250}.$$
@@ Zeile 95: / Zeile 95: @@
-'''(3)'''&nbsp; Wir betrachten nun&nbsp; <i>Run&ndash;Length Coding</i>&nbsp; $\rm (RLC)$, wobei jeder Abstand zwischen zwei&nbsp; ${\rm B}$&ndash;Symbolen mit acht Bit dargestellt wird&nbsp; $(D = 8)$.
+'''(3)'''&nbsp; Wir betrachten nun&nbsp; "Run&ndash;Length Coding"&nbsp; $\rm (RLC)$, wobei jeder Abstand zwischen zwei&nbsp; ${\rm B}$&ndash;Symbolen mit acht Bit dargestellt wird&nbsp; $(D = 8)$.
 *Damit ergibt sich mit&nbsp; $N_{\rm B} =  25$:
 :$$N_{\rm Bit} = N_{\rm B} \cdot 8 \hspace{0.15cm}\underline{= 200} \hspace{0.05cm}.$$
@@ Zeile 102: / Zeile 102: @@
 '''(4)'''&nbsp; $\rm RLC$&nbsp;  mit&nbsp; $D = 7$&nbsp; erlaubt für&nbsp; $L_i$&nbsp; nur Werte zwischen&nbsp; $1$&nbsp; und&nbsp; $2^7-1 =127$.
 *Der Eintrag &bdquo;226&rdquo; in Zeile 19 ist aber größer &nbsp; &nbsp; &#8658; &nbsp; &nbsp; <u>NEIN</u>.
@@ Zeile 123: / Zeile 124: @@
 * 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 + 16$ &nbsp;&nbsp;(ein Wort mehr),
 * Zeile 13: &nbsp;&nbsp;&nbsp; $93 = 1 &middot; 63 + 30$ &nbsp;&nbsp;(ein Wort mehr),
@@ Zeile 132: / Zeile 133: @@
-Damit erhält man insgesamt $34$ Worte zu je sechs Bit:
+Damit erhält man insgesamt&nbsp; $25 + 9 =34$&nbsp; Worte zu je sechs Bit:
 :$$N_{\rm Bit} = 34 \cdot 6 \hspace{0.15cm}\underline{= 204} \hspace{0.05cm},$$
 also ein schlechteres Ergebnis als mit sieben Bit gemäß Teilaufgabe '''(5)'''.

@@ Zeile 8: / Zeile 8: @@
 * Ohne Quellencodierung würde man pro Quellensymbol genau ein Bit benötigen, und dementsprechend würde bei einer Quellensymbolfolge der Länge&nbsp; $N$&nbsp; für die Codebitfolge ebenfalls&nbsp; $N_\text{Bit} = N$&nbsp; gelten.
 * Entropiecodierung macht hier ohne weitere Maßnahme&nbsp; (Beispiel:&nbsp; Zusammenfassen mehrerer Symbole zu einem Tupel) wegen der ungünstigen Symbolwahrscheinlichkeiten wenig Sinn.
-* Abhilfe schafft&nbsp; [[Informationstheorie/Weitere_Quellencodierverfahren#Laufl.C3.A4ngencodierung_.E2.80.93_Run.E2.80.93Length_Coding|Run-Length Coding]]&nbsp; $(\rm RLC)$, das unter dem genannten Link im Theorieteil beschrieben ist.&nbsp; Zum Beispiel ergibt sich für die Symbolfolge &nbsp; $\rm ABAABAAAABBAAB\text{...}$ &nbsp; die entsprechende Ausgabe von ''Run&ndash;Lenght Coding'': &nbsp; $ 2; \ 3; \ 5; \ 1; \ 3; \text{...}$
+* Abhilfe schafft&nbsp; [[Informationstheorie/Weitere_Quellencodierverfahren#Laufl.C3.A4ngencodierung_.E2.80.93_Run.E2.80.93Length_Coding|Run-Length Coding]]&nbsp; $(\rm RLC)$, das unter dem genannten Link im Theorieteil beschrieben ist.&nbsp; Zum Beispiel ergibt sich für die Symbolfolge &nbsp; $\rm ABAABAAAABBAAB\text{...}$ &nbsp; die entsprechende Ausgabe von&nbsp; "Run&ndash;Lenght Coding"': &nbsp; $ 2; \ 3; \ 5; \ 1; \ 3; \text{...}$
 * Natürlich muss man die Längen&nbsp; $L_1 = 2$,&nbsp; $L_2 = 3$, ...&nbsp; der einzelnen, jeweils durch&nbsp; $\rm B$&nbsp; getrennten Substrings vor der Übertragung binär darstellen.&nbsp; Verwendet man für alle&nbsp; $L_i$&nbsp; jeweils&nbsp; $D = 3$&nbsp; (Bit), so erhält man die RLC&ndash;Binärfolge
 :$$010\hspace{0.05cm}\text{'}\hspace{0.05cm}011\hspace{0.05cm}\text{'}\hspace{0.05cm}101\hspace{0.05cm}\text{'}\hspace{0.05cm}001\hspace{0.05cm}\text{'}\hspace{0.05cm}011\hspace{0.05cm}\text{'}\hspace{0.05cm}\text{...}$$
@@ Zeile 14: / Zeile 14: @@
 Die Grafik zeigt das  das zu analysierende RLC&ndash;Ergebnis.&nbsp; In Spalte 2 und 3 sind die Substringlängen&nbsp; $L_i$&nbsp; binär bzw. dezimal angegeben und in Spalte 4 in kumulierter Form&nbsp; (Werte von Spalte 3 aufsummiert).
-*Ein Problem von ''Run-Length Coding''&nbsp; $\rm (RLC)$ ist der  unbegrenzte Wertebereich der Größen&nbsp; $L_i$.&nbsp; Mit&nbsp; $D = 3$&nbsp; kann kein Wert&nbsp; $L_i > 7$&nbsp; dargestellt werden und mit&nbsp; $D = 2$&nbsp; lautet die Beschränkung&nbsp; $1 \le L_i \le 3$.
+*Ein Problem von&nbsp; "Run-Length Coding"&nbsp; $\rm (RLC)$&nbsp; ist der  unbegrenzte Wertebereich der Größen&nbsp; $L_i$.&nbsp; Mit&nbsp; $D = 3$&nbsp; kann kein Wert&nbsp; $L_i > 7$&nbsp; dargestellt werden und mit&nbsp; $D = 2$&nbsp; lautet die Beschränkung&nbsp; $1 \le L_i \le 3$.
-*Das Problem umgeht man mit <i>Run&ndash;Length Limited Coding</i>&nbsp; $\rm (RLLC)$.&nbsp; Ist ein Wert&nbsp; $L_i \ge 2^D$, so ersetzt man&nbsp; $L_i$&nbsp; durch ein Sonderzeichen&nbsp; <b>S</b>&nbsp; und die Differenz&nbsp; $L_i - 2^D +1$.&nbsp; Beim RLLC&ndash;Decoder wird dieses Sonderzeichen&nbsp; <b>S</b>&nbsp; wieder expandiert.
+*Das Problem umgeht man mit&nbsp; "Run&ndash;Length Limited Coding"&nbsp; $\rm (RLLC)$.&nbsp; Ist ein Wert&nbsp; $L_i \ge 2^D$, so ersetzt man&nbsp; $L_i$&nbsp; durch ein Sonderzeichen&nbsp; <b>S</b>&nbsp; und die Differenz&nbsp; $L_i - 2^D +1$.&nbsp; Beim RLLC&ndash;Decoder wird dieses Sonderzeichen&nbsp; <b>S</b>&nbsp; wieder expandiert.
@@ Zeile 36: / Zeile 36: @@
 * RLC&ndash;Dezimalfolge: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;'''2; 3; 5; 1; 3;''' ...
 * RLLC&ndash;Dezimalfolge: &nbsp;&nbsp;&nbsp; '''2;&nbsp; 3;&nbsp;'''<font color="#cc0000"><span style="font-weight: bold;"> S;</span></font>'''&nbsp;2;&nbsp; 1;&nbsp; 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;'''...
+* RLLC&ndash;Binärfolge: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; '''10&prime;11&prime;''' <font color="#cc0000"><span style="font-weight: bold;">00&prime;</span></font>'''10&prime;01&prime;11&prime;'''...

@@ Zeile 75: / Zeile 75: @@
-{Wie viele Bit benötigt man für&nbsp; $\rm (RLC)$&nbsp; <u>Run&ndash;Length Limited Coding</u>&nbsp; $\rm (RLLC)$&nbsp; mit sechs Bit pro Codewort&nbsp; $(D = 6)$?
+{Wie viele Bit benötigt man für&nbsp; <u>Run&ndash;Length Limited Coding</u>&nbsp; $\rm (RLLC)$&nbsp; mit sechs Bit pro Codewort&nbsp; $(D = 6)$?
 |type="{}"}
 $N_\text{Bit} \ = \ ${ 204 }
@@ Zeile 85: / Zeile 85: @@
 ===Musterlösung===
 {{ML-Kopf}}
-'''(1)'''&nbsp; 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:
+'''(1)'''&nbsp; Die Binärfolge besteht aus&nbsp; $N = 1250$&nbsp; Binärsymbolen (ablesbar aus der letzten Spalte in der Tabelle).&nbsp; Damit benötigt man ohne Codierung ebenso viele Bit:
-:$$N_\text{Bit}\hspace{0.15cm}\underline{== 1250}.$$
+:$$N_\text{Bit}\hspace{0.15cm}\underline{= 1250}.$$
-'''(2)'''&nbsp; Die gesamte Symbolfolge der Länge $N = 1250$ beinhaltet $N_{\rm B} =  25$ Symbole ${\rm B}$ und somit $N_{\rm A} =  1225$ Symbole ${\rm A}$. Damit gilt für die relative Häufigkeit von ${\rm B}$:
+'''(2)'''&nbsp; Die gesamte Symbolfolge der Länge&nbsp; $N = 1250$&nbsp; beinhaltet&nbsp; $N_{\rm B} =  25$&nbsp; Symbole&nbsp; ${\rm B}$&nbsp; und somit&nbsp; $N_{\rm A} =  1225$&nbsp; Symbole&nbsp; ${\rm A}$.&nbsp;
 :$$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 ${\rm B}$&ndash;Symbolen mit 8 Bit dargestellt wird $(D = 8)$. Damit ergibt sich mit $N_{\rm B} =  25$:
+'''(3)'''&nbsp; Wir betrachten nun&nbsp; <i>Run&ndash;Length Coding</i>&nbsp; $\rm (RLC)$, wobei jeder Abstand zwischen zwei&nbsp; ${\rm B}$&ndash;Symbolen mit acht Bit dargestellt wird&nbsp; $(D = 8)$.
 :$$N_{\rm Bit} = N_{\rm B} \cdot 8 \hspace{0.15cm}\underline{= 200} \hspace{0.05cm}.$$
-'''(4)'''&nbsp; Run&ndash;Length Coding mit $D = 7$ erlaubt für $L_i$ nur Werte zwischen $1$ und $2^7-1 =127$. Der Eintrag &bdquo;226&rdquo; in Zeile 19 ist aber größer &nbsp; &nbsp; &#8658; &nbsp; &nbsp; <u>NEIN</u>.
+'''(4)'''&nbsp; $\rm RLC$&nbsp;  mit&nbsp; $D = 7$&nbsp; erlaubt für&nbsp; $L_i$&nbsp; nur Werte zwischen&nbsp; $1$&nbsp; und&nbsp; $2^7-1 =127$.
-'''(5)'''&nbsp; Auch bei Run&ndash;Length Limited Coding (RLLC) sind für die &bdquo;echten&rdquo; Abstände $L_i$ mit  $D = 7$ nur Werte zwischen $1$ und $127$ zulässig. Der Eintrag &bdquo;226&rdquo; in Zeile 19 wird bei RLLC ersetzt durch
+'''(5)'''&nbsp; Auch bei Run&ndash;Length Limited Coding&nbsp;  $\rm (RLLC)$&nbsp; sind für die &bdquo;echten&rdquo; Abstände&nbsp; $L_i$&nbsp; mit&nbsp;  $D = 7$&nbsp; nur Werte bis&nbsp; $127$&nbsp; zulässig.
-* Zeile 19a: <b>S</b> = <b>0000000</b> &nbsp;&nbsp;&#8658;&nbsp;&nbsp; Sonderzeichen, steht für &bdquo;+ 127&rdquo;,
+:* Zeile 19a: &nbsp;   <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: &nbsp;  <b>1100011</b> &nbsp;&nbsp;&#8658;&nbsp;&nbsp; Dezimal 99.
+*Damit erhält man insgesamt $26$ Worte zu je sieben 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:
+'''(6)'''&nbsp; Nun müssen bei&nbsp; $\rm RLLC$&nbsp; gegenüber&nbsp; $\rm RLC$&nbsp; (siehe Tabelle) folgende Änderungen vorgenommen werden:
 * Zeile &nbsp;&nbsp;1: &nbsp; $122 = 1 &middot; 63 + 59$ &nbsp;&nbsp;(ein Wort mehr),

@@ Zeile 16: / Zeile 16: @@
 *Ein Problem von ''Run-Length Coding''&nbsp; $\rm (RLC)$ ist der  unbegrenzte Wertebereich der Größen&nbsp; $L_i$.&nbsp; Mit&nbsp; $D = 3$&nbsp; kann kein Wert&nbsp; $L_i > 7$&nbsp; dargestellt werden und mit&nbsp; $D = 2$&nbsp; lautet die Beschränkung&nbsp; $1 \le L_i \le 3$.
-+Das Problem umgeht man mit <i>Run&ndash;Length Limited Coding</i>&nbsp; $\rm (RLLC)$.&nbsp; Ist ein Wert&nbsp; $L_i \ge 2^D$, so ersetzt man&nbsp; $L_i$&nbsp; durch ein Sonderzeichen&nbsp; <b>S</b>&nbsp; und die Differenz&nbsp; $L_i - 2^D +1$.&nbsp; Beim RLLC&ndash;Decoder wird dieses Sonderzeichen&nbsp; <b>S</b>&nbsp; wieder expandiert.
+*Das Problem umgeht man mit <i>Run&ndash;Length Limited Coding</i>&nbsp; $\rm (RLLC)$.&nbsp; Ist ein Wert&nbsp; $L_i \ge 2^D$, so ersetzt man&nbsp; $L_i$&nbsp; durch ein Sonderzeichen&nbsp; <b>S</b>&nbsp; und die Differenz&nbsp; $L_i - 2^D +1$.&nbsp; Beim RLLC&ndash;Decoder wird dieses Sonderzeichen&nbsp; <b>S</b>&nbsp; wieder expandiert.
@@ Zeile 32: / Zeile 32: @@
 {{GraueBox|
-TEXT=$\text{RLLC-Beispiel 2}$:&nbsp; Wir gehen wieder von obiger Folge und dem Parameter $D = 2$ aus:
+TEXT=$\text{RLLC-Beispiel}$:&nbsp; Wir gehen wieder von obiger Folge und dem Parameter&nbsp; $D = 2$&nbsp; aus:
 * Quellensymbolfolge: &nbsp;&nbsp; $\rm 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;Dezimalfolge: &nbsp;&nbsp;&nbsp; '''2;&nbsp; 3;&nbsp;'''<font color="#cc0000"><span style="font-weight: bold;"> S;</span></font>'''&nbsp;2;&nbsp; 1;&nbsp; 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.
+*Das Sonderzeichen&nbsp; <b>S</b>&nbsp; ist hier als&nbsp; <b>00</b>&nbsp; binär&ndash;codiert.&nbsp; 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'''.
+*Da mit&nbsp; $D = 2$&nbsp; für alle echten RLC&ndash;Werte&nbsp; $1 \le L_i \le 3$&nbsp; gilt, erkennt der Decoder das Sonderzeichen&nbsp; '''00'''.
-*Er  ersetzt dieses wieder durch $2^D -1$   (im Beispiel drei) $\rm A$&ndash;Symbole.}}
+*Er  ersetzt dieses wieder durch&nbsp; $2^D -1$&nbsp;   (im Beispiel drei)&nbsp; $\rm A$&ndash;Symbole.}}
@@ Zeile 49: / Zeile 49: @@
 <quiz display=simple>
-{Wieviele Bit würde man <u>ohne Quellencodierung</u> benötigen, also mit der Zuordnung $\rm A$ &nbsp; &#8594; &nbsp;<b>0</b> und $\rm B$ &nbsp; &#8594; &nbsp;<b>1</b>?
+{Wieviele Bit würde man&nbsp; <u>ohne Quellencodierung</u>&nbsp; benötigen, also mit der Zuordnung&nbsp; $\rm A$ &nbsp; &#8594; &nbsp;<b>0</b>&nbsp; und&nbsp; $\rm B$ &nbsp; &#8594; &nbsp;<b>1</b>?
 |type="{}"}
 $N_\text{Bit} \ = \ $  { 1250 }
-{Wie groß ist die relative Häufigkeit des Symbols $\rm B$?
+{Wie groß ist die relative Häufigkeit des Symbols&nbsp; $\rm B$?
 |type="{}"}
 $h_{\rm B}\ = \ $ { 2 3% } $\ \%$
-{Wie viele Bit benötigt man für <u>Run&ndash;Length Coding</U> (RLC) nach der angegebenen Tabelle mit 8 Bit&ndash;Codeworten $(D = 8)$?
+{Wie viele Bit benötigt man für&nbsp; <u>Run&ndash;Length Coding</U>&nbsp; $\rm (RLC)$&nbsp; nach der angegebenen Tabelle mit acht Bit pro Codewort&nbsp; $(D = 8)$?
 |type="{}"}
 $N_\text{Bit} \ = \ $ { 200 }
-{Ist hier <u>Run&ndash;Length Coding</u> mit 7 Bit&ndash;Codeworten $(D = 7)$ möglich?
+{Ist hier&nbsp; <u>Run&ndash;Length Coding</u>&nbsp; mit sieben Bit&ndash;Codeworten&nbsp; $(D = 7)$&nbsp; möglich?
 |type="()"}
 - Ja.
@@ Zeile 70: / Zeile 70: @@
-{Wie viele Bit benötigt man mit <u>Run&ndash;Length Limited Coding</U> (RLLC) mit 7 Bit pro Codewort $(D = 7)$?
+{Wie viele Bit benötigt man für&nbsp; <u>Run&ndash;Length Limited Coding</U>&nbsp; $\rm (RLLC)$&nbsp; mit sieben Bit pro Codewort&nbsp; $(D = 7)$?
 |type="{}"}
 $N_\text{Bit} \ = \ $ { 182 }
-{Wie viele Bit benötigt man mit <u>Run&ndash;Length Limited Coding</u> (RLLC) mit 6 Bit pro Codewort $(D = 6)$?
+{Wie viele Bit benötigt man für&nbsp; $\rm (RLC)$&nbsp; <u>Run&ndash;Length Limited Coding</u>&nbsp; $\rm (RLLC)$&nbsp; mit sechs Bit pro Codewort&nbsp; $(D = 6)$?
 |type="{}"}
 $N_\text{Bit} \ = \ ${ 204 }

@@ Zeile 4: / Zeile 4: @@
 [[Datei:P_ID2474__Inf_A_2_13_neu.png|right|frame|Tabelle zu Run–Length Coding]]
-Wir betrachten eine Binärquelle mit dem Symbolvorrat $\rm A$ und $\rm B$, wobei $\rm B$ allerdings nur sehr selten auftritt.
+Wir betrachten eine Binärquelle mit dem Symbolvorrat&nbsp; $\rm A$&nbsp; und&nbsp; $\rm B$, wobei&nbsp; $\rm B$&nbsp; 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 Codebitfolge ebenfalls $N_\text{Bit} = N$ gelten.
+* Ohne Quellencodierung würde man pro Quellensymbol genau ein Bit benötigen, und dementsprechend würde bei einer Quellensymbolfolge der Länge&nbsp; $N$&nbsp; für die Codebitfolge ebenfalls&nbsp; $N_\text{Bit} = N$&nbsp; gelten.
-* Entropiecodierung macht hier ohne weitere Maßnahme (Zusammenfassen mehrerer Symbole zu einem Tupel) wegen der ungünstigen Symbolwahrscheinlichkeiten wenig Sinn.
+* Entropiecodierung macht hier ohne weitere Maßnahme&nbsp; (Beispiel:&nbsp; 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 &nbsp;
+* Abhilfe schafft&nbsp; [[Informationstheorie/Weitere_Quellencodierverfahren#Laufl.C3.A4ngencodierung_.E2.80.93_Run.E2.80.93Length_Coding|Run-Length Coding]]&nbsp; $(\rm RLC)$, das unter dem genannten Link im Theorieteil beschrieben ist.&nbsp; Zum Beispiel ergibt sich für die Symbolfolge &nbsp; $\rm ABAABAAAABBAAB\text{...}$ &nbsp; die entsprechende Ausgabe von ''Run&ndash;Lenght Coding'': &nbsp; $ 2; \ 3; \ 5; \ 1; \ 3; \text{...}$
-:$$\rm ABAABAAAABBAAB\text{...}$$
+* Natürlich muss man die Längen&nbsp; $L_1 = 2$,&nbsp; $L_2 = 3$, ...&nbsp; der einzelnen, jeweils durch&nbsp; $\rm B$&nbsp; getrennten Substrings vor der Übertragung binär darstellen.&nbsp; Verwendet man für alle&nbsp; $L_i$&nbsp; jeweils&nbsp; $D = 3$&nbsp; (Bit), so erhält man die RLC&ndash;Binärfolge
 :$$010\hspace{0.05cm}\text{'}\hspace{0.05cm}011\hspace{0.05cm}\text{'}\hspace{0.05cm}101\hspace{0.05cm}\text{'}\hspace{0.05cm}001\hspace{0.05cm}\text{'}\hspace{0.05cm}011\hspace{0.05cm}\text{'}\hspace{0.05cm}\text{...}$$
-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).
+Die Grafik zeigt das  das zu analysierende RLC&ndash;Ergebnis.&nbsp; In Spalte 2 und 3 sind die Substringlängen&nbsp; $L_i$&nbsp; binär bzw. dezimal angegeben und in Spalte 4 in kumulierter Form&nbsp; (Werte von Spalte 3 aufsummiert).

@@ Zeile 8: / Zeile 8: @@
 * 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 Codebitfolge 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 &nbsp;
+* 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 &nbsp;
 :$$\rm ABAABAAAABBAAB\text{...}$$
 die entsprechende Ausgabe von ''Run&ndash;Lenght Coding'':
@@ Zeile 19: / Zeile 19: @@
 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.
+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]].
+*Die Aufgabe gehört zum  Kapitel&nbsp; [[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]].
+*Insbesondere wird  Bezug genommen auf die Seite&nbsp; [[Informationstheorie/Weitere_Quellencodierverfahren#Laufl.C3.A4ngencodierung_.E2.80.93_Run.E2.80.93Length_Coding|Lauflängencodierung &ndash; Run-Length Coding]].
@@ Zeile 45: / Zeile 48: @@
 <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>?
+{Wieviele Bit würde man <u>ohne Quellencodierung</u> benötigen, also mit der Zuordnung $\rm A$ &nbsp; &#8594; &nbsp;<b>0</b> und $\rm B$ &nbsp; &#8594; &nbsp;<b>1</b>?
 |type="{}"}
-$\text{ohne Codierung:} \ N_\text{Bit} \ = \ $  { 1250 3% }
+$N_\text{Bit} \ = \ $  { 1250 }
-{Wie groß ist die relative Häufigkeit des Symbols <b>B</b>?
+{Wie groß ist die relative Häufigkeit des Symbols $\rm 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 ?
+{Wie viele Bit benötigt man für <u>Run&ndash;Length Coding</U> (RLC) nach der angegebenen Tabelle mit 8 Bit&ndash;Codeworten $($D = 8)$?
 |type="{}"}
-$\text{RLC mit } D = 8\text{:} \ N_\text{Bit} \ = \ $ { 200 3% }
+$N_\text{Bit} \ = \ $ { 200 }
-{Ist hier <i>Run&ndash;Length Coding</i> mit 7 Bit&ndash;Codeworten möglich?
+{Ist hier <u>Run&ndash;Length Coding</u> mit 7 Bit&ndash;Codeworten $(D = 8)$ möglich?
-|type="[]"}
+|type="()"}
 - Ja.
 + Nein.
-{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 <u>Run&ndash;Length Limited Coding</U> (RLLC) mit 7 Bit pro Codewort $(D = 7)$?
 |type="{}"}
-$\text{RLLC mit } D = 7\text{:} \ N_\text{Bit} \ = \ $ { 182 3% }
+$N_\text{Bit} \ = \ $ { 182 }
-{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 <u>Run&ndash;Length Limited Coding</u> (RLLC) mit 6 Bit pro Codewort $(D = 6)$?
 |type="{}"}
-$\text{RLLC mit } D = 6\text{:} \ N_\text{Bit} \ = \ ${ 204 3% }
+$N_\text{Bit} \ = \ ${ 204 }

← Nächstältere Version	Version vom 2. Oktober 2018, 12:48 Uhr
(kein Unterschied)