Aufgabe 2.7Z: Huffman-Codierung für Zweiertupel einer Ternärquelle

Aus LNTwww
Wechseln zu:Navigation, Suche

Huffman–Baum für 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

1

Wie groß ist die mittlere Codewortlänge, wenn der Huffman–Algorithmus direkt auf die ternären Quellensymbole $\rm X$, $\rm Y$ und $\rm Z$ angewendet wird?

$\underline{k=1}\text{:} \hspace{0.25cm}L_{\rm M} \ = \ $

$\ \rm bit/Quellensymbol$

2

Wie groß sind die Tupel–Wahrscheinlichkeiten? Insbesondere:

$p_{\rm A} = \rm Pr(XX)\ = \ $

$p_{\rm B} = \rm Pr(XY)\ = \ $

$p_{\rm C} = \rm Pr(XZ)\ = \ $

3

Wie groß ist die mittlere Codewortlänge, wenn man zuerst Zweiertupel bildet und darauf den Huffman–Algorithmus anwendet?

$\underline{k=2}\text{:} \hspace{0.25cm}L_{\rm M} \ = \ $

$\ \rm bit/Quellensymbol$

4

Welche der folgenden Aussagen sind zutreffend, wenn man mehr als zwei Ternärzeichen zusammenfasst ($k>2$)?

$L_{\rm M}$  fällt monoton mit steigendem  $k$  ab.
$L_{\rm M}$  ändert sich nicht, wenn man  $k$  erhöht.
Für  $k= 3$  erhält man  $L_{\rm M} = 1.05 \ \rm bit/Quellensymbol$.


Musterlösung

(1)  Die mittlere Codewortlänge ergibt sich mit pX = 0.7, LX = 1, pY = 0.2, LY = 2, pZ = 0.1, LZ = 2 zu

$$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.

Huffman–Baum für Ternärquelle und Zweiertupel

Damit erhält man

  • für die einzelnen Zweiertupels folgende Binärcodierungen:
    XX = A0,   XY = B111,   XZ = C1011,    YX = D110,   YY = E1000,
    YZ = F10010,    ZX = G1010,   ZY = H100111,   ZZ = I100110 .
  • 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.