Difference between revisions of "Aufgaben:Exercise 2.11: Arithmetic Coding"

From LNTwww
 
(29 intermediate revisions by 5 users not shown)
Line 1: Line 1:
  
{{quiz-Header|Buchseite=Informationstheorie und Quellencodierung/Weitere Quellencodierverfahren
+
{{quiz-Header|Buchseite=Information_Theory/Further_Source_Coding_Methods
 
}}
 
}}
  
[[File:P_ID2468__Inf_A_2_11.png|right|]]
+
[[File:EN_Inf_A_2_11_v3.png|right|frame|Interval nesting for arithmetic coding]]
Die arithmetische Codierung ist eine spezielle Form der Entropiecodierung: Auch hier müssen die Symbolwahrscheinlichkeiten bekannt sein. In dieser Aufgabe gehen wir von <i>M</i> = 3 Symbolen aus, die wir mit <b>X</b>, <b>Y</b>, <b>Z</b> benennen.
+
Arithmetic coding is a special form of entropy coding: &nbsp;  The symbol probabilities must also be known here.&nbsp;
  
Im Gegensatz zur Huffman&ndash;Codierung wird bei der Arithmetischen Codierung (AC) eine Symbolfolge der Länge <i>N</i> gemeinsam codiert. Das Codierergebnis ist ein reeller Zahlenwert <i>r</i> aus dem Intervall
+
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;
:$$I = [B, E) = [B, B +{\it \Delta} )\hspace{0.05cm}.$$
+
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
Diese Notation bedeutet:
+
:$$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$.
  
:* Der Beginn <i>B</i> gehört zum Intervall <i>I</i>.
 
  
:* Das Ende <i>E</i> ist nicht mehr in <i>I</i> enthalten.
+
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}, $$
  
:* Die Intervallbreite ist <i>&Delta;</i> = <i>E</i> &ndash; <i>B</i>.
+
* 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}. $$
  
Von den unendlich vielen möglichen Werten <i>r</i> &#8712; <i>I</i> (da <i>r</i> reellwertig ist, also kein Integer) wird derjenige Zahlenwert ausgewählt, der mit der geringsten Bitanzahl auskommt. Hierzu zwei Beispiele zur Verdeutlichung:
+
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}.$$
  
:* Der Dezimalwert <i>r</i> = 3/4 lässt sich mit zwei Bit darstellen:
+
* 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;
:$$r = 1 \cdot 2^{-1}  + 1 \cdot 2^{-2} = 0.75 $$
+
*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$.
:$$\Rightarrow\hspace{0.3cm}{\rm bin\ddot{a}r: 0.11}\hspace{0.3cm}\Rightarrow\hspace{0.3cm}
+
* 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.
{\rm Code:} \hspace{0.15cm} \boldsymbol{\rm 11} \hspace{0.05cm}, $$
 
  
:* Der Dezimalwert <i>r</i> = 1/3 benötigt dagegen unendlich viele Bit:
 
:$$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}... $$
 
:$$\Rightarrow\hspace{0.3cm}{\rm bin\ddot{a}r: 0.011101}\hspace{0.3cm}\Rightarrow\hspace{0.3cm}
 
