Aufgabe 2.11Z: Nochmals Arithmetische Codierung

Aus LNTwww
Wechseln zu:Navigation, Suche

P ID2473 Inf A 2 12.png

Wir betrachten hier die arithmetische Codierung (AC). Alle notwendigen Informationen zu dieser Art von Entropiecodierung finden Sie in der Aufgabe A2.11.

Auch nebenstehende Grafik ist das Ergebnis der letzten Aufgabe. Die für die aktuelle Aufgabe wichtigen Zahlenwerte für die Codierschritte 3 und 7 sind farblich hervorgehoben:

  • Das Intervall für N = 3 (Symbolfolge XXY) beginnt bei B3 = 0.343 und reicht bis zum Endwert E3 = 0.392.
  • Das Intervall für N = 7 (Symbolfolge XXYXXXZ) beginnt bei B7 = 0.3564456 und endet bei E7 = 0.359807.

In dieser Aufgabe geht es nur um die Zuweisung von Binärfolgen zu den ausgewählten Intervallen. Man geht wie folgt vor:

  • Das Intervall I wird bestimmt durch den Beginn B, das Ende E, die Intervallbreite Δ = EB sowie die Intervallmitte M = (B + E)/2.
  • Das Intervall I wird gekennzeichnet durch die Binärdarstellung (mit begrenzter Auflösung) eines beliebigen reellen Zahlenwertes rI. Beispielsweise wählt man rM.
  • Die erforderliche Bitanzahl ergibt sich aus der Intervallbreite nach folgender Gleichung (die nach unten offenen Klammern bedeuten „nach oben runden”):
$$N_{\rm Bit} = \left\lceil{\rm ld} \hspace{0.15cm} 1/{\it \Delta} \right\rceil+1\hspace{0.05cm}. $$

Beispielsweise steht für NBit = 5 der Binärcode 01001 für die folgende reellwertige Zahl r:

$$r = 0 \cdot 2^{-1}+1 \cdot 2^{-2}+0 \cdot 2^{-3}+0 \cdot 2^{-4}+1 \cdot 2^{-5} = 0.28125 \hspace{0.05cm}. $$

Hinweis: Die Aufgabe gehört zum Themengebiet von Kapitel 2.4. Allerdings wird in LNTwww die arithmetische Codierung nur sehr knapp behandelt. Eine Übersicht finden Sie auch in WIKIPEDIA und eine ausführlichere Abhandlung in [BCK02].


Fragebogen

1

Wie viele Bit werden zur Darstellung der Folge XXY benutzt?

$N = 3:\ N_\text{Bit}$ =

2

Welcher arithmetischer Code (AC) gilt für diesen Fall?

AC = 01011,
AC = 010111,
AC = 110111.

3

Wie viele Bit werden zur Darstellung von XXYXXXZ benutzt?

$N = 7:\ N_\text{Bit}$ =

4

Ist 01011100001 ein gültiger Code für die Symbolfolge XXYXXXZ?

Ja.
Nein.

5

Welche Aussagen gelten für die arithmetische Codierung allgemein?

Es handelt sich um eine gemeinsame Codierung ganzer Folgen.
Eine 32 Bit–Rechnerarchitektur begrenzt die Folgenlänge N.
Dieses Problem lässt sich durch Integer–Realisierung umgehen.
Eine Integer–Realisierung erhöht die Codiergeschwindigkeit.


Musterlösung

1.  Das ausgewählte Intervall beginnt bei B3 = 0.343 und endet bei E3 = 0.392. Die Intervallbreite ist somit Δ3 = 0.049 und damit gilt mit dem Logarithmus dualis „log2”  →  „ld”:

$$N_{\rm Bit} = {\rm ld} \hspace{0.15cm} \left\lceil \frac{1}{0.049}\right\rceil+1\hspace{0.15cm}\underline{= 6} \hspace{0.05cm}.$$

2.  Das ausgewählte Intervall ergibt sich zu I = [0.343, 0.392). Die Mitte liegt bei M3 = 0.3675. Zur Bestimmung des arithmetischen Codes versuchen wir, die Intervallmitte durch eine Binärdarstellung möglichst gut zu erreichen. Da uns gerade kein entsprechendes Tool zur Lösung dieser Aufgabe zur Verfügung steht, gehen wir von folgenden Nebenrechnungen aus:

H4 = 2–2 + 2–4 = 0.3125  ⇒  gehört nicht zum Intervall I,
H5 = H4 + 2–5 = 0.34375 ∈ I  ⇒  Binärdarstellung: 0.01011  ⇒  Code: 01011.
H6 = H5 + 2–6 = 0.359375 ∈ I ⇒  Binärdarstellung: 0.010111  ⇒  Code: 010111.
H7 = H6 + 2–7 = 0.3671875 ∈ I  ⇒  Binärdarstellung: 0.0101111  ⇒  Code: 0101111.
H12 = H7 + 2–12 = 0.3674316406 ∈ I ⇒  binär: 0.010111100001  ⇒  Code: 010111100001.

Der entsprechende 6 Bit–Code lautet somit AC = 010111   ⇒   Richtig ist der Vorschlag 2.

3.  Hier ergibt sich mit dem Beginn B7 = 0.3564456 und dem Ende E7 = 0.359807 die Intervallbreite Δ7 = 0.0033614 und damit

$$N_{\rm Bit} = \left\lceil {\rm ld} \hspace{0.15cm} \frac{1}{0.0033614} \right\rceil + 1\hspace{0.15cm} = \left\lceil {\rm ld} \hspace{0.15cm} 297.5 \right\rceil + 1\hspace{0.15cm} \underline{= 11} \hspace{0.05cm}.$$

4.  Die Binärdarstellung des Codes 01011100001 ergibt

$$2^{-2}+ 2^{-4}+ 2^{-5}+ 2^{-6}+ 2^{-11} = 0.3598632813 > E_7 \hspace{0.05cm}.$$

Richtig ist also NEIN. Wegen

$$2^{-2}+ 2^{-4}+ 2^{-5}+ 2^{-7}+ 2^{-8}+ 2^{-9}+ 2^{-11} =0.3579101563$$
$$\Rightarrow \hspace{0.3cm} B_7 \le 0.3579101563 < E_7$$

ist der gültige arithmetische Code gleich 01011011101.

e)  Alle Aussagen sind richtig. Sie können sich davon beispielsweise in [BCK02] überzeugen.