Aufgaben:Exercise 2.10: Shannon-Fano Coding - Revision history

Maintenance script: Fix interlanguage link: resolve redirect chain

2026-03-16T15:57:12Z

Fix interlanguage link: resolve redirect chain

← Older revision		Revision as of 17:57, 16 March 2026
Line 54:		Line 54:
	Hints:		Hints:
	*The assignment belongs to the chapter  [[Information_Theory/Weitere_Quellencodierverfahren\|Further source coding methods]].		*The assignment belongs to the chapter  [[Information_Theory/Weitere_Quellencodierverfahren\|Further source coding methods]].
	*In particular, reference is made to the page  [[Information_Theory/~~Weitere_Quellencodierverfahren~~#The_Shannon-Fano_algorithm\|The Shannon-Fano algorithm]].		*In particular, reference is made to the page  [[Information_Theory/Further_Source_Coding_Methods#The_Shannon-Fano_algorithm\|The Shannon-Fano algorithm]].
	*To check your results, please refer to the (German language) SWF module  [[Applets:Huffman_Shannon_Fano\|Coding according to Huffman and Shannon/Fano]].		*To check your results, please refer to the (German language) SWF module  [[Applets:Huffman_Shannon_Fano\|Coding according to Huffman and Shannon/Fano]].

Line 136:		Line 136:

	[[Category:Information Theory: Exercises\|^2.4 Further Source Coding Methods^]]		[[Category:Information Theory: Exercises\|^2.4 Further Source Coding Methods^]]
	[[de:Aufgaben:2.~~10_Shannon~~-Fano-Codierung]]		[[de:Aufgaben:Aufgabe 2.10: Shannon-Fano-Codierung]]

Maintenance script: Join split $$ formula lines for correct rendering

2026-03-16T13:47:38Z

Join split $$ formula lines for correct rendering

← Older revision		Revision as of 15:47, 16 March 2026
Line 8:		Line 8:
	This special type of source coding will be described here using a simple example for the symbol set size  $M = 4$  and the following symbol probabilities:		This special type of source coding will be described here using a simple example for the symbol set size  $M = 4$  and the following symbol probabilities:

	:$$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}. $$

	The graph shows the corresponding tree diagram.  Proceed as follows:		The graph shows the corresponding tree diagram.  Proceed as follows:
Line 37:		Line 36:

	In this task you are to calculate the Shannon-Fano code for  $M = 8$  and the probabilities		In this task you are to calculate the Shannon-Fano code for  $M = 8$  and the probabilities
	:$$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.$$
	You will see that with these probabilities  "Shannon-Fano"  will also differ from  "Huffman"  in terms of efficiency.		You will see that with these probabilities  "Shannon-Fano"  will also differ from  "Huffman"  in terms of efficiency.

Maintenance script: Add German interlanguage link

2026-03-16T12:30:52Z

Add German interlanguage link

← Older revision		Revision as of 14:30, 16 March 2026
Line 138:		Line 138:

	[[Category:Information Theory: Exercises\|^2.4 Further Source Coding Methods^]]		[[Category:Information Theory: Exercises\|^2.4 Further Source Coding Methods^]]
			[[de:Aufgaben:2.10_Shannon-Fano-Codierung]]

Hwang at 15:05, 1 November 2022

2022-11-01T15:05:53Z

← Older revision		Revision as of 17:05, 1 November 2022
Line 25:		Line 25:
	:       $\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>.

	This gives the following for the average ~~codeword~~ length:		This gives the following for the average code word length:
	:$$L_{\rm M} = 0.4 \cdot 1 + 0.3 \cdot 2 + (0.2 + 0.1) \cdot 3 = 1.9\,\,{\rm bit/source\hspace{0.15cm}symbol}\hspace{0.05cm}.$$		:$$L_{\rm M} = 0.4 \cdot 1 + 0.3 \cdot 2 + (0.2 + 0.1) \cdot 3 = 1.9\,\,{\rm bit/source\hspace{0.15cm}symbol}\hspace{0.05cm}.$$

Line 65:		Line 65:

	<quiz display=simple>		<quiz display=simple>
	{What is the average ~~codeword~~ length  $L_{\rm M}$  for the  <u>Huffman code</u>?		{What is the average code word length  $L_{\rm M}$  for the  <u>Huffman code</u>?
	\|type="{}"}		\|type="{}"}
	$L_{\rm M}\ = \ $ { 2.54 3% } $\ \rm bit/source\hspace{0.15cm}symbol$		$L_{\rm M}\ = \ $ { 2.54 3% } $\ \rm bit/source\hspace{0.15cm}symbol$
Line 84:		Line 84:


	{What is the average ~~codeword~~ length  $L_{\rm M}$  for  <u>Shannon–Fano code</u>?		{What is the average code word length  $L_{\rm M}$  for  <u>Shannon–Fano code</u>?
	\|type="{}"}		\|type="{}"}
	$L_{\rm M}\ = \ $ { 2.58 3% } $\ \rm bit/source\hspace{0.15cm}symbol$		$L_{\rm M}\ = \ $ { 2.58 3% } $\ \rm bit/source\hspace{0.15cm}symbol$

Guenter at 12:33, 12 August 2021

2021-08-12T12:33:03Z

← Older revision		Revision as of 14:33, 12 August 2021
Line 1:		Line 1:

	{{quiz-Header\|Buchseite=~~Informationstheorie~~/~~Weitere Quellencodierverfahren~~		{{quiz-Header\|Buchseite=Information_Theory/Further_Source_Coding_Methods
	}}		}}

Guenter at 12:20, 12 August 2021

2021-08-12T12:20:43Z

← Older revision		Revision as of 14:20, 12 August 2021
Line 102:		Line 102:
	{{ML-Kopf}}		{{ML-Kopf}}
	'''(1)'''  For the given Huffman code one obtains:		'''(1)'''  For the given Huffman code one obtains:
	:$$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/source\:symbol}}\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/source\hspace{0.15cm}symbol}}\hspace{0.05cm}. $$


