View source for Aufgaben:Exercise 2.11: Arithmetic Coding


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

[[File:EN_Inf_A_2_11_v3.png|right|frame|Interval nesting for arithmetic coding]]
Arithmetic coding is a special form of entropy coding: &nbsp;  The symbol probabilities must also be known here.&nbsp; 

In this exercise, we assume&nbsp; $M = 3$&nbsp; symbols, which we name with&nbsp; $\rm X$,&nbsp; $\rm Y$&nbsp; and  $\rm Z$.&nbsp;
While Huffman coding is done symbol by symbol, in Arithmetic Coding&nbsp; $(\rm AC)$&nbsp; a sequence of symbols of length&nbsp; $N$&nbsp; is encoded together.&nbsp; The coding result is a real numerical value&nbsp; $r$&nbsp; from the interval
:$$I = \big[B, \ E \big) = \big[B, \ B +{\it \Delta} \big)\hspace{0.05cm}.$$
This notation means:
* The beginning&nbsp; $B$&nbsp; belongs to the interval&nbsp; $I$.
* The end&nbsp; $E$&nbsp; is no longer contained in&nbsp; $I$&nbsp;.
* The interval width is&nbsp; ${\it} {\it \Delta} = E - B$.


Of the infinite number of possible values&nbsp; $r \in I$&nbsp; $($since&nbsp; $r$&nbsp; is real-valued, i.e. not an integer$)$,&nbsp; the numerical value that gets by with the smallest number of bits is selected.&nbsp; Here are two examples for clarification:
* The decimal value &nbsp;$r = 3/4$&nbsp; can be represented with two bits:
:$$r =  1 \cdot 2^{-1}  + 1 \cdot 2^{-2} = 0.75 \hspace{0.3cm}
\Rightarrow\hspace{0.3cm}\text{binary:}\hspace{0.25cm} 0.11\hspace{0.3cm}\Rightarrow\hspace{0.3cm}\text
{Code:} \hspace{0.25cm} \boldsymbol{\rm 11} \hspace{0.05cm}, $$

* The decimal value &nbsp;$r = 1/3$&nbsp;, on the other hand, requires an infinite number of bits:
:$$r =  0 \cdot 2^{-1}  + 1 \cdot 2^{-2} + 1 \cdot 2^{-3}+ 1 \cdot 2^{-4}+ 0 \cdot 2^{-5} + 1 \cdot 2^{-6} + \hspace{0.05cm}\text{...}$$
:$$
\Rightarrow\hspace{0.3cm}\text{binär:} \hspace{0.25cm}0.011101\hspace{0.05cm}\text{...}\hspace{0.3cm}\Rightarrow\hspace{0.3cm}
\text{Code:} \hspace{0.25cm} \boldsymbol{\rm 011101}\hspace{0.05cm}\text{...} \hspace{0.05cm}. $$

In this task we restrict ourselves to the determination of the current interval &nbsp;$I$, marked by the beginning &nbsp;$B$&nbsp; as well as the end &nbsp;$E$&nbsp; and the width &nbsp;${\it \Delta}$ respectively. 
*This determination is done according to the interval nesting in the above diagram.
*The hatching shows that the sequence begins with the ternary symbols&nbsp; $\rm XXY$&nbsp;.
<br clear=all>
The algorithm works as follows:
* Before the beginning&nbsp; (quasi at the zero symbol)&nbsp; the entire probability range is divided into three areas according to the probabilities&nbsp; $p_{\rm X}$,&nbsp; $p_{\rm Y}$&nbsp; and&nbsp; $p_{\rm Z}$&nbsp;.&nbsp; The limits are
:$$B_0 = 0\hspace{0.05cm},\hspace{0.4cm}C_0 = p_{\rm X}\hspace{0.05cm},\hspace{0.4cm}D_0 = p_{\rm X} + p_{\rm Y}\hspace{0.05cm},\hspace{0.4cm} E_0 = p_{\rm X} + p_{\rm Y}+ p_{\rm Z} = 1\hspace{0.05cm}.$$

