Aufgaben:Aufgabe 2.11: Arithmetische Codierung: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(14 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 3: Zeile 3:
 
}}
 
}}
  
[[Datei:P_ID2468__Inf_A_2_11.png|right|]]
+
[[Datei:P_ID2468__Inf_A_2_11.png|right|frame|Intervallschachtelung bei <br>arithmetischer Codierung]]
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.
+
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.
  
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
+
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
:$$I = [B, E) = [B, B +{\it \Delta} )\hspace{0.05cm}.$$
+
:$$I = \big[B, \ E \big) = \big[B, \ B +{\it \Delta} \big)\hspace{0.05cm}.$$
 
Diese Notation bedeutet:
 
Diese Notation bedeutet:
 +
* Der Beginn&nbsp; $B$&nbsp; gehört zum Intervall&nbsp; $I$.
 +
* Das Ende&nbsp; $E$&nbsp; ist nicht mehr in&nbsp; $I$&nbsp; enthalten.
 +
* Die Intervallbreite ist&nbsp; ${\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.
+
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:
 +
* Der Dezimalwert &nbsp;$r = 3/4$&nbsp; lässt sich mit zwei Bit darstellen:
 +
:$$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
 +
{Code:} \hspace{0.25cm} \boldsymbol{\rm 11} \hspace{0.05cm}, $$
  
:* Die Intervallbreite ist <i>&Delta;</i> = <i>E</i> &ndash; <i>B</i>.
+
* Der Dezimalwert &nbsp;$r = 1/3$&nbsp; 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}\text{...}$$
 +
:$$
 +
\Rightarrow\hspace{0.3cm}\text{binär:} \hspace{0.25cm}0.011101\hspace{0.3cm}\Rightarrow\hspace{0.3cm}
 +
\text{Code:} \hspace{0.25cm} \boldsymbol{\rm 011101} \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 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$.
 
+
*Diese Bestimmung geschieht entsprechend der Intervallschachtelung in obiger Grafik.  
:* Der Dezimalwert <i>r</i> = 3/4 lässt sich mit zwei Bit darstellen:
+
*An der Schraffierung ist zu erkennen, dass die Folge mit  den Ternärsymbolen&nbsp; $\rm XXY$&nbsp; beginnt.
:$$r =  1 \cdot 2^{-1}  + 1 \cdot 2^{-2} = 0.75 $$
+
<br clear=all>
:$$\Rightarrow\hspace{0.3cm}{\rm bin\ddot{a}r: 0.11}\hspace{0.3cm}\Rightarrow\hspace{0.3cm}
+
Der Algorithmus funktioniert wie folgt:
{\rm Code:} \hspace{0.15cm} \boldsymbol{\rm 11} \hspace{0.05cm}, $$
+
* 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
 
+
:$$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> = 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.
+
* 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$.
 +
* 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$.
  
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
 
:$$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}
 
E_0 = p_{\rm X} + p_{\rm Y}+ p_{\rm Z} = 1\hspace{0.05cm}.$$
 
  
:* 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.
+
''Hinweise:''
 +
*Die Aufgabe gehört zum  Kapitel&nbsp; [[Informationstheorie/Weitere_Quellencodierverfahren|Weitere Quellencodierverfahren]].
 +