Line 110:		Line 110:
	*All sorted characters must be divided into two groups in such a way that the group probabilities are as equal as possible. For the first step:		*All sorted characters must be divided into two groups in such a way that the group probabilities are as equal as possible. For the first step:

			[[File:P_ID2466__Inf_A_2_10c.png\|right\|frame\|Tree diagram of Shannon-Fano coding]]
	:$${\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}.$$
	~~[[File:P_ID2466__Inf_A_2_10c.png\|right\|frame\|Tree diagram of Shannon-Fano coding]]~~
	*With the distribution according to solution suggestion 3, the equal distribution would be achieved even less:		*With the distribution according to solution suggestion 3, the equal distribution would be achieved even less:
	:$${\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}.$$




Line 127:		Line 125:

	'''(4)'''  Using the result of sub-task  '''(3)''' , we get:		'''(4)'''  Using the result of sub-task  '''(3)''' , we get:
	:$$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/source\:symbol}}\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/source\hspace{0.15cm}symbol}}\hspace{0.05cm}. $$


Line 133:		Line 131:
	'''(5)'''  <u>Statements 2 and 3</u> are correct:		'''(5)'''  <u>Statements 2 and 3</u> are correct:
	*In the present example, Shannon-Fano results in a less favourable value than Huffman.		*In the present example, Shannon-Fano results in a less favourable value than Huffman.
	*In most cases – including the example on the information page – Huffman and Shannon-Fano result in an equivalent code and thus also the same average code word length.		*In most cases – including the example on the information page –  "Huffman"  and  "Shannon-Fano"  result in an equivalent code and thus also to the same average code word length.
	*Shannon-Fano, on the other hand, never delivers a more effective code than Huffman.		*Shannon-Fano, on the other hand, never delivers a more effective code than Huffman.
	{{ML-Fuß}}		{{ML-Fuß}}

Guenter at 12:13, 12 August 2021

2021-08-12T12:13:57Z

← Older revision		Revision as of 14:13, 12 August 2021
Line 70:		Line 70:


	{What happens in the first step of  <u>Shannon–Fano coding</u>?  ''Hint'':  All other symbols are grouped together in the second group.		{What happens in the first step of  <u>Shannon–Fano coding</u>?  <u>Hint</u>:  All other symbols are grouped together in the second group.
	\|type="[]"}		\|type="()"}
	-   $\rm A$  and  $\rm B$  are combined into the first group.		-   $\rm A$  and  $\rm B$  are combined into the first group.
	+   $\rm B$  and  $\rm E$  are combined into the first group.		+   $\rm B$  and  $\rm E$  are combined into the first group.
Line 79:		Line 79:
	{Which assignments result for the  <u>Shannon–Fano algorithm</u>?		{Which assignments result for the  <u>Shannon–Fano algorithm</u>?
	\|type="[]"}		\|type="[]"}
	+ The character  $\rm A$  is binary ~~coded~~ with  <b>010</b> .		+ The character  $\rm A$  is binary encoded with  <b>010</b> .
	+ The character  $\rm B$  is binary ~~coded~~ with  <b>11</b> .		+ The character  $\rm B$  is binary encoded with  <b>11</b> .
	+ The character  $\rm C$  is binary ~~coded~~ with  <b>00110</b> .		+ The character  $\rm C$  is binary encoded with  <b>00110</b> .