* The first symbol of the sequence to be coded is&nbsp; $\rm X$. This means: &nbsp; The selected interval is limited by&nbsp; $B_0$&nbsp; and&nbsp; $C_0$&nbsp;.&nbsp; 
*This interval is divided with new beginning&nbsp; $B_1 = B_0$&nbsp; and new end&nbsp; $E_1 = C_0$&nbsp; in the same way as the total range in the zero step.&nbsp; <br>The intermediate values are&nbsp; $C_1$&nbsp; and&nbsp; $D_1$.
* The further interval division is your task.&nbsp; For example, in subtask&nbsp; '''(2)'''&nbsp; the boundaries&nbsp; $B_2$,&nbsp; $C_2$,&nbsp; $D_2$&nbsp; and&nbsp; $E_2$&nbsp; for the second symbol&nbsp; $\rm X$&nbsp;  are to be determined <br>and in subtask&nbsp; '''(3)'''&nbsp; the boundaries&nbsp; $B_3$,&nbsp; $C_3$,&nbsp; $D_3$&nbsp; and&nbsp; $E_3$&nbsp; for the third symbol&nbsp; $\rm Y$ are to be determined.




<u>Hints:</u> 
*The 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#Arithmetic_coding|Arithmetic Coding]].
*The binary representation of the selected interval is dealt with in&nbsp; [[Aufgaben:Exercise_2.11Z:_Arithmetic_Coding_once_again|Exercise 2.11Z]].
 



===Questions===

<quiz display=simple>
{What are the underlying probabilities of the graph?
|type="{}"}
$p_{\rm X} \hspace{0.10cm} = \ $ { 0.7 3% }
$p_{\rm Y} \hspace{0.10cm} =  \ $ { 0.1 3% }
$p_{\rm Z} \hspace{0.15cm} =  \ $ { 0.2 3% }


{What are the range limits after coding the second symbol&nbsp; $\rm X$?
|type="{}"}
$B_2 \hspace{0.12cm} = \ $  { 0. }
$C_2 \hspace{0.15cm} = \ $ { 0.343 1% }
$D_2 \hspace{0.10cm} = \ $ { 0.392 1% }
$E_2 \hspace{0.15cm} = \ $ { 0.49 1% }


{What are the range limits after coding the third symbol&nbsp;  $\rm Y$?
|type="{}"}
$B_3 \hspace{0.12cm} = \ $ { 0.343 1% }
$C_3 \hspace{0.15cm} = \ $ { 0.3773 1% }
$D_3 \hspace{0.10cm} = \ $ { 0.3822 1% }
$E_3 \hspace{0.15cm} = \ $ { 0.392 1% }


{After coding the fourth symbol,&nbsp; $B_4 = 0.343$.&nbsp; What follows from this?
|type="()"}
+ The fourth symbol was&nbsp; $\rm X$.
- The fourth symbol was&nbsp; $\rm Y$.
- The fourth symbol was&nbsp; $\rm Z$.


{After more symbols, the interval is bounded by&nbsp; $B_7  = 0.3564456$&nbsp; and&nbsp; $E_7  = 0.359807$&nbsp;.&nbsp; Which statements are true?

|type="[]"}
- The symbol sequence to be encoded is&nbsp; $\rm XXYXXZX$.
+ The symbol sequence to be encoded is&nbsp; $\rm XXYXXXZ$.
+ The width of the resulting interval is&nbsp; ${\it \Delta} = p_{\rm X}^5 \cdot p_{\rm Y} \cdot p_{\rm Z}$.


{Which real numbers&nbsp; (in binary form)&nbsp; fall into the selected interval?
|type="[]"}
- $r_1 = (0.101100)_{\text{binary}}$,
+ $r_2 = (0.010111)_{\text{binary}}$,
- $r_3 = (0.001011)_{\text{binary}}$.



