Exercise 2.12: Run–Length Coding and Run–Length Limited Coding - Revision history

Hwang at 23:34, 12 November 2022

2022-11-12T23:34:12Z

Hwang at 15:09, 1 November 2022

2022-11-01T15:09:05Z

Javier: Text replacement - "analyse" to "analyze"

2021-09-22T11:47:37Z

Text replacement - "analyse" to "analyze"

Javier at 12:04, 16 August 2021

2021-08-16T12:04:21Z

Javier at 12:03, 16 August 2021

2021-08-16T12:03:13Z

Guenter at 16:40, 12 August 2021

2021-08-12T16:40:34Z

Guenter at 16:28, 12 August 2021

2021-08-12T16:28:56Z

Guenter at 16:10, 12 August 2021

2021-08-12T16:10:36Z

Guenter at 16:05, 12 August 2021

2021-08-12T16:05:21Z

Guenter at 12:34, 12 August 2021

2021-08-12T12:34:35Z

@@ Line 27: / Line 27: @@
 Hints:
 *This exercise belongs to the chapter&nbsp; [[Information_Theory/Further_Source_Coding_Methods|Further source coding methods]].
-*In particular, reference is made to the page&nbsp; [[Information_Theory/Further_Source_Coding_Methods#Run.E2.80.93Length_coding|Run-Length Coding]].
+*In particular, reference is made to the section&nbsp; [[Information_Theory/Further_Source_Coding_Methods#Run.E2.80.93Length_coding|Run-Length Coding]].

@@ Line 59: / Line 59: @@
-{How many bits are needed for&nbsp; <u>Run&ndash;Length Coding</U>&nbsp; $\rm (RLC)$&nbsp; according to the given table with eight bits per codeword&nbsp; $(D = 8)$?
+{How many bits are needed for&nbsp; <u>Run&ndash;Length Coding</U>&nbsp; $\rm (RLC)$&nbsp; according to the given table with eight bits per code word&nbsp; $(D = 8)$?
 |type="{}"}
 $N_\text{bits} \ = \ $ { 200 }
-{Is&nbsp; <u>Run&ndash;Length Coding</u>&nbsp; with seven bit codewords&nbsp; $(D = 7)$&nbsp; possible here?
+{Is&nbsp; <u>Run&ndash;Length Coding</u>&nbsp; with seven bit code words&nbsp; $(D = 7)$&nbsp; possible here?
 |type="()"}
 - Yes.
@@ Line 70: / Line 70: @@
-{How many bits are needed for&nbsp; <u>Run&ndash;Length Limited Coding</U>&nbsp; $\rm (RLLC)$&nbsp; with seven bits per codeword&nbsp; $(D = 7)$?
+{How many bits are needed for&nbsp; <u>Run&ndash;Length Limited Coding</U>&nbsp; $\rm (RLLC)$&nbsp; with seven bits per code word&nbsp; $(D = 7)$?
 |type="{}"}
 $N_\text{bits} \ = \ $ { 182 }
-{How many bits are needed for&nbsp; <u>Run&ndash;Length Limited Coding</u>&nbsp; $\rm (RLLC)$&nbsp; with six bits per codeword&nbsp; $(D = 6)$?
+{How many bits are needed for&nbsp; <u>Run&ndash;Length Limited Coding</u>&nbsp; $\rm (RLLC)$&nbsp; with six bits per code word&nbsp; $(D = 6)$?
 |type="{}"}
 $N_\text{bits} \ = \ ${ 204 }

@@ Line 12: / Line 12: @@
 :$$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{...}$$
-The graph shows the RLC result to be analysed.&nbsp; Columns 2 and 3 show the substring lengths&nbsp; $L_i$&nbsp; in binary and decimal, respectively, and column 4 shows them in cumulative form&nbsp; (values from column 3 added up).
+The graph shows the RLC result to be analyzed.&nbsp; Columns 2 and 3 show the substring lengths&nbsp; $L_i$&nbsp; in binary and decimal, respectively, and column 4 shows them in cumulative form&nbsp; (values from column 3 added up).
 *One problem of&nbsp; "Run-Length Coding"&nbsp; $\rm (RLC)$ is the unlimited range of values of the quantities&nbsp; $L_i$.&nbsp; With&nbsp; $D = 3$,&nbsp; no value&nbsp; $L_i > 7$&nbsp; can be represented and with&nbsp; $D = 2$,&nbsp; the restriction is&nbsp; $1 \le L_i \le 3$.

@@ Line 6: / Line 6: @@
 We consider a binary source with the symbol set&nbsp; $\rm A$&nbsp; and&nbsp; $\rm B$, where&nbsp; $\rm B$&nbsp; however, occurs only very rarely.
-* Without source coding, exactly one bit would be needed per source symbol, and accordingly, for a source symbol sequence of length&nbsp; $N$&nbsp; would also apply to the encoded sequence&nbsp; $N_\text{bits} = N$.
+* Without source coding, exactly one bit would be needed per source symbol, and accordingly, for a source symbol sequence of length&nbsp; $N$&nbsp;, the encoded sequence would also have length &nbsp; $N_\text{bits} = N$.
 * Entropy coding makes little sense here without further measures&nbsp; (example:&nbsp; combining several symbols into a tuple)&nbsp; because of the unfavourable symbol probabilities.
 * The remedy is&nbsp; [[Information_Theory/Weitere_Quellencodierverfahren#Run.E2.80.93Length_coding|Run-Length Coding]]&nbsp; $(\rm RLC)$, which is described in the theory section under the link mentioned.&nbsp; For example, for the symbol sequence &nbsp; $\rm ABAABAAAABBAAB\text{...}$ &nbsp;  the corresponding output of&nbsp; "Run&ndash;Length Coding": &nbsp; $ 2; \ 3; \ 5; \ 1; \ 3; \text{...}$

@@ Line 6: / Line 6: @@
 We consider a binary source with the symbol set&nbsp; $\rm A$&nbsp; and&nbsp; $\rm B$, where&nbsp; $\rm B$&nbsp; however, occurs only very rarely.
-* Without source coding, exactly one bit would be needed per source symbol, and accordingly, for a source symbol sequence of length&nbsp; $N$&nbsp; would also apply to the coder symbol sequence&nbsp; $N_\text{bits} = N$.
+* Without source coding, exactly one bit would be needed per source symbol, and accordingly, for a source symbol sequence of length&nbsp; $N$&nbsp; would also apply to the encoded sequence&nbsp; $N_\text{bits} = N$.
 * Entropy coding makes little sense here without further measures&nbsp; (example:&nbsp; combining several symbols into a tuple)&nbsp; because of the unfavourable symbol probabilities.
 * The remedy is&nbsp; [[Information_Theory/Weitere_Quellencodierverfahren#Run.E2.80.93Length_coding|Run-Length Coding]]&nbsp; $(\rm RLC)$, which is described in the theory section under the link mentioned.&nbsp; For example, for the symbol sequence &nbsp; $\rm ABAABAAAABBAAB\text{...}$ &nbsp;  the corresponding output of&nbsp; "Run&ndash;Length Coding": &nbsp; $ 2; \ 3; \ 5; \ 1; \ 3; \text{...}$

@@ Line 85: / Line 85: @@
 ===Solution===
 {{ML-Kopf}}
-'''(1)'''&nbsp; The binary sequence consists of&nbsp; $N = 1250$&nbsp; binary symbols (can be read from the last column in the table).&nbsp; This means that the same number of bits is needed without coding:
+'''(1)'''&nbsp; The binary sequence consists of&nbsp; $N = 1250$&nbsp; binary symbols&nbsp; (can be read from the last column in the table).&nbsp;
-:$$N_\text{Bit}\hspace{0.15cm}\underline{= 1250}.$$
+*This means that the same number of bits is needed without coding:
 '''(2)'''&nbsp; The entire symbol sequence of length&nbsp; $N = 1250$&nbsp; contains&nbsp; $N_{\rm B} =  25$&nbsp; symbols&nbsp; ${\rm B}$&nbsp; and thus&nbsp; $N_{\rm A} =  1225$&nbsp; symbols&nbsp; ${\rm A}$.&nbsp;
-*The number&nbsp; $N_{\rm B}$&nbsp; der Symbole&nbsp; ${\rm B}$&nbsp; ist dabei gleich der Zeilenzahl in der vorne angegebenen Tabelle.
+*The number&nbsp; $N_{\rm B}$&nbsp; of symbols&nbsp; ${\rm B}$&nbsp; is equal to the number of rows in the table given at the front.
-*Thus the following applies to the relative frequency of&nbsp;&nbsp; ${\rm B}$:
+*Thus the following applies to the relative frequency of symbol&nbsp; ${\rm B}$:
 :$$h_{\rm B} = \frac{N_{\rm B}}{N} = \frac{25}{1250} \hspace{0.15cm}\underline{= 0.02} = 2\%\hspace{0.05cm}. $$
-'''(3)'''&nbsp; We now consider&nbsp; <i>Run&ndash;Length Coding</i>&nbsp; $\rm (RLC)$, where each distance between two&nbsp; ${\rm B}$&ndash;symbols is represented by eight bits&nbsp; $(D = 8)$.
+'''(3)'''&nbsp; We now consider&nbsp; "Run&ndash;Length Coding"&nbsp; $\rm (RLC)$, where each distance between two&nbsp; ${\rm B}$&ndash;symbols is represented by eight bits&nbsp; $(D = 8)$.
-*Thus, with&nbsp; $N_{\rm B} =  25$, we get::
+*Thus, with&nbsp; $N_{\rm B} =  25$, we get:
-:$$N_{\rm Bit} = N_{\rm B} \cdot 8 \hspace{0.15cm}\underline{= 200} \hspace{0.05cm}.$$
+:$$N_{\rm bits} = N_{\rm B} \cdot 8 \hspace{0.15cm}\underline{= 200} \hspace{0.05cm}.$$
-'''(4)'''&nbsp; $\rm RLC$&nbsp;  with&nbsp; $D = 7$&nbsp;only allows values between&nbsp; $1$&nbsp; und&nbsp; $2^7-1 =127$ for&nbsp; $L_i$&nbsp; .
+'''(4)'''&nbsp; $\rm RLC$&nbsp;  with&nbsp; $D = 7$&nbsp;only allows values between&nbsp; $1$&nbsp; und&nbsp; $2^7-1 =127$ for&nbsp; $L_i$.
-*However, the entry "226" in line 19 is greater &nbsp; &nbsp; &#8658; &nbsp; &nbsp; <u>NO</u>.
+*However, the entry&nbsp; "226"&nbsp; in line 19 is greater &nbsp; &nbsp; &#8658; &nbsp; &nbsp; <u>NO</u>.
-'''(5)'''&nbsp; Even with Run&ndash;Length Limited Coding&nbsp;  $\rm (RLLC)$&nbsp; , only values up to&nbsp; $127$&nbsp are permitted for the "real" distances&nbsp; $L_i$&nbsp; with&nbsp;  $D = 7$&nbsp; ;.
+'''(5)'''&nbsp; Even with Run&ndash;Length Limited Coding&nbsp;  $\rm (RLLC)$,&nbsp; only values up to&nbsp; $127$&nbsp; are permitted for the&nbsp; "real"&nbsp; distances&nbsp; $L_i$&nbsp; with&nbsp;  $D = 7$.
-*The entry "226" in line 19 is replaced by the following for&nbsp;  $\rm RLLC$&nbsp;
+*The entry&nbsp; "226"&nbsp; in line 19 is replaced by the following for&nbsp;  $\rm RLLC$:
-:* Line 19a: &nbsp;   <b>S</b> = <b>0000000</b> &nbsp;&nbsp;&#8658;&nbsp;&nbsp; special character, stands for "+ 127",
+:* Line 19a: &nbsp;   <b>S</b> = <b>0000000</b> &nbsp;&nbsp;&#8658;&nbsp;&nbsp; special character, stands for "+127",
 :* Line 19b: &nbsp;  <b>1100011</b> &nbsp;&nbsp;&#8658;&nbsp;&nbsp; decimal 99.
 *This gives a total of $26$ words of seven bits each:
-:$$N_{\rm Bit} = 26 \cdot 7 \hspace{0.15cm}\underline{= 182} \hspace{0.05cm}.$$
+:$$N_{\rm bits} = 26 \cdot 7 \hspace{0.15cm}\underline{= 182} \hspace{0.05cm}.$$
-'''(6)'''&nbsp; Now the following changes have to be made in&nbsp; $\rm RLLC$&nbsp; compared to&nbsp; $\rm RLC$&nbsp; (see table):
+'''(6)'''&nbsp; With&nbsp;  $D = 6$&nbsp; the following changes have to be made in&nbsp; $\rm RLLC$&nbsp; compared to&nbsp; $\rm RLC$&nbsp; (see table):
-* Zeile &nbsp;&nbsp;1: &nbsp; $122 = 1 &middot; 63 + 59$ &nbsp;&nbsp;(one word more),
+* Line &nbsp;&nbsp;1: &nbsp; $122 = 1 &middot; 63 + 59$ &nbsp;&nbsp;(one word more),
-* Zeile &nbsp;&nbsp;6: &nbsp;&nbsp;&nbsp; $70 = 1 &middot; 63 + 7$ &nbsp;&nbsp;&nbsp;&nbsp;(one word more),
+* Line &nbsp;&nbsp;6: &nbsp;&nbsp;&nbsp; $70 = 1 &middot; 63 + 7$ &nbsp;&nbsp;&nbsp;&nbsp;(one word more),
-* Zeile &nbsp;&nbsp;7: &nbsp;&nbsp;&nbsp; $80 = 1 &middot; 63 + 17$ &nbsp;&nbsp;(one word more),
+* Line &nbsp;&nbsp;7: &nbsp;&nbsp;&nbsp; $80 = 1 &middot; 63 + 17$ &nbsp;&nbsp;(one word more),
-* Zeile 12: &nbsp;&nbsp;&nbsp; $79 = 1 &middot; 63 + 18$ &nbsp;&nbsp;(one word more),
+* Line 12: &nbsp;&nbsp;&nbsp; $79 = 1 &middot; 63 + 16$ &nbsp;&nbsp;(one word more),
-* Zeile 13: &nbsp;&nbsp;&nbsp; $93 = 1 &middot; 63 + 30$ &nbsp;&nbsp;(one word more),
+* Line 13: &nbsp;&nbsp;&nbsp; $93 = 1 &middot; 63 + 30$ &nbsp;&nbsp;(one word more),
-* Zeile 19: &nbsp; $226 = 3 &middot; 63 + 37$  &nbsp;&nbsp;(one word more),
+* Line 19: &nbsp; $226 = 3 &middot; 63 + 37$  &nbsp;&nbsp;(one word more),
-* Zeile 25: &nbsp;&nbsp;&nbsp; $97 = 1 &middot; 63 + 34$  &nbsp;&nbsp;(one word more).
+* Line 25: &nbsp;&nbsp;&nbsp; $97 = 1 &middot; 63 + 34$  &nbsp;&nbsp;(one word more).
-This gives a total of $34$ words of six bits each:
+This gives a total of&nbsp; $25+9=34$&nbsp; words of six bits each:
-:$$N_{\rm Bit} = 34 \cdot 6 \hspace{0.15cm}\underline{= 204} \hspace{0.05cm},$$
+:$$N_{\rm bits} = 34 \cdot 6 \hspace{0.15cm}\underline{= 204} \hspace{0.05cm},$$
 i.e. a worse result than with seven bits according to subtask '''(5)'''.
 {{ML-Fuß}}

@@ Line 34: / Line 34: @@
 TEXT=$\text{RLLC Example}$:&nbsp; We again assume the above sequence and the parameter&nbsp; $D = 2$&nbsp;:
 * Source symbol sequence: &nbsp;&nbsp; $\rm ABAABAAAABBAAB$...
-* RLC decimal sequence: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;'''2; 3; 5; 1; 3;''' ...
+* RLC decimal sequence: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;'''2; 3; 5; 1; 3;''' ...
-* RLLC decimal sequence: &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 decimal sequence: &nbsp;&nbsp;&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 binary sequence: &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 binary sequence: &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;'''...
 You can see:
 *The special character&nbsp; <b>S</b>&nbsp; is binary-coded here as&nbsp; <b>00</b>&nbsp;.&nbsp; This is only an example &ndash; it does not have to be like this.
-*Since with&nbsp; $D = 2$&nbsp; for all real RLC values&nbsp; $1 \le L_i \le 3$&nbsp;, the decoder recognises the special character&nbsp; '''00'''.
+*Since with&nbsp; $D = 2$&nbsp; for all real RLC values&nbsp; $1 \le L_i \le 3$&nbsp;, the decoder recognizes the special character&nbsp; '''00'''.
 *It replaces this again with&nbsp; $2^D -1$&nbsp;   (three in the example)&nbsp; $\rm A$&ndash;symbols.}}

@@ Line 6: / Line 6: @@
 We consider a binary source with the symbol set&nbsp; $\rm A$&nbsp; and&nbsp; $\rm B$, where&nbsp; $\rm B$&nbsp; however, occurs only very rarely.
-* Without source coding, exactly one bit would be needed per source symbol, and accordingly, for a source symbol sequence of length&nbsp; $N$&nbsp; would also apply to the code bit sequence&nbsp; $N_\text{Bit} = N$&nbsp;.
+* Without source coding, exactly one bit would be needed per source symbol, and accordingly, for a source symbol sequence of length&nbsp; $N$&nbsp; would also apply to the coder symbol sequence&nbsp; $N_\text{bits} = N$.
-* Entropy coding makes little sense here without further measures&nbsp; (example:&nbsp; combining several symbols into a tuple) wbecause of the unfavourable symbol probabilities.
+* Entropy coding makes little sense here without further measures&nbsp; (example:&nbsp; combining several symbols into a tuple)&nbsp; because of the unfavourable symbol probabilities.
-* The remedy is&nbsp; [[Information_Theory/Weitere_Quellencodierverfahren#Run.E2.80.93Length_coding|Run-Length Coding]]&nbsp; $(\rm RLC)$, which is described in the theory section under the link mentioned.&nbsp; For example, for the symbol sequence &nbsp; $\rm ABAABAAAABBAAB\text{...}$ &nbsp;  the corresponding output of ''Run&ndash;Length Coding'': &nbsp; $ 2; \ 3; \ 5; \ 1; \ 3; \text{...}$
+* The remedy is&nbsp; [[Information_Theory/Weitere_Quellencodierverfahren#Run.E2.80.93Length_coding|Run-Length Coding]]&nbsp; $(\rm RLC)$, which is described in the theory section under the link mentioned.&nbsp; For example, for the symbol sequence &nbsp; $\rm ABAABAAAABBAAB\text{...}$ &nbsp;  the corresponding output of&nbsp; "Run&ndash;Length Coding": &nbsp; $ 2; \ 3; \ 5; \ 1; \ 3; \text{...}$
-* Of course, the lengths&nbsp; $L_1 = 2$,&nbsp; $L_2 = 3$, ...&nbsp; of the individual substrings, each separated by&nbsp; $\rm B$&nbsp;, must be represented in binary before transmission.&nbsp; If one uses&nbsp; $D = 3$&nbsp; (bit) for all&nbsp; $L_i$&nbsp; one obtains the RLC binary sequence
+* Of course, the lengths&nbsp; $L_1 = 2$,&nbsp; $L_2 = 3$, ...&nbsp; of the individual substrings, each separated by&nbsp; $\rm B$&nbsp;, must be represented in binary before transmission.&nbsp; If one uses&nbsp; $D = 3$&nbsp; (bit) for all&nbsp; $L_i$&nbsp; one obtains the RLC binary symbol sequence
 :$$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{...}$$
 The graph shows the RLC result to be analysed.&nbsp; Columns 2 and 3 show the substring lengths&nbsp; $L_i$&nbsp; in binary and decimal, respectively, and column 4 shows them in cumulative form&nbsp; (values from column 3 added up).
-*One problem of ''Run-Length Coding''&nbsp; $\rm (RLC)$ is the unlimited range of values of the quantities&nbsp; $L_i$.&nbsp; With&nbsp; $D = 3$&nbsp;, no value&nbsp; $L_i > 7$&nbsp; can be represented and with&nbsp; $D = 2$&nbsp;, the restriction is&nbsp; $1 \le L_i \le 3$.
+*One problem of&nbsp; "Run-Length Coding"&nbsp; $\rm (RLC)$ is the unlimited range of values of the quantities&nbsp; $L_i$.&nbsp; With&nbsp; $D = 3$,&nbsp; no value&nbsp; $L_i > 7$&nbsp; can be represented and with&nbsp; $D = 2$,&nbsp; the restriction is&nbsp; $1 \le L_i \le 3$.
-*The problem is circumvented with <i>Run&ndash;Length Limited Coding</i>&nbsp; $\rm (RLLC)$.&nbsp; If a value is&nbsp; $L_i \ge 2^D$, one replaces&nbsp; $L_i$&nbsp; with a special character&nbsp; <b>S</b>&nbsp; and the difference&nbsp; $L_i - 2^D +1$.&nbsp; With the RLLC decoder, this special character&nbsp; <b>S</b>&nbsp; is expanded again.
+*The problem is circumvented with&nbsp; "Run&ndash;Length Limited Coding"&nbsp; $\rm (RLLC)$.&nbsp; If a value is&nbsp; $L_i \ge 2^D$,&nbsp; one replaces&nbsp; $L_i$&nbsp; with a special character&nbsp; <b>S</b>&nbsp; and the difference&nbsp; $L_i - 2^D +1$.&nbsp; With the RLLC decoder, this special character&nbsp; <b>S</b>&nbsp; is expanded again.
@@ Line 26: / Line 26: @@
 Hints:
-*This exercise belongs to the chapter&nbsp; [[Information_Theory/Weitere_Quellencodierverfahren|Other source coding methods]].
+*This exercise belongs to the chapter&nbsp; [[Information_Theory/Further_Source_Coding_Methods|Further source coding methods]].
-*In particular, reference is made to the page&nbsp; [[Information_Theory/Weitere_Quellencodierverfahren#Run.E2.80.93Length_coding|Run-Length Coding]].
+*In particular, reference is made to the page&nbsp; [[Information_Theory/Further_Source_Coding_Methods#Run.E2.80.93Length_coding|Run-Length Coding]].

← Older revision		Revision as of 12:34, 12 August 2021
Line 1:		Line 1:

−	{{quiz-Header\|Buchseite=~~Informationstheorie~~/~~Weitere Quellencodierverfahren~~	+	{{quiz-Header\|Buchseite=Information_Theory/Further_Source_Coding_Methods
	}}		}}