Line 91:		Line 91:
	{Which statements are true for arbitrary probabilities?		{Which statements are true for arbitrary probabilities?
	\|type="[]"}		\|type="[]"}
	- $L_{\rm M}$  could be smaller for "Shannon–Fano" than for "Huffman".		- $L_{\rm M}$  could be smaller for  "Shannon–Fano"  than for  "Huffman".
	+ $L_{\rm M}$  could be larger at "Shannon–Fano" than at "Huffman".		+ $L_{\rm M}$  could be larger at  "Shannon–Fano"  than at  "Huffman".
	+ $L_{\rm M}$  could be the same for "Shannon–Fano" and "Huffman".		+ $L_{\rm M}$  could be the same for  "Shannon–Fano"  and  "Huffman".

Guenter at 12:10, 12 August 2021

2021-08-12T12:10:39Z

← Older revision		Revision as of 14:10, 12 August 2021
Line 55:		Line 55:

	Hints:		Hints:
	*The assignment belongs to the chapter  [[Information_Theory/Weitere_Quellencodierverfahren\|~~Other~~ source coding methods]].		*The assignment belongs to the chapter  [[Information_Theory/Weitere_Quellencodierverfahren\|Further source coding methods]].
	*In particular, reference is made to the page  [[Information_Theory/Weitere_Quellencodierverfahren#The_Shannon-Fano_algorithm\|The Shannon-Fano algorithm]].		*In particular, reference is made to the page  [[Information_Theory/Weitere_Quellencodierverfahren#The_Shannon-Fano_algorithm\|The Shannon-Fano algorithm]].
	*To check your results, please refer to the (German language) SWF module  [[Applets:Huffman_Shannon_Fano\|Coding according to Huffman and Shannon/Fano]].		*To check your results, please refer to the (German language) SWF module  [[Applets:Huffman_Shannon_Fano\|Coding according to Huffman and Shannon/Fano]].

Guenter at 12:09, 12 August 2021

2021-08-12T12:09:33Z

Noah at 19:59, 6 August 2021

2021-08-06T19:59:08Z

← Older revision		Revision as of 21:59, 6 August 2021
Line 54:		Line 54:


	''Hints:''		Hints:
	*The assignment belongs to the chapter  [[Information_Theory/Weitere_Quellencodierverfahren\|Other source coding methods]].		*The assignment belongs to the chapter  [[Information_Theory/Weitere_Quellencodierverfahren\|Other source coding methods]].
	*In particular, reference is made to the page  [[Information_Theory/Weitere_Quellencodierverfahren#The_Shannon-Fano_algorithm\|The Shannon-Fano algorithm]].		*In particular, reference is made to the page  [[Information_Theory/Weitere_Quellencodierverfahren#The_Shannon-Fano_algorithm\|The Shannon-Fano algorithm]].

← Older revision		Revision as of 14:09, 12 August 2021
Line 4:		Line 4:

	[[File:P_ID2465__Inf_A_2_10.png \|right\|frame\|Tree diagram of the <br>Shannon-Fano coding]]		[[File:P_ID2465__Inf_A_2_10.png \|right\|frame\|Tree diagram of the <br>Shannon-Fano coding]]
	Another algorithm for entropy coding was given in 1949 by  [https://en.wikipedia.org/wiki/Claude_Shannon Claude Elwood Shannon]  and  [https://en.wikipedia.org/wiki/Robert_Fano Robert Fano] , which is described in the theory section.		Another algorithm for entropy coding was given in 1949 by  [https://en.wikipedia.org/wiki/Claude_Shannon Claude Elwood Shannon]  and  [https://en.wikipedia.org/wiki/Robert_Fano Robert Fano],  which is described in the theory section.

	This special type of source coding will be described here using a simple example for the symbol ~~range~~  $M = 4$  and the following symbol probabilities:		This special type of source coding will be described here using a simple example for the symbol set size  $M = 4$  and the following symbol probabilities:

	:$$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}
Line 17:		Line 17:
	:2. Divide the symbols into two groups of approximately equal probability, here  $\rm C$  and  $\rm BAD$.		:2. Divide the symbols into two groups of approximately equal probability, here  $\rm C$  and  $\rm BAD$.

	:3. The binary symbol  <b>0</b>is assigned to the less probable group,  <b>1</b>  to the other group.		:3. The binary symbol  <b>0</b>  is assigned to the less probable group,  <b>1</b>  to the other group.

	:4. If there is more than one symbol in a group, the algorithm is to be applied recursively.		:4. If there is more than one symbol in a group, the algorithm is to be applied recursively.

	For this example, the following code assignment results (in the tree diagram, a red connection marks a  <b>1</b>  and a blue one a  <b>0</b>:		For this example, the following code assignment results  (in the tree diagram, a red connection marks a  <b>1</b>  and a blue one a  <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>.

	This gives the following for the ~~mean~~ codeword length:		This gives the following for the average codeword length:
	:$$L_{\rm M} = 0.4 \cdot 1 + 0.3 \cdot 2 + (0.2 + 0.1) \cdot 3 = 1.9\,\,{\rm bit/source\:symbol}\hspace{0.05cm}.$$		:$$L_{\rm M} = 0.4 \cdot 1 + 0.3 \cdot 2 + (0.2 + 0.1) \cdot 3 = 1.9\,\,{\rm bit/source\hspace{0.15cm}symbol}\hspace{0.05cm}.$$

	The Huffman algorithm would produce a slightly different code here, but even in this case		The Huffman algorithm would produce a slightly different code here, but even in this case
	*$\rm C$  is ~~coded~~ with one bit,		*$\rm C$  is encoded with one bit,
	*$\rm B$  with two bits and		*$\rm B$  with two bits and
	*$\rm A$ and  $\rm D$  with three bits each.		*$\rm A$ and  $\rm D$  with three bits each.


	This would also result in  $L_{\rm M} = 1.9 \ \rm bit/source\:symbol$.		This would also result in  $L_{\rm M} = 1.9 \ \rm bit/source\hspace{0.15cm}symbol$.

	In this task you are to calculate the Shannon-Fano code for  $M = 8$  and the probabilities		In this task you are to calculate the Shannon-Fano code for  $M = 8$  and the probabilities
	:$$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.$$
	~~determine. ~~ You will see that with these probabilities "Shannon-Fano" will also differ from "Huffman" in terms of efficiency.		You will see that with these probabilities  "Shannon-Fano"  will also differ from  "Huffman"  in terms of efficiency.

	With the Huffman code, the following assignment results with the probabilities at hand:		With the Huffman code, the following assignment results with the probabilities at hand:
Line 57:		Line 57:
	*The assignment belongs to the chapter  [[Information_Theory/Weitere_Quellencodierverfahren\|Other source coding methods]].		*The assignment belongs to the chapter  [[Information_Theory/Weitere_Quellencodierverfahren\|Other source coding methods]].
	*In particular, reference is made to the page  [[Information_Theory/Weitere_Quellencodierverfahren#The_Shannon-Fano_algorithm\|The Shannon-Fano algorithm]].		*In particular, reference is made to the page  [[Information_Theory/Weitere_Quellencodierverfahren#The_Shannon-Fano_algorithm\|The Shannon-Fano algorithm]].
	*To check your results, please refer to the ~~interactive applet~~  [[Applets:~~Huffman-_und_Shannon-Fano-Codierung~~\|Huffman and Shannon-Fano ~~coding~~]].		*To check your results, please refer to the (German language) SWF module  [[Applets:Huffman_Shannon_Fano\|Coding according to Huffman and Shannon/Fano]].


Line 65:		Line 65:

	<quiz display=simple>		<quiz display=simple>
	{What is the ~~mean~~ codeword length  $L_{\rm M}$  for the  <u>Huffman code</u>?		{What is the average codeword length  $L_{\rm M}$  for the  <u>Huffman code</u>?
	\|type="{}"}		\|type="{}"}
	$L_{\rm M}\ = \ $ { 2.54 3% } $\ \rm bit/source\:symbol$		$L_{\rm M}\ = \ $ { 2.54 3% } $\ \rm bit/source\hspace{0.15cm}symbol$


Line 86:		Line 86:
	{What is the average codeword length  $L_{\rm M}$  for  <u>Shannon–Fano code</u>?		{What is the average codeword length  $L_{\rm M}$  for  <u>Shannon–Fano code</u>?
	\|type="{}"}		\|type="{}"}
	$L_{\rm M}\ = \ $ { 2.58 3% } $\ \rm bit/source\:symbol$		$L_{\rm M}\ = \ $ { 2.58 3% } $\ \rm bit/source\hspace{0.15cm}symbol$