Aufgaben:Aufgabe 2.8: Huffman-Anwendung bei einer Markovquelle - Versionsgeschichte

Maintenance script: Add English interlanguage link

2026-03-16T12:35:56Z

Add English interlanguage link

← Nächstältere Version		Version vom 16. März 2026, 14:35 Uhr
Zeile 159:		Zeile 159:

	[[Category:Aufgaben zu Informationstheorie\|^2.3 Entropiecodierung nach Huffman^]]		[[Category:Aufgaben zu Informationstheorie\|^2.3 Entropiecodierung nach Huffman^]]
			[[en:Aufgaben:Exercise_2.8:_Huffman_Application_for_a_Markov_Source]]

Maintenance script: Join multi-line formulas for MW 1.43 parser compat

2026-02-24T13:39:02Z

Join multi-line formulas for MW 1.43 parser compat

Guenter am 11. August 2021 um 12:06 Uhr

2021-08-11T12:06:05Z

← Nächstältere Version		Version vom 11. August 2021, 14:06 Uhr
Zeile 122:		Zeile 122:

	[[Datei:P_ID2462__Inf_A_2_8d.png\|right\|frame\|Zur Huffman–Codierung für $k = 2$]]		[[Datei:P_ID2462__Inf_A_2_8d.png\|right\|frame\|Zur Huffman–Codierung für $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)'''  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.
	*Damit gilt für die mittlere Codewortlänge:		*Damit gilt für die mittlere Codewortlänge:
	:$$L_{\rm M}\hspace{0.01cm}' = 0.4 \cdot 1 + 0.4 \cdot 2 + (0.1 + 0.1) \cdot 3 = 1.8\,\,{\rm bit/Zweiertupel}$$		:$$L_{\rm M}\hspace{0.01cm}' = 0.4 \cdot 1 + 0.4 \cdot 2 + (0.1 + 0.1) \cdot 3 = 1.8\,\,{\rm bit/Zweiertupel}$$
Zeile 128:		Zeile 128:


	'''(5)'''  Richtig ~~iist~~ der <u>Lösungsvorschlag 2</u>:		'''(5)'''  Richtig ist der <u>Lösungsvorschlag 2</u>:
	*Nach dem Quellencodierungstheorem gilt  $L_{\rm M} ≥ H$.		*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).		*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.$		*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$.		*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.		*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.		*Auch nicht, wie sich der Wert  $0.875$  auf  $0.861$  senken ließe. Der Huffman–Algorithmus ist hierfür jedenfalls ungeeignet.
Zeile 144:		Zeile 144:


	'''(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:~~		[[Datei:P_ID2463__Inf_A_2_8g.png\|right\|frame\|Zur Huffman–Codierung für $k = 3$]]
	~~:$$L_{\rm M}\hspace{0.01cm}' = 0.64 \cdot 2 + 0.24 \cdot 3 + 0.04 \cdot 5 = 2.52\,\,{\rm bit/Dreiertupel}\hspace{0.3cm}~~		'''(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$.
	~~\Rightarrow\hspace{0.3cm}L_{\rm M} = {L_{\rm M}\hspace{0.01cm}'}/{3}\hspace{0.15cm}\underline{ = 0.84\,{\rm bit/Quellensymbol}}\hspace{0.05cm}.$$~~

	~~[[Datei~~:~~P_ID2463__Inf_A_2_8g~~.~~png\|right\|frame\|Zur Huffman–Codierung für~~ $k = 3$]]		Damit erhält man für die mittlere Codewortlänge:
			:$$L_{\rm M}\hspace{0.01cm}' = 0.64 \cdot 2 + 0.24 \cdot 3 + 0.04 \cdot 5 = 2.52\,\,{\rm bit/Dreiertupel}$$
			:$$\Rightarrow\hspace{0.3cm}L_{\rm M} = {L_{\rm M}\hspace{0.01cm}'}/{3}\hspace{0.15cm}\underline{ = 0.84\,{\rm bit/Quellensymbol}}\hspace{0.05cm}.$$

	*Man erkennt die Verbesserung gegenüber der Teilaufgabe  '''(4)'''.		*Man erkennt die Verbesserung gegenüber der Teilaufgabe  '''(4)'''.

Guenter am 11. August 2021 um 11:53 Uhr

2021-08-11T11:53:56Z

← Nächstältere Version		Version vom 11. August 2021, 13:53 Uhr
Zeile 44:		Zeile 44:
	<quiz display=simple>		<quiz display=simple>
	{Welche der vorne angegebenen Beispielfolgen gilt für  $q = 0.8$?		{Welche der vorne angegebenen Beispielfolgen gilt für  $q = 0.8$?
	\|type="[]"}		\|type="()"}
	- die rote Quellensymbolfolge  '''1''',		- die rote Quellensymbolfolge  '''1''',
	+ die blaue Quellensymbolfolge  '''2'''.		+ die blaue Quellensymbolfolge  '''2'''.

Guenter am 11. August 2021 um 11:52 Uhr

2021-08-11T11:52:15Z

← Nächstältere Version		Version vom 11. August 2021, 13:52 Uhr
Zeile 36:		Zeile 36:
	*Insbesondere wird auf die Seite  [[Informationstheorie/Entropiecodierung_nach_Huffman#Anwendung_der_Huffman.E2.80.93Codierung_auf_.7F.27.22.60UNIQ-MathJax169-QINU.60.22.27.7F.E2.80.93Tupel\|Anwendung der Huffman-Codierung auf k-Tupel]]  Bezug genommen.		*Insbesondere wird auf die Seite  [[Informationstheorie/Entropiecodierung_nach_Huffman#Anwendung_der_Huffman.E2.80.93Codierung_auf_.7F.27.22.60UNIQ-MathJax169-QINU.60.22.27.7F.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\|Aufgabe 2.7Z]].		*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]].
	*Zur Kontrolle Ihrer Ergebnisse verweisen wir auf das Interaktionsmodul  [[Applets:Huffman-~~_und_Shannon~~-Fano-Codierung~~\|Huffman und Shannon~~&~~ndash~~;~~Fano~~&~~ndash~~;–~~Codierung~~]].		*Zur Kontrolle Ihrer Ergebnisse verweisen wir auf das folgende Interaktionsmodul:  [[Applets:Huffman_Shannon_Fano\|Huffman- und Shannon-Fano-Codierung  ⇒   $\text{SWF}$–Version]].

Guenter am 11. August 2021 um 11:50 Uhr

2021-08-11T11:50:07Z

← Nächstältere Version		Version vom 11. August 2021, 13:50 Uhr
Zeile 34:		Zeile 34:
	''Hinweise:''		''Hinweise:''
	*Die Aufgabe gehört zum Kapitel  [[Informationstheorie/Entropiecodierung_nach_Huffman\|Entropiecodierung nach Huffman]].		*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_.7F.27.22.60UNIQ-~~MathJax164~~-QINU.60.22.27.7F.E2.80.93Tupel\|Anwendung der Huffman-Codierung auf k-Tupel]]  Bezug genommen.		*Insbesondere wird auf die Seite  [[Informationstheorie/Entropiecodierung_nach_Huffman#Anwendung_der_Huffman.E2.80.93Codierung_auf_.7F.27.22.60UNIQ-MathJax169-QINU.60.22.27.7F.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\|Aufgabe 2.7Z]].		*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]].
	*Zur Kontrolle Ihrer Ergebnisse verweisen wir auf das Interaktionsmodul  [[Applets:Huffman-_und_Shannon-Fano-Codierung\|Huffman und Shannon–Fano––Codierung]].		*Zur Kontrolle Ihrer Ergebnisse verweisen wir auf das Interaktionsmodul  [[Applets:Huffman-_und_Shannon-Fano-Codierung\|Huffman und Shannon–Fano––Codierung]].

Guenter am 26. Januar 2020 um 12:59 Uhr

2020-01-26T12:59:37Z

Guenter am 26. Januar 2020 um 12:35 Uhr

2020-01-26T12:35:20Z

← Nächstältere Version		Version vom 26. Januar 2020, 14:35 Uhr
Zeile 44:		Zeile 44:

	<quiz display=simple>		<quiz display=simple>
	{Welche der vorne angegebenen Beispielfolgen gilt für $q = 0.8$?		{Welche der vorne angegebenen Beispielfolgen gilt für  $q = 0.8$?
	\|type="[]"}		\|type="[]"}
	- die rote Quellensymbolfolge '''1''',		- die rote Quellensymbolfolge  '''1''',
	+ die blaue Quellensymbolfolge '''2''',		+ die blaue Quellensymbolfolge  '''2'''.


Zeile 53:		Zeile 53:
	\|type="[]"}		\|type="[]"}
	- Auch die direkte Anwendung von Huffman ist hier sinnvoll.		- Auch die direkte Anwendung von Huffman ist hier sinnvoll.
	+ Huffman macht bei Bildung von Zweiertupeln $(k = 2)$ Sinn.		+ Huffman macht bei Bildung von Zweiertupeln  $(k = 2)$  Sinn.
	+ Huffman macht bei Bildung von Dreiertupeln $(k = 3)$ Sinn.		+ Huffman macht bei Bildung von Dreiertupeln  $(k = 3)$  Sinn.


	{Wie lauten die Wahrscheinlichkeiten der <u>Zweiertupel</u> $(k = 2)$ für  $\underline{q = 0.8}$?		{Wie lauten die Wahrscheinlichkeiten der <u>Zweiertupel</u>  $(k = 2)$  für  $\underline{q = 0.8}$?
	\|type="{}"}		\|type="{}"}
	$p_{\rm A} = \rm Pr(XX)\ = \ $ { 0.4 3% }		$p_{\rm A} = \rm Pr(XX)\ = \ $ { 0.4 3% }
Zeile 65:		Zeile 65:


	{Ermitteln Sie mit dem angegebenen ~~Flash–Modul~~ den Huffman–Code für $\underline{k = 2}$. ~~<br>~~Wie groß ist in diesem Fall die mittlere Codewortlänge?		{Ermitteln Sie mit dem angegebenen Applet den Huffman–Code für  $\underline{k = 2}$.  Wie groß ist in diesem Fall die mittlere Codewortlänge?
	\|type="{}"}		\|type="{}"}
	$L_{\rm M} \ = \ $ { 0.9 3% } $\ \rm bit/Quellensymbol$		$L_{\rm M} \ = \ $ { 0.9 3% } $\ \rm bit/Quellensymbol$


	{Welche Schranke ergibt sich für die mittlere Codewortlänge, wenn <u>Zweiertupel</u> gebildet werden $(k = 2)$? Interpretation.		{Welche Schranke ergibt sich für die mittlere Codewortlänge, wenn <u>Zweiertupel</u> gebildet werden  $(k = 2)$? Interpretation.
	\|type="()"}		\|type="()"}
	- $L_{\rm M} \ge H_1 = 1.000$ bit/Quellensymbol,		- $L_{\rm M} \ge H_1 = 1.000$  bit/Quellensymbol,
	+ $L_{\rm M} \ge H_2 \approx 0.861$ bit/Quellensymbol,		+ $L_{\rm M} \ge H_2 \approx 0.861$  bit/Quellensymbol,
	- $L_{\rm M} \ge H_3 \approx 0.815$ bit/Quellensymbol,		- $L_{\rm M} \ge H_3 \approx 0.815$  bit/Quellensymbol,
	- $L_{\rm M} \ge H_{k \to \infty} \approx 0.722$ bit/Quellensymbol,		- $L_{\rm M} \ge H_{k \to \infty} \approx 0.722$  bit/Quellensymbol,
	- $L_{\rm M} \ge 0.5$ bit/Quellensymbol.		- $L_{\rm M} \ge 0.5$  bit/Quellensymbol.


	{Berechnen Sie die Wahrscheinlichkeiten der <u>Dreiertupel</u> $(k = 3)$ für  $\underline{q = 0.8}$?		{Berechnen Sie die Wahrscheinlichkeiten der <u>Dreiertupel</u>  $(k = 3)$  für  $\underline{q = 0.8}$?
	\|type="{}"}		\|type="{}"}
	$p_{\rm A} = \rm Pr(XXX)\ = \ $ { 0.32 3% }		$p_{\rm A} = \rm Pr(XXX)\ = \ $ { 0.32 3% }
Zeile 91:		Zeile 91:


	{Ermitteln Sie mit dem ~~genannten Flash–Modul~~ den Huffman–Code für $\underline{k = 3}$. ~~<br>~~Wie groß ist in diesem Fall die mittlere Codewortlänge?		{Ermitteln Sie mit dem angegebenen Applet den Huffman–Code für $\underline{k = 3}$.  Wie groß ist in diesem Fall die mittlere Codewortlänge?
	\|type="{}"}		\|type="{}"}
	$L_{\rm M} \ = \ $ { 0.84 3% } $\ \rm bit/Quellensymbol$		$L_{\rm M} \ = \ $ { 0.84 3% } $\ \rm bit/Quellensymbol$

Guenter am 26. Januar 2020 um 12:30 Uhr

2020-01-26T12:30:47Z

← Nächstältere Version		Version vom 26. Januar 2020, 14:30 Uhr
Zeile 17:		Zeile 17:
	:$$H = q \cdot {\rm log_2}\hspace{0.15cm}\frac{1}{q} + (1-q) \cdot {\rm log_2}\hspace{0.15cm}\frac{1}{1-q}		:$$H = q \cdot {\rm log_2}\hspace{0.15cm}\frac{1}{q} + (1-q) \cdot {\rm log_2}\hspace{0.15cm}\frac{1}{1-q}
	= 0.722\,\,{\rm bit/Quellensymbol}\hspace{0.05cm}.$$		= 0.722\,\,{\rm bit/Quellensymbol}\hspace{0.05cm}.$$
	* 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:		* Bei Markovquellen sind alle Entropienäherungen  $H_k$  mit Ordnung  $k \ge 2$  durch  $H_1$  und  $H = H_{k \to \infty}$  bestimmt:
	:$$H_k = {1}/{k}\cdot \big [ H_1 + H \big ] \hspace{0.05cm}.$$		:$$H_k = {1}/{k}\cdot \big [ H_1 + H \big ] \hspace{0.05cm}.$$
	*Die folgenden Zahlenwerte gelten wieder für  $q = 0.2$  und  $q = 0.8$  gleichermaßen:		*Die folgenden Zahlenwerte gelten wieder für  $q = 0.2$  und  $q = 0.8$  gleichermaßen:

Guenter am 26. Januar 2020 um 12:29 Uhr

2020-01-26T12:29:16Z

← Nächstältere Version		Version vom 26. Januar 2020, 14:29 Uhr
Zeile 17:		Zeile 17:
	:$$H = q \cdot {\rm log_2}\hspace{0.15cm}\frac{1}{q} + (1-q) \cdot {\rm log_2}\hspace{0.15cm}\frac{1}{1-q}		:$$H = q \cdot {\rm log_2}\hspace{0.15cm}\frac{1}{q} + (1-q) \cdot {\rm log_2}\hspace{0.15cm}\frac{1}{1-q}
	= 0.722\,\,{\rm bit/Quellensymbol}\hspace{0.05cm}.$$		= 0.722\,\,{\rm bit/Quellensymbol}\hspace{0.05cm}.$$
	* 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.		* 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:
			:$$H_k = {1}/{k}\cdot \big [ H_1 + H \big ] \hspace{0.05cm}.$$
	*Die folgenden Zahlenwerte gelten wieder für  $q = 0.2$  und  $q = 0.8$  gleichermaßen:		*Die folgenden Zahlenwerte gelten wieder für  $q = 0.2$  und  $q = 0.8$  gleichermaßen:
	:$$H_2 = {1}/{2}\cdot \big [ H_1 + H \big ] = 0.861\,\,{\rm bit/Quellensymbol}\hspace{0.05cm},$$		:$$H_2 = {1}/{2}\cdot \big [ H_1 + H \big ] = 0.861\,\,{\rm bit/Quellensymbol}\hspace{0.05cm},$$
Zeile 35:		Zeile 36:
	*Insbesondere wird auf die Seite  [[Informationstheorie/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.		*Insbesondere wird auf die Seite  [[Informationstheorie/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.
	*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]].		*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]].
	*Zur Kontrolle Ihrer Ergebnisse verweisen wir auf das Interaktionsmodul  [[Applets:Huffman-_und_Shannon-Fano-Codierung\|Huffman und Shannon–Fano–Codierung]].		*Zur Kontrolle Ihrer Ergebnisse verweisen wir auf das Interaktionsmodul  [[Applets:Huffman-_und_Shannon-Fano-Codierung\|Huffman und Shannon–Fano––Codierung]].

← Nächstältere Version		Version vom 11. August 2021, 13:52 Uhr
Zeile 36:		Zeile 36:
	*Insbesondere wird auf die Seite  [[Informationstheorie/Entropiecodierung_nach_Huffman#Anwendung_der_Huffman.E2.80.93Codierung_auf_.7F.27.22.60UNIQ-MathJax169-QINU.60.22.27.7F.E2.80.93Tupel\|Anwendung der Huffman-Codierung auf k-Tupel]]  Bezug genommen.		*Insbesondere wird auf die Seite  [[Informationstheorie/Entropiecodierung_nach_Huffman#Anwendung_der_Huffman.E2.80.93Codierung_auf_.7F.27.22.60UNIQ-MathJax169-QINU.60.22.27.7F.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\|Aufgabe 2.7Z]].		*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]].
	*Zur Kontrolle Ihrer Ergebnisse verweisen wir auf das Interaktionsmodul  [[Applets:Huffman-~~_und_Shannon~~-Fano-Codierung~~\|Huffman und Shannon~~&~~ndash~~;~~Fano~~&~~ndash~~;–~~Codierung~~]].		*Zur Kontrolle Ihrer Ergebnisse verweisen wir auf das folgende Interaktionsmodul:  [[Applets:Huffman_Shannon_Fano\|Huffman- und Shannon-Fano-Codierung  ⇒   $\text{SWF}$–Version]].

← Nächstältere Version		Version vom 11. August 2021, 13:50 Uhr
Zeile 34:		Zeile 34:
	''Hinweise:''		''Hinweise:''
	*Die Aufgabe gehört zum Kapitel  [[Informationstheorie/Entropiecodierung_nach_Huffman\|Entropiecodierung nach Huffman]].		*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_.7F.27.22.60UNIQ-~~MathJax164~~-QINU.60.22.27.7F.E2.80.93Tupel\|Anwendung der Huffman-Codierung auf k-Tupel]]  Bezug genommen.		*Insbesondere wird auf die Seite  [[Informationstheorie/Entropiecodierung_nach_Huffman#Anwendung_der_Huffman.E2.80.93Codierung_auf_.7F.27.22.60UNIQ-MathJax169-QINU.60.22.27.7F.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\|Aufgabe 2.7Z]].		*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]].
	*Zur Kontrolle Ihrer Ergebnisse verweisen wir auf das Interaktionsmodul  [[Applets:Huffman-_und_Shannon-Fano-Codierung\|Huffman und Shannon–Fano––Codierung]].		*Zur Kontrolle Ihrer Ergebnisse verweisen wir auf das Interaktionsmodul  [[Applets:Huffman-_und_Shannon-Fano-Codierung\|Huffman und Shannon–Fano––Codierung]].

← Nächstältere Version		Version vom 24. Februar 2026, 15:39 Uhr
Zeile 5:		Zeile 5:
	[[Datei:P_ID2460__Inf_A_2_8.png\|right\|frame\|Binäre symmetrische Markovquelle]]		[[Datei:P_ID2460__Inf_A_2_8.png\|right\|frame\|Binäre symmetrische Markovquelle]]
	Wir betrachten die binäre symmetrische Markovquelle entsprechend der Grafik, die durch den einzigen Parameter		Wir betrachten die binäre symmetrische Markovquelle entsprechend der Grafik, die durch den einzigen Parameter
	:$$q = {\rm Pr}(\boldsymbol{\rm X}\hspace{0.05cm}\|\hspace{0.05cm}\boldsymbol{\rm X}) =		:$$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})$$
	{\rm Pr}(\boldsymbol{\rm Y}\hspace{0.05cm}\|\hspace{0.05cm}\boldsymbol{\rm Y})$$
	vollständig beschrieben wird.		vollständig beschrieben wird.
	*Die angegebenen Quellensymbolfolgen gelten für die bedingten Wahrscheinlichkeiten  $q = 0.2$  bzw.  $q = 0.8$.		*Die angegebenen Quellensymbolfolgen gelten für die bedingten Wahrscheinlichkeiten  $q = 0.2$  bzw.  $q = 0.8$.
Zeile 15:		Zeile 14:
	* 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}. $		* 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}. $
	* 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
	:$$H = q \cdot {\rm log_2}\hspace{0.15cm}\frac{1}{q} + (1-q) \cdot {\rm log_2}\hspace{0.15cm}\frac{1}{1-q}		:$$H = q \cdot {\rm log_2}\hspace{0.15cm}\frac{1}{q} + (1-q) \cdot {\rm log_2}\hspace{0.15cm}\frac{1}{1-q} = 0.722\,\,{\rm bit/Quellensymbol}\hspace{0.05cm}.$$
	= 0.722\,\,{\rm bit/Quellensymbol}\hspace{0.05cm}.$$
	* Bei Markovquellen sind alle Entropienäherungen  $H_k$  mit Ordnung  $k \ge 2$  durch  $H_1$  und  $H = H_{k \to \infty}$  bestimmt:		* Bei Markovquellen sind alle Entropienäherungen  $H_k$  mit Ordnung  $k \ge 2$  durch  $H_1$  und  $H = H_{k \to \infty}$  bestimmt:
	:$$H_k = {1}/{k}\cdot \big [ H_1 + H \big ] \hspace{0.05cm}.$$		:$$H_k = {1}/{k}\cdot \big [ H_1 + H \big ] \hspace{0.05cm}.$$

← Nächstältere Version		Version vom 26. Januar 2020, 14:59 Uhr
Zeile 65:		Zeile 65:


	{Ermitteln Sie ~~mit dem angegebenen Applet~~ den Huffman–Code für  $\underline{k = 2}$.  Wie groß ist in diesem Fall die mittlere Codewortlänge?		{Ermitteln Sie den Huffman–Code für  $\underline{k = 2}$.  Wie groß ist in diesem Fall die mittlere Codewortlänge?
	\|type="{}"}		\|type="{}"}
	$L_{\rm M} \ = \ $ { 0.9 3% } $\ \rm bit/Quellensymbol$		$L_{\rm M} \ = \ $ { 0.9 3% } $\ \rm bit/Quellensymbol$
Zeile 91:		Zeile 91:


	{Ermitteln Sie ~~mit dem angegebenen Applet~~ den Huffman–Code für $\underline{k = 3}$.  Wie groß ist in diesem Fall die mittlere Codewortlänge?		{Ermitteln Sie den Huffman–Code für $\underline{k = 3}$.  Wie groß ist in diesem Fall die mittlere Codewortlänge?
	\|type="{}"}		\|type="{}"}
	$L_{\rm M} \ = \ $ { 0.84 3% } $\ \rm bit/Quellensymbol$		$L_{\rm M} \ = \ $ { 0.84 3% } $\ \rm bit/Quellensymbol$
Zeile 102:		Zeile 102:
	{{ML-Kopf}}		{{ML-Kopf}}
	'''(1)'''  Richtig ist der <u>Lösungsvorschlag 2</u>:		'''(1)'''  Richtig ist der <u>Lösungsvorschlag 2</u>:
	*Bei der blauen Quellensymbolfolge '''2''' erkennt man sehr viel weniger Symbolwechsel als in der roten Folge.		*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}) =		*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$.		{\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 $\rm X$ und $\rm X$ gleichwahrscheinlich angenommen wurden, macht die direkte Anwendung von Huffman keinen Sinn.		*Da hier die Quellensymbole  $\rm X$  und  $\rm Y$  als 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 $k$–Tupel bildet $(k ≥ 2)$.		*Dagegen kann man die inneren statistischen Bindungen der Markovquelle zur Datenkomprimierung nutzen, wenn man  $k$–Tupel bildet  $(k ≥ 2)$.
	*Je größer $k$ ist, desto mehr nähert sich die Codewortlänge $L_{\rm M}$ der Entropie $H$.		*Je größer  $k$  ist, desto mehr nähert sich die mittlere Codewortlänge  $L_{\rm M}$  der Entropie  $H$.



	'''(3)'''  Die Symbolwahrscheinlichkeiten sind $p_{\rm X} = p_{\rm Y} = 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:
	:$$p_{\rm A} \hspace{0.2cm} = \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm XX}) = p_{\rm X} \cdot {\rm Pr}(\boldsymbol{\rm X}\hspace{0.05cm}\|\hspace{0.05cm}\boldsymbol{\rm X}) = 0.5 \cdot q = 0.5 \cdot 0.8 \hspace{0.15cm}\underline{ = 0.4} \hspace{0.05cm},$$		:$$p_{\rm A} \hspace{0.2cm} = \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm XX}) = p_{\rm X} \cdot {\rm Pr}(\boldsymbol{\rm X}\hspace{0.05cm}\|\hspace{0.05cm}\boldsymbol{\rm X}) = 0.5 \cdot q = 0.5 \cdot 0.8 \hspace{0.15cm}\underline{ = 0.4} \hspace{0.05cm},$$
	:$$p_{\rm B} \hspace{0.2cm} = \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm XY}) = p_{\rm X} \cdot {\rm Pr}(\boldsymbol{\rm Y}\hspace{0.05cm}\|\hspace{0.05cm}\boldsymbol{\rm X}) = 0.5 \cdot (1-q)= 0.5 \cdot 0.2 \hspace{0.15cm}\underline{ = 0.1} \hspace{0.05cm},$$		:$$p_{\rm B} \hspace{0.2cm} = \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm XY}) = p_{\rm X} \cdot {\rm Pr}(\boldsymbol{\rm Y}\hspace{0.05cm}\|\hspace{0.05cm}\boldsymbol{\rm X}) = 0.5 \cdot (1-q)= 0.5 \cdot 0.2 \hspace{0.15cm}\underline{ = 0.1} \hspace{0.05cm},$$
