Difference between revisions of "Aufgaben:Exercise 2.8: Huffman Application for a Markov Source"
From LNTwww
| Line 16: | Line 16: | ||
* The entropy of the Markov source for $q = 0.2$ as well as for $q = 0.8$ results in | * The entropy of the Markov source for $q = 0.2$ as well as for $q = 0.8$ results in | ||
:$$H = q \cdot {\rm log_2}\hspace{0.15cm}\frac{1}{q} + (1-q) \cdot {\rm log_2}\hspace{0.15cm}\frac{1}{1-q} | :$$H = q \cdot {\rm log_2}\hspace{0.15cm}\frac{1}{q} + (1-q) \cdot {\rm log_2}\hspace{0.15cm}\frac{1}{1-q} | ||
| − | = 0.722\,\,{\rm bit/source symbol}\hspace{0.05cm}.$$ | + | = 0.722\,\,{\rm bit/source\:symbol}\hspace{0.05cm}.$$ |
* For Markov sources, all entropy approximations $H_k$ with order $k \ge 2$ are determined by $H_1$ and $H = H_{k \to \infty}$ : | * For Markov sources, all entropy approximations $H_k$ with order $k \ge 2$ are determined by $H_1$ and $H = H_{k \to \infty}$ : | ||
:$$H_k = {1}/{k}\cdot \big [ H_1 + H \big ] \hspace{0.05cm}.$$ | :$$H_k = {1}/{k}\cdot \big [ H_1 + H \big ] \hspace{0.05cm}.$$ | ||
*The following numerical values again apply equally to $q = 0.2$ and $q = 0.8$ : | *The following numerical values again apply equally to $q = 0.2$ and $q = 0.8$ : | ||
| − | :$$H_2 = {1}/{2}\cdot \big [ H_1 + H \big ] = 0.861\,\,{\rm bit/source symbol}\hspace{0.05cm},$$ | + | :$$H_2 = {1}/{2}\cdot \big [ H_1 + H \big ] = 0.861\,\,{\rm bit/source\:symbol}\hspace{0.05cm},$$ |
| − | :$$H_3 = {1}/{3} \cdot \big [ H_1 + 2H \big ] = 0.815\,\,{\rm bit/source symbol}\hspace{0.05cm}.$$ | + | :$$H_3 = {1}/{3} \cdot \big [ H_1 + 2H \big ] = 0.815\,\,{\rm bit/source\:symbol}\hspace{0.05cm}.$$ |
In this exercise, the Huffman algorithm is to be applied to $k$–tuples, where we restrict ourselves to $k = 2$ and $k = 3$ . | In this exercise, the Huffman algorithm is to be applied to $k$–tuples, where we restrict ourselves to $k = 2$ and $k = 3$ . | ||
| Line 67: | Line 67: | ||
Find the Huffman code for $\underline{k = 2}$. What is the mean codeword length in this case? | Find the Huffman code for $\underline{k = 2}$. What is the mean codeword length in this case? | ||
|type="{}"} | |type="{}"} | ||
| − | $L_{\rm M} \ = \ $ { 0.9 3% } $\ \rm bit/source symbol$ | + | $L_{\rm M} \ = \ $ { 0.9 3% } $\ \rm bit/source\:symbol$ |
{What is the bound on the mean codeword length when <u>two-tuples</u> are formed $(k = 2)$? Interpretation. | {What is the bound on the mean codeword length when <u>two-tuples</u> are formed $(k = 2)$? Interpretation. | ||
|type="()"} | |type="()"} | ||
| − | - $L_{\rm M} \ge H_1 = 1.000$ bit/source symbol, | + | - $L_{\rm M} \ge H_1 = 1.000$ bit/source\:symbol, |
| − | + $L_{\rm M} \ge H_2 \approx 0.861$ bit/source symbol, | + | + $L_{\rm M} \ge H_2 \approx 0.861$ bit/source\:symbol, |
| − | - $L_{\rm M} \ge H_3 \approx 0.815$ bit/source symbol, | + | - $L_{\rm M} \ge H_3 \approx 0.815$ bit/source\:symbol, |
| − | - $L_{\rm M} \ge H_{k \to \infty} \approx 0.722$ bit/source symbol, | + | - $L_{\rm M} \ge H_{k \to \infty} \approx 0.722$ bit/source\:symbol, |
| − | - $L_{\rm M} \ge 0.5$ bit/source symbol. | + | - $L_{\rm M} \ge 0.5$ bit/source\:symbol. |
| Line 93: | Line 93: | ||
{Find the Huffman code for $\underline{k = 3}$. What is the mean codeword length in this case? | {Find the Huffman code for $\underline{k = 3}$. What is the mean codeword length in this case? | ||
|type="{}"} | |type="{}"} | ||
| − | $L_{\rm M} \ = \ $ { 0.84 3% } $\ \rm bit/source symbol$ | + | $L_{\rm M} \ = \ $ { 0.84 3% } $\ \rm bit/source\:symbol$ |
Revision as of 19:58, 4 August 2021
Binary symmetric Markov source
We consider the binary symmetric Markov source according to the graph, which is given by the single parameter
- $$q = {\rm Pr}(\boldsymbol{\rm X}\hspace{0.05cm}|\hspace{0.05cm}\boldsymbol{\rm X}) = {\rm Pr}(\boldsymbol{\rm Y}\hspace{0.05cm}|\hspace{0.05cm}\boldsymbol{\rm Y})$$
completely.
- The given source symbol sequences apply to the conditional probabilities $q = 0.2$ bzw. $q = 0.8$, respectively.
- In subtask (1) it has to be clarified which symbol sequence – the red or the blue one – was generated with $q = 0.2$ and which with $q = 0.8$ .
The properties of Markov sources are described in detail in the chapter Message Sources with Memory . Due to the symmetry assumed here with regard to the binary symbols $\rm X$ and $\rm Y$ , some serious simplifications result, as is derived in exercise 1.5Z :
- The symbols $\rm X$ and $\rm Y$ are equally probable, that is, $p_{\rm X} = p_{\rm Y} = 0.5$ holds.
Thus the first entropy approximation is: $H_1 = 1\,\,{\rm bit/source symbol}\hspace{0.05cm}. $ - The entropy of the Markov source for $q = 0.2$ as well as for $q = 0.8$ results in
- $$H = q \cdot {\rm log_2}\hspace{0.15cm}\frac{1}{q} + (1-q) \cdot {\rm log_2}\hspace{0.15cm}\frac{1}{1-q} = 0.722\,\,{\rm bit/source\:symbol}\hspace{0.05cm}.$$
- For Markov sources, all entropy approximations $H_k$ with order $k \ge 2$ are determined by $H_1$ and $H = H_{k \to \infty}$ :
- $$H_k = {1}/{k}\cdot \big [ H_1 + H \big ] \hspace{0.05cm}.$$
- The following numerical values again apply equally to $q = 0.2$ and $q = 0.8$ :
- $$H_2 = {1}/{2}\cdot \big [ H_1 + H \big ] = 0.861\,\,{\rm bit/source\:symbol}\hspace{0.05cm},$$
- $$H_3 = {1}/{3} \cdot \big [ H_1 + 2H \big ] = 0.815\,\,{\rm bit/source\:symbol}\hspace{0.05cm}.$$
In this exercise, the Huffman algorithm is to be applied to $k$–tuples, where we restrict ourselves to $k = 2$ and $k = 3$ .
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 .
- Useful information can also be found in the specification sheets for exercise 2.7 and exercise 2.7Z.
- To check your results, please refer to the interaction module Huffman and Shannon–Fano––coding.
Questions
Solution
(1) Richtig ist der Lösungsvorschlag 2:
- Bei der blauen Quellensymbolfolge 2 erkennt man sehr viel weniger Symbolwechsel als in der roten Folge.
- Die Symbolfolge 2 wurde mit dem Parameter $q = {\rm Pr}(\boldsymbol{\rm X}\hspace{0.05cm}|\hspace{0.05cm}\boldsymbol{\rm X}) = {\rm Pr}(\boldsymbol{\rm Y}\hspace{0.05cm}|\hspace{0.05cm}\boldsymbol{\rm Y}) = 0.8$ erzeugt und die rote Symbolfolge 1 mit $q = 0.2$.
(2) Richtig sind die Antworten 2 und 3.:
- Da hier die Quellensymbole $\rm X$ und $\rm Y$ als gleichwahrscheinlich angenommen wurden, macht die direkte Anwendung von Huffman keinen Sinn.
- Dagegen kann man die inneren statistischen Bindungen der Markovquelle zur Datenkomprimierung nutzen, wenn man $k$–Tupel bildet $(k ≥ 2)$.
- Je größer $k$ ist, desto mehr nähert sich die mittlere Codewortlänge $L_{\rm M}$ der Entropie $H$.
(3) Die Symbolwahrscheinlichkeiten sind $p_{\rm X} = p_{\rm Y} = 0.5$. Damit erhält man für die Zweiertupel:
- $$p_{\rm A} \hspace{0.2cm} = \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm XX}) = p_{\rm X} \cdot {\rm Pr}(\boldsymbol{\rm X}\hspace{0.05cm}|\hspace{0.05cm}\boldsymbol{\rm X}) = 0.5 \cdot q = 0.5 \cdot 0.8 \hspace{0.15cm}\underline{ = 0.4} \hspace{0.05cm},$$
- $$p_{\rm B} \hspace{0.2cm} = \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm XY}) = p_{\rm X} \cdot {\rm Pr}(\boldsymbol{\rm Y}\hspace{0.05cm}|\hspace{0.05cm}\boldsymbol{\rm X}) = 0.5 \cdot (1-q)= 0.5 \cdot 0.2 \hspace{0.15cm}\underline{ = 0.1} \hspace{0.05cm},$$
- $$p_{\rm C} \hspace{0.2cm} = \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm YX}) = p_{\rm Y} \cdot {\rm Pr}(\boldsymbol{\rm X}\hspace{0.05cm}|\hspace{0.05cm}\boldsymbol{\rm Y}) = 0.5 \cdot (1-q)= 0.5 \cdot 0.2 \hspace{0.15cm}\underline{ = 0.1} \hspace{0.05cm},$$
- $$p_{\rm D} \hspace{0.2cm} = \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm YY}) = p_{\rm Y} \cdot {\rm Pr}(\boldsymbol{\rm Y}\hspace{0.05cm}|\hspace{0.05cm}\boldsymbol{\rm Y}) = 0.5 \cdot q = 0.5 \cdot 0.8\hspace{0.15cm}\underline{ = 0.4} \hspace{0.05cm}.$$
Zur Huffman–Codierung für $k = 2$
(4) Nebenstehender Bildschirmabzug des (früheren) SWF–Programms Shannon–Fano– und Huffman–Codierung zeigt die Konstruktion des Huffman–Codes für $k = 2$ mit den soeben berechneten Wahrscheinlichkeiten.
- Damit gilt für die mittlere Codewortlänge:
- $$L_{\rm M}\hspace{0.01cm}' = 0.4 \cdot 1 + 0.4 \cdot 2 + (0.1 + 0.1) \cdot 3 = 1.8\,\,{\rm bit/Zweiertupel}$$
- $$\Rightarrow\hspace{0.3cm}L_{\rm M} = {L_{\rm M}\hspace{0.01cm}'}/{2}\hspace{0.15cm}\underline{ = 0.9\,{\rm bit/Quellensymbol}}\hspace{0.05cm}.$$
(5) Richtig iist der Lösungsvorschlag 2:
- Nach dem Quellencodierungstheorem gilt $L_{\rm M} ≥ H$.
- Wendet man aber Huffman–Codierung an und lässt dabei Bindungen zwischen nicht benachbarten Symbolen außer Betracht $(k = 2)$, so gilt als unterste Grenze der Codewortlänge nicht $H = 0.722$, sondern $H_2 = 0.861$ (auf den Zusatz bit/Quellensymbol wird für den Rest der Aufgabe verzichtet).
- Das Ergebnis der Teilaufgabe (4) war $L_{\rm M} = 0.9.$
- Würde eine unsymmetrische Markovkette vorliegen und zwar derart, dass sich für die Wahrscheinlichkeiten $p_{\rm A}$, ... , $p_{\rm D}$ die Werte $50\%$, $25\%$ und zweimal $12.5\%$ ergeben würden, so käme man auf die mittlere Codewortlänge $L_{\rm M} = 0.875$.
- Wie die genauen Parameter dieser unsymmetrischen Markovquelle aussehen, weiß aber auch der Aufgabensteller (G. Söder) nicht.
- Auch nicht, wie sich der Wert $0.875$ auf $0.861$ senken ließe. Der Huffman–Algorithmus ist hierfür jedenfalls ungeeignet.
(6) Mit $q = 0.8$ und $1 - q = 0.2$ erhält man:
- $$p_{\rm A} \hspace{0.2cm} = \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm XXX}) = 0.5 \cdot q^2 \hspace{0.15cm}\underline{ = 0.32} = p_{\rm H} = {\rm Pr}(\boldsymbol{\rm YYY})\hspace{0.05cm},$$
- $$p_{\rm B} \hspace{0.2cm} = \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm XXY}) = 0.5 \cdot q \cdot (1-q) \hspace{0.15cm}\underline{ = 0.08}= p_{\rm G} = {\rm Pr}(\boldsymbol{\rm YYX}) \hspace{0.05cm},$$
- $$p_{\rm C} \hspace{0.2cm} = \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm XYX}) = 0.5 \cdot (1-q)^2\hspace{0.15cm}\underline{ = 0.02} = p_{\rm F}= {\rm Pr}(\boldsymbol{\rm YXY}) \hspace{0.05cm},$$
- $$p_{\rm D} \hspace{0.2cm} = \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm XYY}) = 0.5 \cdot (1-q) \cdot q \hspace{0.15cm}\underline{ = 0.08} = p_{\rm E} = {\rm Pr}(\boldsymbol{\rm YXX})\hspace{0.05cm}.$$
(7) Der Bildschirmabzug des des (früheren) SWF–Programms Shannon–Fano– und Huffman–Codierung verdeutlicht die Konstellation des Huffman–Codes für $k = 3$. Damit erhält man für die mittlere Codewortlänge:
- $$L_{\rm M}\hspace{0.01cm}' = 0.64 \cdot 2 + 0.24 \cdot 3 + 0.04 \cdot 5 = 2.52\,\,{\rm bit/Dreiertupel}\hspace{0.3cm} \Rightarrow\hspace{0.3cm}L_{\rm M} = {L_{\rm M}\hspace{0.01cm}'}/{3}\hspace{0.15cm}\underline{ = 0.84\,{\rm bit/Quellensymbol}}\hspace{0.05cm}.$$
Zur Huffman–Codierung für $k = 3$
- Man erkennt die Verbesserung gegenüber der Teilaufgabe (4).
- Die für $k = 2$ gültige Schranke $H_2 = 0.861$ wird nun von der mittleren Codewortlänge $L_{\rm M}$ unterschritten.
- Die neue Schranke für $k = 3$ ist $H_3 = 0.815$.
- Um die Quellenentropie $H = 0.722$ zu erreichen (besser gesagt: diesem Endwert bis auf ein $ε$ nahe zu kommen), müsste man allerdings unendlich lange Tupel bilden $(k → ∞)$.