{\rm Code:} \hspace{0.15cm} \boldsymbol{\rm 011101} \hspace{0.05cm}. $$
 
  
In dieser Aufgabe beschränken wir uns auf die Bestimmung des aktuellen Intervalls <i>I</i>, gekennzeichnet durch den Beginn <i>B</i> sowie dem Ende <i>E</i> bzw. der Breite <i>&Delta;</i>. Diese Bestimmung geschieht entsprechend der Intervallschachtelung in obiger Grafik. An der Schraffierung ist zu erkennen, dass die Folge mit  den Ternärsymbolen <b>XXY</b> beginnt.
 
  
Der Algorithmus funktioniert wie folgt:
 
  
:* Vor Beginn (quasi beim Symbol 0) wird der gesamte Wahrscheinlichkeitsbereich nach den Wahrscheinlichkeiten <i>p</i><sub>X</sub>, <i>p</i><sub>Y</sub> und <i>p</i><sub>Z</sub> in drei Bereiche unterteilt. Die Grenzen liegen bei
+
<u>Hints:</u>  
:$$B_0 = 0\hspace{0.05cm},\hspace{0.2cm}C_0 = p_{\rm X}\hspace{0.05cm},\hspace{0.2cm}D_0 = p_{\rm X} + p_{\rm Y}\hspace{0.05cm},\hspace{0.2cm}
+
*The exercise belongs to the chapter&nbsp; [[Information_Theory/Further_Source_Coding_Methods|Further source coding methods]].
  E_0 = p_{\rm X} + p_{\rm Y}+ p_{\rm Z} = 1\hspace{0.05cm}.$$
+
*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]].
 +
   
  
:* Das erste Symbol ist <b>X</b> &nbsp;&#8658;&nbsp; das ausgewählte Intervall wird  durch <i>B</i><sub>0</sub> und <i>C</i><sub>0</sub> begrenzt. Dieses Intervall wird mit neuem Beginn <i>B</i><sub>1</sub> = <i>B</i><sub>0</sub> und neuem Ende <i>E</i><sub>1</sub> = <i>C</i><sub>0</sub> in gleicher Weise aufgeteilt wie der Gesamtbereich im Schritt 0. Die Zwischenwerte sind <i>C</i><sub>1</sub> und <i>D</i><sub>1</sub>.
 
  
:* Die weitere Intervall&ndash;Aufteilung ist Ihre Aufgabe. Beispielsweise sollen in der Teilaufgabe (2) die Grenzen <i>B</i><sub>2</sub>, <i>C</i><sub>2</sub>, <i>D</i><sub>2</sub>, <i>E</i><sub>2</sub> für das zweite Symbol <b>X</b> und in der Teilaufgabe (3) die Grenzen <nobr><i>B</i><sub>3</sub>, <i>C</i><sub>3</sub>, <i>D</i><sub>3</sub>, <i>E</i><sub>3</sub></nobr> für das dritte Symbol <b>Y</b> ermittelt werden.
 
  
<b>Hinweis:</b> Die Aufgabe bezieht sich auf die Seite 2a und die Seite 2b in Kapitel 2.4. Die Binärdarstellung des ausgewählten Intervalls wird in Aufgabe A2.12 behandelt.
+
===Questions===
 
 
 
 
===Fragebogen===
 
  
 
<quiz display=simple>
 
<quiz display=simple>
{Welche Wahrscheinlichkeiten sind der Grafik zugrundegelegt?
+
{What are the underlying probabilities of the graph?
 
|type="{}"}
 
|type="{}"}
$p_X$ = { 0.7 3% }
+
$p_{\rm X} \hspace{0.10cm} = \ $ { 0.7 3% }
$p_Y$ = { 0.1 3% }
+
$p_{\rm Y} \hspace{0.10cm} =  \ $ { 0.1 3% }
$p_Z$ = { 0.2 3% }
+
$p_{\rm Z} \hspace{0.15cm} =  \ $ { 0.2 3% }
  
  
{Wie lauten die Bereichsgrenzen nach der Codierung des zweiten Symbols?
+
{What are the range limits after coding the second symbol&nbsp; $\rm X$?
 
|type="{}"}
 
|type="{}"}
2. Symbol ist „X”: $B_2$ = { 0 3% }
+
$B_2 \hspace{0.12cm} = \ $ { 0. }
$C_2$ = { 0.343 3% }
+
$C_2 \hspace{0.15cm} = \ $ { 0.343 1% }
$D_2$ = { 0.392 3% }
+
$D_2 \hspace{0.10cm} = \ $ { 0.392 1% }
$E_2$ = { 0.49 3% }
+
$E_2 \hspace{0.15cm} = \ $ { 0.49 1% }
  
  
{Wie lauten die Bereichsgrenzen nach der Codierung des dritten Symbols?
+
{What are the range limits after coding the third symbol&nbsp;  $\rm Y$?
 
|type="{}"}
 
|type="{}"}
3. Symbol ist „Y”: $B_3$ = { 0.343 3% }
+
$B_3 \hspace{0.12cm} = \ $ { 0.343 1% }
$C_3$ = { 0.3773 3% }
+
$C_3 \hspace{0.15cm} = \ $ { 0.3773 1% }
$D_3$ = { 0.3822 3% }
+
$D_3 \hspace{0.10cm} = \ $ { 0.3822 1% }
$E_3$ = { 0.392 3% }
+
$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$.
  