Zeile 123:		Zeile 123:

	[[Datei:P_ID2462__Inf_A_2_8d.png\|right\|frame\|Zur Huffman–Codierung für $k = 2$]]		[[Datei: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:		'''(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.
			*Damit gilt für die mittlere Codewortlänge:
	:$$L_{\rm M}\hspace{0.01cm}' = 0.4 \cdot 1 + 0.4 \cdot 2 + (0.1 + 0.1) \cdot 3 = 1.8\,\,{\rm bit/Zweiertupel}$$		:$$L_{\rm M}\hspace{0.01cm}' = 0.4 \cdot 1 + 0.4 \cdot 2 + (0.1 + 0.1) \cdot 3 = 1.8\,\,{\rm bit/Zweiertupel}$$
	:$$\Rightarrow\hspace{0.3cm}L_{\rm M} = {L_{\rm M}\hspace{0.01cm}'}/{2}\hspace{0.15cm}\underline{ = 0.9\,{\rm bit/Quellensymbol}}\hspace{0.05cm}.$$		:$$\Rightarrow\hspace{0.3cm}L_{\rm M} = {L_{\rm M}\hspace{0.01cm}'}/{2}\hspace{0.15cm}\underline{ = 0.9\,{\rm bit/Quellensymbol}}\hspace{0.05cm}.$$
Zeile 129:		Zeile 130:

	'''(5)'''  Richtig iist der <u>Lösungsvorschlag 2</u>:		'''(5)'''  Richtig iist der <u>Lösungsvorschlag 2</u>:
	*Nach dem Quellencodierungstheorem gilt $L_{\rm M} ≥ H$.		*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).		*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.$		*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$.		*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.		*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.		*Auch nicht, wie sich der Wert  $0.875$  auf  $0.861$  senken ließe. Der Huffman–Algorithmus ist hierfür jedenfalls ungeeignet.


	'''(6)'''  Mit $q = 0.8$ und $1 - q = 0.2$ erhält man:		'''(6)'''  Mit  $q = 0.8$  und  $1 - q = 0.2$  erhält man:
	:$$p_{\rm A} \hspace{0.2cm} = \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm XXX}) = 0.5 \cdot q^2 \hspace{0.15cm}\underline{ = 0.32} = p_{\rm H} = {\rm Pr}(\boldsymbol{\rm YYY})\hspace{0.05cm},$$		:$$p_{\rm A} \hspace{0.2cm} = \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm XXX}) = 0.5 \cdot q^2 \hspace{0.15cm}\underline{ = 0.32} = p_{\rm H} = {\rm Pr}(\boldsymbol{\rm YYY})\hspace{0.05cm},$$
	:$$p_{\rm B} \hspace{0.2cm} = \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm XXY}) = 0.5 \cdot q \cdot (1-q) \hspace{0.15cm}\underline{ = 0.08}= p_{\rm G} = {\rm Pr}(\boldsymbol{\rm YYX}) \hspace{0.05cm},$$		:$$p_{\rm B} \hspace{0.2cm} = \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm XXY}) = 0.5 \cdot q \cdot (1-q) \hspace{0.15cm}\underline{ = 0.08}= p_{\rm G} = {\rm Pr}(\boldsymbol{\rm YYX}) \hspace{0.05cm},$$
Zeile 144:		Zeile 145:


	'''(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:		'''(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:
	:$$L_{\rm M}\hspace{0.01cm}' = 0.64 \cdot 2 + 0.24 \cdot 3 + 0.04 \cdot 5 = 2.52\,\,{\rm bit/Dreiertupel}\hspace{0.3cm}		:$$L_{\rm M}\hspace{0.01cm}' = 0.64 \cdot 2 + 0.24 \cdot 3 + 0.04 \cdot 5 = 2.52\,\,{\rm bit/Dreiertupel}\hspace{0.3cm}
	\Rightarrow\hspace{0.3cm}L_{\rm M} = {L_{\rm M}\hspace{0.01cm}'}/{3}\hspace{0.15cm}\underline{ = 0.84\,{\rm bit/Quellensymbol}}\hspace{0.05cm}.$$		\Rightarrow\hspace{0.3cm}L_{\rm M} = {L_{\rm M}\hspace{0.01cm}'}/{3}\hspace{0.15cm}\underline{ = 0.84\,{\rm bit/Quellensymbol}}\hspace{0.05cm}.$$
Zeile 150:		Zeile 151:
	[[Datei:P_ID2463__Inf_A_2_8g.png\|right\|frame\|Zur Huffman–Codierung für $k = 3$]]		[[Datei:P_ID2463__Inf_A_2_8g.png\|right\|frame\|Zur Huffman–Codierung für $k = 3$]]

	*Man erkennt die Verbesserung gegenüber '''(4)'''.		*Man erkennt die Verbesserung gegenüber der Teilaufgabe  '''(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 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$.		*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 → ∞)$.		*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 → ∞)$.

	{{ML-Fuß}}		{{ML-Fuß}}