Aufgaben:Aufgabe 2.10: Shannon-Fano-Codierung - Versionsgeschichte

Maintenance script: Add English interlanguage link

2026-03-16T12:35:11Z

Add English interlanguage link

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

	[[Category:Aufgaben zu Informationstheorie\|^2.4 Weitere Quellencodierverfahren^]]		[[Category:Aufgaben zu Informationstheorie\|^2.4 Weitere Quellencodierverfahren^]]
			[[en:Aufgaben:Exercise_2.10:_Shannon-Fano_Coding]]

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

2026-02-24T13:38:38Z

Join multi-line formulas for MW 1.43 parser compat

← Nächstältere Version		Version vom 24. Februar 2026, 15:38 Uhr
Zeile 8:		Zeile 8:
	Diese spezielle Art von Quellencodierung soll hier an einem einfachen Beispiel für den Symbolumfang  $M = 4$  und die folgenden Symbolwahrscheinlichkeiten beschrieben werden:		Diese spezielle Art von Quellencodierung soll hier an einem einfachen Beispiel für den Symbolumfang  $M = 4$  und die folgenden Symbolwahrscheinlichkeiten beschrieben werden:

	:$$p_{\rm A} = 0.2 \hspace{0.05cm}, \hspace{0.4cm}p_{\rm B}= 0.3 \hspace{0.05cm}, \hspace{0.4cm}p_{\rm C}= 0.4 \hspace{0.05cm},\hspace{0.4cm}		:$$p_{\rm A} = 0.2 \hspace{0.05cm}, \hspace{0.4cm}p_{\rm B}= 0.3 \hspace{0.05cm}, \hspace{0.4cm}p_{\rm C}= 0.4 \hspace{0.05cm},\hspace{0.4cm}p_{\rm D}= 0.1 \hspace{0.05cm}. $$
	p_{\rm D}= 0.1 \hspace{0.05cm}. $$

	Die Grafik zeigt das dazugehörige Baumdiagramm.  Man geht folgendermaßen vor:		Die Grafik zeigt das dazugehörige Baumdiagramm.  Man geht folgendermaßen vor:
Zeile 37:		Zeile 36:

	In dieser Aufgabe sollen Sie den Shannon–Fano–Code für  $M = 8$  und die Wahrscheinlichkeiten		In dieser Aufgabe sollen Sie den Shannon–Fano–Code für  $M = 8$  und die Wahrscheinlichkeiten
	:$$p_{\rm A} = 0.10 \hspace{0.05cm}, \hspace{0.4cm}p_{\rm B}= 0.40 \hspace{0.05cm}, \hspace{0.4cm}p_{\rm C}= 0.02 \hspace{0.05cm},\hspace{0.4cm} p_{\rm D}= 0.14 \hspace{0.05cm},\hspace{0.4cm}		:$$p_{\rm A} = 0.10 \hspace{0.05cm}, \hspace{0.4cm}p_{\rm B}= 0.40 \hspace{0.05cm}, \hspace{0.4cm}p_{\rm C}= 0.02 \hspace{0.05cm},\hspace{0.4cm} p_{\rm D}= 0.14 \hspace{0.05cm},\hspace{0.4cm} p_{\rm E} = 0.17 \hspace{0.05cm}, \hspace{0.4cm}p_{\rm F}= 0.03 \hspace{0.05cm}, \hspace{0.4cm}p_{\rm G}= 0.05 \hspace{0.05cm},\hspace{0.4cm}p_{\rm H}= 0.09$$
	p_{\rm E} = 0.17 \hspace{0.05cm}, \hspace{0.4cm}p_{\rm F}= 0.03 \hspace{0.05cm}, \hspace{0.4cm}p_{\rm G}= 0.05 \hspace{0.05cm},\hspace{0.4cm}p_{\rm H}= 0.09$$
	ermitteln.  Sie werden erkennen, dass sich mit diesen Wahrscheinlichkeiten &bdquo;Shannon–Fano” auch hinsichtlich der Effizienz von &bdquo;Huffman” unterscheiden wird.		ermitteln.  Sie werden erkennen, dass sich mit diesen Wahrscheinlichkeiten &bdquo;Shannon–Fano” auch hinsichtlich der Effizienz von &bdquo;Huffman” unterscheiden wird.

Guenter am 12. August 2021 um 11:59 Uhr

2021-08-12T11:59:55Z

