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

• Zurück zum Buch

Huffman–Baum für
eine 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\hspace{0.03cm}' = 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 hier 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

Musterlösung

(1)  Die mittlere Codewortlänge ergibt sich mit  $p_{\rm X} = 0.7$,  $L_{\rm X} = 1$,  $p_{\rm Y} = 0.2$,  $L_{\rm Y} = 2$,  $p_{\rm Z} = 0.1$,  $L_{\rm Z} = 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^k = 3^2$ = 9 Zweiertupel mit folgenden Wahrscheinlichkeiten:

Huffman–Baum für Ternärquelle und Zweiertupel

$$p_{\rm A} = \rm Pr(XX) = 0.7 \cdot 0.7\hspace{0.15cm}\underline{= 0.49},$$

$$p_{\rm B} = \rm Pr(XY) = 0.7 \cdot 0.2\hspace{0.15cm}\underline{= 0.14},$$

$$p_{\rm C} = \rm Pr(XZ) = 0.7 \cdot 0.1\hspace{0.15cm}\underline{= 0.07},$$

$$p_{\rm D} = \rm Pr(YX) = 0.2 \cdot 0.7 = 0.14,$$

$$p_{\rm E} = \rm Pr(YY) = 0.2 \cdot 0.2 = 0.04,$$

$$p_{\rm F} = \rm Pr(YZ) = 0.2 \cdot 0.1 = 0.02,$$

$$p_{\rm G} = \rm Pr(ZX) = 0.1 \cdot 0.7 = 0.07,$$

$$p_{\rm H} = \rm Pr(ZY) = 0.1 \cdot 0.2 = 0.02,$$

$$p_{\rm I} = \rm Pr(ZZ) = 0.1 \cdot 0.1 = 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:
  

    $\rm XX = A$   →   0,     $\rm XY = B$   →   111,     $\rm XZ = C$   →   1011,

    $\rm YX = D$   →   110,     $\rm YY = E$   →   1000,     $\rm YZ = F$   →   10010,

    $\rm ZX = G$   →   1010,     $\rm ZY = H$   →   100111,     $\rm ZZ =I$   →   100110.

• für die mittlere Codewortlänge:

$$L_{\rm M}\hspace{0.01cm}' =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}\hspace{0.01cm}'}/{2}\hspace{0.15cm}\underline{ = 1.165\,\,{\rm bit/Quellensymbol}}\hspace{0.05cm}.$$

(4)  Richtig ist die Aussage 1, auch wenn $L_{\rm M}$ mit wachsendem $k$ nur sehr langsam abfällt.

• Die letzte Aussage ist falsch, da $L_{\rm M}$ 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 $L_{\rm M} > H$ gilt, kann $k = 3$ zu einer weiteren Verbesserung führen.