*Die angegebenen Quellensymbolfolgen gelten für die bedingten Wahrscheinlichkeiten $q = 0.2$ bzw. $q = 0.8$.
*The given source symbol sequences apply to the conditional probabilities $q = 0.2$ bzw. $q = 0.8$, respectively.
*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.
*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 Eigenschaften von Markovquellen werden im Kapitel [[Information_Theory/Nachrichtenquellen_mit_Gedächtnis|Nachrichtenquellen mit Gedächtnis]] ausführlich beschrieben. Aufgrund der hier vorausgesetzten Symmetrie bezüglich der Binärsymbole $\rm X$ und $\rm Y$ ergeben sich einige gravierende Vereinfachungen, wie in der [[Aufgaben:1.5Z_Symmetrische_Markovquelle|Aufgabe 1.5Z]] hergeleitet wird:
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]] :
* Die Symbole $\rm X$ und $\rm Y$ sind gleichwahrscheinlich, das heißt, es gilt $p_{\rm X} = p_{\rm Y} = 0.5$. <br>Damit lautet die erste Entropienäherung: $H_1 = 1\,\,{\rm bit/Quellensymbol}\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 symbol}\hspace{0.05cm}. $
* Die Entropie der Markovquelle ergibt sich sowohl für $q = 0.2$ als auch für $q = 0.8$ zu
* Die Entropie der Markovquelle ergibt sich sowohl für $q = 0.2$ als auch für $q = 0.8$ zu
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}. $
Die Entropie der Markovquelle ergibt sich sowohl für $q = 0.2$ als auch für $q = 0.8$ zu
(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.
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.
(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:
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 → ∞)$.
