Aufgaben:Exercise 2.11: Arithmetic Coding - Revision history

Guenter at 15:14, 30 August 2021

2021-08-30T15:14:24Z

Guenter at 13:31, 12 August 2021

2021-08-12T13:31:34Z

Guenter at 13:22, 12 August 2021

2021-08-12T13:22:22Z

Guenter at 13:19, 12 August 2021

2021-08-12T13:19:01Z

Guenter at 13:04, 12 August 2021

2021-08-12T13:04:07Z

Guenter at 12:33, 12 August 2021

2021-08-12T12:33:33Z

Noah at 20:09, 10 August 2021

2021-08-10T20:09:11Z

Noah at 21:12, 6 August 2021

2021-08-06T21:12:38Z

Show changes

Guenter at 13:03, 16 July 2021

2021-07-16T13:03:48Z

Guenter at 16:06, 8 July 2021

2021-07-08T16:06:29Z

@@ Line 103: / Line 103: @@
 ===Solution===
 {{ML-Kopf}}
-[[File:EN_Inf_A_2_11_ML.png|right|frame|Interval nesting with all numerical values]]
+[[File:EN_Inf_A_2_11_ML_vers2.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}.$$

@@ Line 42: / Line 42: @@
-Hints:
+<u>Hints:</u>
-*The task belongs to the chapter&nbsp; [[Information_Theory/Further_Source_Coding_Methods|Further source coding methods]].
+*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]].
@@ Line 106: / Line 106: @@
 '''(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}.$$
@@ Line 112: / Line 111: @@
 :$$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}.$$
@@ Line 118: / Line 116: @@
 :$$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$&nbsp; war.
+*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$.
@@ Line 130: / Line 126: @@
 * 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},$$
-:$${\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}. $$
 '''(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$&nbsp;.
+*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}}$&nbsp; will be.
+*The last suggested solution is also wrong, since&nbsp; $r_3 = (0.001011)_{\text{binary}} < (0.01)_{\text{binary}} = (0.25)_{\text{decimal}}$.

@@ Line 45: / Line 45: @@
 *The task 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]]&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]].
@@ Line 86: / Line 86: @@
 |type="[]"}
-- The symbol sequence to be coded is&nbsp; $\rm XXYXXZX$.
+- 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 (in binary form) fall into the selected interval?
+{Which real numbers&nbsp; (in binary form)&nbsp; fall into the selected interval?
 |type="[]"}
 - $r_1 = (0.101100)_{\text{binary}}$,

@@ Line 44: / Line 44: @@
 Hints:
 *The task 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#Arithmetische_Codierung|Arithmetic Coding]].
+*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:Aufgabe_2.11:_Nochmals_Arithmetische_Codierung|Exercise 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]]&nbsp; behandelt.

@@ Line 3: / Line 3: @@
 }}
-[[File:EN_Inf_A_2_11_v3.png|right|frame|Interval nesting for <br>arithmetic coding]]
+[[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 task, we assume&nbsp; $M = 3$&nbsp; symbols, which we name with&nbsp; $\rm X$,&nbsp; $\rm Y$&nbsp; and  $\rm Z$&nbsp;.
+Arithmetic coding is a special form of entropy coding: &nbsp;  The symbol probabilities must also be known here.&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 coded 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} \Delta = E - B$.
+* 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:
+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 deciaml value &nbsp;$r = 3/4$&nbsp; can be represented with two bits:
+* 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
@@ Line 22: / Line 24: @@
 :$$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 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;$\Delta$ respectively.
+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;.
@@ Line 33: / Line 35: @@
 :$$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; The intermediate values are&nbsp; $C_1$&nbsp; and&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;
-* 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 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.
+*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$.
@@ Line 40: / Line 43: @@
 Hints:
-*The task belongs to the chapter&nbsp; [[Information_Theory/Weitere_Quellencodierverfahren|Other source coding methods]].
+*The task 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#Arithmetische_Codierung|Arithmetic Coding]].
 *The binary representation of the selected interval is dealt with in&nbsp; [[Aufgaben:Aufgabe_2.11:_Nochmals_Arithmetische_Codierung|Exercise 2.11Z]]&nbsp; behandelt.

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

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

← Older revision		Revision as of 13:03, 16 July 2021
Line 141:		Line 141:


−	[[Category:Information Theory: Exercises\|^2.4 ~~Weitere Quellencodierverfahren~~^]]	+	[[Category:Information Theory: Exercises\|^2.4 Further Source Coding Methods^]]

@@ Line 3: / Line 3: @@
 }}
-[[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|Intervallschachtelung bei <br>arithmetischer Codierung]]
 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.