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

Aus LNTwww
Wechseln zu:Navigation, Suche

P ID2458 Inf Z 2 7.png

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 LM, 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: {X, Y, Z},
  • Wahrscheinlichkeiten: pX = 0.7, pY = 0.2, pZ = 0.1,
  • Entropie: H = 1.157 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).

Hinweis: Die Aufgabe bezieht sich auf die letzte Theorieseite von Kapitel 2.3. Bezeichnen Sie die möglichen Zweiertupel mit

XX = A,  XY = B,  XZ = C,   YX = D,  YY = E,  YZ = F,  ZX = G,  ZY = H,  ZZ = I .


Fragebogen

1

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

$k = 1:\ L_M$ =

bit/Quellensymbol

2

Wie groß sind die Tupel–Wahrscheinlichkeiten? Insbesondere:

$p_A = Pr(XX)$ =

$p_B = Pr(XY)$ =

$p_C = Pr(XZ)$ =

3

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

$k = 2:\ L_M$ =

bit/Quellensymbol

4

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

LM fällt monoton mit steigendem k ab.
LM ändert sich nicht, wenn man k erhöht.
Für k = 3 erhält man LM = 1.05 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.

P ID2459 Inf Z 2 7c.png

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}' \hspace{0.2cm} = \hspace{0.2cm} 0.49 \cdot 1 + (0.14 + 0.14) \cdot 3 + (0.07 + 0.04 + 0.07) \cdot 4 + \\ \hspace{0.2cm} + \hspace{0.2cm}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 falsch: Da mit k = 2 weiterhin LM > H gilt, führt k = 3 zu einer Verbesserung.