*The given source symbol sequences apply to the conditional probabilities $q = 0.2$ bzw. $q = 0.8$, respectively.
*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$ .
*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/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 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\:symbol}\hspace{0.05cm}. $
* 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
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 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
(4) Opposite screen capture of the (earlier) SWF program Shannon–Fano– and Huffman–coding 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 codeword 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 asymmetric 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.
(7) The screen capture of the of the (earlier) SWF program Shannon–Fano– and Huffman–coding coding illustrates the constellation of the Huffman code for $k = 3$. This gives us for the mean codeword length:
The bound $k = 2$ valid for $H_2 = 0.861$ is now undercut by the mean codeword 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 → ∞)$.