*Insbesondere wird  Bezug genommen auf die Seite&nbsp; [[Informationstheorie/Weitere_Quellencodierverfahren#Arithmetische_Codierung|Arithmetische Codierung]].
 +
*Die Binärdarstellung des ausgewählten Intervalls wird in der&nbsp; [[Aufgaben:Aufgabe_2.11:_Nochmals_Arithmetische_Codierung|Aufgabe 2.11Z]]&nbsp; behandelt.
 +
  
<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.
 
  
  
Zeile 46: Zeile 51:
  
 
<quiz display=simple>
 
<quiz display=simple>
{Welche Wahrscheinlichkeiten sind der Grafik zugrundegelegt?
+
{Welche Wahrscheinlichkeiten liegen der Grafik zugrunde?
 
|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?
+
{Wie lauten die Bereichsgrenzen nach der Codierung des zweiten Symbols&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?
+
{Wie lauten die Bereichsgrenzen nach der Codierung des dritten Symbols&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% }
  
  
{Nach der Codierung des vierten Symbols ist <i>B</i><sub>4</sub> = 0.343. Was folgt daraus?
+
{Nach der Codierung des vierten Symbols ist&nbsp; $B_4 = 0.343$.&nbsp; Was folgt daraus?
|type="[]"}
+
|type="()"}
+ Das vierte Symbol war <b>X</b>.
+
+ Das vierte Symbol war&nbsp; $\rm X$.
- Das vierte Symbol war <b>Y</b>.
+
- Das vierte Symbol war&nbsp; $\rm Y$.
- Das vierte Symbol war <b>Z</b>.
+
- Das vierte Symbol war&nbsp; $\rm Z$.
  
  
{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?
+
{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?
 
|type="[]"}
 
|type="[]"}
- Die zur Codierung anstehende Symbolfolge lautet <b>XXYXXZX</b>.
+
- Die zur Codierung anstehende Symbolfolge lautet&nbsp; $\rm XXYXXZX$.
+ Die zur Codierung anstehende Symbolfolge lautet <b>XXYXXXZ</b>.
+
+ Die zur Codierung anstehende Symbolfolge lautet&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>.
+
+ Die Breite des resultierenden Intervalls ist&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?
 
{Welche reellen Zahlen (in Binärform) fallen in das ausgewählte Intervall?
 
|type="[]"}
 
|type="[]"}
- <i>r</i><sub>1</sub> = (0.101100)<sub>binär</sub>
+
- $r_1 = (0.101100)_{\text{binär}}$,
+ <i>r</i><sub>2</sub> = (0.010111)<sub>binär</sub>
+
+ $r_2 = (0.010111)_{\text{binär}}$,
- <i>r</i><sub>3</sub> = (0.001011)<sub>binär</sub>
+
- $r_3 = (0.001011)_{\text{binär}}$.
  
  
Zeile 95: Zeile 100:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
[[Datei:P_ID2469__Inf_A_2_11_ML.png|right|]]
+
[[Datei:P_ID2469__Inf_A_2_11_ML.png|right|frame|Intervallschachtelung mit allen Zahlenwerten]]
<b>1.</b>&nbsp;&nbsp;Aus der Grafik auf der Angabenseite kann man die Wahrscheinlichkeiten ablesen:
+
'''(1)'''&nbsp; Aus der Grafik auf der Angabenseite kann man die Wahrscheinlichkeiten ablesen:
 
:$$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>:
 
:$$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},$$
 
:$$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}.$$
 
  
<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>
+
'''(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}
 +
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>5.</b>&nbsp;&nbsp;Die Grafik zeigt die Intervallschachtelung mit allen bisherigen Ergebnissen.
 
  
:* 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:
+
'''(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$:
:$${\it \Delta} \hspace{0.2cm} = \hspace{0.2cm} 0.359807 - 0.3564456 = 0.003614 \hspace{0.05cm},\\
+
:$$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}
{\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  
+
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; Richtig ist der <u>Lösungsvorschlag 1</u>:
 +
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; Richtig sind die <u>Lösungsvorschläge 2 und 3:</u>
 +
*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$.
 +
* 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} =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.
 
  
Richtig ist der <u>Lösungsvorschlag 2</u>: (0.010111)<sub>binär</sub>, wegen:
+
'''(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.
 +
*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.
 +
 
 +
 
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  

Aktuelle Version vom 28. Januar 2020, 15:13 Uhr

Intervallschachtelung bei
arithmetischer Codierung

Die arithmetische Codierung ist eine spezielle Form der Entropiecodierung:   Die Symbolwahrscheinlichkeiten müssen auch hier bekannt sein.  In dieser Aufgabe gehen wir von  $M = 3$  Symbolen aus, die wir mit  $\rm X$,  $\rm Y$  und $\rm Z$  benennen.

Während die Huffman–Codierung symbolweise erfolgt, wird bei der Arithmetischen Codierung  $(\rm AC)$  eine Symbolfolge der Länge  $N$  gemeinsam codiert.  Das Codierergebnis ist ein reeller Zahlenwert  $r$  aus dem Intervall

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

Diese Notation bedeutet:

  • Der Beginn  $B$  gehört zum Intervall  $I$.
  • Das Ende  $E$  ist nicht mehr in  $I$  enthalten.
  • Die Intervallbreite ist  ${\it} \Delta = E - B$.


Von den unendlich vielen möglichen Werten  $r \in I$  $($da  $r$  reellwertig ist, also kein Integer$)$  wird derjenige Zahlenwert ausgewählt, der mit der geringsten Bitanzahl auskommt.  Hierzu zwei Beispiele zur Verdeutlichung:

  • Der Dezimalwert  $r = 3/4$  lässt sich mit zwei Bit darstellen:
$$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 {Code:} \hspace{0.25cm} \boldsymbol{\rm 11} \hspace{0.05cm}, $$
  • Der Dezimalwert  $r = 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}\text{...}$$
$$ \Rightarrow\hspace{0.3cm}\text{binär:} \hspace{0.25cm}0.011101\hspace{0.3cm}\Rightarrow\hspace{0.3cm} \text{Code:} \hspace{0.25cm} \boldsymbol{\rm 011101} \hspace{0.05cm}. $$

In dieser Aufgabe beschränken wir uns auf die Bestimmung des aktuellen Intervalls  $I$, gekennzeichnet durch den Beginn  $B$  sowie dem Ende  $E$  bzw. der Breite  $\Delta$.

  • Diese Bestimmung geschieht entsprechend der Intervallschachtelung in obiger Grafik.
  • An der Schraffierung ist zu erkennen, dass die Folge mit den Ternärsymbolen  $\rm XXY$  beginnt.


Der Algorithmus funktioniert wie folgt:

  • Vor Beginn  (quasi beim nullten Symbol)  wird der gesamte Wahrscheinlichkeitsbereich nach den Wahrscheinlichkeiten  $p_{\rm X}$,  $p_{\rm Y}$  und  $p_{\rm Z}$  in drei Bereiche unterteilt.  Die Grenzen liegen bei
$$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  $\rm X$. Das bedeutet:   das ausgewählte Intervall wird durch  $B_0$  und  $C_0$  begrenzt.  Dieses Intervall wird mit neuem Beginn  $B_1 = B_0$  und neuem Ende  $E_1 = C_0$  in gleicher Weise aufgeteilt wie der Gesamtbereich im nullten Schritt.  Die Zwischenwerte sind  $C_1$  und  $D_1$.
  • Die weitere Intervall–Aufteilung ist Ihre Aufgabe.  Beispielsweise sollen in der Teilaufgabe  (2)  die Grenzen  $B_2$,  $C_2$,  $D_2$  und  $E_2$  für das zweite Symbol  $\rm X$  ermittelt werden und in der Teilaufgabe  (3)  die Grenzen  $B_3$,  $C_3$,  $D_3$  und  $E_3$  für das dritte Symbol  $\rm Y$.



Hinweise:



Fragebogen

1

Welche Wahrscheinlichkeiten liegen der Grafik zugrunde?

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

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

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

2

Wie lauten die Bereichsgrenzen nach der Codierung des zweiten Symbols  $\rm X$?

$B_2 \hspace{0.12cm} = \ $

$C_2 \hspace{0.15cm} = \ $

$D_2 \hspace{0.10cm} = \ $

$E_2 \hspace{0.15cm} = \ $

3

Wie lauten die Bereichsgrenzen nach der Codierung des dritten Symbols  $\rm Y$?

$B_3 \hspace{0.12cm} = \ $

$C_3 \hspace{0.15cm} = \ $

$D_3 \hspace{0.10cm} = \ $

$E_3 \hspace{0.15cm} = \ $

4

Nach der Codierung des vierten Symbols ist  $B_4 = 0.343$.  Was folgt daraus?

Das vierte Symbol war  $\rm X$.
Das vierte Symbol war  $\rm Y$.
Das vierte Symbol war  $\rm Z$.

5

Nach weiteren Symbolen wird das Intervall durch  $B_7 = 0.3564456$  und  $E_7 = 0.359807$  begrenzt.  Welche Aussagen treffen zu?

Die zur Codierung anstehende Symbolfolge lautet  $\rm XXYXXZX$.
Die zur Codierung anstehende Symbolfolge lautet  $\rm XXYXXXZ$.
Die Breite des resultierenden Intervalls ist  ${\it \Delta} = p_{\rm X}^5 \cdot p_{\rm Y} \cdot p_{\rm Z}$.

6

Welche reellen Zahlen (in Binärform) fallen in das ausgewählte Intervall?

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


Musterlösung

Intervallschachtelung mit allen Zahlenwerten

(1)  Aus der Grafik auf der Angabenseite kann man die Wahrscheinlichkeiten ablesen:

$$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)  Auch das zweite Symbol ist  $\rm X$.  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} 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)  Für das dritte Symbol  $\rm Y$  gelten nun die Begrenzungen  $B_3 = C_2$  und  $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} 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)  Richtig ist der Lösungsvorschlag 1: Aus  $B_4 = 0.343 = B_3$  (abzulesen in der Grafik auf dem Angabenblatt) folgt zwingend, dass das vierte Quellensymbol ein  $\rm X$  war.


(5)  Richtig sind die Lösungsvorschläge 2 und 3:

  • Die Grafik zeigt die Intervallschachtelung mit allen bisherigen Ergebnissen.  Man erkennt aus der Schraffierung, dass der zweite Lösungsvorschlag die richtige Symbolfolge angibt:   $\rm XXYXXXZ$.
  • Die Intervallbreite  $\it \Delta$  kann wirklich gemäß dem Vorschlag 3 ermittelt werden. Es gilt:
$${\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 \hspace{0.05cm}. $$


(6)  Richtig ist der Lösungsvorschlag 2   ⇒   $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}. $$
  • Der Vorschlag 1:   $r_1 = (0.101100)_{\text{binär}}$  ist auszuschließen, da der zugehörige Dezimalwert  $r_1 > 0.5$  ist.
  • Auch der letzte Lösungsvorschlag ist falsch, da  $r_3 = (0.001011)_{\text{binär}} < (0.01)_{\text{binär}} = (0.25)_{\text{dezimal}}$  sein wird.