{Nach der Codierung des vierten Symbols ist <i>B</i><sub>4</sub> = 0.343. Was folgt daraus?
 
|type="[]"}
 
+ Das vierte Symbol war <b>X</b>.
 
- Das vierte Symbol war <b>Y</b>.
 
- Das vierte Symbol war <b>Z</b>.
 
  
 +
{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?
  
{Nach weiteren Symbolen wird das Ergebnisintervall durch <i>B</i><sub>7</sub> = 0.3564456 und <i>E</i><sub>7</sub> = 0.359807 begrenzt. Welche Aussagen treffen zu?
 
 
|type="[]"}
 
|type="[]"}
- Die zur Codierung anstehende Symbolfolge lautet <b>XXYXXZX</b>.
+
- The symbol sequence to be encoded is&nbsp; $\rm XXYXXZX$.
+ Die zur Codierung anstehende Symbolfolge lautet <b>XXYXXXZ</b>.
+
+ The symbol sequence to be encoded is&nbsp; $\rm XXYXXXZ$.
+ Die Breite des resultierenden Intervalls ist <i>&Delta;</i> = <i>p</i><sub><sub>X</sub></sub><sup>5</sup> &middot; <i>p</i><sub><sub>Y</sub></sub> &middot; <i>p</i><sub><sub>Z</sub></sub>.
+
+ The width of the resulting interval is&nbsp; ${\it \Delta} = p_{\rm X}^5 \cdot p_{\rm Y} \cdot p_{\rm Z}$.
  
  
{Welche reellen Zahlen (in Binärform) fallen in das ausgewählte Intervall?
+
{Which real numbers&nbsp; (in binary form)&nbsp; fall into the selected interval?
 
|type="[]"}
 
|type="[]"}
- <i>r</i><sub>1</sub> = (0.101100)<sub>binär</sub>
+
- $r_1 = (0.101100)_{\text{binary}}$,
+ <i>r</i><sub>2</sub> = (0.010111)<sub>binär</sub>
+
+ $r_2 = (0.010111)_{\text{binary}}$,
- <i>r</i><sub>3</sub> = (0.001011)<sub>binär</sub>
+
- $r_3 = (0.001011)_{\text{binary}}$.
  
  
Line 93: Line 101:
 
</quiz>
 
</quiz>
  
