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

Aus LNTwww
Wechseln zu:Navigation, Suche
(Die Seite wurde neu angelegt: „ {{quiz-Header|Buchseite=Informationstheorie und Quellencodierung/Weitere Quellencodierverfahren }} right| Die arithmetisch…“)
 
Zeile 127: Zeile 127:
  
  
[[Category:Aufgaben zu Informationstheorie und Quellencodierung|^2.4 Weitere Quellencodierverfahren^]]
+
[[Category:Aufgaben zu Informationstheorie|^2.4 Weitere Quellencodierverfahren^]]

Version vom 24. November 2016, 16:30 Uhr

P ID2468 Inf A 2 11.png

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

Im Gegensatz zur Huffman–Codierung 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 = [B, E) = [B, B +{\it \Delta} )\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 Δ = EB.

Von den unendlich vielen möglichen Werten rI (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 $$
$$\Rightarrow\hspace{0.3cm}{\rm bin\ddot{a}r: 0.11}\hspace{0.3cm}\Rightarrow\hspace{0.3cm} {\rm 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}... $$
$$\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, gekennzeichnet durch den Beginn B sowie dem Ende E bzw. der Breite Δ. Diese Bestimmung geschieht entsprechend der Intervallschachtelung in obiger Grafik. An der Schraffierung ist zu erkennen, dass die Folge mit den Ternärsymbolen XXY beginnt.

Der Algorithmus funktioniert wie folgt:

  • Vor Beginn (quasi beim Symbol 0) wird der gesamte Wahrscheinlichkeitsbereich nach den Wahrscheinlichkeiten pX, pY und pZ 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 X  ⇒  das ausgewählte Intervall wird durch B0 und C0 begrenzt. Dieses Intervall wird mit neuem Beginn B1 = B0 und neuem Ende E1 = C0 in gleicher Weise aufgeteilt wie der Gesamtbereich im Schritt 0. Die Zwischenwerte sind C1 und D1.
  • Die weitere Intervall–Aufteilung ist Ihre Aufgabe. Beispielsweise sollen in der Teilaufgabe (2) die Grenzen B2, C2, D2, E2 für das zweite Symbol X und in der Teilaufgabe (3) die Grenzen <nobr>B3, C3, D3, E3</nobr> für das dritte Symbol Y ermittelt werden.

Hinweis: 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.


Fragebogen

1

Welche Wahrscheinlichkeiten sind der Grafik zugrundegelegt?

$p_X$ =

$p_Y$ =

$p_Z$ =

2

Wie lauten die Bereichsgrenzen nach der Codierung des zweiten Symbols?

2. Symbol ist „X”: $B_2$ =

$C_2$ =

$D_2$ =

$E_2$ =

3

Wie lauten die Bereichsgrenzen nach der Codierung des dritten Symbols?

3. Symbol ist „Y”: $B_3$ =

$C_3$ =

$D_3$ =

$E_3$ =

4

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

Das vierte Symbol war X.
Das vierte Symbol war Y.
Das vierte Symbol war Z.

5

Nach weiteren Symbolen wird das Ergebnisintervall durch B7 = 0.3564456 und E7 = 0.359807 begrenzt. Welche Aussagen treffen zu?

Die zur Codierung anstehende Symbolfolge lautet XXYXXZX.
Die zur Codierung anstehende Symbolfolge lautet XXYXXXZ.
Die Breite des resultierenden Intervalls ist Δ = pX5 · pY · pZ.

6

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

r1 = (0.101100)binär
r2 = (0.010111)binär
r3 = (0.001011)binär


Musterlösung

P ID2469 Inf A 2 11 ML.png

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 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},$$
$$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.  Aufgrund von Y als drittes Symbol gelten nun die Begrenzungen B3 = C2 und E3 = D2:

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

4.  Aus B4 = 0.343 = B3 (abzulesen in der Grafik auf dem Angabenblatt) folgt zwingend, dass das vierte zu codierende Quellensymbol ein X war ⇒ Lösungsvorschlag 1.

5.  Die Grafik zeigt die Intervallschachtelung mit allen bisherigen Ergebnissen.

  • Man erkennt aus der Schraffierung, dass der zweite Lösungsvorschlag die richtige Symbolfolge angibt: XXYXXXZ.
  • Die Intervallbreite Δ kann wirklich gemäß dem Lösungsvorschlag 3 ermittelt werden:
$${\it \Delta} \hspace{0.2cm} = \hspace{0.2cm} 0.359807 - 0.3564456 = 0.003614 \hspace{0.05cm},\\ {\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 \hspace{0.05cm}. $$

Richtig sind somit die Lösungsvorschläge 2 und 3.

6.  Der Vorschlag 1: (0.101100)binär ist auszuschließen, da der zugehörige Dezimalwert r1 > 0.5 ist. Auch der letzte Lösungsvorschlag ist falsch, da (0.001011)binär < (0.01)binär = 0.25dezimal gilt.

Richtig ist der Lösungsvorschlag 2: (0.010111)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}. $$