← Nächstältere Version		Version vom 12. August 2021, 13:59 Uhr
Zeile 44:		Zeile 44:

	:       $\rm A$   →   <b>100</b>,     $\rm B$   →   <b>0</b>,     $\rm C$   →   <b>111100</b>,     $\rm D$   →   <b>101</b>,     $\rm E$   →   <b>110</b>,     $\rm F$   →   <b>111101</b>,     $\rm G$   →   <b>11111</b>,     $\rm H$   →   <b>1110</b>.		:       $\rm A$   →   <b>100</b>,     $\rm B$   →   <b>0</b>,     $\rm C$   →   <b>111100</b>,     $\rm D$   →   <b>101</b>,     $\rm E$   →   <b>110</b>,     $\rm F$   →   <b>111101</b>,     $\rm G$   →   <b>11111</b>,     $\rm H$   →   <b>1110</b>.

Guenter am 12. August 2021 um 11:55 Uhr

2021-08-12T11:55:07Z

← Nächstältere Version		Version vom 12. August 2021, 13:55 Uhr
Zeile 21:		Zeile 21:
	:4. Sind in einer Gruppe mehr als ein Zeichen, so ist der Algorithmus rekursiv anzuwenden.		:4. Sind in einer Gruppe mehr als ein Zeichen, so ist der Algorithmus rekursiv anzuwenden.

	Für dieses Beispiel ergibt sich die folgende Codezuordnung (im Baumdiagramm markiert eine rote Verbindung eine  <b>1</b>  und eine blaue eine  <b>0</b>:		Für dieses Beispiel ergibt sich die folgende Codezuordnung (im Baumdiagramm markiert eine rote Verbindung eine  <b>1</b>  und eine blaue eine  <b>0</b>):

	:       $\rm A$   →   <b>111</b>,     $\rm B$   →   <b>10</b>,     $\rm C$   →   <b>0</b>,     $\rm D$   →   <b>110</b>.		:       $\rm A$   →   <b>111</b>,     $\rm B$   →   <b>10</b>,     $\rm C$   →   <b>0</b>,     $\rm D$   →   <b>110</b>.
Zeile 57:		Zeile 57:
	*Die Aufgabe gehört zum Kapitel  [[Informationstheorie/Weitere_Quellencodierverfahren\|Weitere Quellencodierverfahren]].		*Die Aufgabe gehört zum Kapitel  [[Informationstheorie/Weitere_Quellencodierverfahren\|Weitere Quellencodierverfahren]].
	*Insbesondere wird Bezug genommen auf die Seite  [[Informationstheorie/Weitere_Quellencodierverfahren#Der_Shannon.E2.80.93Fano.E2.80.93Algorithmus\|Der Shannon-Fano-Algorithmus]].		*Insbesondere wird Bezug genommen auf die Seite  [[Informationstheorie/Weitere_Quellencodierverfahren#Der_Shannon.E2.80.93Fano.E2.80.93Algorithmus\|Der Shannon-Fano-Algorithmus]].
	*Zur Kontrolle Ihrer Ergebnisse verweisen wir auf das ~~interaktive Applet~~  [[Applets:Huffman-~~_und_Shannon~~-Fano-Codierung~~\|Huffman~~&~~ndash~~; ~~und Shannon~~&~~ndash~~;~~Fano~~–~~Codierung~~]].		*Zur Kontrolle Ihrer Ergebnisse verweisen wir auf das folgende Interaktionsmodul:  [[Applets:Huffman_Shannon_Fano\|Huffman- und Shannon-Fano-Codierung  ⇒   $\text{SWF}$–Version]].


Zeile 70:		Zeile 70:


	{Was geschieht im ersten Schritt der  <u>Shannon–Fano–Codierung</u>?  ''Hinweis'':  Alle anderen Symbole werden in der zweiten Gruppe zusammengefasst.		{Was geschieht im ersten Schritt der  <u>Shannon–Fano–Codierung</u>?  <u>Hinweis</u>:  Alle anderen Symbole werden in der zweiten Gruppe zusammengefasst.
	\|type="[]"}		\|type="()"}
	- Man fasst  $\rm A$  und  $\rm B$  zur ersten Gruppe zusammen.		- Man fasst  $\rm A$  und  $\rm B$  zur ersten Gruppe zusammen.
	+ Man fasst  $\rm B$  und  $\rm E$  zur ersten Gruppe zusammen.		+ Man fasst  $\rm B$  und  $\rm E$  zur ersten Gruppe zusammen.

Guenter am 28. Januar 2020 um 12:49 Uhr

2020-01-28T12:49:48Z

← Nächstältere Version		Version vom 28. Januar 2020, 14:49 Uhr
Zeile 103:		Zeile 103:
	'''(1)'''  Für den angegebenen Huffman–Code erhält man:		'''(1)'''  Für den angegebenen Huffman–Code erhält man:
	:$$L_{\rm M} = 0.4 \cdot 1 + (0.17 + 0.14 + 0.10) \cdot 3 + 0.09 \cdot 4 + 0.05 \cdot 5 + (0.03 + 0.02) \cdot 6 =\underline{ 2.54 \,\,{\rm bit/Quellensymbol}}\hspace{0.05cm}. $$		:$$L_{\rm M} = 0.4 \cdot 1 + (0.17 + 0.14 + 0.10) \cdot 3 + 0.09 \cdot 4 + 0.05 \cdot 5 + (0.03 + 0.02) \cdot 6 =\underline{ 2.54 \,\,{\rm bit/Quellensymbol}}\hspace{0.05cm}. $$



	'''(2)'''  Richtig ist die <u>Antwort 2</u>:		'''(2)'''  Richtig ist die <u>Antwort 2</u>:
	*Vor Anwendung des Shannon–Fano–Algorithmus müssen die Zeichen erst nach ihren Auftrittswahrscheinlichkeiten sortiert werden. Damit ist die Antwort 1 falsch.		*Vor Anwendung des Shannon–Fano–Algorithmus müssen die Zeichen erst nach ihren Auftrittswahrscheinlichkeiten sortiert werden.  Damit ist die Antwort 1 falsch.
	*Alle sortierten Zeichen müssen so in zwei Gruppen eingeteilt werden, dass die Gruppenwahrscheinlichkeiten möglichst gleich sind. Für den ersten Schritt:		*Alle sortierten Zeichen müssen so in zwei Gruppen eingeteilt werden, dass die Gruppenwahrscheinlichkeiten möglichst gleich sind. Für den ersten Schritt:

	:$${\rm Pr}(\boldsymbol{\rm BE}) = 0.57\hspace{0.05cm}, \hspace{0.2cm}{\rm Pr}(\boldsymbol{\rm DAHGFC}) = 0.43 \hspace{0.05cm}.$$		:$${\rm Pr}(\boldsymbol{\rm BE}) = 0.57\hspace{0.05cm}, \hspace{0.2cm}{\rm Pr}(\boldsymbol{\rm DAHGFC}) = 0.43 \hspace{0.05cm}.$$
			[[Datei:P_ID2466__Inf_A_2_10c.png\|right\|frame\|Baumdiagramm der Shannon–Fano–Codierung]]
	*Bei der Aufteilung gemäß Lösungsvorschlag 3 würde die Gleichverteilung noch weniger erreicht:		*Bei der Aufteilung gemäß Lösungsvorschlag 3 würde die Gleichverteilung noch weniger erreicht:
	:$${\rm Pr}(\boldsymbol{\rm B}) = 0.40\hspace{0.05cm}, \hspace{0.2cm}{\rm Pr}(\boldsymbol{\rm EDAHGFC}) = 0.60 \hspace{0.05cm}.$$		:$${\rm Pr}(\boldsymbol{\rm B}) = 0.40\hspace{0.05cm}, \hspace{0.2cm}{\rm Pr}(\boldsymbol{\rm EDAHGFC}) = 0.60 \hspace{0.05cm}.$$


	~~[[Datei:P_ID2466__Inf_A_2_10c.png\|right\|frame\|Baumdiagramm der Shannon–Fano–Codierung]]~~

	'''(3)'''  <u>Alle Lösungsvorschläge</u> sind richtig:		'''(3)'''  <u>Alle Lösungsvorschläge</u> sind richtig:
	*Die Grafik zeigt das Baumdiagramm der Shannon–Fano–Codierung.		*Die Grafik zeigt das Baumdiagramm der Shannon–Fano–Codierung.
	*Daraus ergibt sich folgende Zuordnung (eine rote Verbindung weist auf <b>1</b> hin, eine blaue auf <b>0</b>):		*Daraus ergibt sich folgende Zuordnung (eine rote Verbindung weist auf eine  <b>1</b>  hin, eine blaue auf eine  <b>0</b>):
	: $\underline{\rm A}$ → <u><b>010</b></u>,		: $\underline{\rm A}$   →   <u><b>010</b></u>,     $\underline{\rm B}$   →   <u><b>11</b></u>,     $\underline{\rm C}$   →   <u><b>00110</b></u>,
	: $\underline{\rm B}$ → <u><b>11</b></u>,		: ${\rm D}$   →   <b>011</b>,     ${\rm E}$   →   <b>10</b>,     ${\rm F}$   →   <b>00111</b>,     ${\rm G}$   →   <b>0010</b>,     ${\rm H}$   →   <b>000</b>.
	: $\underline{\rm C}$ → <u><b>00110</b></u>,
	: ${\rm D}$ → <b>011</b>,     ${\rm E}$ → <b>10</b>,     ${\rm F}$ → <b>00111</b>,     ${\rm G}$ → <b>0010</b>,     ${\rm H}$ → <b>000</b>.
	~~<br clear=all>~~
	'''(4)'''  Mit dem Ergebnis der Teilaufgabe '''(3)''' erhält man:		'''(4)'''  Mit dem Ergebnis der Teilaufgabe  '''(3)'''  erhält man:
	:$$L_{\rm M}= (0.40 + 0.17) \cdot 2 + (0.14 + 0.10 + 0.09) \cdot 3 + 0.05 \cdot 4 + (0.03 + 0.02) \cdot 5 =\underline{ 2.58 \,\,{\rm bit/Quellensymbol}}\hspace{0.05cm}. $$		:$$L_{\rm M}= (0.40 + 0.17) \cdot 2 + (0.14 + 0.10 + 0.09) \cdot 3 + 0.05 \cdot 4 + (0.03 + 0.02) \cdot 5 =\underline{ 2.58 \,\,{\rm bit/Quellensymbol}}\hspace{0.05cm}. $$

Guenter am 28. Januar 2020 um 12:34 Uhr

2020-01-28T12:34:02Z

Änderungen zeigen

Guenter am 2. Oktober 2018 um 11:35 Uhr

2018-10-02T11:35:16Z

← Nächstältere Version		Version vom 2. Oktober 2018, 13:35 Uhr
Zeile 107:		Zeile 107:
	: $\underline{\rm B}$ → <u><b>11</b></u>,		: $\underline{\rm B}$ → <u><b>11</b></u>,
	: $\underline{\rm C}$ → <u><b>00110</b></u>,		: $\underline{\rm C}$ → <u><b>00110</b></u>,
	: ${\rm D}$ → <b>011</b>, ${\rm E}$ → <b>10</b>, ${\rm F}$ → <b>00111</b>, ~~<b>~~G~~</b>~~ → <b>0010</b>, ~~<b>~~H~~</b>~~ → <b>000</b>.		: ${\rm D}$ → <b>011</b>,     ${\rm E}$ → <b>10</b>,     ${\rm F}$ → <b>00111</b>,     ${\rm G}$ → <b>0010</b>,     ${\rm H}$ → <b>000</b>.
			<br clear=all>
			'''(4)'''  Mit dem Ergebnis der Teilaufgabe '''(3)''' erhält man:
			:$$L_{\rm M}= (0.40 + 0.17) \cdot 2 + (0.14 + 0.10 + 0.09) \cdot 3 + 0.05 \cdot 4 + (0.03 + 0.02) \cdot 5 =\underline{ 2.58 \,\,{\rm bit/Quellensymbol}}\hspace{0.05cm}. $$


	~~'''(4)'''  Mit dem Ergebnis der Teilaufgabe (3) erhält man:~~
	~~:$$L_{\rm M}= (0.40 + 0.17) \cdot 2 + (0.14 + 0.10 + 0.09) \cdot 3 + 0.05 \cdot 4 + (0.03 + 0.02) \cdot 5 =\underline{ 2.58 \,\,{\rm bit/Quellensymbol}}\hspace{0.05cm}. $$~~

	'''(5)'''  Richtig sind die <u>Aussagen 2 und 3</u>:		'''(5)'''  Richtig sind die <u>Aussagen 2 und 3</u>:

Guenter am 2. Oktober 2018 um 10:24 Uhr

2018-10-02T10:24:43Z

← Nächstältere Version		Version vom 2. Oktober 2018, 12:24 Uhr
Zeile 90:		Zeile 90:
	'''(1)'''  Für den angegebenen Huffman–Code erhält man:		'''(1)'''  Für den angegebenen Huffman–Code erhält man:
	:$$L_{\rm M} = 0.4 \cdot 1 + (0.17 + 0.14 + 0.10) \cdot 3 + 0.09 \cdot 4 + 0.05 \cdot 5 + (0.03 + 0.02) \cdot 6 =\underline{ 2.54 \,\,{\rm bit/Quellensymbol}}\hspace{0.05cm}. $$		:$$L_{\rm M} = 0.4 \cdot 1 + (0.17 + 0.14 + 0.10) \cdot 3 + 0.09 \cdot 4 + 0.05 \cdot 5 + (0.03 + 0.02) \cdot 6 =\underline{ 2.54 \,\,{\rm bit/Quellensymbol}}\hspace{0.05cm}. $$


	'''(2)'''  Richtig ist die <u>Antwort 2</u>:		'''(2)'''  Richtig ist die <u>Antwort 2</u>:
	*Vor Anwendung des Shannon–Fano–Algorithmus müssen die Zeichen ~~zuerst noch~~ nach ihren Auftrittswahrscheinlichkeiten sortiert werden. Damit ist die Antwort 1 falsch.		*Vor Anwendung des Shannon–Fano–Algorithmus müssen die Zeichen erst nach ihren Auftrittswahrscheinlichkeiten sortiert werden. Damit ist die Antwort 1 falsch.
	*Alle sortierten Zeichen müssen so in zwei Gruppen eingeteilt werden, dass die Gruppenwahrscheinlichkeiten möglichst gleich sind. Für den ersten Schritt ~~bedeutet dies~~:		*Alle sortierten Zeichen müssen so in zwei Gruppen eingeteilt werden, dass die Gruppenwahrscheinlichkeiten möglichst gleich sind. Für den ersten Schritt:
	:$${\rm Pr}(\boldsymbol{\rm BE}) = 0.57\hspace{0.05cm}, \hspace{0.2cm}{\rm Pr}(\boldsymbol{\rm DAHGFC}) = 0.43 \hspace{0.05cm}.$$		:$${\rm Pr}(\boldsymbol{\rm BE}) = 0.57\hspace{0.05cm}, \hspace{0.2cm}{\rm Pr}(\boldsymbol{\rm DAHGFC}) = 0.43 \hspace{0.05cm}.$$
	*Bei der Aufteilung gemäß Lösungsvorschlag 3 würde die Gleichverteilung noch weniger erreicht:		*Bei der Aufteilung gemäß Lösungsvorschlag 3 würde die Gleichverteilung noch weniger erreicht:
	:$${\rm Pr}(\boldsymbol{\rm B}) = 0.40\hspace{0.05cm}, \hspace{0.2cm}{\rm Pr}(\boldsymbol{\rm EDAHGFC}) = 0.60 \hspace{0.05cm}.$$		:$${\rm Pr}(\boldsymbol{\rm B}) = 0.40\hspace{0.05cm}, \hspace{0.2cm}{\rm Pr}(\boldsymbol{\rm EDAHGFC}) = 0.60 \hspace{0.05cm}.$$

	[[Datei:P_ID2466__Inf_A_2_10c.png\|right\|Baumdiagramm der Shannon–Fano–Codierung]]
			[[Datei:P_ID2466__Inf_A_2_10c.png\|right\|frame\|Baumdiagramm der Shannon–Fano–Codierung]]
	'''(3)'''  <u>Alle Lösungsvorschläge</u> sind richtig:		'''(3)'''  <u>Alle Lösungsvorschläge</u> sind richtig:
	*Die Grafik zeigt das Baumdiagramm der Shannon–Fano–Codierung.		*Die Grafik zeigt das Baumdiagramm der Shannon–Fano–Codierung.
	*Daraus ergibt sich folgende Zuordnung (eine rote Verbindung weist auf <b>1</b> hin, eine blaue auf <b>0</b>):		*Daraus ergibt sich folgende Zuordnung (eine rote Verbindung weist auf <b>1</b> hin, eine blaue auf <b>0</b>):
	: ~~<u><b>~~A~~</b>~~ → <b>010</b></u>,		: $\underline{\rm A}$ → <u><b>010</b></u>,
	: ~~<u><b>~~B~~</b>~~ → <b>11</b></u>,		: $\underline{\rm B}$ → <u><b>11</b></u>,
	: ~~<u><b>~~C~~</b>~~ → <b>00110</b></u>,		: $\underline{\rm C}$ → <u><b>00110</b></u>,
	: ~~<b>~~D~~</b>~~ → <b>011</b>, ~~<b>~~E~~</b>~~ → <b>10</b>, ~~<b>~~F~~</b>~~ → <b>00111</b>,		: ${\rm D}$ → <b>011</b>, ${\rm E}$ → <b>10</b>, ${\rm F}$ → <b>00111</b>, <b>G</b> → <b>0010</b>, <b>H</b> → <b>000</b>.
	: <b>G</b> → <b>0010</b>, <b>H</b> → <b>000</b>.

Guenter am 2. Oktober 2018 um 10:16 Uhr

2018-10-02T10:16:05Z

← Nächstältere Version		Version vom 2. Oktober 2018, 12:16 Uhr
Zeile 44:		Zeile 44:
	*Die Aufgabe gehört zum Kapitel [[Informationstheorie/Weitere_Quellencodierverfahren\|Weitere Quellencodierverfahren]].		*Die Aufgabe gehört zum Kapitel [[Informationstheorie/Weitere_Quellencodierverfahren\|Weitere Quellencodierverfahren]].
	*Insbesondere wird Bezug genommen auf die Seite [[Informationstheorie/Weitere_Quellencodierverfahren#Der_Shannon.E2.80.93Fano.E2.80.93Algorithmus\|Der Shannon-Fano-Algorithmus]].		*Insbesondere wird Bezug genommen auf die Seite [[Informationstheorie/Weitere_Quellencodierverfahren#Der_Shannon.E2.80.93Fano.E2.80.93Algorithmus\|Der Shannon-Fano-Algorithmus]].
	*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 interaktive Applet [[Applets:Huffman_Shannon_Fano\|Shannon–Fano– und Huffman–Codierung]].


Zeile 52:		Zeile 52:

	<quiz display=simple>		<quiz display=simple>
	{Wie groß ist die mittlere Codewortlänge beim Huffman–Code?		{Wie groß ist die mittlere Codewortlänge $L_{\rm M}$ beim <u>Huffman–Code</u>?
	\|type="{}"}		\|type="{}"}
	$~~\text{Huffman:} \ \~~ L_{\rm M}\ = \ $ { 2.54 3% } $\ \rm bit/Quellensymbol$		$L_{\rm M}\ = \ $ { 2.54 3% } $\ \rm bit/Quellensymbol$


	{Was geschieht im ersten Schritt der Shannon–Fano–Codierung? Alle anderen Symbole werden in der zweiten Gruppe zusammengefasst.		{Was geschieht im ersten Schritt der <u>Shannon–Fano–Codierung</u>? <br>Alle anderen Symbole werden in der zweiten Gruppe zusammengefasst.
	\|type="[]"}		\|type="[]"}
	- Man fasst ~~<b>~~A~~</b>~~ und ~~<b>~~B~~</b>~~ zur ersten Gruppe zusammen.		- Man fasst $\rm A$ und $\rm B$ zur ersten Gruppe zusammen.
	+ Man fasst ~~<b>~~B~~</b>~~ und ~~<b>~~E~~</b>~~ zur ersten Gruppe zusammen.		+ Man fasst $\rm B$ und $\rm E$ zur ersten Gruppe zusammen.
	- Die erste Gruppe besteht nur aus dem Symbol ~~<b>~~B~~</b>~~.		- Die erste Gruppe besteht nur aus dem Symbol $\rm B$.


	{Welche Zuordnungen ergeben sich für den Shannon–Fano–Algorithmus?		{Welche Zuordnungen ergeben sich für den <u>Shannon–Fano–Algorithmus</u>?
	\|type="[]"}		\|type="[]"}
	+ Das Zeichen ~~<b>~~A~~</b>~~ wird binär mit <b>010</b> codiert.		+ Das Zeichen $\rm A$ wird binär mit <b>010</b> codiert.
	+ Das Zeichen ~~<b>~~B~~</b>~~ wird binär mit <b>11</b> codiert.		+ Das Zeichen $\rm B$ wird binär mit <b>11</b> codiert.
	+ Das Zeichen ~~<b>~~C~~</b>~~ wird binär mit <b>00110</b> codiert.		+ Das Zeichen $\rm C$ wird binär mit <b>00110</b> codiert.


	{Wie groß ist die mittlere Codewortlänge beim Shannon–Fano–Code?		{Wie groß ist die mittlere Codewortlänge $L_{\rm M}$ beim <u>Shannon–Fano–Code</u>?
	\|type="{}"}		\|type="{}"}
	$~~\text{Shannon-Fano:} \ \~~ L_{\rm M}\ = \ $ { 2.58 3% } $\ \rm bit/Quellensymbol$		$L_{\rm M}\ = \ $ { 2.58 3% } $\ \rm bit/Quellensymbol$

Guenter am 2. Oktober 2018 um 10:10 Uhr

2018-10-02T10:10:29Z

← Nächstältere Version		Version vom 2. Oktober 2018, 12:10 Uhr
Zeile 3:		Zeile 3:
	}}		}}

	[[Datei:P_ID2465__Inf_A_2_10.png \|right\|Baumdiagramm der Shannon–Fano–Codierung]]		[[Datei:P_ID2465__Inf_A_2_10.png \|right\|frame\|Baumdiagramm der Shannon–Fano–Codierung]]
	Ein weiterer Algorithmus zur Entropiecodierung wurde 1949 von [https://de.wikipedia.org/wiki/Claude_Shannon Claude Elwood Shannon] und [https://de.wikipedia.org/wiki/Robert_Fano\|Robert Fano] angegeben, der im Theorieteil angegeben ist.		Ein weiterer Algorithmus zur Entropiecodierung wurde 1949 von [https://de.wikipedia.org/wiki/Claude_Shannon Claude Elwood Shannon] und [https://de.wikipedia.org/wiki/Robert_Fano\|Robert Fano] angegeben, der im Theorieteil angegeben ist.

	Diese spezielle Art von Quellencodierung soll hier an einem einfachen Beispiel für den Symbolumfang $M = 4$ und ~~folgende~~ Symbolwahrscheinlichkeiten beschrieben werden:		Diese spezielle Art von Quellencodierung soll hier an einem einfachen Beispiel für den Symbolumfang $M = 4$ und die folgenden Symbolwahrscheinlichkeiten beschrieben werden:

	:$$p_{\rm A} = 0.2 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm B}= 0.3 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm C}= 0.4 \hspace{0.05cm},\hspace{0.2cm}		:$$p_{\rm A} = 0.2 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm B}= 0.3 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm C}= 0.4 \hspace{0.05cm},\hspace{0.2cm}
	p_{\rm D}= 0.1 \hspace{0.05cm}. $$		p_{\rm D}= 0.1 \hspace{0.05cm}. $$

	Die ~~obige~~ Grafik zeigt das dazugehörige Baumdiagramm. Man geht folgendermaßen vor:		Die Grafik zeigt das dazugehörige Baumdiagramm. Man geht folgendermaßen vor:

	:1. Man ordnet die Symbole nach fallender Auftrittswahrscheinlichkeit, hier ~~<b>~~C~~</b>~~ – ~~<b>~~B~~</b>~~ – ~~<b>~~A~~</b>~~ – ~~<b>~~D~~</b>~~.		:1. Man ordnet die Symbole nach fallender Auftrittswahrscheinlichkeit, hier $\rm C$ – $\rm B$ – $\rm A$ – $\rm D$.

	:2. Man teilt die Symbole in zwei etwa gleichwahrscheinliche Gruppen ein, hier ~~<b>~~C~~</b>~~ und ~~<b>~~BAD~~</b>~~.		:2. Man teilt die Symbole in zwei etwa gleichwahrscheinliche Gruppen ein, hier $\rm C$ und $\rm BAD$.

	:3. Der unwahrscheinlicheren Gruppe wird das Binärsymbol <b>0</b>, der anderen die <b>1</b> zugeordnet.		:3. Der unwahrscheinlicheren Gruppe wird das Binärsymbol <b>0</b>, der anderen die <b>1</b> zugeordnet.