===Musterlösung===
+
===Solution===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
[[File:P_ID2469__Inf_A_2_11_ML.png|right|]]
+
[[File:EN_Inf_A_2_11_ML_vers2.png|right|frame|Interval nesting with all numerical values]]
<b>1.</b>&nbsp;&nbsp;Aus der Grafik auf der Angabenseite kann man die Wahrscheinlichkeiten ablesen:
+
'''(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}.$$
 
:$$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}.$$
  
<b>2.</b>&nbsp;&nbsp;Auch das zweite Symbol ist <b>X</b>. Bei gleichem Vorgehen wie in der Aufgabenbeschreibung erhält man
 
:$$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},$$
 
:$$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}.$$
 
  
<b>3.</b>&nbsp;&nbsp;Aufgrund von  <b>Y</b> als drittes Symbol gelten nun die Begrenzungen <i>B</i><sub>3</sub> = <i>C</i><sub>2</sub>  und <i>E</i><sub>3</sub> = <i>D</i><sub>2</sub>:
+
'''(2)'''&nbsp; The second symbol is also&nbsp; $\rm X$.&nbsp; Using the same procedure as in the task description, we get
:$$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},$$
+
:$$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_3 \hspace{0.1cm} \underline{= 0.3822}\hspace{0.05cm},\hspace{0.2cm}E_3 \hspace{0.1cm}\underline{= 0.392} \hspace{0.05cm}.$$
+
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}.$$
  
<b>4.</b>&nbsp;&nbsp;Aus <i>B</i><sub>4</sub> = 0.343 = <i>B</i><sub>3</sub> (abzulesen in der Grafik auf dem Angabenblatt) folgt zwingend, dass das vierte zu codierende Quellensymbol ein <b>X</b> war &#8658; <u>Lösungsvorschlag 1.</u>
 
  
<b>5.</b>&nbsp;&nbsp;Die Grafik zeigt die Intervallschachtelung mit allen bisherigen Ergebnissen.
+
'''(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}.$$
  
:* Man erkennt aus der Schraffierung, dass der zweite Lösungsvorschlag die richtige Symbolfolge angibt:  <b>XXYXXXZ</b>.
 
  
:* Die Intervallbreite <i>&Delta;</i> kann wirklich gemäß dem Lösungsvorschlag 3 ermittelt werden:
+
'''(4)'''&nbsp;<u>Solution suggestion 1</u> is correct:
:$${\it \Delta}  \hspace{0.2cm} = \hspace{0.2cm} 0.359807 - 0.3564456 = 0.003614 \hspace{0.05cm},\\
+
*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$.
{\it \Delta} \hspace{0.2cm} \hspace{0.2cm} p_{\rm X}^5 \cdot p_{\rm Y} \cdot p_{\rm Z} = 0.7^5 \cdot 0.1 \cdot 0.2 = 0.003614  
+
 
 +
 
 +
'''(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}. $$
 
\hspace{0.05cm}. $$
Richtig sind somit die <u>Lösungsvorschläge 2 und 3.</u>
 
  
<b>6.</b>&nbsp;&nbsp;Der Vorschlag 1: (0.101100)<sub>binär</sub> ist auszuschließen, da der zugehörige Dezimalwert <i>r</i><sub>1</sub> > 0.5 ist. Auch der letzte Lösungsvorschlag ist falsch, da (0.001011)<sub>binär</sub> < (0.01)<sub>binär</sub> = 0.25<sub>dezimal</sub> gilt.
+
'''(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}}$.
 +
 
  
Richtig ist der <u>Lösungsvorschlag 2</u>: (0.010111)<sub>binär</sub>, wegen:
 
:$$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}. $$
 
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  
  
  
[[Category:Aufgaben zu Informationstheorie|^2.4 Weitere Quellencodierverfahren^]]
+
[[Category:Information Theory: Exercises|^2.4 Further Source Coding Methods^]]

Latest revision as of 16:14, 30 August 2021

Interval nesting for arithmetic coding

Arithmetic coding is a special form of entropy coding:   The symbol probabilities must also be known here. 

In this exercise, we assume  $M = 3$  symbols, which we name with  $\rm X$,  $\rm Y$  and $\rm Z$.  While Huffman coding is done symbol by symbol, in Arithmetic Coding  $(\rm AC)$  a sequence of symbols of length  $N$  is encoded together.  The coding result is a real numerical value  $r$  from the interval

$$I = \big[B, \ E \big) = \big[B, \ B +{\it \Delta} \big)\hspace{0.05cm}.$$

This notation means:

  • The beginning  $B$  belongs to the interval  $I$.
  • The end  $E$  is no longer contained in  $I$ .
  • The interval width is  ${\it} {\it \Delta} = E - B$.


