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

From LNTwww
m (Text replacement - "Category:Aufgaben zu Informationstheorie" to "Category:Information Theory: Exercises")
 
(11 intermediate revisions by 2 users not shown)
Line 1: Line 1:
  
{{quiz-Header|Buchseite=Informationstheorie/Weitere Quellencodierverfahren
+
{{quiz-Header|Buchseite=Information_Theory/Further_Source_Coding_Methods
 
}}
 
}}
  
[[File:P_ID2468__Inf_A_2_11.png|right|frame|Intervallschachtelung bei <br>arithmetischer Codierung]]
+
[[File:EN_Inf_A_2_11_v3.png|right|frame|Interval nesting for arithmetic coding]]
Die arithmetische Codierung ist eine spezielle Form der Entropiecodierung: &nbsp;  Die Symbolwahrscheinlichkeiten müssen auch hier bekannt sein.&nbsp; In dieser Aufgabe gehen wir von&nbsp; $M = 3$&nbsp; Symbolen aus, die wir mit&nbsp; $\rm X$,&nbsp; $\rm Y$&nbsp; und  $\rm Z$&nbsp; benennen.
+
Arithmetic coding is a special form of entropy coding: &nbsp;  The symbol probabilities must also be known here.&nbsp;  
  
Während die Huffman&ndash;Codierung symbolweise erfolgt, wird bei der Arithmetischen Codierung&nbsp; $(\rm AC)$&nbsp; eine Symbolfolge der Länge&nbsp; $N$&nbsp; gemeinsam codiert.&nbsp; Das Codierergebnis ist ein reeller Zahlenwert&nbsp; $r$&nbsp; 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;
 +
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}.$$
 
:$$I = \big[B, \ E \big) = \big[B, \ B +{\it \Delta} \big)\hspace{0.05cm}.$$
Diese Notation bedeutet:
+
This notation means:
* Der Beginn&nbsp; $B$&nbsp; gehört zum Intervall&nbsp; $I$.
+
* The beginning&nbsp; $B$&nbsp; belongs to the interval&nbsp; $I$.
* Das Ende&nbsp; $E$&nbsp; ist nicht mehr in&nbsp; $I$&nbsp; enthalten.
+
* The end&nbsp; $E$&nbsp; is no longer contained in&nbsp; $I$&nbsp;.
* Die Intervallbreite ist&nbsp; ${\it} \Delta = E - B$.
+
* The interval width is&nbsp; ${\it} {\it \Delta} = E - B$.
  
  
Von den unendlich vielen möglichen Werten&nbsp; $r \in I$&nbsp; $($da&nbsp; $r$&nbsp; reellwertig ist, also kein Integer$)$&nbsp; wird derjenige Zahlenwert ausgewählt, der mit der geringsten Bitanzahl auskommt.&nbsp; Hierzu zwei Beispiele zur Verdeutlichung:
+
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:
* Der Dezimalwert &nbsp;$r = 3/4$&nbsp; lässt sich mit zwei Bit darstellen:
+
* 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}
 
:$$r =  1 \cdot 2^{-1}  + 1 \cdot 2^{-2} = 0.75 \hspace{0.3cm}
\Rightarrow\hspace{0.3cm}\text{binär:}\hspace{0.25cm} 0.11\hspace{0.3cm}\Rightarrow\hspace{0.3cm}\text
+
\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}, $$
 
{Code:} \hspace{0.25cm} \boldsymbol{\rm 11} \hspace{0.05cm}, $$
  
* Der Dezimalwert &nbsp;$r = 1/3$&nbsp; benötigt dagegen unendlich viele Bit:
+
* 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{...}$$
 
:$$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.3cm}\Rightarrow\hspace{0.3cm}
+
\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{Code:} \hspace{0.25cm} \boldsymbol{\rm 011101}\hspace{0.05cm}\text{...} \hspace{0.05cm}. $$
  
In dieser Aufgabe beschränken wir uns auf die Bestimmung des aktuellen Intervalls &nbsp;$I$, gekennzeichnet durch den Beginn &nbsp;$B$&nbsp; sowie dem Ende &nbsp;$E$&nbsp; bzw. der Breite &nbsp;$\Delta$.  
+
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.  
*Diese Bestimmung geschieht entsprechend der Intervallschachtelung in obiger Grafik.  
+
*This determination is done according to the interval nesting in the above diagram.
*An der Schraffierung ist zu erkennen, dass die Folge mit  den Ternärsymbolen&nbsp; $\rm XXY$&nbsp; beginnt.
+
*The hatching shows that the sequence begins with the ternary symbols&nbsp; $\rm XXY$&nbsp;.
 
<br clear=all>
 
<br clear=all>
Der Algorithmus funktioniert wie folgt:
+
The algorithm works as follows:
* Vor Beginn&nbsp; (quasi beim nullten Symbol)&nbsp; wird der gesamte Wahrscheinlichkeitsbereich nach den Wahrscheinlichkeiten&nbsp; $p_{\rm X}$,&nbsp; $p_{\rm Y}$&nbsp; und&nbsp; $p_{\rm Z}$&nbsp; in drei Bereiche unterteilt.&nbsp; Die Grenzen liegen bei
+
* 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}.$$
 