</quiz>

===Solution===
{{ML-Kopf}}
[[File:EN_Inf_A_2_11_ML.png|right|frame|Interval nesting with all numerical values]]
'''(1)'''&nbsp; From the graph on the information page you can read the probabilities:
:$$p_{\rm X} = 0.7\hspace{0.05cm},\hspace{0.2cm}p_{\rm Y} = 0.1\hspace{0.05cm},\hspace{0.2cm}p_{\rm Z} = 0.2\hspace{0.05cm}.$$


'''(2)'''&nbsp; The second symbol is also&nbsp; $\rm X$.&nbsp; Using the same procedure as in the task description, we get
:$$B_2 \hspace{0.1cm}\underline{= 0}\hspace{0.05cm},\hspace{0.2cm}C_2 = 0.49 \cdot 0.7 \hspace{0.1cm}\underline{= 0.343}\hspace{0.05cm},\hspace{0.2cm}
D_2 \hspace{0.1cm} \underline{= 0.392}\hspace{0.05cm},\hspace{0.2cm}E_2 = C_1  \hspace{0.1cm}\underline{= 0.49} \hspace{0.05cm}.$$


'''(3)'''&nbsp; For the third symbol&nbsp; $\rm Y$&nbsp; the limitations&nbsp; $B_3 = C_2$&nbsp;  and&nbsp; $E_3 = D_2$ now apply:
:$$B_3 \hspace{0.1cm}\underline{= 0.343}\hspace{0.05cm},\hspace{0.2cm}C_3 \hspace{0.1cm}\underline{= 0.3773}\hspace{0.05cm},\hspace{0.2cm}
D_3 \hspace{0.1cm} \underline{= 0.3822}\hspace{0.05cm},\hspace{0.2cm}E_3  \hspace{0.1cm}\underline{= 0.392} \hspace{0.05cm}.$$


'''(4)'''&nbsp;<u>Solution suggestion 1</u> is correct:
*From&nbsp; $B_4 = 0.343 = B_3$&nbsp; (to be read in the diagram on the data sheet) it follows that the fourth source symbol was an&nbsp; $\rm X$. 


'''(5)'''&nbsp; <u>Proposed solutions 2 and 3</u> are correct:
*The graph shows the interval nesting with all previous results.&nbsp; You can see from the hatching that the second suggested solution gives the correct sequence of symbols:  &nbsp; $\rm XXYXXXZ$.
* The interval width&nbsp; $\it \Delta$&nbsp; can really be determined according to suggestion 3. It holds:
:$${\it \Delta}  = 0.359807 - 0.3564456 = 0.003614 \hspace{0.05cm},$$
:$$\Rightarrow \hspace{0.3cm} {\it \Delta} =p_{\rm X}^5 \cdot p_{\rm Y} \cdot p_{\rm Z} = 0.7^5 \cdot 0.1 \cdot 0.2 = 0.003614 
\hspace{0.05cm}. $$

'''(6)'''&nbsp; Correct is the <u>proposed solution 2</u> &nbsp; &rArr; &nbsp; $r_2 = (0.010111)_{\text{binary}}$, because of:
:$$r_2 =  0 \cdot 2^{-1}  + 1 \cdot 2^{-2} + 0 \cdot 2^{-3}+ 1 \cdot 2^{-4}+ 1 \cdot 2^{-5} + 1 \cdot 2^{-6} = 0.359375\hspace{0.05cm}. $$ 
*Proposition 1: &nbsp; $r_1 = (0.101100)_{\text{binary}}$&nbsp; must be ruled out because the associated decimal value is&nbsp; $r_1 > (0.5)_{\text{decimal}}$&nbsp;.
*The last suggested solution is also wrong, since&nbsp; $r_3 = (0.001011)_{\text{binary}} < (0.01)_{\text{binary}} = (0.25)_{\text{decimal}}$.


{{ML-Fuß}}



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