Of the infinite number of possible values  $r \in I$  $($since  $r$  is real-valued, i.e. not an integer$)$,  the numerical value that gets by with the smallest number of bits is selected.  Here are two examples for clarification:

  • The decimal value  $r = 3/4$  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  $r = 1/3$ , 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  $I$, marked by the beginning  $B$  as well as the end  $E$  and the width  ${\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  $\rm XXY$ .


The algorithm works as follows:

  • Before the beginning  (quasi at the zero symbol)  the entire probability range is divided into three areas according to the probabilities  $p_{\rm X}$,  $p_{\rm Y}$  and  $p_{\rm Z}$ .  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  $\rm X$. This means:   The selected interval is limited by  $B_0$  and  $C_0$ . 
  • This interval is divided with new beginning  $B_1 = B_0$  and new end  $E_1 = C_0$  in the same way as the total range in the zero step. 
    The intermediate values are  $C_1$  and  $D_1$.
  • The further interval division is your task.  For example, in subtask  (2)  the boundaries  $B_2$,  $C_2$,  $D_2$  and  $E_2$  for the second symbol  $\rm X$  are to be determined
    and in subtask  (3)  the boundaries  $B_3$,  $C_3$,  $D_3$  and  $E_3$  for the third symbol  $\rm Y$ are to be determined.



Hints:



Questions

1

What are the underlying probabilities of the graph?

$p_{\rm X} \hspace{0.10cm} = \ $

$p_{\rm Y} \hspace{0.10cm} = \ $

$p_{\rm Z} \hspace{0.15cm} = \ $

2

What are the range limits after coding the second symbol  $\rm X$?

$B_2 \hspace{0.12cm} = \ $

$C_2 \hspace{0.15cm} = \ $

$D_2 \hspace{0.10cm} = \ $

$E_2 \hspace{0.15cm} = \ $

3

What are the range limits after coding the third symbol  $\rm Y$?

$B_3 \hspace{0.12cm} = \ $

$C_3 \hspace{0.15cm} = \ $

$D_3 \hspace{0.10cm} = \ $

$E_3 \hspace{0.15cm} = \ $

4

After coding the fourth symbol,  $B_4 = 0.343$.  What follows from this?

The fourth symbol was  $\rm X$.
The fourth symbol was  $\rm Y$.
The fourth symbol was  $\rm Z$.

5

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

The symbol sequence to be encoded is  $\rm XXYXXZX$.
The symbol sequence to be encoded is  $\rm XXYXXXZ$.
The width of the resulting interval is  ${\it \Delta} = p_{\rm X}^5 \cdot p_{\rm Y} \cdot p_{\rm Z}$.

6

Which real numbers  (in binary form)  fall into the selected interval?

$r_1 = (0.101100)_{\text{binary}}$,
$r_2 = (0.010111)_{\text{binary}}$,
$r_3 = (0.001011)_{\text{binary}}$.


Solution

Interval nesting with all numerical values

(1)  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)  The second symbol is also  $\rm X$.  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)  For the third symbol  $\rm Y$  the limitations  $B_3 = C_2$  and  $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) Solution suggestion 1 is correct:

  • From  $B_4 = 0.343 = B_3$  (to be read in the diagram on the data sheet) it follows that the fourth source symbol was an  $\rm X$.


(5)  Proposed solutions 2 and 3 are correct:

  • The graph shows the interval nesting with all previous results.  You can see from the hatching that the second suggested solution gives the correct sequence of symbols:   $\rm XXYXXXZ$.
  • The interval width  $\it \Delta$  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)  Correct is the proposed solution 2   ⇒   $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:   $r_1 = (0.101100)_{\text{binary}}$  must be ruled out because the associated decimal value is  $r_1 > (0.5)_{\text{decimal}}$ .
  • The last suggested solution is also wrong, since  $r_3 = (0.001011)_{\text{binary}} < (0.01)_{\text{binary}} = (0.25)_{\text{decimal}}$.