Aufgaben:Exercise 2.6Z: Again on the Huffman Code - Revision history

Hwang at 14:55, 1 November 2022

2022-11-01T14:55:42Z

Guenter at 14:07, 13 August 2021

2021-08-13T14:07:20Z

Guenter at 14:46, 10 August 2021

2021-08-10T14:46:46Z

Guenter at 14:37, 10 August 2021

2021-08-10T14:37:43Z

Guenter at 14:36, 10 August 2021

2021-08-10T14:36:25Z

Guenter at 12:15, 10 August 2021

2021-08-10T12:15:04Z

Noah at 20:03, 6 August 2021

2021-08-06T20:03:17Z

Noah at 19:50, 4 August 2021

2021-08-04T19:50:04Z

Noah at 19:48, 4 August 2021

2021-08-04T19:48:51Z

Noah at 19:48, 4 August 2021

2021-08-04T19:48:24Z

@@ Line 7: / Line 7: @@
 * The resulting binary code is prefix-free and thus easily (and immediately) decodable.
-* With a memoryless source, the code leads to the smallest possible average codeword length&nbsp; $L_{\rm M}$.
+* With a memoryless source, the code leads to the smallest possible average code word length&nbsp; $L_{\rm M}$.
 * However, $L_{\rm M}$&nbsp; is never smaller than the source entropy&nbsp; $H$.
 * These two quantities can be calculated from the&nbsp; $M$&nbsp; symbol probabilities alone.
