'''(1)''' 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}) =
'''(1)''' Richtig ist der <u>Lösungsvorschlag 2</u>:
{\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$ ⇒ Richtig ist der <u>Lösungsvorschlag 2</u>.
*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 <u>Antworten 2 und 3</u>.:
'''(2)''' Richtig sind die <u>Antworten 2 und 3</u>.:
*Da hier die Quellensymbole <b>X</b> und <b>Y</b> gleichwahrscheinlich angenommen wurden, macht die direkte Anwendung von Huffman keinen Sinn.
*Da hier die Quellensymbole $\rm X$ und $\rm X$ 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).
*Dagegen kann man die inneren statistischen Bindungen der Markovquelle zur Datenkomprimierung nutzen, wenn man $k$–Tupel bildet $(k ≥ 2)$.
*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>.
*Je größer $k$ ist, desto mehr nähert sich die Codewortlänge $L_{\rm M}$ der Entropie $H$.
'''(3)''' 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:
'''(3)''' Die Symbolwahrscheinlichkeiten sind $p_{\rm X} = p_{\rm Y} = 0.5$. Damit erhält man für die Zweiertupel:
[[File:P_ID2462__Inf_A_2_8d.png|right|Zur Huffman–Codierung für <i>k</i> = 2]]
'''(4)''' 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:
'''(5)''' 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>.
[[File:P_ID2462__Inf_A_2_8d.png|right|frame|Zur Huffman–Codierung für $k = 2$]]
'''(4)''' Nebenstehender Bildschirmabzug des 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. Damit gilt für die mittlere Codewortlänge:
'''(5)''' Richtig iist der <u>Lösungsvorschlag 2</u>:
*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.
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.
'''(6)''' Mit <i>q</i> = 0.8 und 1 – <i>q</i> = 0.2 erhält man:
'''(6)''' Mit $q = 0.8$ und $1 - q = 0.2$ erhält man:
'''(7)''' 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:
[[File:P_ID2463__Inf_A_2_8g.png|Zur Huffman–Codierung für <i>k</i> = 3]]
'''(7)''' Der Bildschirmabzug des Flash–Moduls 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|Zur Huffman–Codierung für $k = 3$]]
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> → ∞).
*Man erkennt die Verbesserung gegenüber '''(4)'''.
*Die für $k = 2$ gültige informationstheoretische 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 → ∞)$.
{\rm Pr}(\boldsymbol{\rm Y}\hspace{0.05cm}|\hspace{0.05cm}\boldsymbol{\rm Y})$$
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 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 Zusatzaufgabe 1.5Z hergeleitet wird:
Die Symbole $\rm X$ und $\rm Y$ 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}. $
Die Entropie der Markovquelle ergibt sich sowohl für $q = 0.2$ als auch für $q = 0.8$ zu
Bei Markovquellen sind 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:
(4) Nebenstehender Bildschirmabzug des 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:
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 Flash–Moduls verdeutlicht die Konstellation des Huffman–Codes für $k = 3$. Damit erhält man für die mittlere Codewortlänge:
Die für $k = 2$ gültige informationstheoretische 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 → ∞)$.
