Aufgaben:Aufgabe 2.6: Zur Huffman-Codierung - Versionsgeschichte

Maintenance script: Add English interlanguage link

2026-03-16T12:35:50Z

Add English interlanguage link

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

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

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

2026-02-24T13:38:58Z

Join multi-line formulas for MW 1.43 parser compat

Guenter am 10. August 2021 um 14:11 Uhr

2021-08-10T14:11:43Z

← Nächstältere Version		Version vom 10. August 2021, 16:11 Uhr
Zeile 58:		Zeile 58:
	** [[Informationstheorie/Entropiecodierung_nach_Huffman#Der_Huffman.E2.80.93Algorithmus\|Der Huffman-Algorithmus]],		** [[Informationstheorie/Entropiecodierung_nach_Huffman#Der_Huffman.E2.80.93Algorithmus\|Der Huffman-Algorithmus]],
	**[[Informationstheorie/Entropiecodierung_nach_Huffman#Darstellung_des_Huffman.E2.80.93Codes_als_Baumdiagramm\|Darstellung des Huffman-Codes als Baumdiagramm]].		**[[Informationstheorie/Entropiecodierung_nach_Huffman#Darstellung_des_Huffman.E2.80.93Codes_als_Baumdiagramm\|Darstellung des Huffman-Codes als Baumdiagramm]].
	*Zur Kontrolle Ihrer Ergebnisse verweisen wir auf folgende ~~Interaktionsmodule~~:		*Zur Kontrolle Ihrer Ergebnisse verweisen wir auf das folgende Interaktionsmodul:  [[Applets:Huffman_Shannon_Fano\|Huffman- und Shannon-Fano-Codierung  ⇒   $\text{SWF}$–Version]].
	**  [[Applets:Huffman-_und_Shannon-Fano-Codierung\|Huffman- und Shannon-Fano-Codierung  ⇒   $\text{HTML 5/JS}$–Version]],
	**  [[Applets:Huffman_Shannon_Fano\|Huffman- und Shannon-Fano-Codierung  ⇒   $\text{SWF}$–Version]].

Guenter am 10. August 2021 um 11:56 Uhr

2021-08-10T11:56:53Z

← Nächstältere Version		Version vom 10. August 2021, 13:56 Uhr
Zeile 169:		Zeile 169:


	dargestellt werden.  Damit erhält man für die mittlere Codewortlänge (in &bdquo;bit/Quellensymbol&~~dquo~~;):		dargestellt werden.  Damit erhält man für die mittlere Codewortlänge (in &bdquo;bit/Quellensymbol”):
	:$$L_{\rm M} \hspace{0.2cm} = \hspace{0.2cm} (p_{\rm D} + p_{\rm E}) \cdot 2 + (p_{\rm C} + p_{\rm F} + p_{\rm G}) \cdot 3 + p_{\rm B} \cdot 4 +(p_{\rm A} + p_{\rm H}) \cdot 5 = 0.49 \cdot 2 + 0.36 \cdot 3 +0.08 \cdot 4 +0.07 \cdot 5		:$$L_{\rm M} \hspace{0.2cm} = \hspace{0.2cm} (p_{\rm D} + p_{\rm E}) \cdot 2 + (p_{\rm C} + p_{\rm F} + p_{\rm G}) \cdot 3 + p_{\rm B} \cdot 4 +(p_{\rm A} + p_{\rm H}) \cdot 5 = 0.49 \cdot 2 + 0.36 \cdot 3 +0.08 \cdot 4 +0.07 \cdot 5
	\hspace{0.15cm}\underline{= 2.73}\hspace{0.05cm}.$$		\hspace{0.15cm}\underline{= 2.73}\hspace{0.05cm}.$$

Guenter am 10. August 2021 um 11:50 Uhr

2021-08-10T11:50:30Z

← Nächstältere Version		Version vom 10. August 2021, 13:50 Uhr
Zeile 58:		Zeile 58:
	** [[Informationstheorie/Entropiecodierung_nach_Huffman#Der_Huffman.E2.80.93Algorithmus\|Der Huffman-Algorithmus]],		** [[Informationstheorie/Entropiecodierung_nach_Huffman#Der_Huffman.E2.80.93Algorithmus\|Der Huffman-Algorithmus]],
	**[[Informationstheorie/Entropiecodierung_nach_Huffman#Darstellung_des_Huffman.E2.80.93Codes_als_Baumdiagramm\|Darstellung des Huffman-Codes als Baumdiagramm]].		**[[Informationstheorie/Entropiecodierung_nach_Huffman#Darstellung_des_Huffman.E2.80.93Codes_als_Baumdiagramm\|Darstellung des Huffman-Codes als Baumdiagramm]].
	*Zur Kontrolle Ihrer Ergebnisse verweisen wir auf ~~das Interaktionsmodul~~  [[Applets:Huffman-_und_Shannon-Fano-Codierung\|Shannon–Fano&~~ndash~~; ~~und Huffman~~–~~Codierung~~]].		*Zur Kontrolle Ihrer Ergebnisse verweisen wir auf folgende Interaktionsmodule:
			**  [[Applets:Huffman-_und_Shannon-Fano-Codierung\|Huffman- und Shannon-Fano-Codierung  ⇒   $\text{HTML 5/JS}$–Version]],
			**  [[Applets:Huffman_Shannon_Fano\|Huffman- und Shannon-Fano-Codierung  ⇒   $\text{SWF}$–Version]].

Guenter am 10. August 2021 um 11:43 Uhr

2021-08-10T11:43:45Z

Guenter am 25. Januar 2020 um 14:45 Uhr

2020-01-25T14:45:36Z

← Nächstältere Version		Version vom 25. Januar 2020, 16:45 Uhr
Zeile 58:		Zeile 58:
	** [[Informationstheorie/Entropiecodierung_nach_Huffman#Der_Huffman.E2.80.93Algorithmus\|Der Huffman-Algorithmus]],		** [[Informationstheorie/Entropiecodierung_nach_Huffman#Der_Huffman.E2.80.93Algorithmus\|Der Huffman-Algorithmus]],
	**[[Informationstheorie/Entropiecodierung_nach_Huffman#Darstellung_des_Huffman.E2.80.93Codes_als_Baumdiagramm\|Darstellung des Huffman-Codes als Baumdiagramm]].		**[[Informationstheorie/Entropiecodierung_nach_Huffman#Darstellung_des_Huffman.E2.80.93Codes_als_Baumdiagramm\|Darstellung des Huffman-Codes als Baumdiagramm]].
	*Zur Kontrolle Ihrer Ergebnisse verweisen wir auf das Interaktionsmodul  [[Applets:~~Huffman_Shannon_Fano~~\|Shannon–Fano– und Huffman–Codierung]].		*Zur Kontrolle Ihrer Ergebnisse verweisen wir auf das Interaktionsmodul  [[Applets:Huffman-_und_Shannon-Fano-Codierung\|Shannon–Fano– und Huffman–Codierung]].

Guenter am 25. Januar 2020 um 14:35 Uhr

2020-01-25T14:35:27Z

← Nächstältere Version		Version vom 25. Januar 2020, 16:35 Uhr
Zeile 110:		Zeile 110:
	===Musterlösung===		===Musterlösung===
	{{ML-Kopf}}		{{ML-Kopf}}
	'''(1)'''  Vor dem Huffman–Algorithmus müssen die Symbole nach ihren Auftrittswahrscheinlichkeiten sortiert werden. Da die zwei unwahrscheinlichsten Symbole schon im ersten Schritt zusammengefasst werden, nehmen die Auftrittswahrscheinlichkeiten von oben nach unten ab (in der ~~unteren~~ Grafik zu dieser Musterlösung von links nach rechts). Durch Vergleich mit dem Angabenblatt erhält man:		'''(1)'''  Vor dem Huffman–Algorithmus müssen die Symbole nach ihren Auftrittswahrscheinlichkeiten sortiert werden.
			*Da die zwei unwahrscheinlichsten Symbole schon im ersten Schritt zusammengefasst werden, nehmen die Auftrittswahrscheinlichkeiten von oben nach unten ab <br>(in der Grafik zu dieser Musterlösung von links nach rechts).
			*Durch Vergleich mit dem Angabenblatt erhält man:

	:Symbol $\rm A$: <u>Eingang 7</u>,     Symbol $\rm B$: <u>Eingang 6</u>,     Symbol $\rm C$: <u>Eingang 3</u>,     Symbol $\rm D$: <u>Eingang 1</u>.		:Symbol $\rm A$:  <u>Eingang 7</u>,     Symbol $\rm B$:  <u>Eingang 6</u>,     Symbol $\rm C$:  <u>Eingang 3</u>,     Symbol $\rm D$:  <u>Eingang 1</u>.

	[[Datei:P_ID2452__Inf_A_2_6a.png\|right\|right\|frame\|An die Aufgabe angepasstes Baumdiagramm]]		[[Datei:P_ID2452__Inf_A_2_6a.png\|right\|right\|frame\|An die Aufgabe angepasstes Baumdiagramm]]
Zeile 118:		Zeile 120:


	'''(2)'''  Der Knoten $\rm R$ ist die Baumwurzel (<i>Root</i>). Dieser ist stets mit ~~<u><i>~~R~~</i>~~ = 1~~</u>~~ belegt, unabhängig von den Auftrittswahrscheinlichkeiten.
			'''(2)'''  Der Knoten  $\rm R$  ist die Baumwurzel  (<i>Root</i>).  Dieser ist stets mit  $\underline{R=1}$  belegt, unabhängig von den Auftrittswahrscheinlichkeiten.

	Für die weiteren Werte gilt:		Für die weiteren Werte gilt:
Zeile 134:		Zeile 137:
	:Schritt 6:    $p_{\rm Z} = p_{\rm X} + p_{\rm D} = 0.29 + 0.25 \hspace{0.15cm}\underline{ =0.54}$.		:Schritt 6:    $p_{\rm Z} = p_{\rm X} + p_{\rm D} = 0.29 + 0.25 \hspace{0.15cm}\underline{ =0.54}$.
	<br clear=all>		<br clear=all>
	'''(3)'''  Den Huffman–Code für das Symbol $\rm A$ erhält man, wenn man den Weg von der $\rm Root$ (gelber Punkt) zum Symbol $\rm A$ zurückverfolgt und jeder roten Verbindungslinie eine <b>1</b> zuordnet, jeder blauen eine <b>0</b>.		'''(3)'''  Den Huffman–Code für das Symbol  $\rm A$  erhält man, wenn man den Weg von der  $\rm Root$  (gelber Punkt) zum Symbol  $\rm A$  zurückverfolgt und jeder roten Verbindungslinie eine  <b>1</b>  zuordnet, jeder blauen eine  <b>0</b>.

	* Symbol $\rm A$:    rot–rot–rot–blau–rot → <b><u>11101</u></b>,		* Symbol $\rm A$:    rot–rot–rot–blau–rot → <b><u>11101</u></b>,
Zeile 153:		Zeile 156:


	'''(4)'''  Die Codierung unter Punkt '''(3)''' hat ergeben, dass		'''(4)'''  Die Codierung unter Punkt  '''(3)'''  hat ergeben, dass

	* die Symbole $\rm D$ und $\rm E$ mit zwei Bit,		* die Symbole  $\rm D$  und  $\rm E$  mit zwei Bit,

	* die Symbole $\rm C$, $\rm F$ und $\rm G$ mit drei Bit,		* die Symbole  $\rm C$,  $\rm F$  und  $\rm G$  mit drei Bit,

	* das Symbol $\rm B$ mit vier Bit, und		* das Symbol  $\rm B$  mit vier Bit,  und

	* die Symbole $\rm A$ und $\rm H$ jeweils mit fünf Bit		* die Symbole  $\rm A$  und  $\rm H$  jeweils mit fünf Bit


	dargestellt werden. Damit erhält man für die mittlere Codewortlänge (in &bdquo;bit/Quellensymbol&dquo;):		dargestellt werden.  Damit erhält man für die mittlere Codewortlänge (in &bdquo;bit/Quellensymbol&dquo;):
	:$$L_{\rm M} \hspace{0.2cm} = \hspace{0.2cm} (p_{\rm D} + p_{\rm E}) \cdot 2 + (p_{\rm C} + p_{\rm F} + p_{\rm G}) \cdot 3 + p_{\rm B} \cdot 4 +(p_{\rm A} + p_{\rm H}) \cdot 5 = 0.49 \cdot 2 + 0.36 \cdot 3 +0.08 \cdot 4 +0.07 \cdot 5		:$$L_{\rm M} \hspace{0.2cm} = \hspace{0.2cm} (p_{\rm D} + p_{\rm E}) \cdot 2 + (p_{\rm C} + p_{\rm F} + p_{\rm G}) \cdot 3 + p_{\rm B} \cdot 4 +(p_{\rm A} + p_{\rm H}) \cdot 5 = 0.49 \cdot 2 + 0.36 \cdot 3 +0.08 \cdot 4 +0.07 \cdot 5
	\hspace{0.15cm}\underline{= 2.73}\hspace{0.05cm}.$$		\hspace{0.15cm}\underline{= 2.73}\hspace{0.05cm}.$$



	'''(5)'''  Richtig ist allein die <u>Antwort 1</u>:		'''(5)'''  Richtig ist allein die <u>Antwort 1</u>:
	*Die mittlere Codewortlänge $L_{\rm M}$ kann nicht kleiner sein als die Quellenentropie $H$. Damit scheiden die Antworten 2 und 3 aus.		*Die mittlere Codewortlänge  $L_{\rm M}$  kann nicht kleiner sein als die Quellenentropie  $H$.  Damit scheiden die Antworten 2 und 3 aus.
	*Aus den vorgegebenen Auftrittswahrscheinlichkeiten kann die Quellenentropie zu $H = 2.71$ bit/Quellensymbol berechnet werden.		*Aus den vorgegebenen Auftrittswahrscheinlichkeiten kann die Quellenentropie tatsächlich zu  $H = 2.71$ bit/Quellensymbol berechnet werden.
	*Man erkennt, dass diese Huffman–Codierung die vorgegebene Grenze (Quellencodierungstheorem) $L_{\rm M, \ min } = H = 2.71$ bit/Quellensymbol nahezu erreicht.		*Man erkennt, dass diese Huffman–Codierung die vorgegebene Grenze  (Quellencodierungstheorem)  $L_{\rm M, \ min } \ge H = 2.71$  bit/Quellensymbol nahezu erreicht.
	{{ML-Fuß}}		{{ML-Fuß}}

Guenter am 25. Januar 2020 um 14:21 Uhr

2020-01-25T14:21:41Z

← Nächstältere Version		Version vom 25. Januar 2020, 16:21 Uhr
Zeile 4:		Zeile 4:

	[[Datei:P_ID2451__Inf_A_2_6.png\|right\|frame\|Baumdiagramm des <br>Huffman–Verfahrens]]		[[Datei:P_ID2451__Inf_A_2_6.png\|right\|frame\|Baumdiagramm des <br>Huffman–Verfahrens]]
	Wir betrachten hier eine Quellensymbolfolge $\langle q_\nu \rangle$ mit dem Symbolumfang $M = 8$:		Wir betrachten hier eine Quellensymbolfolge  $\langle q_\nu \rangle$  mit dem Symbolumfang  $M = 8$:
	:$$q_{\nu} = \{ \hspace{0.05cm}q_{\mu} \} = \{ \boldsymbol{\rm A} \hspace{0.05cm}, \boldsymbol{\rm B}\hspace{0.05cm}, \boldsymbol{\rm C}\hspace{0.05cm}, \boldsymbol{\rm D}\hspace{0.05cm}, \boldsymbol{\rm E}\hspace{0.05cm}, \boldsymbol{\rm F}\hspace{0.05cm}, \boldsymbol{\rm G}\hspace{0.05cm}, \boldsymbol{\rm H}\hspace{0.05cm}		:$$q_{\nu} = \{ \hspace{0.05cm}q_{\mu} \} = \{ \boldsymbol{\rm A} \hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm B}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm C}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm D}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm E}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm F}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm G}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm H}\hspace{0.05cm}
	\}\hspace{0.05cm}.$$		\}\hspace{0.05cm}.$$
	Sind die Symbole gleichwahrscheinlich, also ~~gilt~~ $p_{\rm A} = p_{\rm B} =$ ... $ = p_{\rm H} = 1/M$, so macht Quellencodierung keinen Sinn. Bereits mit dem Dualcode $\rm A$ → <b>000</b>, $\rm B$ → <b>001</b>, ... , $\rm H$ → <b>111</b>, erreicht nämlich die mittlere Codewortlänge $L_{\rm M}$ ihre untere Schranke $H$ gemäß dem Quellencodierungstheorem ($H$ bezeichnet hierbei die <i>Quellenentropie</i>):		Sind die Symbole gleichwahrscheinlich, gilt also  $p_{\rm A} = p_{\rm B} =$ ... $ = p_{\rm H} = 1/M$, so macht Quellencodierung keinen Sinn.  Bereits mit dem Dualcode  $\rm A$  →  <b>000</b>,  $\rm B$  →  <b>001</b>, ... ,  $\rm H$  →  <b>111</b>, erreicht nämlich dann die mittlere Codewortlänge  $L_{\rm M}$  ihre untere Schranke  $H$  gemäß dem Quellencodierungstheorem  $(H$ bezeichnet hierbei die <i>Quellenentropie</i>$)$:
	:$$L_{\rm M,\hspace{0.08cm}min} = H = 3 \hspace{0.15cm}{\rm bit/Quellensymbol} \hspace{0.05cm}.$$		:$$L_{\rm M,\hspace{0.08cm}min} = H = 3 \hspace{0.15cm}{\rm bit/Quellensymbol} \hspace{0.05cm}.$$

	Die Symbolwahrscheinlichkeiten seien aber in dieser Aufgabe wie folgt gegeben:		Die Symbolwahrscheinlichkeiten seien aber in dieser Aufgabe wie folgt gegeben:
	:$$p_{\rm A} \hspace{-0.05cm}= \hspace{-0.05cm} 0.04 \hspace{0.05cm},\hspace{0.1cm}p_{\rm B} \hspace{-0.05cm}= \hspace{-0.05cm} 0.08 \hspace{0.05cm},\hspace{0.1cm}p_{\rm C} \hspace{-0.05cm}= \hspace{-0.05cm} 0.14 \hspace{0.05cm},\hspace{0.1cm}		:$$p_{\rm A} \hspace{-0.05cm}= \hspace{-0.05cm} 0.04 \hspace{0.05cm},\hspace{0.1cm}p_{\rm B} \hspace{-0.05cm}= \hspace{-0.05cm} 0.08 \hspace{0.05cm},\hspace{0.1cm}p_{\rm C} \hspace{-0.05cm}= \hspace{-0.05cm} 0.14 \hspace{0.05cm},\hspace{0.1cm}
	p_{\rm D} \hspace{-0.05cm}= \hspace{-0.05cm} 0.25 \hspace{0.05cm},$$		p_{\rm D} \hspace{-0.05cm}= \hspace{-0.05cm} 0.25 \hspace{0.05cm},\hspace{0.1cm} p_{\rm E} \hspace{-0.05cm}= \hspace{-0.05cm} 0.24 \hspace{0.05cm},\hspace{0.1cm}p_{\rm F} \hspace{-0.05cm}= \hspace{-0.05cm} 0.12 \hspace{0.05cm},\hspace{0.1cm}p_{\rm G} \hspace{-0.05cm}= \hspace{-0.05cm} 0.10 \hspace{0.05cm},\hspace{0.1cm}
	~~:$$~~p_{\rm E} \hspace{-0.05cm}= \hspace{-0.05cm} 0.24 \hspace{0.05cm},\hspace{0.1cm}p_{\rm F} \hspace{-0.05cm}= \hspace{-0.05cm} 0.12 \hspace{0.05cm},\hspace{0.1cm}p_{\rm G} \hspace{-0.05cm}= \hspace{-0.05cm} 0.10 \hspace{0.05cm},\hspace{0.1cm}
	p_{\rm H} \hspace{-0.05cm}= \hspace{-0.05cm} 0.03 \hspace{0.05cm}.$$		p_{\rm H} \hspace{-0.05cm}= \hspace{-0.05cm} 0.03 \hspace{0.05cm}.$$
	Es liegt hier also eine redundante Nachrichtenquelle vor, die man durch Huffman–Codierung komprimieren kann. ~~Der~~ Algorithmus wurde 1952 – also kurz nach Shannons bahnbrechenden Arbeiten zur Informationstheorie – von [https://de.wikipedia.org/wiki/David_A._Huffman David Albert Huffman] veröffentlicht und erlaubt die Konstruktion von optimalen präfixfreien Codes.		*Es liegt hier also eine redundante Nachrichtenquelle vor, die man durch Huffman–Codierung komprimieren kann.
			*Dieser Algorithmus wurde 1952 – also kurz nach Shannons bahnbrechenden Arbeiten zur Informationstheorie – von  [https://de.wikipedia.org/wiki/David_A._Huffman David Albert Huffman]  veröffentlicht und erlaubt die Konstruktion von optimalen präfixfreien Codes.


	Der Algorithmus soll hier ohne Herleitung und Beweis angegeben werden, wobei wir uns auf Binärcodes beschränken   ⇒   die Codesymbolfolge besteht nur aus Nullen und Einsen:		Der Algorithmus soll hier ohne Herleitung und Beweis angegeben werden, wobei wir uns auf Binärcodes beschränken   ⇒   die Codesymbolfolge besteht nur aus Nullen und Einsen:
Zeile 23:		Zeile 24:
	:'''(2)'''   Man fasse die zwei unwahrscheinlichsten Symbole zu einem neuen Symbol zusammen.		:'''(2)'''   Man fasse die zwei unwahrscheinlichsten Symbole zu einem neuen Symbol zusammen.

	:'''(3)'''   Man wiederhole Schritt '''(1)''' und '''(2)''', bis nur zwei (zusammengefasste) Symbole übrig bleiben.		:'''(3)'''   Man wiederhole Schritt  '''(1)'''  und  '''(2)''', bis nur zwei (zusammengefasste) Symbole übrig bleiben.

	:'''(4)'''   Die wahrscheinlichere Symbolmenge wird mit <b>1</b> binär codiert, die andere Menge mit <b>0</b>.		:'''(4)'''   Die wahrscheinlichere Symbolmenge wird mit  <b>1</b>  binär codiert, die andere Menge mit  <b>0</b>.

	:'''(5)'''   Man ergänze schrittweise (von unten nach oben) die aufgespaltenen Teilcodes mit <b>1</b> bzw. <b>0</b>.		:'''(5)'''   Man ergänze schrittweise (von unten nach oben) die aufgespaltenen Teilcodes mit  <b>1</b>  bzw.  <b>0</b>.

	~~Oft wird dieser Algorithmus durch ein Baumdiagramm veranschaulicht. Die obige Grafik zeigt dieses für den vorliegenden Fall. Sie haben folgende Aufgaben:~~

	~~:'''(a)'''   Zuordnung der Symbole $\rm A$,~~ .~~.. , $\rm H$ zu~~ den ~~mit '''[1]''', ... , '''[8]''' bezeichneten Eingängen~~.		Oft wird dieser Algorithmus durch ein Baumdiagramm veranschaulicht. Die obige Grafik zeigt dieses für den vorliegenden Fall.

	:~~'''(b)'''   Bestimmung der Summenwahrscheinlichkeiten $U$, ... , $Z$ sowie $R$ (<i>Root</i>).~~		Sie haben folgende Aufgaben:

	:'''(c)'''   Zuordnung der Symbole $\rm A$, ... , $\rm H$ zu den entsprechenden Huffman–Binärfolgen. Eine rote Verbindung ~~im Baumdiagramm~~ entspricht einer <b>1</b> ~~und~~ eine blaue Verbindung einer <b>0</b>.		:'''(a)'''   Zuordnung der Symbole  $\rm A$, ... , $\rm H$  zu den mit  '''[1]''', ... , '''[8]'''  bezeichneten Eingängen.

			:'''(b)'''   Bestimmung der Summenwahrscheinlichkeiten  $U$, ... ,  $Z$  sowie  $R$  (<i>Root</i>).

			:'''(c)'''   Zuordnung der Symbole  $\rm A$, ... ,  $\rm H$  zu den entsprechenden Huffman–Binärfolgen. Eine rote Verbindung entspricht einer  <b>1</b>, eine blaue Verbindung einer  <b>0</b>.

	Sie werden feststellen, dass die mittlere Codewortlänge		Sie werden feststellen, dass die mittlere Codewortlänge
	:$$L_{\rm M} = \sum_{\mu = 1}^{M}\hspace{0.05cm} p_{\mu} \cdot L_{\mu} $$		:$$L_{\rm M} = \sum_{\mu = 1}^{M}\hspace{0.05cm} p_{\mu} \cdot L_{\mu} $$
	bei Huffman–Codierung nur unwesentlich größer ist als die Quellenentropie $H$. In dieser Gleichung gelten für den vorliegenden Fall folgende Werte:		bei Huffman–Codierung nur unwesentlich größer ist als die Quellenentropie  $H$.  In dieser Gleichung gelten für den vorliegenden Fall folgende Werte:
	*$M = 8$, $p_1 = p_{\rm A}$, ... , $p_8 = p_{\rm H}$.		*$M = 8$,  $p_1 = p_{\rm A}$,  ... ,  $p_8 = p_{\rm H}$.
	*Die jeweilige Bitanzahl der Codesymbole für $\rm A$, ... , $\rm H$ ist mit $L_1$, ... , $L_8$ bezeichnet.		*Die jeweilige Bitanzahl der Codesymbole für  $\rm A$, ... ,  $\rm H$  ist mit  $L_1$, ... ,  $L_8$  bezeichnet.




Zeile 48:		Zeile 54:

	''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 Bezug genommen auf die Seiten		*Insbesondere wird Bezug genommen auf die Seiten
	** [[Informationstheorie/Entropiecodierung_nach_Huffman#Der_Huffman.E2.80.93Algorithmus\|Der Huffman-Algorithmus]],		** [[Informationstheorie/Entropiecodierung_nach_Huffman#Der_Huffman.E2.80.93Algorithmus\|Der Huffman-Algorithmus]],
	**[[Informationstheorie/Entropiecodierung_nach_Huffman#Darstellung_des_Huffman.E2.80.93Codes_als_Baumdiagramm\|Darstellung des Huffman-Codes als Baumdiagramm]].		**[[Informationstheorie/Entropiecodierung_nach_Huffman#Darstellung_des_Huffman.E2.80.93Codes_als_Baumdiagramm\|Darstellung des Huffman-Codes als Baumdiagramm]].
	*Zur Kontrolle Ihrer Ergebnisse verweisen wir auf das Interaktionsmodul [[Applets:Huffman_Shannon_Fano\|Shannon–Fano– und Huffman–Codierung]].		*Zur Kontrolle Ihrer Ergebnisse verweisen wir auf das Interaktionsmodul  [[Applets:Huffman_Shannon_Fano\|Shannon–Fano– und Huffman–Codierung]].


Zeile 92:		Zeile 98:


	{Wie groß ist die Quellenentropie $H$? ~~  <i>Hinweis:</i> Es gibt genau eine Lösung.~~		{Wie groß ist die Quellenentropie  $H$?
	\|type="[]"}		\|type="()"}
	+ $H = 2.71\ \rm bit/Quellensymbol.$		+ $H = 2.71\ \rm bit/Quellensymbol.$
	- $H = 2.75\ \rm bit/Quellensymbol.$		- $H = 2.75\ \rm bit/Quellensymbol.$

Guenter am 28. September 2018 um 08:04 Uhr

2018-09-28T08:04:17Z

← Nächstältere Version		Version vom 28. September 2018, 10:04 Uhr
Zeile 106:		Zeile 106:
	'''(1)'''  Vor dem Huffman–Algorithmus müssen die Symbole nach ihren Auftrittswahrscheinlichkeiten sortiert werden. Da die zwei unwahrscheinlichsten Symbole schon im ersten Schritt zusammengefasst werden, nehmen die Auftrittswahrscheinlichkeiten von oben nach unten ab (in der unteren Grafik zu dieser Musterlösung von links nach rechts). Durch Vergleich mit dem Angabenblatt erhält man:		'''(1)'''  Vor dem Huffman–Algorithmus müssen die Symbole nach ihren Auftrittswahrscheinlichkeiten sortiert werden. Da die zwei unwahrscheinlichsten Symbole schon im ersten Schritt zusammengefasst werden, nehmen die Auftrittswahrscheinlichkeiten von oben nach unten ab (in der unteren Grafik zu dieser Musterlösung von links nach rechts). Durch Vergleich mit dem Angabenblatt erhält man:

	:Symbol ~~<b>~~A~~</B>~~: <u>Eingang 7</u>,     Symbol ~~<b>B</~~B>: <u>Eingang 6</u>,     Symbol ~~<b>~~C~~</B>~~: <u>Eingang 3</u>,     Symbol ~~<b>~~D~~</B>~~: <u>Eingang 1</u>.		:Symbol $\rm A$: <u>Eingang 7</u>,     Symbol $\rm B$: <u>Eingang 6</u>,     Symbol $\rm C$: <u>Eingang 3</u>,     Symbol $\rm D$: <u>Eingang 1</u>.

			[[Datei:P_ID2452__Inf_A_2_6a.png\|right\|right\|frame\|An die Aufgabe angepasstes Baumdiagramm]]

	~~[[Datei:P_ID2452__Inf_A_2_6a.png\|right\|An die Aufgabe angepasstes Baumdiagramm]]~~
	~~'''(2)'''  Der Knoten '''R''' ist die Baumwurzel (<i>Root</i>). Dieser ist stets mit <u><i>R</i> = 1</u> belegt, unabhängig von den Auftrittswahrscheinlichkeiten.~~

	~~Für die weiteren Werte gilt:~~

	~~:Schritt 1:  ~~  <i>U</i> = <~~i>p</i><sub~~>~~A</sub> +~~ <i>p</i~~><sub>H</sub~~> = ~~0.04 + 0.03 = <u>0.07~~</u>,		'''(2)'''  Der Knoten $\rm R$ ist die Baumwurzel (<i>Root</i>). Dieser ist stets mit <u><i>R</i> = 1</u> belegt, unabhängig von den Auftrittswahrscheinlichkeiten.

	:~~Schritt 2:    <i>V</i> = <i>U</i> + <i>p</i><sub>B</sub> = 0.07 + 0.08 = <u>0.15</u>,~~		Für die weiteren Werte gilt:

	:Schritt 3:    ~~<i>W</i>~~ = ~~<i>p</i><sub>F</sub>~~ + ~~<i>p</i><sub>G</sub>~~ = 0.12 + 0.10 = ~~<u>~~0.~~22</u>~~,		:Schritt 1:    $p_{\rm U} = p_{\rm A} + p_{\rm H} = 0.04 + 0.03 \hspace{0.15cm}\underline{ =0.07}$,

	:Schritt 4:    ~~<i>X</i>~~ = ~~<i>V</i>~~ + ~~<i>p</i><sub>C</sub>~~ = 0.15 + 0.14 = 0.29,		:Schritt 2:    $p_{\rm V} = p_{\rm U} + p_{\rm B} = 0.07 + 0.08 \hspace{0.15cm}\underline{ =0.15}$,

	:Schritt 5:    ~~<i>Y</i>~~ = ~~<i>W</i>~~ + ~~<i>p</i><sub>E</sub>~~ = 0.22 + 0.24 = 0.46,		:Schritt 3:    $p_{\rm W} = p_{\rm F} + p_{\rm G} = 0.12 + 0.10 \hspace{0.15cm}\underline{ =0.22}$,

	:Schritt 6:    ~~<i>Z</i>~~ = ~~<i>X</i>~~ + ~~<i>p</i><sub>D</sub>~~ = 0.29 + 0.25 = ~~<u>~~0.~~54</u>.~~		:Schritt 4:    $p_{\rm X} = p_{\rm V} + p_{\rm C} = 0.15 + 0.14 \hspace{0.15cm}\underline{ =0.29}$,

	~~Damit ergibt sich das hier dargestelle Baumdiagramm~~.		:Schritt 5:    $p_{\rm Y} = p_{\rm W} + p_{\rm E} = 0.22 + 0.24 \hspace{0.15cm}\underline{ =0.46}$,

			:Schritt 6:    $p_{\rm Z} = p_{\rm X} + p_{\rm D} = 0.29 + 0.25 \hspace{0.15cm}\underline{ =0.54}$.
			<br clear=all>
			'''(3)'''  Den Huffman–Code für das Symbol $\rm A$ erhält man, wenn man den Weg von der $\rm Root$ (gelber Punkt) zum Symbol $\rm A$ zurückverfolgt und jeder roten Verbindungslinie eine <b>1</b> zuordnet, jeder blauen eine <b>0</b>.

	~~'''(3)'''~~  ~~Den Huffman~~–~~Code für das Symbol~~ <b>A<~~/b> erhält man, wenn man den Weg von der <i~~>~~Root~~</i> ~~(gelber Punkt) zum Symbol <b>A</b> zurückverfolgt und jeder roten Verbindungslinie eine &bdquo;<b>1~~</b>~~” zuordnet~~, ~~jeder blauen eine &bdquo;<b>0</b>”.~~		* Symbol $\rm A$:    rot–rot–rot–blau–rot → <b><u>11101</u></b>,

	* Symbol ~~<b>A</b>~~:    rot–rot–rot~~–blau~~–rot → <b><u>~~11101~~</u></b>,		* Symbol $\rm B$:    rot–rot–rot–rot → <b><u>1111</u></b>,

	* Symbol ~~<b>B</b>~~:    rot–rot–~~rot–rot~~ → <b><u>~~1111~~</u></b>,		* Symbol $\rm C$:    rot–rot–blau → <b><u>110</u></b>,

	* Symbol ~~<b>C</b>~~:    rot–~~rot~~–~~blau~~ → <b><u>~~110~~</u></b>,		* Symbol $\rm D$:    rot–blau– → <b><u>10</u></b>,

	* Symbol ~~<b>D</b>~~:  &nbsp~~; rot&ndash~~;blau– → <b>~~<u>10</u>~~</b>,		* Symbol $\rm E$:    blau–rot → <b>01</b>,

	* Symbol ~~<b>E</b>~~:    blau–rot → <b>01</b>,		* Symbol $\rm F$:    blau–blau–rot → <b>001</b>,

	* Symbol ~~<b>F</b>~~:    blau–blau–~~rot~~ → <b>~~001~~</b>,		* Symbol $\rm G$:    blau–blau–blau → <b>000</b>,

	* Symbol ~~<b>G</b>~~:    ~~blau~~–blau–blau → <b>~~000~~</b>,		* Symbol $\rm H$:    rot–rot–rot–blau–blau → <b>11100</b>.

	* Symbol <b>H</b>:    rot–rot–rot–blau–blau → <b>11100</b>.

			'''(4)'''  Die Codierung unter Punkt '''(3)''' hat ergeben, dass

	~~'''(4)'''  Die Codierung unter Punkt (3) hat ergeben~~, ~~dass~~		* die Symbole $\rm D$ und $\rm E$ mit zwei Bit,

	* die Symbole ~~<b>D</b>~~ und ~~<b>E</b>~~ mit ~~zwei~~ Bit,		* die Symbole $\rm C$, $\rm F$ und $\rm G$ mit drei Bit,

	* ~~die Symbole <b>C</b>, <b>F</b> und <b>G</b>~~ mit ~~drei~~ Bit,		* das Symbol $\rm B$ mit vier Bit, und

	* ~~das Symbol <b>B</b>~~ mit ~~vier~~ Bit~~, und~~		* die Symbole $\rm A$ und $\rm H$ jeweils mit fünf Bit

	* die Symbole <b>A</b> und <b>H</b> jeweils mit fünf Bit

	dargestellt werden. Damit erhält man für die mittlere Codewortlänge (in &bdquo;bit/Quellensymbol&dquo;):		dargestellt werden. Damit erhält man für die mittlere Codewortlänge (in &bdquo;bit/Quellensymbol&dquo;):
Zeile 163:		Zeile 163:


	'''(5)'''  Richtig ist allein <u>Antwort 1</u>:		'''(5)'''  Richtig ist allein die <u>Antwort 1</u>:
	*Die mittlere Codewortlänge ~~<i>L</i><sub>~~M~~</sub>~~ kann nicht kleiner sein als die Quellenentropie ~~<i>~~H~~</i>~~. Damit scheiden die Antworten 2 und 3 aus.		*Die mittlere Codewortlänge $L_{\rm M}$ kann nicht kleiner sein als die Quellenentropie $H$. Damit scheiden die Antworten 2 und 3 aus.
	*Aus den vorgegebenen Auftrittswahrscheinlichkeiten kann die Quellenentropie zu ~~<i>~~H~~</i>~~ = 2.71 bit/Quellensymbol berechnet werden.		*Aus den vorgegebenen Auftrittswahrscheinlichkeiten kann die Quellenentropie zu $H = 2.71$ bit/Quellensymbol berechnet werden.
	*Man erkennt, dass ~~die vorliegende~~ Huffman–Codierung die ~~durch das Quellencodierungstheorem~~ vorgegebene Grenze ~~<i>L</i><sub>~~M, min~~</sub>~~ = ~~<i>~~H~~</i>~~ = 2.71 bit/Quellensymbol nahezu erreicht.		*Man erkennt, dass diese Huffman–Codierung die vorgegebene Grenze (Quellencodierungstheorem) $L_{\rm M, \ min } = H = 2.71$ bit/Quellensymbol nahezu erreicht.
	{{ML-Fuß}}		{{ML-Fuß}}

← Nächstältere Version		Version vom 10. August 2021, 16:11 Uhr
Zeile 58:		Zeile 58:
	** [[Informationstheorie/Entropiecodierung_nach_Huffman#Der_Huffman.E2.80.93Algorithmus\|Der Huffman-Algorithmus]],		** [[Informationstheorie/Entropiecodierung_nach_Huffman#Der_Huffman.E2.80.93Algorithmus\|Der Huffman-Algorithmus]],
	**[[Informationstheorie/Entropiecodierung_nach_Huffman#Darstellung_des_Huffman.E2.80.93Codes_als_Baumdiagramm\|Darstellung des Huffman-Codes als Baumdiagramm]].		**[[Informationstheorie/Entropiecodierung_nach_Huffman#Darstellung_des_Huffman.E2.80.93Codes_als_Baumdiagramm\|Darstellung des Huffman-Codes als Baumdiagramm]].
	*Zur Kontrolle Ihrer Ergebnisse verweisen wir auf folgende ~~Interaktionsmodule~~:		*Zur Kontrolle Ihrer Ergebnisse verweisen wir auf das folgende Interaktionsmodul:  [[Applets:Huffman_Shannon_Fano\|Huffman- und Shannon-Fano-Codierung  ⇒   $\text{SWF}$–Version]].
	**  [[Applets:Huffman-_und_Shannon-Fano-Codierung\|Huffman- und Shannon-Fano-Codierung  ⇒   $\text{HTML 5/JS}$–Version]],
	**  [[Applets:Huffman_Shannon_Fano\|Huffman- und Shannon-Fano-Codierung  ⇒   $\text{SWF}$–Version]].

← Nächstältere Version		Version vom 10. August 2021, 13:50 Uhr
Zeile 58:		Zeile 58:
	** [[Informationstheorie/Entropiecodierung_nach_Huffman#Der_Huffman.E2.80.93Algorithmus\|Der Huffman-Algorithmus]],		** [[Informationstheorie/Entropiecodierung_nach_Huffman#Der_Huffman.E2.80.93Algorithmus\|Der Huffman-Algorithmus]],
	**[[Informationstheorie/Entropiecodierung_nach_Huffman#Darstellung_des_Huffman.E2.80.93Codes_als_Baumdiagramm\|Darstellung des Huffman-Codes als Baumdiagramm]].		**[[Informationstheorie/Entropiecodierung_nach_Huffman#Darstellung_des_Huffman.E2.80.93Codes_als_Baumdiagramm\|Darstellung des Huffman-Codes als Baumdiagramm]].
	*Zur Kontrolle Ihrer Ergebnisse verweisen wir auf ~~das Interaktionsmodul~~  [[Applets:Huffman-_und_Shannon-Fano-Codierung\|Shannon–Fano&~~ndash~~; ~~und Huffman~~–~~Codierung~~]].		*Zur Kontrolle Ihrer Ergebnisse verweisen wir auf folgende Interaktionsmodule:
			**  [[Applets:Huffman-_und_Shannon-Fano-Codierung\|Huffman- und Shannon-Fano-Codierung  ⇒   $\text{HTML 5/JS}$–Version]],
			**  [[Applets:Huffman_Shannon_Fano\|Huffman- und Shannon-Fano-Codierung  ⇒   $\text{SWF}$–Version]].

← Nächstältere Version		Version vom 25. Januar 2020, 16:45 Uhr
Zeile 58:		Zeile 58:
	** [[Informationstheorie/Entropiecodierung_nach_Huffman#Der_Huffman.E2.80.93Algorithmus\|Der Huffman-Algorithmus]],		** [[Informationstheorie/Entropiecodierung_nach_Huffman#Der_Huffman.E2.80.93Algorithmus\|Der Huffman-Algorithmus]],
	**[[Informationstheorie/Entropiecodierung_nach_Huffman#Darstellung_des_Huffman.E2.80.93Codes_als_Baumdiagramm\|Darstellung des Huffman-Codes als Baumdiagramm]].		**[[Informationstheorie/Entropiecodierung_nach_Huffman#Darstellung_des_Huffman.E2.80.93Codes_als_Baumdiagramm\|Darstellung des Huffman-Codes als Baumdiagramm]].
	*Zur Kontrolle Ihrer Ergebnisse verweisen wir auf das Interaktionsmodul  [[Applets:~~Huffman_Shannon_Fano~~\|Shannon–Fano– und Huffman–Codierung]].		*Zur Kontrolle Ihrer Ergebnisse verweisen wir auf das Interaktionsmodul  [[Applets:Huffman-_und_Shannon-Fano-Codierung\|Shannon–Fano– und Huffman–Codierung]].

← Nächstältere Version		Version vom 24. Februar 2026, 15:38 Uhr
Zeile 5:		Zeile 5:
	[[Datei:P_ID2451__Inf_A_2_6.png\|right\|frame\|Huffman–Baumdiagramm]]		[[Datei:P_ID2451__Inf_A_2_6.png\|right\|frame\|Huffman–Baumdiagramm]]
	Wir betrachten hier eine Quellensymbolfolge  $\langle q_\nu \rangle$  mit dem Symbolumfang  $M = 8$:		Wir betrachten hier eine Quellensymbolfolge  $\langle q_\nu \rangle$  mit dem Symbolumfang  $M = 8$:
	:$$q_{\nu} \in \{ \hspace{0.05cm}q_{\mu} \} = \{ \boldsymbol{\rm A} \hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm B}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm C}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm D}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm E}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm F}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm G}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm H}\hspace{0.05cm}		:$$q_{\nu} \in \{ \hspace{0.05cm}q_{\mu} \} = \{ \boldsymbol{\rm A} \hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm B}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm C}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm D}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm E}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm F}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm G}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm H}\hspace{0.05cm}\}\hspace{0.05cm}.$$
	\}\hspace{0.05cm}.$$
	Sind die Symbole gleichwahrscheinlich,  gilt also  $p_{\rm A} = p_{\rm B} =$ ... $ = p_{\rm H} = 1/M$,  so macht Quellencodierung keinen Sinn.  Bereits mit dem Dualcode  $\rm A$  →  <b>000</b>,  $\rm B$  →  <b>001</b>, ... ,  $\rm H$  →  <b>111</b>, erreicht nämlich dann die mittlere Codewortlänge  $L_{\rm M}$  ihre untere Schranke  $H$  gemäß dem Quellencodierungstheorem  $(H$ bezeichnet hierbei die Quellenentropie$)$:		Sind die Symbole gleichwahrscheinlich,  gilt also  $p_{\rm A} = p_{\rm B} =$ ... $ = p_{\rm H} = 1/M$,  so macht Quellencodierung keinen Sinn.  Bereits mit dem Dualcode  $\rm A$  →  <b>000</b>,  $\rm B$  →  <b>001</b>, ... ,  $\rm H$  →  <b>111</b>, erreicht nämlich dann die mittlere Codewortlänge  $L_{\rm M}$  ihre untere Schranke  $H$  gemäß dem Quellencodierungstheorem  $(H$ bezeichnet hierbei die Quellenentropie$)$:
	:$$L_{\rm M,\hspace{0.08cm}min} = H = 3 \hspace{0.15cm}{\rm bit/Quellensymbol} \hspace{0.05cm}.$$		:$$L_{\rm M,\hspace{0.08cm}min} = H = 3 \hspace{0.15cm}{\rm bit/Quellensymbol} \hspace{0.05cm}.$$

	Die Symbolwahrscheinlichkeiten seien aber in dieser Aufgabe wie folgt gegeben:		Die Symbolwahrscheinlichkeiten seien aber in dieser Aufgabe wie folgt gegeben:
	:$$p_{\rm A} \hspace{-0.05cm}= \hspace{-0.05cm} 0.04 \hspace{0.05cm},\hspace{0.1cm}p_{\rm B} \hspace{-0.05cm}= \hspace{-0.05cm} 0.08 \hspace{0.05cm},\hspace{0.1cm}p_{\rm C} \hspace{-0.05cm}= \hspace{-0.05cm} 0.14 \hspace{0.05cm},\hspace{0.1cm}		:$$p_{\rm A} \hspace{-0.05cm}= \hspace{-0.05cm} 0.04 \hspace{0.05cm},\hspace{0.1cm}p_{\rm B} \hspace{-0.05cm}= \hspace{-0.05cm} 0.08 \hspace{0.05cm},\hspace{0.1cm}p_{\rm C} \hspace{-0.05cm}= \hspace{-0.05cm} 0.14 \hspace{0.05cm},\hspace{0.1cm}p_{\rm D} \hspace{-0.05cm}= \hspace{-0.05cm} 0.25 \hspace{0.05cm},\hspace{0.1cm} p_{\rm E} \hspace{-0.05cm}= \hspace{-0.05cm} 0.24 \hspace{0.05cm},\hspace{0.1cm}p_{\rm F} \hspace{-0.05cm}= \hspace{-0.05cm} 0.12 \hspace{0.05cm},\hspace{0.1cm}p_{\rm G} \hspace{-0.05cm}= \hspace{-0.05cm} 0.10 \hspace{0.05cm},\hspace{0.1cm}p_{\rm H} \hspace{-0.05cm}= \hspace{-0.05cm} 0.03 \hspace{0.05cm}.$$
	p_{\rm D} \hspace{-0.05cm}= \hspace{-0.05cm} 0.25 \hspace{0.05cm},\hspace{0.1cm} p_{\rm E} \hspace{-0.05cm}= \hspace{-0.05cm} 0.24 \hspace{0.05cm},\hspace{0.1cm}p_{\rm F} \hspace{-0.05cm}= \hspace{-0.05cm} 0.12 \hspace{0.05cm},\hspace{0.1cm}p_{\rm G} \hspace{-0.05cm}= \hspace{-0.05cm} 0.10 \hspace{0.05cm},\hspace{0.1cm}
	p_{\rm H} \hspace{-0.05cm}= \hspace{-0.05cm} 0.03 \hspace{0.05cm}.$$
	*Es liegt hier also eine redundante Nachrichtenquelle vor, die man durch Huffman–Codierung komprimieren kann.		*Es liegt hier also eine redundante Nachrichtenquelle vor, die man durch Huffman–Codierung komprimieren kann.
	*Dieser Algorithmus wurde 1952 – also kurz nach Shannons bahnbrechenden Arbeiten zur Informationstheorie – von  [https://de.wikipedia.org/wiki/David_A._Huffman David Albert Huffman]  veröffentlicht und erlaubt die Konstruktion von optimalen präfixfreien Codes.		*Dieser Algorithmus wurde 1952 – also kurz nach Shannons bahnbrechenden Arbeiten zur Informationstheorie – von  [https://de.wikipedia.org/wiki/David_A._Huffman David Albert Huffman]  veröffentlicht und erlaubt die Konstruktion von optimalen präfixfreien Codes.
Zeile 168:		Zeile 165:

	dargestellt werden.  Damit erhält man für die mittlere Codewortlänge (in &bdquo;bit/Quellensymbol”):		dargestellt werden.  Damit erhält man für die mittlere Codewortlänge (in &bdquo;bit/Quellensymbol”):
	:$$L_{\rm M} \hspace{0.2cm} = \hspace{0.2cm} (p_{\rm D} + p_{\rm E}) \cdot 2 + (p_{\rm C} + p_{\rm F} + p_{\rm G}) \cdot 3 + p_{\rm B} \cdot 4 +(p_{\rm A} + p_{\rm H}) \cdot 5 = 0.49 \cdot 2 + 0.36 \cdot 3 +0.08 \cdot 4 +0.07 \cdot 5		:$$L_{\rm M} \hspace{0.2cm} = \hspace{0.2cm} (p_{\rm D} + p_{\rm E}) \cdot 2 + (p_{\rm C} + p_{\rm F} + p_{\rm G}) \cdot 3 + p_{\rm B} \cdot 4 +(p_{\rm A} + p_{\rm H}) \cdot 5 = 0.49 \cdot 2 + 0.36 \cdot 3 +0.08 \cdot 4 +0.07 \cdot 5 \hspace{0.15cm}\underline{= 2.73}\hspace{0.05cm}.$$
	\hspace{0.15cm}\underline{= 2.73}\hspace{0.05cm}.$$

← Nächstältere Version		Version vom 10. August 2021, 13:43 Uhr
Zeile 3:		Zeile 3:
	}}		}}

	[[Datei:P_ID2451__Inf_A_2_6.png\|right\|frame\|~~Baumdiagramm des <br>~~Huffman–~~Verfahrens~~]]		[[Datei:P_ID2451__Inf_A_2_6.png\|right\|frame\|Huffman–Baumdiagramm]]
	Wir betrachten hier eine Quellensymbolfolge  $\langle q_\nu \rangle$  mit dem Symbolumfang  $M = 8$:		Wir betrachten hier eine Quellensymbolfolge  $\langle q_\nu \rangle$  mit dem Symbolumfang  $M = 8$:
	:$$q_{\nu} = \{ \hspace{0.05cm}q_{\mu} \} = \{ \boldsymbol{\rm A} \hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm B}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm C}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm D}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm E}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm F}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm G}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm H}\hspace{0.05cm}		:$$q_{\nu} \in \{ \hspace{0.05cm}q_{\mu} \} = \{ \boldsymbol{\rm A} \hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm B}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm C}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm D}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm E}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm F}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm G}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm H}\hspace{0.05cm}
	\}\hspace{0.05cm}.$$		\}\hspace{0.05cm}.$$
	Sind die Symbole gleichwahrscheinlich, gilt also  $p_{\rm A} = p_{\rm B} =$ ... $ = p_{\rm H} = 1/M$, so macht Quellencodierung keinen Sinn.  Bereits mit dem Dualcode  $\rm A$  →  <b>000</b>,  $\rm B$  →  <b>001</b>, ... ,  $\rm H$  →  <b>111</b>, erreicht nämlich dann die mittlere Codewortlänge  $L_{\rm M}$  ihre untere Schranke  $H$  gemäß dem Quellencodierungstheorem  $(H$ bezeichnet hierbei die ~~<i>~~Quellenentropie~~</i>~~$)$:		Sind die Symbole gleichwahrscheinlich,  gilt also  $p_{\rm A} = p_{\rm B} =$ ... $ = p_{\rm H} = 1/M$,  so macht Quellencodierung keinen Sinn.  Bereits mit dem Dualcode  $\rm A$  →  <b>000</b>,  $\rm B$  →  <b>001</b>, ... ,  $\rm H$  →  <b>111</b>, erreicht nämlich dann die mittlere Codewortlänge  $L_{\rm M}$  ihre untere Schranke  $H$  gemäß dem Quellencodierungstheorem  $(H$ bezeichnet hierbei die Quellenentropie$)$:
	:$$L_{\rm M,\hspace{0.08cm}min} = H = 3 \hspace{0.15cm}{\rm bit/Quellensymbol} \hspace{0.05cm}.$$		:$$L_{\rm M,\hspace{0.08cm}min} = H = 3 \hspace{0.15cm}{\rm bit/Quellensymbol} \hspace{0.05cm}.$$

