*The given source symbol sequences apply to the conditional probabilities $q = 0.2$ and $q = 0.8$, respectively.
*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$ .
*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 [[Information_Theory/Nachrichtenquellen_mit_Gedächtnis|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 [[Aufgaben:1.5Z_Symmetrische_Markovquelle|exercise 1.5Z]] :
The properties of Markov sources are described in detail in the chapter [[Information_Theory/Discrete_Sources_with_Memory|Discrete 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 [[Aufgaben:1.5Z_Symmetrische_Markovquelle|Exercise 1.5Z]]:
* The symbols $\rm X$ and $\rm Y$ are equally probable, that is, $p_{\rm X} = p_{\rm Y} = 0.5$ holds. <br>Thus the first entropy approximation is: $H_1 = 1\,\,{\rm bit/source symbol}\hspace{0.05cm}. $
* The symbols $\rm X$ and $\rm Y$ are equally probable, that is, $p_{\rm X} = p_{\rm Y} = 0.5$ holds. <br>Thus the first entropy approximation is $H_1 = 1\,\,{\rm bit/source\hspace{0.15cm}symbol}\hspace{0.05cm}. $
* Die Entropie der Markovquelle ergibt sich sowohl für $q = 0.2$ als auch für $q = 0.8$ zu
* The entropy of the Markov source for $q = 0.2$ as well as for $q = 0.8$ results in
In dieser Aufgabe soll der Huffman–Algorithmus auf $k$–Tupel angewandt werden, wobei wir uns auf $k = 2$ und $k = 3$ beschränken.
In this exercise, the Huffman algorithm is to be applied to $k$–tuples, where we restrict ourselves to $k = 2$ and $k = 3$.
Line 32:
Line 27:
''Hinweise:''
<u>Hints:</u>
*Die Aufgabe gehört zum Kapitel [[Information_Theory/Entropiecodierung_nach_Huffman|Entropiecodierung nach Huffman]].
*The exercise belongs to the chapter [[Information_Theory/Entropiecodierung_nach_Huffman|Entropy Coding according to Huffman]].
*Insbesondere wird auf die Seite [[Information_Theory/Entropiecodierung_nach_Huffman#Anwendung_der_Huffman.E2.80.93Codierung_auf_.7F.27.22.60UNIQ-MathJax164-QINU.60.22.27.7F.E2.80.93Tupel|Anwendung der Huffman-Codierung auf k-Tupel]] Bezug genommen.
*In particular, reference is made to the page [[Information_Theory/Entropy_Coding_According_to_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]].
*Nützliche Informationen finden Sie auch in den Angabenblättern zu [[Aufgaben:2.7_Huffman-Anwendung_für_binäre_Zweiertupel|Aufgabe 2.7]] und [[Aufgaben:2.7Z_Huffman-Codierung_für_Zweiertupel_einer_Ternärquelle|Aufgabe 2.7Z]].
*Useful information can also be found in the specification sheets for [[Aufgaben:Exercise_2.7:_Huffman_Application_for_Binary_Two-Tuples|Exercise 2.7]] and [[Aufgaben:Exercise_2.7Z:_Huffman_Coding_for_Two-Tuples_of_a_Ternary_Source|Exercise 2.7Z]].
*Zur Kontrolle Ihrer Ergebnisse verweisen wir auf das Interaktionsmodul [[Applets:Huffman-_und_Shannon-Fano-Codierung|Huffman und Shannon–Fano––Codierung]].
*To check your results, please refer to the (German language) SWF module [[Applets:Huffman_Shannon_Fano|Coding according to Huffman and Shannon/Fano]].
===Fragebogen===
===Questions===
<quiz display=simple>
<quiz display=simple>
{Welche der vorne angegebenen Beispielfolgen gilt für $q = 0.8$?
{Which of the example sequences given at the front is true for $q = 0.8$?
|type="[]"}
|type="()"}
- die rote Quellensymbolfolge '''1''',
- The red source symbol sequence '''1''',
+ die blaue Quellensymbolfolge '''2'''.
+ the blue source symbol sequence '''2'''.
{Welche der folgenden Aussagen treffen zu?
{Which of the following statements are true?
|type="[]"}
|type="[]"}
- Auch die direkte Anwendung von Huffman ist hier sinnvoll.
- The direct application of Huffman is also useful here.
+ Huffman macht bei Bildung von Zweiertupeln $(k = 2)$ Sinn.
+ Huffman makes sense when forming two-tuples $(k = 2)$.
+ Huffman macht bei Bildung von Dreiertupeln $(k = 3)$ Sinn.
+ Huffman makes sense when forming tuples of three $(k = 3)$.
{Wie lauten die Wahrscheinlichkeiten der <u>Zweiertupel</u> $(k = 2)$ für $\underline{q = 0.8}$?
{What are the probabilities of <u>two-tuples</u> $(k = 2)$ for $\underline{q = 0.8}$?
|type="{}"}
|type="{}"}
$p_{\rm A} = \rm Pr(XX)\ = \ $ { 0.4 3% }
$p_{\rm A} = \rm Pr(XX)\ = \ $ { 0.4 3% }
Line 65:
Line 60:
{Ermitteln Sie den Huffman–Code für $\underline{k = 2}$. Wie groß ist in diesem Fall die mittlere Codewortlänge?
{Find the Huffman code for $\underline{k = 2}$. What is the average code word length in this case?
'''(1)''' Richtig ist der <u>Lösungsvorschlag 2</u>:
'''(1)''' Correct is the <u>solution suggestion 2</u>:
*Bei der blauen Quellensymbolfolge '''2''' erkennt man sehr viel weniger Symbolwechsel als in der roten Folge.
*In the blue source symbol sequence '''2''' one recognizes much less symbol changes than in the red sequence.
*Die Symbolfolge '''2''' wurde mit dem Parameter $q = {\rm Pr}(\boldsymbol{\rm X}\hspace{0.05cm}|\hspace{0.05cm}\boldsymbol{\rm X}) =
*The symbol sequence '''2''' was generated with the 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$.
{\rm Pr}(\boldsymbol{\rm Y}\hspace{0.05cm}|\hspace{0.05cm}\boldsymbol{\rm Y}) = 0.8$ and the red symbol sequence '''1''' with $q = 0.2$.
'''(2)''' Richtig sind die <u>Antworten 2 und 3</u>.:
'''(2)''' <u>Answers 2 and 3</u> are correct:
*Da hier die Quellensymbole $\rm X$ und $\rm Y$ als gleichwahrscheinlich angenommen wurden, macht die direkte Anwendung von Huffman keinen Sinn.
*Since here the source symbols $\rm X$ and $\rm Y$ were assumed to be equally probable, the direct application of Huffman makes no sense.
*Dagegen kann man die inneren statistischen Bindungen der Markovquelle zur Datenkomprimierung nutzen, wenn man $k$–Tupel bildet $(k ≥ 2)$.
*In contrast, one can use the inner statistical depenndecies of the Markov source for data compression if one forms $k$–tuples $(k ≥ 2)$.
*Je größer $k$ ist, desto mehr nähert sich die mittlere Codewortlänge $L_{\rm M}$ der Entropie $H$.
*The larger $k$ is, the more the average code word length $L_{\rm M}$ approaches the entropy $H$.
'''(3)''' Die Symbolwahrscheinlichkeiten sind $p_{\rm X} = p_{\rm Y} = 0.5$. Damit erhält man für die Zweiertupel:
'''(3)''' The symbol probabilities are $p_{\rm X} = p_{\rm Y} = 0.5$, which gives us for the two-tuples:
[[File:P_ID2462__Inf_A_2_8d.png|right|frame|Zur Huffman–Codierung für $k = 2$]]
[[File:P_ID2462__Inf_A_2_8d.png|right|frame|For Huffman coding for $k = 2$]]
'''(4)''' Nebenstehender Bildschirmabzug des (früheren) SWF–Programms [[Applets:Huffman_Shannon_Fano|Shannon–Fano– und Huffman–Codierung]] zeigt die Konstruktion des Huffman–Codes für $k = 2$ mit den soeben berechneten Wahrscheinlichkeiten.
'''(4)''' Opposite screen capture of the (earlier) SWF applet [[Applets:Huffman_Shannon_Fano|Coding according to Huffman and Shannon/Fano]] shows the construction of the Huffman code for $k = 2$ with the probabilities just calculated.
'''(5)''' Richtig iist der <u>Lösungsvorschlag 2</u>:
'''(5)''' Correct is the <u>suggested solution 2</u>:
*Nach dem Quellencodierungstheorem gilt $L_{\rm M} ≥ H$.
*According to the source coding theorem $L_{\rm M} ≥ H$ holds.
*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).
*However, if we apply Huffman coding and disregard ties between non-adjacent symbols $(k = 2)$, the lower bound of the code word length is not $H = 0.722$, but $H_2 = 0.861$ (the addition "bit/source symbol" is omitted for the rest of the task).
*Das Ergebnis der Teilaufgabe '''(4)''' war $L_{\rm M} = 0.9.$
*The result of subtask '''(4)''' was $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$.
*If an asymmetrical Markov chain were present and in such a way that for the probabilities $p_{\rm A}$, ... , $p_{\rm D}$ the values $50\%$, $25\%$ and twice $12.5\%$ would result, then one would come to the average code word length $L_{\rm M} = 0.875$.
*Wie die genauen Parameter dieser unsymmetrischen Markovquelle aussehen, weiß aber auch der Aufgabensteller (G. Söder) nicht.
*How the exact parameters of this asymmetrical Markov source look, however, is not known even to the task creator (G. Söder).
*Auch nicht, wie sich der Wert $0.875$ auf $0.861$ senken ließe. Der Huffman–Algorithmus ist hierfür jedenfalls ungeeignet.
*Nor how the value $0.875$ could be reduced to $0.861$. In any case, the Huffman algorithm is unsuitable for this.
'''(7)''' Der Bildschirmabzug des des (früheren) SWF–Programms [[Applets:Huffman_Shannon_Fano|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:
[[File:P_ID2463__Inf_A_2_8g.png|right|frame|On the Huffman coding for $k = 3$]]
'''(7)''' The screen capture of the of the (earlier) SWF applet [[Applets:Huffman_Shannon_Fano|Coding according to Huffman and Shannon/Fano]] coding illustrates the constellation of the Huffman code for $k = 3$.
*Man erkennt die Verbesserung gegenüber der Teilaufgabe '''(4)'''.
*One can see the improvement over subtask '''(4)'''.
*Die für $k = 2$ gültige Schranke $H_2 = 0.861$ wird nun von der mittleren Codewortlänge $L_{\rm M}$ unterschritten.
*The bound $k = 2$ valid for $H_2 = 0.861$ is now undercut by the average code word length $L_{\rm M}$.
*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 → ∞)$.
*However, to reach the source entropy $H = 0.722$ (or better: to come close to this final value up to an $ε$ ), one would have to form infinitely long tuples $(k → ∞)$.
{{ML-Fuß}}
{{ML-Fuß}}
Line 161:
Line 157:
[[Category:Information Theory: Exercises|^2.3 Entropy Coding according to Huffman^]]
[[Category:Information Theory: Exercises|^2.3 Entropy Coding according to Huffman^]]
[[de:Aufgaben:Aufgabe 2.8: Huffman-Anwendung bei einer Markovquelle]]
The given source symbol sequences apply to the conditional probabilities $q = 0.2$ and $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 Discrete 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\hspace{0.15cm}symbol}\hspace{0.05cm}. $
The entropy of the Markov source for $q = 0.2$ as well as for $q = 0.8$ results in
(4) Opposite screen capture of the (earlier) SWF applet Coding according to Huffman and Shannon/Fano shows the construction of the Huffman code for $k = 2$ with the probabilities just calculated.
According to the source coding theorem $L_{\rm M} ≥ H$ holds.
However, if we apply Huffman coding and disregard ties between non-adjacent symbols $(k = 2)$, the lower bound of the code word length is not $H = 0.722$, but $H_2 = 0.861$ (the addition "bit/source symbol" is omitted for the rest of the task).
The result of subtask (4) was $L_{\rm M} = 0.9.$
If an asymmetrical Markov chain were present and in such a way that for the probabilities $p_{\rm A}$, ... , $p_{\rm D}$ the values $50\%$, $25\%$ and twice $12.5\%$ would result, then one would come to the average code word length $L_{\rm M} = 0.875$.
How the exact parameters of this asymmetrical Markov source look, however, is not known even to the task creator (G. Söder).
Nor how the value $0.875$ could be reduced to $0.861$. In any case, the Huffman algorithm is unsuitable for this.
The bound $k = 2$ valid for $H_2 = 0.861$ is now undercut by the average code word length $L_{\rm M}$.
The new bound for $k = 3$ is $H_3 = 0.815$.
However, to reach the source entropy $H = 0.722$ (or better: to come close to this final value up to an $ε$ ), one would have to form infinitely long tuples $(k → ∞)$.
