Aufgabe 2.6: Zur Huffman-Codierung
Wir betrachten hier eine Quellensymbolfolge $\langle q_\nu \rangle$ mit dem Symbolumfang $M = 8$:
- $$q_{\nu} \in \{ \hspace{0.05cm}q_{\mu} \} = \{ \boldsymbol{\rm A} \hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm B}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm C}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm D}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm E}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm F}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm G}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm H}\hspace{0.05cm} \}\hspace{0.05cm}.$$
Sind die Symbole gleichwahrscheinlich, gilt also $p_{\rm A} = p_{\rm B} =$ ... $ = p_{\rm H} = 1/M$, so macht Quellencodierung keinen Sinn. Bereits mit dem Dualcode $\rm A$ → 000, $\rm B$ → 001, ... , $\rm H$ → 111, erreicht nämlich dann die mittlere Codewortlänge $L_{\rm M}$ ihre untere Schranke $H$ gemäß dem Quellencodierungstheorem $(H$ bezeichnet hierbei die Quellenentropie$)$:
- $$L_{\rm M,\hspace{0.08cm}min} = H = 3 \hspace{0.15cm}{\rm bit/Quellensymbol} \hspace{0.05cm}.$$
Die Symbolwahrscheinlichkeiten seien aber in dieser Aufgabe wie folgt gegeben:
- $$p_{\rm A} \hspace{-0.05cm}= \hspace{-0.05cm} 0.04 \hspace{0.05cm},\hspace{0.1cm}p_{\rm B} \hspace{-0.05cm}= \hspace{-0.05cm} 0.08 \hspace{0.05cm},\hspace{0.1cm}p_{\rm C} \hspace{-0.05cm}= \hspace{-0.05cm} 0.14 \hspace{0.05cm},\hspace{0.1cm} p_{\rm D} \hspace{-0.05cm}= \hspace{-0.05cm} 0.25 \hspace{0.05cm},\hspace{0.1cm} p_{\rm E} \hspace{-0.05cm}= \hspace{-0.05cm} 0.24 \hspace{0.05cm},\hspace{0.1cm}p_{\rm F} \hspace{-0.05cm}= \hspace{-0.05cm} 0.12 \hspace{0.05cm},\hspace{0.1cm}p_{\rm G} \hspace{-0.05cm}= \hspace{-0.05cm} 0.10 \hspace{0.05cm},\hspace{0.1cm} p_{\rm H} \hspace{-0.05cm}= \hspace{-0.05cm} 0.03 \hspace{0.05cm}.$$
- Es liegt hier also eine redundante Nachrichtenquelle vor, die man durch Huffman–Codierung komprimieren kann.
- Dieser Algorithmus wurde 1952 – also kurz nach Shannons bahnbrechenden Arbeiten zur Informationstheorie – von David Albert Huffman veröffentlicht und erlaubt die Konstruktion von optimalen präfixfreien Codes.
Der Algorithmus soll hier ohne Herleitung und Beweis angegeben werden, wobei wir uns auf Binärcodes beschränken ⇒ die Codesymbolfolge besteht nur aus Nullen und Einsen:
- (1) Man ordne die Symbole nach fallenden Auftrittswahrscheinlichkeiten.
- (2) Man fasse die zwei unwahrscheinlichsten Symbole zu einem neuen Symbol zusammen.
- (3) Man wiederhole Schritt (1) und (2), bis nur zwei (zusammengefasste) Symbole übrig bleiben.
- (4) Die wahrscheinlichere Symbolmenge wird mit 1 binär codiert, die andere Menge mit 0.
- (5) Man ergänze schrittweise (von unten nach oben) die aufgespaltenen Teilcodes mit 1 bzw. 0.
Oft wird dieser Algorithmus durch ein Baumdiagramm veranschaulicht. Die Grafik zeigt dieses für den vorliegenden Fall.
Sie haben folgende Aufgaben:
- (a) Zuordnung der Symbole $\rm A$, ... , $\rm H$ zu den mit [1], ... , [8] bezeichneten Eingängen.
- (b) Bestimmung der Summenwahrscheinlichkeiten $U$, ... , $Z$ sowie $R$ („Root”).
- (c) Zuordnung der Symbole $\rm A$, ... , $\rm H$ zu den entsprechenden Huffman–Binärfolgen. Eine rote Verbindung entspricht einer 1, eine blaue Verbindung einer 0.
Sie werden feststellen, dass die mittlere Codewortlänge
- $$L_{\rm M} = \sum_{\mu = 1}^{M}\hspace{0.05cm} p_{\mu} \cdot L_{\mu} $$
bei Huffman–Codierung nur unwesentlich größer ist als die Quellenentropie $H$. In dieser Gleichung gelten für den vorliegenden Fall folgende Werte:
- $M = 8$, $p_1 = p_{\rm A}$, ... , $p_8 = p_{\rm H}$.
- Die jeweilige Bitanzahl der Codesymbole für $\rm A$, ... , $\rm H$ ist mit $L_1$, ... , $L_8$ bezeichnet.
Hinweise:
- Die Aufgabe gehört zum Kapitel Entropiecodierung nach Huffman.
- Insbesondere wird Bezug genommen auf die Seiten
- Zur Kontrolle Ihrer Ergebnisse verweisen wir auf folgende Interaktionsmodule:
Fragebogen
Musterlösung
- Da die zwei unwahrscheinlichsten Symbole schon im ersten Schritt zusammengefasst werden, nehmen die Auftrittswahrscheinlichkeiten von oben nach unten ab
(in der Grafik zu dieser Musterlösung von links nach rechts). - Durch Vergleich mit dem Angabenblatt erhält man:
- Symbol $\rm A$: Eingang 7, Symbol $\rm B$: Eingang 6, Symbol $\rm C$: Eingang 3, Symbol $\rm D$: Eingang 1.
(2) Der Knoten $\rm R$ ist die Baumwurzel (Root). Dieser ist stets mit $\underline{R=1}$ belegt, unabhängig von den Auftrittswahrscheinlichkeiten.
Für die weiteren Werte gilt:
- Schritt 1: $p_{\rm U} = p_{\rm A} + p_{\rm H} = 0.04 + 0.03 \hspace{0.15cm}\underline{ =0.07}$,
- Schritt 2: $p_{\rm V} = p_{\rm U} + p_{\rm B} = 0.07 + 0.08 \hspace{0.15cm}\underline{ =0.15}$,
- Schritt 3: $p_{\rm W} = p_{\rm F} + p_{\rm G} = 0.12 + 0.10 \hspace{0.15cm}\underline{ =0.22}$,
- Schritt 4: $p_{\rm X} = p_{\rm V} + p_{\rm C} = 0.15 + 0.14 \hspace{0.15cm}\underline{ =0.29}$,
- Schritt 5: $p_{\rm Y} = p_{\rm W} + p_{\rm E} = 0.22 + 0.24 \hspace{0.15cm}\underline{ =0.46}$,
- Schritt 6: $p_{\rm Z} = p_{\rm X} + p_{\rm D} = 0.29 + 0.25 \hspace{0.15cm}\underline{ =0.54}$.
(3) Den Huffman–Code für das Symbol $\rm A$ erhält man, wenn man den Weg von der $\rm Root$ (gelber Punkt) zum Symbol $\rm A$ zurückverfolgt und jeder roten Verbindungslinie eine 1 zuordnet, jeder blauen eine 0.
- Symbol $\rm A$: rot–rot–rot–blau–rot → 11101,
- Symbol $\rm B$: rot–rot–rot–rot → 1111,
- Symbol $\rm C$: rot–rot–blau → 110,
- Symbol $\rm D$: rot–blau– → 10,
- Symbol $\rm E$: blau–rot → 01,
- Symbol $\rm F$: blau–blau–rot → 001,
- Symbol $\rm G$: blau–blau–blau → 000,
- Symbol $\rm H$: rot–rot–rot–blau–blau → 11100.
(4) Die Codierung unter Punkt (3) hat ergeben, dass
- die Symbole $\rm D$ und $\rm E$ mit zwei Bit,
- die Symbole $\rm C$, $\rm F$ und $\rm G$ mit drei Bit,
- das Symbol $\rm B$ mit vier Bit, und
- die Symbole $\rm A$ und $\rm H$ jeweils mit fünf Bit
dargestellt werden. Damit erhält man für die mittlere Codewortlänge (in „bit/Quellensymbol&dquo;):
- $$L_{\rm M} \hspace{0.2cm} = \hspace{0.2cm} (p_{\rm D} + p_{\rm E}) \cdot 2 + (p_{\rm C} + p_{\rm F} + p_{\rm G}) \cdot 3 + p_{\rm B} \cdot 4 +(p_{\rm A} + p_{\rm H}) \cdot 5 = 0.49 \cdot 2 + 0.36 \cdot 3 +0.08 \cdot 4 +0.07 \cdot 5 \hspace{0.15cm}\underline{= 2.73}\hspace{0.05cm}.$$
(5) Richtig ist allein die Antwort 1:
- Die mittlere Codewortlänge $L_{\rm M}$ kann nicht kleiner sein als die Quellenentropie $H$. Damit scheiden die Antworten 2 und 3 aus.
- Aus den vorgegebenen Auftrittswahrscheinlichkeiten kann die Quellenentropie tatsächlich zu $H = 2.71$ bit/Quellensymbol berechnet werden.
- Man erkennt, dass diese Huffman–Codierung die vorgegebene Grenze (Quellencodierungstheorem) $L_{\rm M, \ min } \ge H = 2.71$ bit/Quellensymbol nahezu erreicht.
