View source for Exercise 2.12: Run–Length Coding and Run–Length Limited Coding


{{quiz-Header|Buchseite=Information_Theory/Further_Source_Coding_Methods
}}

[[File:EN_Inf_A_2_13.png|right|frame|Table on Run-Length Coding]]
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;, 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{...}$
* 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 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$.

*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.








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]].
 


{{GraueBox|
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;&nbsp;&nbsp;'''2; 3; 5; 1; 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; '''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 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.}}



===Questions===

<quiz display=simple>
{How many bits would be needed&nbsp; <u>without source coding</u>&nbsp;, i.e. with the assignment&nbsp; $\rm A$ &nbsp; &#8594; &nbsp;<b>0</b>&nbsp; and&nbsp; $\rm B$ &nbsp; &#8594; &nbsp;<b>1</b>?
|type="{}"}
$N_\text{bits} \ = \ $  { 1250 }


{What is the relative frequency of symbol&nbsp; $\rm B$?
|type="{}"}
$h_{\rm B}\ = \ $ { 2 3% } $\ \%$


{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)$?
|type="{}"}
$N_\text{bits} \ = \ $ { 200 } 


{Is&nbsp; <u>Run&ndash;Length Coding</u>&nbsp; with seven bit codewords&nbsp; $(D = 7)$&nbsp; possible here?
|type="()"}
- Yes.
+ No.


{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)$?
|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)$?
|type="{}"}
$N_\text{bits} \ = \ ${ 204 }



</quiz>

===Solution===
{{ML-Kopf}}
'''(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; 
*This means that the same number of bits is needed without coding:
:$$N_\text{bits}\hspace{0.15cm}\underline{= 1250}.$$


'''(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; 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 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; "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:
:$$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$. 
*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&nbsp; "real"&nbsp; distances&nbsp; $L_i$&nbsp; with&nbsp;  $D = 7$.
*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 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 bits} = 26 \cdot 7 \hspace{0.15cm}\underline{= 182} \hspace{0.05cm}.$$


'''(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):

* Line &nbsp;&nbsp;1: &nbsp; $122 = 1 &middot; 63 + 59$ &nbsp;&nbsp;(one word more),

* Line &nbsp;&nbsp;6: &nbsp;&nbsp;&nbsp; $70 = 1 &middot; 63 + 7$ &nbsp;&nbsp;&nbsp;&nbsp;(one word more),

* Line &nbsp;&nbsp;7: &nbsp;&nbsp;&nbsp; $80 = 1 &middot; 63 + 17$ &nbsp;&nbsp;(one word more),

* Line 12: &nbsp;&nbsp;&nbsp; $79 = 1 &middot; 63 + 16$ &nbsp;&nbsp;(one word more),

* Line 13: &nbsp;&nbsp;&nbsp; $93 = 1 &middot; 63 + 30$ &nbsp;&nbsp;(one word more),

* Line 19: &nbsp; $226 = 3 &middot; 63 + 37$  &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&nbsp; $25+9=34$&nbsp; words of six bits each:
:$$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ß}}



[[Category:Information Theory: Exercises|^2.4 Further Source Coding Methods^]]