Exercise 2.11: Arithmetic Coding

• Return to book

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 Δ = E – B.

Von den unendlich vielen möglichen Werten r ∈ 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 $$

$$\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 p_X, p_Y und p_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 ist X  ⇒  das ausgewählte Intervall wird durch B₀ und C₀ begrenzt. Dieses Intervall wird mit neuem Beginn B₁ = B₀ und neuem Ende E₁ = C₀ in gleicher Weise aufgeteilt wie der Gesamtbereich im Schritt 0. Die Zwischenwerte sind C₁ und D₁.

• Die weitere Intervall–Aufteilung ist Ihre Aufgabe. Beispielsweise sollen in der Teilaufgabe (2) die Grenzen B₂, C₂, D₂, E₂ für das zweite Symbol X und in der Teilaufgabe (3) die Grenzen <nobr>B₃, C₃, D₃, E₃</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 B₄ = 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 B₇ = 0.3564456 und E₇ = 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

Solution

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 B₃ = C₂ und E₃ = D₂:

$$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 B₄ = 0.343 = B₃ (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 r₁ > 0.5 ist. Auch der letzte Lösungsvorschlag ist falsch, da (0.001011)_binär < (0.01)_binär = 0.25_dezimal 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}. $$