Difference between revisions of "Aufgaben:Exercise 2.7Z: Huffman Coding for Two-Tuples of a Ternary Source"
From LNTwww
| Line 3: | Line 3: | ||
}} | }} | ||
| − | [[File:P_ID2458__Inf_Z_2_7.png|right|frame| | + | [[File:P_ID2458__Inf_Z_2_7.png|right|frame|Huffman tree for <br>a ternary source]] |
| − | + | We consider the same situation as in [[Aufgaben:2.7_Huffman-Anwendung_für_binäre_Zweiertupel|exercise A2.7]]: | |
| − | * | + | *The Huffman algorithm leads to a better result, i.e. to a smaller mean codeword length $L_{\rm M}$, if one does not apply it to individual symbols but forms $k$–tuples beforehand. |
| − | * | + | *This increases the symbol range from $M$ auf $M\hspace{0.03cm}' = M^k$. |
| − | + | For the message source considered here, the following applies: | |
| − | * | + | * Symbol range: $M = 3$, |
| − | * | + | * Symbol set: $\{$ $\rm X$, $\rm Y$, $\rm Z$ $\}$, |
| − | * | + | * Probabilities: $p_{\rm X} = 0.7$, $p_{\rm Y} = 0.2$, $p_{\rm Z} = 0.1$, |
| − | * | + | * Entropy: $H = 1.157 \ \rm bit/ternary symbol$. |
| − | + | The graph shows the Huffman tree when the Huffman algorithm is applied to single symbols $k= 1$. <br>In subtask '''(2)''' you are to give the corresponding Huffman code when two-tuples are formed beforehand $(k=2)$. | |
| Line 25: | Line 25: | ||
| − | '' | + | ''Hints:'' |
| − | * | + | *The task belongs to the chapter [[Information_Theory/Entropiecodierung_nach_Huffman|Entropy Coding according to Huffman]]. |
| − | * | + | *In particular, reference is made to the page [[Information_Theory/Entropiecodierung_nach_Huffman#Application_of_Huffman_coding_to_.7F.27.22.60UNIQ-MathJax168-QINU.60.22.27.7F.E2.80.93tuples|Application of Huffman coding to $k$-tuples]] . |
| − | * | + | *A comparable task with binary input symbols is dealt with in [[Aufgaben:2.7_Huffman-Anwendung_für_binäre_Zweiertupel|exercise 2.7]] behandelt. |
| − | * | + | *Designate the possible two-tuples with $\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$. |
| − | === | + | ===Quetions=== |
<quiz display=simple> | <quiz display=simple> | ||
| − | { | + | {What is the mean codeword length when the Huffman algorithm is applied directly to the ternary source symbols $\rm X$, $\rm Y$ und $\rm Z$ ? |
|type="{}"} | |type="{}"} | ||
| − | $\underline{k=1}\text{:} \hspace{0.25cm}L_{\rm M} \ = \ $ { 1.3 3% } $\ \rm bit/ | + | $\underline{k=1}\text{:} \hspace{0.25cm}L_{\rm M} \ = \ $ { 1.3 3% } $\ \rm bit/source symbol$ |
| − | { | + | {What are the tuple probabilities here? In particular: |
|type="{}"} | |type="{}"} | ||
$p_{\rm A} = \rm Pr(XX)\ = \ $ { 0.49 3% } | $p_{\rm A} = \rm Pr(XX)\ = \ $ { 0.49 3% } | ||
| Line 48: | Line 48: | ||
| − | { | + | {What is the mean codeword length if you first form two-tuples and apply the Huffman algorithm to them? |
|type="{}"} | |type="{}"} | ||
| − | $\underline{k=2}\text{:} \hspace{0.25cm}L_{\rm M} \ = \ $ { 1.165 3% } $\ \rm bit/ | + | $\underline{k=2}\text{:} \hspace{0.25cm}L_{\rm M} \ = \ $ { 1.165 3% } $\ \rm bit/source symbol$ |
| − | { | + | {Which of the following statements are true when more than two ternary symbols are combined $(k>2)$? |
|type="[]"} | |type="[]"} | ||
| − | + $L_{\rm M}$ | + | + $L_{\rm M}$ decreases monotonically with increasing $k$ ab. |
| − | - $L_{\rm M}$ | + | - $L_{\rm M}$ does not change when $k$ is increased. |
| − | - Für $k= 3$ | + | - Für $k= 3$ you get $L_{\rm M} = 1.05 \ \rm bit/source symbol$. |
| Line 63: | Line 63: | ||
</quiz> | </quiz> | ||
| − | === | + | ===Solution=== |
{{ML-Kopf}} | {{ML-Kopf}} | ||
'''(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 | '''(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 | ||
Revision as of 15:13, 3 August 2021
Huffman tree for
a ternary source
a ternary source
We consider the same situation as in exercise A2.7:
- The Huffman algorithm leads to a better result, i.e. to a smaller mean codeword length $L_{\rm M}$, if one does not apply it to individual symbols but forms $k$–tuples beforehand.
- This increases the symbol range from $M$ auf $M\hspace{0.03cm}' = M^k$.
For the message source considered here, the following applies:
- Symbol range: $M = 3$,
- Symbol set: $\{$ $\rm X$, $\rm Y$, $\rm Z$ $\}$,
- Probabilities: $p_{\rm X} = 0.7$, $p_{\rm Y} = 0.2$, $p_{\rm Z} = 0.1$,
- Entropy: $H = 1.157 \ \rm bit/ternary symbol$.
The graph shows the Huffman tree when the Huffman algorithm is applied to single symbols $k= 1$.
In subtask (2) you are to give the corresponding Huffman code when two-tuples are formed beforehand $(k=2)$.
Hints:
- The task belongs to the chapter Entropy Coding according to Huffman.
- In particular, reference is made to the page Application of Huffman coding to $k$-tuples .
- A comparable task with binary input symbols is dealt with in exercise 2.7 behandelt.
- Designate the possible two-tuples with $\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$.
Quetions
Solution
(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\hspace{0.03cm}' = 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.