Zeile 23:		Zeile 23:
	Für dieses Beispiel ergibt sich die folgende Codezuordnung (im Baumdiagramm markiert eine rote Verbindung eine <b>1</b> und eine blaue eine <b>0</b>:		Für dieses Beispiel ergibt sich die folgende Codezuordnung (im Baumdiagramm markiert eine rote Verbindung eine <b>1</b> und eine blaue eine <b>0</b>:

	:       ~~<b>~~A~~</b>~~ → <b>111</b>, ~~<b>~~B~~</b>~~ → <b>10</b>, ~~<b>~~C~~</b>~~ → <b>0</b>, ~~<b>~~D~~</b>~~ → <b>110</b>.		:       $\rm A$ → <b>111</b>,     $\rm B$ → <b>10</b>,     $\rm C$ → <b>0</b>,     $\rm D$ → <b>110</b>.

	Damit ergibt sich für die mittlere Codewortlänge:		Damit ergibt sich für die mittlere Codewortlänge:
	:$$L_{\rm M} = 0.4 \cdot 1 + 0.3 \cdot 2 + (0.2 + 0.1) \cdot 3 = 1.9\,\,{\rm bit/Quellensymbol}\hspace{0.05cm}.$$		:$$L_{\rm M} = 0.4 \cdot 1 + 0.3 \cdot 2 + (0.2 + 0.1) \cdot 3 = 1.9\,\,{\rm bit/Quellensymbol}\hspace{0.05cm}.$$

	Der Huffman-Algorithmus würde hier zwar einen geringfügig anderen Code erzeugen, aber auch bei diesem würde ~~<b>~~C~~</b>~~ mit einem Bit, ~~<b>~~B~~</b>~~ mit zwei Bit und ~~<b>~~A~~</b>~~ und ~~<b>~~D~~</b>~~ mit jeweils drei Bit codiert. Damit ergäbe sich ebenfalls $L_{\rm M} = 1.9 \ \rm bit/Quellensymbol$.		Der Huffman-Algorithmus würde hier zwar einen geringfügig anderen Code erzeugen, aber auch bei diesem würde $\rm C$ mit einem Bit, $\rm B$ mit zwei Bit und $\rm A$ und $\rm D$ mit jeweils drei Bit codiert. Damit ergäbe sich ebenfalls $L_{\rm M} = 1.9 \ \rm bit/Quellensymbol$.

	In dieser Aufgabe sollen Sie den Shannon–Fano–Code für $M = 8$ und die Wahrscheinlichkeiten		In dieser Aufgabe sollen Sie den Shannon–Fano–Code für $M = 8$ und die Wahrscheinlichkeiten
	:$$p_{\rm A} = 0.10 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm B}= 0.40 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm C}= 0.02 \hspace{0.05cm},\hspace{0.2cm} p_{\rm D}= 0.14 \hspace{0.05cm},		:$$p_{\rm A} = 0.10 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm B}= 0.40 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm C}= 0.02 \hspace{0.05cm},\hspace{0.2cm} p_{\rm D}= 0.14 \hspace{0.05cm},\hspace{0.2cm}
	p_{\rm E} = 0.17 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm F}= 0.03 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm G}= 0.05 \hspace{0.05cm},\hspace{0.2cm}p_{\rm H}= 0.09$$		p_{\rm E} = 0.17 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm F}= 0.03 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm G}= 0.05 \hspace{0.05cm},\hspace{0.2cm}p_{\rm H}= 0.09$$
	ermitteln. Sie werden erkennen, dass sich mit diesen Wahrscheinlichkeiten &bdquo;Shannon–Fano” auch hinsichtlich Effizienz von &bdquo;Huffman” unterscheiden wird. Beim Huffman–Code ergibt sich mit den vorliegenden Wahrscheinlichkeiten die folgende Zuordnung:		ermitteln. Sie werden erkennen, dass sich mit diesen Wahrscheinlichkeiten &bdquo;Shannon–Fano” auch hinsichtlich Effizienz von &bdquo;Huffman” unterscheiden wird. Beim Huffman–Code ergibt sich mit den vorliegenden Wahrscheinlichkeiten die folgende Zuordnung:

	:       ~~<b>~~A~~</b>~~ → <b>100</b>, ~~<b>~~B~~</b>~~ → <b>0</b>, ~~<b>~~C~~</b>~~ → <b>111100</b>, ~~<b>~~D~~</b>~~ → <b>101</b>, ~~<b>~~E~~</b>~~ → <b>110</b>, ~~<b>~~F~~</b>~~ → <b>111101</b>, ~~<b>~~G~~</b>~~ → <b>11111</b>, ~~<b>~~H~~</b>~~ → <b>1110</b>.		:       $\rm A$ → <b>100</b>,     $\rm B$ → <b>0</b>,     $\rm C$ → <b>111100</b>,     $\rm D$ → <b>101</b>,     $\rm E$ → <b>110</b>,     $\rm F$ → <b>111101</b>,     $\rm G$ → <b>11111</b>,     $\rm H$ → <b>1110</b>.





Zeile 41:		Zeile 44:
	*Die Aufgabe gehört zum Kapitel [[Informationstheorie/Weitere_Quellencodierverfahren\|Weitere Quellencodierverfahren]].		*Die Aufgabe gehört zum Kapitel [[Informationstheorie/Weitere_Quellencodierverfahren\|Weitere Quellencodierverfahren]].
	*Insbesondere wird Bezug genommen auf die Seite [[Informationstheorie/Weitere_Quellencodierverfahren#Der_Shannon.E2.80.93Fano.E2.80.93Algorithmus\|Der Shannon-Fano-Algorithmus]].		*Insbesondere wird Bezug genommen auf die Seite [[Informationstheorie/Weitere_Quellencodierverfahren#Der_Shannon.E2.80.93Fano.E2.80.93Algorithmus\|Der Shannon-Fano-Algorithmus]].
	*Zur Kontrolle Ihrer Ergebnisse verweisen wir auf das Interaktionsmodul [[Shannon–Fano– und Huffman–Codierung]].		*Zur Kontrolle Ihrer Ergebnisse verweisen wir auf das Interaktionsmodul [[Applets:Huffman_Shannon_Fano\|Shannon–Fano– und Huffman–Codierung]].