Digitale AV-Technik
Prof. Uwe Hahne
Sommersemester 2026

Digitale AV-Technik - Aufgabenblatt 05

Arithmetische Codierung

Hintergrundinformationen zur Arithmetischen Codierung

Die arithmetische Codierung ist eine Technik zur Datenkomprimierung, bei der ein Symbolstrom als eine einzelne Zahl in einem Intervall \([0, 1)\) dargestellt wird. Anstatt jedem Symbol eine eindeutige Bitfolge zuzuweisen, repräsentiert die arithmetische Codierung eine Nachricht als eine Kommazahl in einem Intervall, das durch die Wahrscheinlichkeiten der Symbole bestimmt wird.

Vorgehensweise:

1. Teile das Intervall \([0, 1)\) in Segmente auf, deren Größe der Wahrscheinlichkeit jedes Symbols entspricht.
2. Aktualisiere das Intervall für jedes neue Symbol, das codiert wird.
3. Nach der Codierung aller Symbole ergibt sich eine Zahl, die eindeutig die Nachricht beschreibt.

---

Aufgabe 1: Intervalle berechnen

Gegeben sind die Symbole und ihre Wahrscheinlichkeiten:

Symbol	Wahrscheinlichkeit
A	0.5
B	0.3
C	0.2

1. Bestimme die Intervalle für jedes Symbol:

2. Berechne die Intervalle für A, B und C im Intervall \([0, 1)\) basierend auf ihren Wahrscheinlichkeiten.

3. Codierung der Nachricht "AB":

4. Verwende die berechneten Intervalle, um die Nachricht "AB" zu codieren. Beginne mit dem Intervall \([0, 1)\) und aktualisiere das Intervall Schritt für Schritt für jedes Symbol.

5. Ausgabe:

6. Gib das finale Intervall für die Nachricht "AB" an und nenne eine Zahl innerhalb dieses Intervalls, die als Codierung für die Nachricht genutzt werden kann.

Aufgabe 2: Dekodierung eines Codes

Gegeben sei der gleiche Satz von Symbolen und Wahrscheinlichkeiten wie in Aufgabe 1.

1. Dekodiere den Code 0.325, der in dem Intervall \([0, 1)\) liegt, und bestimme die Originalnachricht. Diese hat die Länge 2.
2. Verwende dabei die Intervalle für jedes Symbol, um die Nachricht wiederherzustellen.

Aufgabe 3: Probleme bei der Implementierung

Teste die in der Vorlesung vorgestellte Implementierung. Funktioniert sie auch für längere Nachrichten? Wenn nicht, was ist das Problem und wie könnte man es beheben?

Tipp: Schau dir die Implementierung von Ahmed Gad an.

---

Lösungen

Prüfe ob die Lösungen richtig sind.

Lösung zu Aufgabe 1

1. Berechnung der Intervalle für jedes Symbol:

2. Das Intervall \([0, 1)\) wird basierend auf den Wahrscheinlichkeiten aufgeteilt:

   • A hat 0.5: Intervall \([0, 0.5)\)
   • B hat 0.3: Intervall \([0.5, 0.8)\)
   • C hat 0.2: Intervall \([0.8, 1)\)

Die Intervalle lauten also:

Symbol	Intervall
A	[0, 0.5)
B	[0.5, 0.8)
C	[0.8, 1)

1. Codierung der Nachricht "AB":

2. Startintervall ist \([0, 1)\).

3. Das 1. Symbol A: Wähle das Intervall für A, das von \([0, 0.5)\) reicht.
4. Das 2. Symbol B: Wähle innerhalb dieses Intervalls das Segment für B (berechne das Teilintervall).
   • Das aktuelle Intervall für A ist \([0, 0.5)\).
   • Innerhalb dieses Intervalls entspricht B dem Segment \([0.25, 0.4)\) (denn \(0 + (0.5 \times 0.5) = 0.25\) und \(0 + (0.8 \times 0.5) = 0.4\)).

Finales Intervall für "AB": \([0.25, 0.4)\).

1. Codierungsausgabe:
2. Eine mögliche Zahl, die die Nachricht "AB" repräsentiert, ist \(0.3\), da diese im Intervall \([0.25, 0.4)\) liegt.

Lösung zu Aufgabe 2

1. Dekodierung von 0.325:
2. Startintervall ist \([0, 1)\).
3. Schritt 1: Prüfe, in welches Symbolintervall 0.325 fällt.
   • Da 0.325 im Intervall \([0, 0.5)\) liegt, entspricht das Symbol A.
4. Aktualisiere das Intervall auf \([0, 0.5)\).
5. Schritt 2: Prüfe erneut mit dem aktualisierten Intervall für den nächsten Symbolbereich.
   • 0.325 fällt im neuen Intervall \([0, 0.5)\) in das Segment für B, das von \([0.25, 0.4)\) reicht.

Die dekodierte Nachricht lautet also "AB".