Zeile 31:		Zeile 31:


	Oft wird dieser Algorithmus durch ein Baumdiagramm veranschaulicht. Die ~~obige~~ Grafik zeigt dieses für den vorliegenden Fall.		Oft wird dieser Algorithmus durch ein Baumdiagramm veranschaulicht. Die Grafik zeigt dieses für den vorliegenden Fall.

	Sie haben folgende Aufgaben:		Sie haben folgende Aufgaben:
Zeile 37:		Zeile 37:
	:'''(a)'''   Zuordnung der Symbole  $\rm A$, ... , $\rm H$  zu den mit  '''[1]''', ... , '''[8]'''  bezeichneten Eingängen.		:'''(a)'''   Zuordnung der Symbole  $\rm A$, ... , $\rm H$  zu den mit  '''[1]''', ... , '''[8]'''  bezeichneten Eingängen.

	:'''(b)'''   Bestimmung der Summenwahrscheinlichkeiten  $U$, ... ,  $Z$  sowie  $R$  (~~<i>~~Root~~</i>~~).		:'''(b)'''   Bestimmung der Summenwahrscheinlichkeiten  $U$, ... ,  $Z$  sowie  $R$  (&bdquo;Root”).

	:'''(c)'''   Zuordnung der Symbole  $\rm A$, ... ,  $\rm H$  zu den entsprechenden Huffman–Binärfolgen. Eine rote Verbindung entspricht einer  <b>1</b>, eine blaue Verbindung einer  <b>0</b>.		:'''(c)'''   Zuordnung der Symbole  $\rm A$, ... ,  $\rm H$  zu den entsprechenden Huffman–Binärfolgen. Eine rote Verbindung entspricht einer  <b>1</b>, eine blaue Verbindung einer  <b>0</b>.