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

Aus LNTwww
Wechseln zu:Navigation, Suche
Zeile 100: Zeile 100:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
[[Datei:P_ID2469__Inf_A_2_11_ML.png|right|Intervallschachtelung mit allen Zahlenwerten]]
+
[[Datei:P_ID2469__Inf_A_2_11_ML.png|right|frame|Intervallschachtelung mit allen Zahlenwerten]]
 
'''(1)'''  Aus der Grafik auf der Angabenseite kann man die Wahrscheinlichkeiten ablesen:
 
'''(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}.$$
 
:$$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; Auch das zweite Symbol ist <b>X</b>. Bei gleichem Vorgehen wie in der Aufgabenbeschreibung erhält man
+
 
 +
'''(2)'''&nbsp; 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}
 
:$$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; Für das  dritte Symbol <b>Y</b> gelten nun die Begrenzungen $B_3 = C_2$  und $E_3 = D_2$:
+
 
 +
'''(3)'''&nbsp; 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}
 
:$$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; Aus $B_4 = 0.343 = B_3$ (abzulesen in der Grafik auf dem Angabenblatt) folgt zwingend, dass das vierte  Quellensymbol ein <b>X</b> war &nbsp; &#8658; &nbsp; <u>Lösungsvorschlag 1.</u>
+
'''(4)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 1</u>:
 +
*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)'''&nbsp; Richtig sind die <u>Lösungsvorschläge 2 und 3:</u>
 
'''(5)'''&nbsp; Richtig sind die <u>Lösungsvorschläge 2 und 3:</u>
*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 Grafik zeigt die Intervallschachtelung mit allen bisherigen Ergebnissen. Man erkennt aus der Schraffierung, dass der zweite Lösungsvorschlag die richtige Symbolfolge angibt:  &nbsp; $\rm XXYXXXZ$.
* Die Intervallbreite $\it \Delta$ kann wirklich gemäß dem Vorschlag 3 ermittelt werden:
+
* 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}  = 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  
 
:$${\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; Richtig ist der <u>Lösungsvorschlag 2</u> &nbsp; &rArr; &nbsp; $r_2 = (0.010111)_{\text{binär}}$, 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: $r_1 = (0.101100)_{\text{binär}}$ ist auszuschließen, da der zugehörige Dezimalwert $r_1 > 0.5$ ist.  
+
*Der Vorschlag 1: &nbsp; $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}}$ ergibt.
 
*Auch der letzte Lösungsvorschlag ist falsch, da $r_3 = (0.001011)_{\text{binär}} < (0.01)_{\text{binär}} = (0.25)_{\text{dezimal}}$ ergibt.
  

Version vom 2. Oktober 2018, 13:03 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 (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.15cm} 0.11\hspace{0.3cm}\Rightarrow\hspace{0.3cm}\text {Code:} \hspace{0.15cm} \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.15cm}0.011101\hspace{0.3cm}\Rightarrow\hspace{0.3cm} \text{Code:} \hspace{0.15cm} \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.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 der zu codierenden Folge ist $\rm X$   ⇒   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 sind der Grafik zugrundegelegt?

$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}}$ ergibt.