:$$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}.$$
  
* Das erste Symbol der zu codierenden Folge ist&nbsp; $\rm X$. Das bedeutet: &nbsp; das ausgewählte Intervall wird  durch&nbsp; $B_0$&nbsp; und&nbsp; $C_0$&nbsp; begrenzt.&nbsp; Dieses Intervall wird mit neuem Beginn&nbsp; $B_1 = B_0$&nbsp; und neuem Ende&nbsp; $E_1 = C_0$&nbsp; in gleicher Weise aufgeteilt wie der Gesamtbereich im nullten Schritt.&nbsp; Die Zwischenwerte sind&nbsp; $C_1$&nbsp; und&nbsp; $D_1$.
+
* 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;  
* Die weitere Intervall&ndash;Aufteilung ist Ihre Aufgabe.&nbsp; Beispielsweise sollen in der Teilaufgabe&nbsp; '''(2)'''&nbsp; die Grenzen&nbsp; $B_2$,&nbsp; $C_2$,&nbsp; $D_2$&nbsp; und&nbsp; $E_2$&nbsp; für das zweite Symbol&nbsp; $\rm X$&nbsp;  ermittelt werden und in der Teilaufgabe&nbsp; '''(3)'''&nbsp; die Grenzen&nbsp; $B_3$,&nbsp; $C_3$,&nbsp; $D_3$&nbsp; und&nbsp; $E_3$&nbsp; für das dritte Symbol&nbsp; $\rm Y$.
+
*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.
  
  
  
  
''Hinweise:''
+
<u>Hints:</u>
*Die Aufgabe gehört zum  Kapitel&nbsp; [[Information_Theory/Weitere_Quellencodierverfahren|Weitere Quellencodierverfahren]].
+
*The exercise belongs to the chapter&nbsp; [[Information_Theory/Further_Source_Coding_Methods|Further source coding methods]].
*Insbesondere wird  Bezug genommen auf die Seite&nbsp; [[Information_Theory/Weitere_Quellencodierverfahren#Arithmetische_Codierung|Arithmetische Codierung]].
+
*In particular, reference is made to the page&nbsp; [[Information_Theory/Further_Source_Coding_Methods#Arithmetic_coding|Arithmetic Coding]].
*Die Binärdarstellung des ausgewählten Intervalls wird in der&nbsp; [[Aufgaben:Aufgabe_2.11:_Nochmals_Arithmetische_Codierung|Aufgabe 2.11Z]]&nbsp; behandelt.
+
*The binary representation of the selected interval is dealt with in&nbsp; [[Aufgaben:Exercise_2.11Z:_Arithmetic_Coding_once_again|Exercise 2.11Z]].
 
   
 
   
  
  
  
===Fragebogen===
+
===Questions===
  
 
<quiz display=simple>
 
<quiz display=simple>
{Welche Wahrscheinlichkeiten liegen der Grafik zugrunde?
+
{What are the underlying probabilities of the graph?
 
|type="{}"}
 
|type="{}"}
 
$p_{\rm X} \hspace{0.10cm} = \ $ { 0.7 3% }
 
$p_{\rm X} \hspace{0.10cm} = \ $ { 0.7 3% }
Line 58: Line 60:
  
  
{Wie lauten die Bereichsgrenzen nach der Codierung des zweiten Symbols&nbsp; $\rm X$?
+
{What are the range limits after coding the second symbol&nbsp; $\rm X$?
 
|type="{}"}
 
|type="{}"}
 
$B_2 \hspace{0.12cm} = \ $  { 0. }
 
$B_2 \hspace{0.12cm} = \ $  { 0. }
Line 66: Line 68:
  
  
{Wie lauten die Bereichsgrenzen nach der Codierung des dritten Symbols&nbsp;  $\rm Y$?
+
{What are the range limits after coding the third symbol&nbsp;  $\rm Y$?
 
|type="{}"}
 
|type="{}"}
 
$B_3 \hspace{0.12cm} = \ $ { 0.343 1% }
 
$B_3 \hspace{0.12cm} = \ $ { 0.343 1% }
Line 74: Line 76:
  
  
{Nach der Codierung des vierten Symbols ist&nbsp; $B_4 = 0.343$.&nbsp; Was folgt daraus?
+
{After coding the fourth symbol,&nbsp; $B_4 = 0.343$.&nbsp; What follows from this?
 
|type="()"}
 
|type="()"}
+ Das vierte Symbol war&nbsp; $\rm X$.
+
+ The fourth symbol was&nbsp; $\rm X$.
- Das vierte Symbol war&nbsp; $\rm Y$.
+
- The fourth symbol was&nbsp; $\rm Y$.
- Das vierte Symbol war&nbsp; $\rm Z$.
+
- The fourth symbol was&nbsp; $\rm Z$.
  
  
{Nach weiteren Symbolen wird das Intervall durch&nbsp; $B_7  = 0.3564456$&nbsp; und&nbsp; $E_7  = 0.359807$&nbsp; begrenzt.&nbsp; Welche Aussagen treffen zu?
+
{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="[]"}
 
|type="[]"}
- Die zur Codierung anstehende Symbolfolge lautet&nbsp; $\rm XXYXXZX$.
+
- The symbol sequence to be encoded is&nbsp; $\rm XXYXXZX$.
+ Die zur Codierung anstehende Symbolfolge lautet&nbsp; $\rm XXYXXXZ$.
+
+ The symbol sequence to be encoded is&nbsp; $\rm XXYXXXZ$.
+ Die Breite des resultierenden Intervalls ist&nbsp; ${\it \Delta} = p_{\rm X}^5 \cdot p_{\rm Y} \cdot p_{\rm Z}$.
+
+ 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="[]"}
- $r_1 = (0.101100)_{\text{binär}}$,
+
- $r_1 = (0.101100)_{\text{binary}}$,
+ $r_2 = (0.010111)_{\text{binär}}$,
+
+ $r_2 = (0.010111)_{\text{binary}}$,
- $r_3 = (0.001011)_{\text{binär}}$.
+
- $r_3 = (0.001011)_{\text{binary}}$.
  
  
Line 98: Line 101:
 
</quiz>
 
</quiz>
  
===Musterlösung===
+
===Solution===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
[[File:P_ID2469__Inf_A_2_11_ML.png|right|frame|Intervallschachtelung mit allen Zahlenwerten]]
+
[[File:EN_Inf_A_2_11_ML_vers2.png|right|frame|Interval nesting with all numerical values]]
'''(1)'''&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}.$$
  
  
 
+
'''(2)'''&nbsp; The second symbol is also&nbsp; $\rm X$.&nbsp; Using the same procedure as in the task description, we get
'''(2)'''&nbsp; Auch das zweite Symbol ist&nbsp; $\rm X$.&nbsp; 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},\hspace{0.2cm}
 
:$$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}.$$
 
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:
'''(3)'''&nbsp; Für das  dritte Symbol&nbsp; $\rm Y$&nbsp; gelten nun die Begrenzungen&nbsp; $B_3 = C_2$&nbsp;  und&nbsp; $E_3 = D_2$:
 
 
:$$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}
 