@@ Line 40: / Line 40: @@
-{How are the average codeword length&nbsp; $L_{\rm M}$&nbsp; and the entropy&nbsp; $H$&nbsp; related for the given probabilities?
+{How are the average code word length&nbsp; $L_{\rm M}$&nbsp; and the entropy&nbsp; $H$&nbsp; related for the given probabilities?
 |type="()"}
 - $L_{\rm M} < H$,
@@ Line 56: / Line 56: @@
-{The probabilities calculated in subtask&nbsp; '''(3)'''&nbsp; still apply. <br>However, the average codeword length is now determined for a sequence of length&nbsp; $N = 40$&nbsp; &nbsp;&#8658;&nbsp; $L_{\rm M}\hspace{0.03cm}'$. What is possible?
+{The probabilities calculated in subtask&nbsp; '''(3)'''&nbsp; still apply. <br>However, the average code word length is now determined for a sequence of length&nbsp; $N = 40$&nbsp; &nbsp;&#8658;&nbsp; $L_{\rm M}\hspace{0.03cm}'$. What is possible?
 |type="[]"}
 + $L_{\rm M}\hspace{0.01cm}' < L_{\rm M}$,
@@ Line 96: / Line 96: @@
 '''(3)'''&nbsp; $\rm A$,&nbsp; $\rm B$&nbsp; and&nbsp; $\rm C$&nbsp; are represented by two bits in&nbsp; $\text{Code 1}$&nbsp;,&nbsp; $\rm E$&nbsp; and&nbsp; $\rm F$&nbsp; by three bits.&nbsp; Thus one obtains for
-* the average codeword length
+* the average code word length
 :$$L_{\rm M} =   p_{\rm A}\cdot 2 + p_{\rm B}\cdot 2 + p_{\rm C}\cdot 2 + p_{\rm D}\cdot 3 + p_{\rm E}\cdot 3
 \hspace{0.05cm},$$
@@ Line 107: / Line 107: @@
 \Rightarrow\hspace{0.3cm} L_{\rm M} = H = 2.25\,{\rm bit/source \:symbol} \hspace{0.05cm}.$$
 It can be seen:
-*With these&nbsp; "more favourable"&nbsp; probabilities, there is even a larger average codeword length than with the&nbsp; "less favourable"&nbsp; ones.
+*With these&nbsp; "more favourable"&nbsp; probabilities, there is even a larger average code word length than with the&nbsp; "less favourable"&nbsp; ones.
 *The equality&nbsp; $(L_{\rm M} = H)$&nbsp; is therefore solely due to the now larger source entropy.
@@ Line 126: / Line 126: @@
 *&nbsp; $\text{Code 2}$&nbsp; is not a Huffman code, since such a code would always have to be prefix-free. <br>However, the prefix freedom is not given here, since&nbsp; <b>1</b>&nbsp; is the beginning of the code word&nbsp; <b>10</b>&nbsp;.
-*&nbsp; $\text{Code 3}$&nbsp; is also not a Huffman code, since it has an average codeword length that is&nbsp;  $p_{\rm C}$&nbsp; longer than required&nbsp; $($see $\text{Code 1})$. It is not optimal&nbsp; <br>There are no symbol probabilities&nbsp; $p_{\rm A}$, ... ,&nbsp; $p_{\rm E}$, that would justify coding the symbol&nbsp; $\rm C$&nbsp; with&nbsp; <b>010</b>&nbsp; instead of&nbsp; <b>01</b>&nbsp;.
+*&nbsp; $\text{Code 3}$&nbsp; is also not a Huffman code, since it has an average code word length that is&nbsp;  $p_{\rm C}$&nbsp; longer than required&nbsp; $($see $\text{Code 1})$. It is not optimal&nbsp; <br>There are no symbol probabilities&nbsp; $p_{\rm A}$, ... ,&nbsp; $p_{\rm E}$, that would justify coding the symbol&nbsp; $\rm C$&nbsp; with&nbsp; <b>010</b>&nbsp; instead of&nbsp; <b>01</b>&nbsp;.
 {{ML-Fuß}}

@@ Line 75: / Line 75: @@
 ===Solution===
 {{ML-Kopf}}
-[[File:Inf_Z_2_6a_version2.png|right|frame|Huffman tree diagrams for subtasks&nbsp; '''(1)'''&nbsp; and&nbsp; '''(3)''']]
+[[File:EN_Inf_Z_2_6a_v2.png|right|frame|Huffman tree diagrams for subtasks&nbsp; '''(1)'''&nbsp; and&nbsp; '''(3)''']]
 '''(1)'''&nbsp;<u>Solution suggestion 1</u> is correct.
 *The diagram shows the construction of the Huffman code by means of a tree diagram.

@@ Line 94: / Line 94: @@
-'''(3)'''&nbsp; $\rm A$,&nbsp; $\rm B$&nbsp; and&nbsp; $\rm C$&nbsp; are represented by two bits in&nbsp; $\text{code 1}$&nbsp;,&nbsp; $\rm E$&nbsp; and&nbsp; $\rm F$&nbsp; by three bits.&nbsp; Thus one obtains for
+'''(3)'''&nbsp; $\rm A$,&nbsp; $\rm B$&nbsp; and&nbsp; $\rm C$&nbsp; are represented by two bits in&nbsp; $\text{Code 1}$&nbsp;,&nbsp; $\rm E$&nbsp; and&nbsp; $\rm F$&nbsp; by three bits.&nbsp; Thus one obtains for
 * the average codeword length
@@ Line 107: / Line 107: @@
 \Rightarrow\hspace{0.3cm} L_{\rm M} = H = 2.25\,{\rm bit/source \:symbol} \hspace{0.05cm}.$$
 It can be seen:
-*With these "more favourable" probabilities, there is even a larger mean codeword length than with the "less favourable" ones.
+*With these&nbsp; "more favourable"&nbsp; probabilities, there is even a larger average codeword length than with the&nbsp; "less favourable"&nbsp; ones.
 *The equality&nbsp; $(L_{\rm M} = H)$&nbsp; is therefore solely due to the now larger source entropy.
@@ Line 126: / Line 126: @@
 *&nbsp; $\text{Code 2}$&nbsp; is not a Huffman code, since such a code would always have to be prefix-free. <br>However, the prefix freedom is not given here, since&nbsp; <b>1</b>&nbsp; is the beginning of the code word&nbsp; <b>10</b>&nbsp;.
-*&nbsp; $\text{Code 3}$&nbsp; is also not a Huffman code, since it has an average codeword length that is&nbsp;  $p_{\rm C}$&nbsp; longer than required&nbsp; $($see $\text{code 1})$. It is not optimal&nbsp; <br>There are no symbol probabilities&nbsp; $p_{\rm A}$, ... ,&nbsp; $p_{\rm E}$, that would justify coding the symbol&nbsp; $\rm C$&nbsp; with&nbsp; <b>010</b>&nbsp; instead of&nbsp; <b>01</b>&nbsp;.
+*&nbsp; $\text{Code 3}$&nbsp; is also not a Huffman code, since it has an average codeword length that is&nbsp;  $p_{\rm C}$&nbsp; longer than required&nbsp; $($see $\text{Code 1})$. It is not optimal&nbsp; <br>There are no symbol probabilities&nbsp; $p_{\rm A}$, ... ,&nbsp; $p_{\rm E}$, that would justify coding the symbol&nbsp; $\rm C$&nbsp; with&nbsp; <b>010</b>&nbsp; instead of&nbsp; <b>01</b>&nbsp;.
 {{ML-Fuß}}

@@ Line 25: / Line 25: @@
 <u>Hints:</u>
 *The exercise belongs to the chapter&nbsp; [[Information_Theory/Entropiecodierung_nach_Huffman|Entropy Coding according to Huffman]].
-*Further information on the Huffman algorithm can also be found in the information sheet for&nbsp; [[Aufgaben:2.6_Zur_Huffman-Codierung|Exercise 2.6]].
+*Further information on the Huffman algorithm can also be found in the information sheet for&nbsp; [[Aufgaben:Exercise_2.6:_About_the_Huffman_Coding|Exercise 2.6]].
 *To check your results, please refer to the (German language) SWF module&nbsp; [[Applets:Huffman_Shannon_Fano|Coding according to Huffman and Shannon/Fano]].

@@ Line 7: / Line 7: @@
 * The resulting binary code is prefix-free and thus easily (and immediately) decodable.
+* With a memoryless source, the code leads to the smallest possible average codeword length&nbsp; $L_{\rm M}$.
 * However, $L_{\rm M}$&nbsp; is never smaller than the source entropy&nbsp; $H$.
 * These two quantities can be calculated from the&nbsp; $M$&nbsp; symbol probabilities alone.
-For this exercise, we assume a memoryless source with the symbol range&nbsp; $M = 5$&nbsp; and the alphabet
+For this exercise, we assume a memoryless source with the symbol set size&nbsp; $M = 5$&nbsp; and the alphabet
 :$$\{ {\rm A},\ {\rm B},\ {\rm C},\ {\rm D},\ {\rm E} \}.$$
-In the above diagram, three codes are given.nbsp; You are to decide which of these codes were (or could be) created by applying the Huffman algorithm.
+In the above diagram, three binary codes are given.&nbsp; You are to decide which of these codes were (or could be) created by applying the Huffman algorithm.
@@ Line 25: / Line 23: @@
-Hints:
+<u>Hints:</u>
 *The exercise belongs to the chapter&nbsp; [[Information_Theory/Entropiecodierung_nach_Huffman|Entropy Coding according to Huffman]].
 *Further information on the Huffman algorithm can also be found in the information sheet for&nbsp; [[Aufgaben:2.6_Zur_Huffman-Codierung|Exercise 2.6]].
-*To check your results, please refer to the interaction module&nbsp; [[Applets:Huffman-_und_Shannon-Fano-Codierung|Shannon&ndash;Fano&ndash; and Huffman&ndash;coding]].
+*To check your results, please refer to the (German language) SWF module&nbsp; [[Applets:Huffman_Shannon_Fano|Coding according to Huffman and Shannon/Fano]].
@@ Line 35: / Line 33: @@
 <quiz display=simple>
-{Which codes could have arisen according to Huffman for&nbsp; $p_{\rm A} = p_{\rm B} = p_{\rm C}  = 0.3$&nbsp; and&nbsp; $p_{\rm D} = p_{\rm E}  = 0.05$&nbsp; entstanden sein?
+{Which codes could have arisen according to Huffman for&nbsp; $p_{\rm A} = p_{\rm B} = p_{\rm C}  = 0.3$&nbsp; and&nbsp; $p_{\rm D} = p_{\rm E}  = 0.05$?
 |type="[]"}
 + $\text{Code 1}$,
@@ Line 42: / Line 40: @@
-{How are the mean codeword length&nbsp; $L_{\rm M}$&nbsp; and the entropy&nbsp; $H$&nbsp; related for the given probabilities?
+{How are the average codeword length&nbsp; $L_{\rm M}$&nbsp; and the entropy&nbsp; $H$&nbsp; related for the given probabilities?
 |type="()"}
 - $L_{\rm M} < H$,
@@ Line 49: / Line 47: @@
-{Consider&nbsp; $\text{code 1}$.&nbsp; With what symbol probabilities would&nbsp; $L_{\rm M} = H$&nbsp; hold?
+{Consider&nbsp; $\text{Code 1}$.&nbsp; With what symbol probabilities would&nbsp; $L_{\rm M} = H$&nbsp; hold?
 |type="{}"}
 $\ p_{\rm A} \ = \ $ { 0.25 3% }
@@ Line 58: / Line 56: @@
-{The probabilities calculated in subtask&nbsp; '''(3)'''&nbsp; still apply. <br>However, the mean codeword length is now determined for a sequence of length&nbsp; $N = 40$&nbsp; &nbsp;&#8658;&nbsp; $L_{\rm M}\hspace{0.03cm}'$. What is possible?
+{The probabilities calculated in subtask&nbsp; '''(3)'''&nbsp; still apply. <br>However, the average codeword length is now determined for a sequence of length&nbsp; $N = 40$&nbsp; &nbsp;&#8658;&nbsp; $L_{\rm M}\hspace{0.03cm}'$. What is possible?
 |type="[]"}
 + $L_{\rm M}\hspace{0.01cm}' < L_{\rm M}$,
@@ Line 126: / Line 124: @@
 *&nbsp; $\text{Code 1}$&nbsp; is a Huffman code, as has already been shown in the previous subtasks. <br>This is not true for all symbol probabilities, but at least for the parameter sets according to subtasks&nbsp; '''(1)'''&nbsp; and&nbsp; '''(3)'''.
-*&nbsp; $\text{Code 2}$&nbsp; is not a Huffman code, since such a code would always have to be prefix-free. <br>However, the prefix freedom is not given here, since&nbsp; <b>0</b>&nbsp; is the beginning of the code word&nbsp; <b>01</b>&nbsp;.
+*&nbsp; $\text{Code 2}$&nbsp; is not a Huffman code, since such a code would always have to be prefix-free. <br>However, the prefix freedom is not given here, since&nbsp; <b>1</b>&nbsp; is the beginning of the code word&nbsp; <b>10</b>&nbsp;.
 *&nbsp; $\text{Code 3}$&nbsp; is also not a Huffman code, since it has an average codeword length that is&nbsp;  $p_{\rm C}$&nbsp; longer than required&nbsp; $($see $\text{code 1})$. It is not optimal&nbsp; <br>There are no symbol probabilities&nbsp; $p_{\rm A}$, ... ,&nbsp; $p_{\rm E}$, that would justify coding the symbol&nbsp; $\rm C$&nbsp; with&nbsp; <b>010</b>&nbsp; instead of&nbsp; <b>01</b>&nbsp;.

← Older revision		Revision as of 12:15, 10 August 2021
Line 1:		Line 1:

−	{{quiz-Header\|Buchseite=~~Informationstheorie~~/~~Entropiecodierung nach Huffman~~	+	{{quiz-Header\|Buchseite=Information_Theory/Entropy_Coding_According_to_Huffman
	}}		}}

@@ Line 117: / Line 117: @@
 :$$\rm EBDCCBDABEBABCCCCCBCAABECAACCBAABBBCDCAB.$$
-*This results in&nbsp; $L_{\rm M}\hspace{0.01cm}' = ( 34 \cdot 2 + 6 \cdot 3)/50  = 2.15$&nbsp; bit/source symbol,  i.e. a smaller value than for the unlimited sequence&nbsp; $(L_{\rm M} = 2.25$ bit/source \:symbol$)$.
+*This results in&nbsp; $L_{\rm M}\hspace{0.01cm}' = ( 34 \cdot 2 + 6 \cdot 3)/50  = 2.15$&nbsp; bit/source symbol,  i.e. a smaller value than for the unlimited sequence&nbsp; $(L_{\rm M} = 2.25$ bit/source symbol$)$.
 *However, with a different starting value of the random generator,&nbsp; $(L_{\rm M}\hspace{0.03cm}' \ge L_{\rm M})$&nbsp; is also possible.
 *This means: &nbsp; <u>All &nbsp;statements</u> are correct.

@@ Line 86: / Line 86: @@
 <br clear=all>
 '''(2)'''&nbsp;<u>Proposed solution 3</u> is correct, as the following calculation also shows:
-:$$L_{\rm M} \hspace{0.2cm} =  \hspace{0.2cm}  (0.3 + 0.3 + 0.3) \cdot 2 + (0.05 + 0.05) \cdot 3  = 2.1\,{\rm bit/source symbol}\hspace{0.05cm},$$
+:$$L_{\rm M} \hspace{0.2cm} =  \hspace{0.2cm}  (0.3 + 0.3 + 0.3) \cdot 2 + (0.05 + 0.05) \cdot 3  = 2.1\,{\rm bit/source \:symbol}\hspace{0.05cm},$$
 :$$H \hspace{0.2cm} =  \hspace{0.2cm}  3 \cdot 0.3 \cdot {\rm log_2}\hspace{0.15cm}(1/0.3) + 2 \cdot 0.05 \cdot {\rm log_2}\hspace{0.15cm}(1/0.05)
-\approx 2.0\,{\rm bit/source symbol}\hspace{0.05cm}.$$
+\approx 2.0\,{\rm bit/source \:symbol}\hspace{0.05cm}.$$
 *According to the source coding theorem, &nbsp; $L_{\rm M} \ge H$ always holds.
@@ Line 107: / Line 107: @@
 By comparing all the terms, we arrive at the result:
 :$$p_{\rm A}= p_{\rm B}=  p_{\rm C}\hspace{0.15cm}\underline{= 0.25} \hspace{0.05cm}, \hspace{0.2cm}p_{\rm D}= p_{\rm E}\hspace{0.15cm}\underline{= 0.125}\hspace{0.3cm}
-\Rightarrow\hspace{0.3cm} L_{\rm M} = H = 2.25\,{\rm bit/source symbol} \hspace{0.05cm}.$$
+\Rightarrow\hspace{0.3cm} L_{\rm M} = H = 2.25\,{\rm bit/source \:symbol} \hspace{0.05cm}.$$
 It can be seen:
 *With these "more favourable" probabilities, there is even a larger mean codeword length than with the "less favourable" ones.
@@ Line 117: / Line 117: @@
 :$$\rm EBDCCBDABEBABCCCCCBCAABECAACCBAABBBCDCAB.$$
-*This results in&nbsp; $L_{\rm M}\hspace{0.01cm}' = ( 34 \cdot 2 + 6 \cdot 3)/50  = 2.15$&nbsp; bit/source symbol,  i.e. a smaller value than for the unlimited sequence&nbsp; $(L_{\rm M} = 2.25$ bit/source symbol$)$.
+*This results in&nbsp; $L_{\rm M}\hspace{0.01cm}' = ( 34 \cdot 2 + 6 \cdot 3)/50  = 2.15$&nbsp; bit/source \:symbol,  i.e. a smaller value than for the unlimited sequence&nbsp; $(L_{\rm M} = 2.25$ bit/source \:symbol$)$.
 *However, with a different starting value of the random generator,&nbsp; $(L_{\rm M}\hspace{0.03cm}' \ge L_{\rm M})$&nbsp; is also possible.
 *This means: &nbsp; <u>All &nbsp;statements</u> are correct.