vollständig beschrieben wird. Die angegebenen Quellensymbolfolgen gelten für die bedingten Wahrscheinlichkeiten $q = 0.2$ bzw. $q = 0.8$. In der Teilaufgabe (1) ist zu klären, welche Symbolfolge – die rote oder die blaue – mit $q = 0.2$ und welche mit $q = 0.8$ generiert wurde.
Die Eigenschaften von Markovquellen werden im Kapitel [[Informationstheorie/Nachrichtenquellen_mit_Gedächtnis|Nachrichtenquellen mit Gedächtnis]] ausführlich beschrieben. Aufgrund der hier vorausgesetzten Symmetrie bezüglich der Binärsymbole <b>X</b> und <b>Y</b> ergeben sich einige gravierende Vereinfachungen, wie in der [[Aufgaben:1.5Z_Symmetrische_Markovquelle|Zusatzaufgabe 1.5Z]] hergeleitet wird:
*The given source symbol sequences apply to the conditional probabilities $q = 0.2$ and $q = 0.8$, respectively.
* Die Symbole <b>X</b> und <b>Y</b> sind gleichwahrscheinlich, das heißt, es ist $p_{\rm X} = p_{\rm Y} = 0.5$. Damit lautet die erste Entropienäherung: $H_1 = 1\,\,{\rm bit/Quellensymbol}\hspace{0.05cm}. $
*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$ .
* Die Entropie der Markovquelle ergibt sich sowohl für $q = 0.2$ als auch für $q = 0.8$ zu
* Bei Markovquellen sind [[Informationstheorie/Nachrichtenquellen_mit_Gedächtnis#Bin.C3.A4rquellen_mit_Markoveigenschaften|alle Entropienäherungen mit Ordnung $k \ge 2$]] durch $H_1$ und $H = H_{k \to \infty}$ bestimmt. Die folgenden Zahlenwerte gelten wieder für $q = 0.2$ und $q = 0.8$ gleichermaßen:
In dieser Aufgabe soll der Huffman–Algorithmus auf $k$–Tupel angewandt werden, wobei wir uns auf $k = 2$ und $k = 3$ beschränken.
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\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
In this exercise, the Huffman algorithm is to be applied to $k$–tuples, where we restrict ourselves to $k = 2$ and $k = 3$.
*Die Aufgabe gehört zum Kapitel [[Informationstheorie/Entropiecodierung_nach_Huffman|Entropiecodierung nach Huffman]].
*Insbesondere wird auf die Seite [[Informationstheorie/Entropiecodierung_nach_Huffman#Anwendung_der_Huffman.E2.80.93Codierung_auf_k.E2.80.93Tupel|Anwendung der Huffman-Codierung auf k-Tupel]] Bezug genommen.
*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|Zusatzaufgabe 2.7Z]].
*Zur Kontrolle Ihrer Ergebnisse verweisen wir auf das Interaktionsmodul [[Shannon–Fano– und Huffman–Codierung]].
*Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.
===Fragebogen===
<u>Hints:</u>
*The exercise belongs to the chapter [[Information_Theory/Entropiecodierung_nach_Huffman|Entropy Coding according to Huffman]].
*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]].
*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]].
*To check your results, please refer to the (German language) SWF module [[Applets:Huffman_Shannon_Fano|Coding according to Huffman and Shannon/Fano]].
===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 Zweiertupel ($k = 2$) für $q = 0.8$?
{What are the probabilities of <u>two-tuples</u> $(k = 2)$ for $\underline{q = 0.8}$?
<b>1.</b> Bei der Quellensymbolfolge 2 erkennt man sehr viel weniger Symbolwechsel als in der roten Folge. Die blaue Symbolfolge 2 wurde mit dem Parameter
'''(1)''' Correct is the <u>solution suggestion 2</u>:
*The symbol sequence '''2''' was generated with the parameter $q = {\rm Pr}(\boldsymbol{\rm X}\hspace{0.05cm}|\hspace{0.05cm}\boldsymbol{\rm X}) =
erzeugt und die rote Symbolfolge 1 mit <i>q</i> = 0.2 ⇒ Richtig ist der <u>Lösungsvorschlag 2</u>.
{\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)''' <u>Answers 2 and 3</u> are correct:
*Since here the source symbols $\rm X$ and $\rm Y$ were assumed to be equally probable, the direct application of Huffman makes no sense.
*In contrast, one can use the inner statistical depenndecies of the Markov source for data compression if one forms $k$–tuples $(k ≥ 2)$.
*The larger $k$ is, the more the average code word length $L_{\rm M}$ approaches the entropy $H$.
'''(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|For Huffman coding for $k = 2$]]
'''(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.
<b>2.</b> Da hier die Quellensymbole <b>X</b> und <b>Y</b> 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 <i>k</i>–Tupel bildet (<i>k</i> ≥ 2). Richtig sind demnach die <u>Antworten 2 und 3</u>. Je größer <i>k</i> ist, desto mehr nähert sich die Codewortlänge <i>L</i><sub>M</sub> der Entropie <i>H</i>.
'''(5)''' Correct is the <u>suggested solution 2</u>:
*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.
<b>3.</b> Die Symbolwahrscheinlichkeiten <i>p</i><sub>X</sub> und <i>p</i><sub>Y</sub> sind jeweils 0.5. Damit erhält man für die Zweiertupel:
<b>4.</b> Nebenstehender Bildschirmabzug des Programms Shannon–Fano– und Huffman–Codierung zeigt die Konstruktion des Huffman–Codes für <i>k</i> = 2 mit den soeben berechneten Wahrscheinlichkeiten. Damit gilt für die mittlere Codewortlänge:
<br><br><b>5.</b> Nach dem Quellencodierungstheorem gilt <i>L</i><sub>M</sub> ≥ <i>H</i>. Wendet man aber Huffman–Codierung an und lässt dabei Bindungen zwischen nicht benachbarten Symbolen außer Betracht (<i>k</i> = 2), so gilt als unterste Grenze der Codewortlänge nicht <i>H</i> = 0.722, sondern <i>H</i><sub>2</sub> = 0.861 (auf den Zusatz bit/Quellensymbol wird für den Rest der Aufgabe verzichtet) ⇒ <u>Lösungsvorschlag 2</u>.
Das Ergebnis der Teilaufgabe 4) war <i>L</i><sub>M</sub> = 0.9. Würde eine unsymmetrische Markovkette vorliegen und zwar derart, dass sich für die Wahrscheinlichkeiten <i>p</i><sub>A</sub>, ... , <i>p</i><sub>D</Sub> die Werte 50%, 25% und zweimal 12.5% ergeben würden, so käme man auf die mittlere Codewortlänge <i>L</i><sub>M</sub> = 0.875. Wie die genauen Parameter dieser unsymmetrischen Markovquelle aussehen, weiß ich (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.
[[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$.
<b>7.</b> Der Bildschirmabzug des Flash–Moduls verdeutlicht die Konstellation des Huffman–Codes für <i>k</i> = 3. Damit erhält man für die mittlere Codewortlänge:
*One can see the improvement over subtask '''(4)'''.
*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 → ∞)$.
Man erkennt die Verbesserung gegenüber (4). Die für <i>k</i> = 2 gültige informationstheoretische Schranke <i>H</i><sub>2</sub> = 0.861 wird nun unterschritten (<i>L</i><sub>M</sub>). Die neue Schranke für <i>k</i> = 3 ist <i>H</i><sub>3</sub> = 0.815. Um die Quellenentropie <i>H</i> = 0.722 zu erreichen (besser gesagt: diesem Endwert bis auf ein ε näher zu kommen), müsste man allerdings unendlich lange Tupel bilden (<i>k</i> → ∞).
{{ML-Fuß}}
{{ML-Fuß}}
Line 129:
Line 156:
[[Category:Aufgaben zu Informationstheorie|^2.3 Entropiecodierung nach 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 → ∞)$.
