Aufgabe 2.7Z: Huffman-Codierung für Zweiertupel einer Ternärquelle
Wir betrachten den gleichen Sachverhalt wie in der Aufgabe A2.7: Der Huffman–Algorithmus führt zu einem besseren Ergebnis, das heißt zu einer kleineren mittleren Codewortlänge $L_{\rm M}$, wenn man ihn nicht auf einzelne Symbole anwendet, sondern vorher $k$–Tupel bildet. Dadurch erhöht man den Symbolumfang von $M$ auf $M' = M^k$.
Für die hier betrachtete Nachrichtenquelle gilt:
- Symbolumfang: $M = 3$,
- Symbolvorrat: $\{$ $\rm X$, $\rm Y$, $\rm Z$ $\}$,
- Wahrscheinlichkeiten: $p_{\rm X} = 0.7$, $p_{\rm Y} = 0.2$, $p_{\rm Z} = 0.1$,
- Entropie: $H = 1.157 \ \rm bit/Ternärsymbol$.
Die Grafik zeigt den Huffman–Baum, wenn man den Huffman–Algorithmus auf Einzelsymbole anwendet, also den Fall $k= 1$. In der Teilaufgabe (2) sollen Sie den entsprechenden Huffman–Code angeben, wenn vorher Zweiertupel gebildet werden $(k=2)$.
Hinweise:
- Die Aufgabe gehört zum Kapitel Entropiecodierung nach Huffman.
- Insbesondere wird auf die Seite Anwendung der Huffman-Codierung auf k-Tupel Bezug genommen.
- Eine vergleichbare Aufgabenstellung mit binären Eingangssymbolen wird in der Aufgabe 2.7 behandelt.
- Bezeichnen Sie die möglichen Zweiertupel mit $\rm XX = A$, $\rm XY = B$, $\rm XZ = C$, $\rm YX = D$, $\rm YY = E$, $\rm YZ = F$, $\rm ZX = G$, $\rm ZY = H$, $\rm ZZ = I$.
Fragebogen
Musterlösung
- $$L_{\rm M} = p_{\rm X} \cdot 1 + (p_{\rm Y} + p_{\rm Z}) \cdot 2 \hspace{0.15cm}\underline{= 1.3\,\,{\rm bit/Quellensymbol}}\hspace{0.05cm}. $$
Dieser Wert liegt noch deutlich über der Quellenentropie H = 1.157 bit/Quellensymbol.
(2) Es gibt M ′ = M 2 = 32 = 9 Zweiertupel mit folgenden Wahrscheinlichkeiten:
- pA = Pr(XX) = 0.49, pB = Pr(XY) = 0.14, pC = Pr(XZ) = 0.07,
- pD = Pr(YX) = 0.14, pE = Pr(YY) = 0.04, pF = Pr(YZ) = 0.02,
- pG = Pr(YX) = 0.07, pH = Pr(YY) = 0.02, pI = Pr(YZ) = 0.01.
(3) Die Grafik zeigt den Huffman–Baum für die Anwendung mit k = 2.
Damit erhält man
- für die einzelnen Zweiertupels folgende Binärcodierungen:
- XX = A → 0, XY = B → 111, XZ = C → 1011, YX = D → 110, YY = E → 1000,
- YZ = F → 10010, ZX = G → 1010, ZY = H → 100111, ZZ = I → 100110 .
- für die mittlere Codewortlänge:
- $$L_{\rm M}' =0.49 \cdot 1 + (0.14 + 0.14) \cdot 3 + (0.07 + 0.04 + 0.07) \cdot 4 + 0.02 \cdot 5 + (0.02 + 0.01) \cdot 6 = 2.33\,\,{\rm bit/Zweiertupel}$$
- $$\Rightarrow\hspace{0.3cm}L_{\rm M} = {L_{\rm M}'}/{2}\hspace{0.15cm}\underline{ = 1.165\,\,{\rm bit/Quellensymbol}}\hspace{0.05cm}.$$
(4) Richtig ist Aussage 1, auch wenn LM mit wachsendem k nur sehr langsam abfällt.
- Die letzte Aussage ist falsch, da LM auch für k → ∞ nicht kleiner sein kann als H = 1.157 bit/Quellensymbol.
- Aber auch die zweite Aussage ist nicht unbedingt richtig: Da mit k = 2 weiterhin LM > H gilt, kann k = 3 zu einer weiteren Verbesserung führen.