:$$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}.$$
 
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:
'''(4)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 1</u>:
+
*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$.  
Aus&nbsp; $B_4 = 0.343 = B_3$&nbsp; (abzulesen in der Grafik auf dem Angabenblatt) folgt zwingend, dass das vierte  Quellensymbol ein&nbsp; $\rm X$&nbsp; war.  
 
  
  
 
+
'''(5)'''&nbsp; <u>Proposed solutions 2 and 3</u> are correct:
'''(5)'''&nbsp; Richtig sind die <u>Lösungsvorschläge 2 und 3:</u>
+
*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$.
*Die Grafik zeigt die Intervallschachtelung mit allen bisherigen Ergebnissen.&nbsp; Man erkennt aus der Schraffierung, dass der zweite Lösungsvorschlag die richtige Symbolfolge angibt:  &nbsp; $\rm XXYXXXZ$.
+
* The interval width&nbsp; $\it \Delta$&nbsp; can really be determined according to suggestion 3. It holds:
* Die Intervallbreite&nbsp; $\it \Delta$&nbsp; kann wirklich gemäß dem Vorschlag 3 ermittelt werden. Es gilt:
 
 
:$${\it \Delta}  = 0.359807 - 0.3564456 = 0.003614 \hspace{0.05cm},$$
 
:$${\it \Delta}  = 0.359807 - 0.3564456 = 0.003614 \hspace{0.05cm},$$
:$${\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  
+
:$$\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}. $$
  
 
+
'''(6)'''&nbsp; Correct is the <u>proposed solution 2</u> &nbsp; &rArr; &nbsp; $r_2 = (0.010111)_{\text{binary}}$, because of:
'''(6)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 2</u> &nbsp; &rArr; &nbsp; $r_2 = (0.010111)_{\text{binär}}$, 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}. $$  
 
:$$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}. $$  
*Der Vorschlag 1: &nbsp; $r_1 = (0.101100)_{\text{binär}}$&nbsp; ist auszuschließen, da der zugehörige Dezimalwert&nbsp; $r_1 > 0.5$&nbsp; ist.  
+
*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;.
*Auch der letzte Lösungsvorschlag ist falsch, da&nbsp; $r_3 = (0.001011)_{\text{binär}} < (0.01)_{\text{binär}} = (0.25)_{\text{dezimal}}$&nbsp; sein wird.
+
*The last suggested solution is also wrong, since&nbsp; $r_3 = (0.001011)_{\text{binary}} < (0.01)_{\text{binary}} = (0.25)_{\text{decimal}}$.
  
  
Line 141: Line 139:
  
  
[[Category:Information Theory: Exercises|^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}}$.