Aufgaben:Exercise 2.2Z: Average Code Word Length - Revision history

Hwang at 14:53, 1 November 2022

2022-11-01T14:53:18Z

Javier: Text replacement - "discrete-value" to "discrete"

2021-10-11T08:28:00Z

Text replacement - "discrete-value" to "discrete"

Javier: Text replacement - "code symbol sequence" to "encoded sequence"

2021-08-16T12:08:08Z

Text replacement - "code symbol sequence" to "encoded sequence"

Guenter at 12:09, 10 August 2021

2021-08-10T12:09:17Z

Noah at 20:29, 6 August 2021

2021-08-06T20:29:08Z

Guenter at 15:13, 7 July 2021

2021-07-07T15:13:17Z

Guenter at 15:04, 7 July 2021

2021-07-07T15:04:46Z

Noah at 20:43, 2 July 2021

2021-07-02T20:43:34Z

Show changes

Guenter at 15:05, 26 June 2021

2021-06-26T15:05:45Z

Guenter: Guenter moved page Aufgaben:Aufgabe 2.2Z: Mittlere Codewortlänge to Aufgaben:Exercise 2.2Z: Average Code Word Length

2021-06-26T15:03:45Z

Guenter moved page Aufgabe 2.2Z: Mittlere Codewortlänge to Exercise 2.2Z: Average Code Word Length

@@ Line 18: / Line 18: @@
-A measure for the quality of a compression method is the average codeword length&nbsp; $L_{\rm M}$&nbsp;  with the additional unit&nbsp; "bit/source symbol".
+A measure for the quality of a compression method is the average code word length&nbsp; $L_{\rm M}$&nbsp;  with the additional unit&nbsp; "bit/source symbol".
@@ Line 37: / Line 37: @@
 <quiz display=simple>
-{Determine the average codeword length&nbsp; $L_{\rm M}$&nbsp; for&nbsp; $p_{\rm A} = p_{\rm B} = p_{\rm C} = p_{\rm D} =  1/4$.
+{Determine the average code word length&nbsp; $L_{\rm M}$&nbsp; for&nbsp; $p_{\rm A} = p_{\rm B} = p_{\rm C} = p_{\rm D} =  1/4$.
 |type="{}"}
 $\text{C1:}\ \ L_{\rm M} \ = \ $  { 2 1% } $\ \rm bit/source\hspace{0.15cm} symbol$
@@ Line 53: / Line 53: @@
 {How can you recognise prefix-free codes?
 |type="[]"}
-+ No codeword is the beginning of another codeword.
++ No code word is the beginning of another code word.
-- All codewords have the same length.
+- All code words have the same length.
@@ Line 75: / Line 75: @@
 ===Solution===
 {{ML-Kopf}}
-'''(1)'''&nbsp; The average codeword length is generally given by
+'''(1)'''&nbsp; The average code word length is generally given by
 :$$L_{\rm M} = p_{\rm A} \cdot L_{\rm A} + p_{\rm B} \cdot L_{\rm B}+ p_{\rm C} \cdot L_{\rm C} + p_{\rm D} \cdot L_{\rm D}
 \hspace{0.05cm}.$$
@@ Line 87: / Line 87: @@
-'''(2)'''&nbsp; With the code table&nbsp; $\text{C1}$&nbsp;, the average codeword length&nbsp; $L_{\rm M} \hspace{0.15cm}\underline{= 2}\ \rm bit/source\hspace{0.15cm} symbol$&nbsp; is always obtained, independent of the symbol probabilities.
+'''(2)'''&nbsp; With the code table&nbsp; $\text{C1}$&nbsp;, the average code word length&nbsp; $L_{\rm M} \hspace{0.15cm}\underline{= 2}\ \rm bit/source\hspace{0.15cm} symbol$&nbsp; is always obtained, independent of the symbol probabilities.
 For the other two codes one obtains:
@@ Line 96: / Line 96: @@
 From the example you can see the principle:
 *Probable symbols are represented by a few binary symbols, improbable ones by more.
-*In the case of equally probable symbols, it is best to choose the same codeword lengths.
+*In the case of equally probable symbols, it is best to choose the same code word lengths.
@@ Line 102: / Line 102: @@
 '''(3)'''&nbsp; <u>Solution suggestion 1</u> is correct:
-*The code&nbsp; $\text{C1}$&nbsp; with uniform length of all codewords is prefix-free,
+*The code&nbsp; $\text{C1}$&nbsp; with uniform length of all code words is prefix-free,
 *but other codes can also be prefix-free, for example the codes&nbsp;  $\text{C2}$&nbsp; and&nbsp;  $\text{C3}$.

@@ Line 6: / Line 6: @@
 The aim of data compression is to represent the message of a source with as few binary characters as possible.
-We consider here a discrete-value message source with the symbol set&nbsp; $\rm \{ A, \ B, \ C, \ D\}$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp; symbol set size&nbsp; $M = 4$&nbsp; and the symbol probabilities
+We consider here a discrete message source with the symbol set&nbsp; $\rm \{ A, \ B, \ C, \ D\}$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp; symbol set size&nbsp; $M = 4$&nbsp; and the symbol probabilities
 :*$p_{\rm A} = p_{\rm B} = p_{\rm C} = p_{\rm D} =  1/4$&nbsp; $($subtask&nbsp; $1)$,
 :* $p_{\rm A} = 1/2, \,  p_{\rm B} = 1/4, \, p_{\rm C} = p_{\rm D} =  1/8$&nbsp;  $($subtask&nbsp; $2$&nbsp; to&nbsp; $5)$.

@@ Line 57: / Line 57: @@
-{For the special source symbol sequence&nbsp; $\rm ADBDCBCBADCA$&nbsp;, the code symbol sequence&nbsp; $\rm 001101111001100100111000$&nbsp; results.
+{For the special source symbol sequence&nbsp; $\rm ADBDCBCBADCA$&nbsp;, the encoded sequence&nbsp; $\rm 001101111001100100111000$&nbsp; results.
 <br>Which code was used?
 |type="()"}
@@ Line 115: / Line 115: @@
 '''(5)'''&nbsp; <u>Solution suggestion 2</u> is correct.
-The first suggested solution gives the source symbol sequence for code&nbsp; $\text{C2}$&nbsp; if the code symbol sequence would be &nbsp; "$\rm 001101111001100100111000$".
+The first suggested solution gives the source symbol sequence for code&nbsp; $\text{C2}$&nbsp; if the encoded sequence would be &nbsp; "$\rm 001101111001100100111000$".
 {{ML-Fuß}}

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

−	{{quiz-Header\|Buchseite=~~Informationstheorie~~/~~Allgemeine Beschreibung~~	+	{{quiz-Header\|Buchseite=Information_Theory/General_Description
	}}		}}

← Older revision		Revision as of 20:29, 6 August 2021
Line 28:		Line 28:


−	''Hint:''	+	Hint:
	*The exercise belongs to the chapter  [[Information_Theory/Allgemeine_Beschreibung\|General Description of Source Coding]].		*The exercise belongs to the chapter  [[Information_Theory/Allgemeine_Beschreibung\|General Description of Source Coding]].

@@ Line 78: / Line 78: @@
 :$$L_{\rm M} = p_{\rm A} \cdot L_{\rm A} + p_{\rm B} \cdot L_{\rm B}+ p_{\rm C} \cdot L_{\rm C} + p_{\rm D} \cdot L_{\rm D}
 \hspace{0.05cm}.$$
-If the four source symbols are equally probable&nbsp; $($all probabilities exactly $1/4)$, then for this we can also write:
+If the four source symbols are equally probable&nbsp; $($all probabilities exactly&nbsp; $1/4)$, then for this we can also write:
 :$$L_{\rm M} = 1/4 \cdot ( L_{\rm A} + L_{\rm B}+ L_{\rm C} + L_{\rm D})
 \hspace{0.05cm}.$$
-* $\text{Code C1:}$&nbsp;&nbsp;&nbsp; $L_{\rm M} \hspace{0.15cm}\underline{= 2.00}\ \rm bit/source symbol$,
+* $\text{Code C1:}$&nbsp;&nbsp;&nbsp; $L_{\rm M} \hspace{0.15cm}\underline{= 2.00}\ \rm bit/source\hspace{0.15cm} symbol$,
-* $\text{Code C2:}$&nbsp;&nbsp;&nbsp; $L_{\rm M} \hspace{0.15cm}\underline{= 2.25}\ \rm bit/source symbol$
+* $\text{Code C2:}$&nbsp;&nbsp;&nbsp; $L_{\rm M} \hspace{0.15cm}\underline{= 2.25}\ \rm bit/source\hspace{0.15cm} symbol$
-* $\text{Code C3:}$&nbsp;&nbsp;&nbsp; $L_{\rm M} \hspace{0.15cm}\underline{= 2.25}\ \rm bit/source symbol$.
+* $\text{Code C3:}$&nbsp;&nbsp;&nbsp; $L_{\rm M} \hspace{0.15cm}\underline{= 2.25}\ \rm bit/source\hspace{0.15cm} symbol$.
-'''(2)'''&nbsp; With the code table&nbsp; $\text{C1}$&nbsp;, the average code word length&nbsp; $L_{\rm M} \hspace{0.15cm}\underline{= 2}\ \rm bit/source symbol$ is always obtained, independent of the symbol probabilities.
+'''(2)'''&nbsp; With the code table&nbsp; $\text{C1}$&nbsp;, the average codeword length&nbsp; $L_{\rm M} \hspace{0.15cm}\underline{= 2}\ \rm bit/source\hspace{0.15cm} symbol$&nbsp; is always obtained, independent of the symbol probabilities.
 For the other two codes one obtains:
-* $\text{Code C2:}$&nbsp;&nbsp;&nbsp; $L_{\rm M} = 1/2 \cdot 1 + 1/4 \cdot 2 + 1/8 \cdot 3 + 1/8 \cdot 3 \hspace{0.15cm}\underline{= 1.75}\ \rm bit/source symbol$,
+* $\text{Code C2:}$&nbsp;&nbsp;&nbsp; $L_{\rm M} = 1/2 \cdot 1 + 1/4 \cdot 2 + 1/8 \cdot 3 + 1/8 \cdot 3 \hspace{0.15cm}\underline{= 1.75}\ \rm bit/source\hspace{0.15cm} symbol$,
-* $\text{Code C3:}$&nbsp;&nbsp;&nbsp; $L_{\rm M} = 1/2 \cdot 3 + 1/4 \cdot 2 + 1/8 \cdot 1 + 1/8 \cdot 3 \hspace{0.15cm}\underline{= 2.50}\ \rm bit/source symbol$.
+* $\text{Code C3:}$&nbsp;&nbsp;&nbsp; $L_{\rm M} = 1/2 \cdot 3 + 1/4 \cdot 2 + 1/8 \cdot 1 + 1/8 \cdot 3 \hspace{0.15cm}\underline{= 2.50}\ \rm bit/source\hspace{0.15cm} symbol$.
-You can see the principle from the example:
+From the example you can see the principle:
 *Probable symbols are represented by a few binary symbols, improbable ones by more.
 *In the case of equally probable symbols, it is best to choose the same codeword lengths.
@@ Line 108: / Line 108: @@
 '''(4)'''&nbsp; <u>Solution suggestion 1</u> is correct:
-*Already from "00" at the beginning one can see that the code&nbsp; $\text{C2}$&nbsp; is out of the question here, because otherwise the source symbol sequence would have to begin with "AA".
+*Already from&nbsp; "00"&nbsp; at the beginning one can see that the code&nbsp; $\text{C2}$&nbsp; is out of the question here, <br>because otherwise the source symbol sequence would have to begin with&nbsp; "AA".
 *In fact, the code&nbsp; $\text{C1}$&nbsp; was used.
-'''(5)'''&nbsp; <u>Solution suggestion 2</u> is correct:
+'''(5)'''&nbsp; <u>Solution suggestion 2</u> is correct.
-*The first suggested solution, on the other hand, gives the source symbol sequence for code&nbsp; $\text{C2}$&nbsp; if the code symbol sequence would be &nbsp; $\rm 001101111001100100111000$&nbsp;.
 {{ML-Fuß}}

@@ Line 3: / Line 3: @@
 }}
-[[File:P_ID2417__Inf_Z_2_2.png|right|frame|Source coding table]]
+[[File:P_ID2417__Inf_Z_2_2.png|right|frame|Three source coding tables]]
 The aim of data compression is to represent the message of a source with as few binary characters as possible.
-We consider here a discrete-value message source with the symbol set&nbsp; $\rm \{ A, \ B, \ C, \ D\}$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp; symbol range&nbsp; $M = 4$&nbsp; and the probabilities of occurrence
+We consider here a discrete-value message source with the symbol set&nbsp; $\rm \{ A, \ B, \ C, \ D\}$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp; symbol set size&nbsp; $M = 4$&nbsp; and the symbol probabilities
-:*$p_{\rm A} = p_{\rm B} = p_{\rm C} = p_{\rm D} =  1/4$&nbsp; (subtask 1),
+:*$p_{\rm A} = p_{\rm B} = p_{\rm C} = p_{\rm D} =  1/4$&nbsp; $($subtask&nbsp; $1)$,
-:* $p_{\rm A} = 1/2, \,  p_{\rm B} = 1/4, \, p_{\rm C} = p_{\rm D} =  1/8$&nbsp;  (from subtask 2).
+:* $p_{\rm A} = 1/2, \,  p_{\rm B} = 1/4, \, p_{\rm C} = p_{\rm D} =  1/8$&nbsp;  $($subtask&nbsp; $2$&nbsp; to&nbsp; $5)$.
-It is assumed that there are no statistical ties between the individual source symbols.
+It is assumed that there are no statistical Dependencies between the individual source symbols.
 Three assignments are given. To be noted:
 * Each of these binary codes&nbsp; $\rm C1$,&nbsp; $\rm C2$&nbsp; and&nbsp; $\rm C3$&nbsp; is designed for a specific source statistic.
 * All codes are prefix-free and thus immediately decodable without further specification.
@@ Line 27: / Line 29: @@
 ''Hint:''
-*The task belongs to the chapter&nbsp; [[Information_Theory/Allgemeine_Beschreibung|General description of source coding]].
+*The exercise belongs to the chapter&nbsp; [[Information_Theory/Allgemeine_Beschreibung|General Description of Source Coding]].
@@ Line 34: / Line 37: @@
 <quiz display=simple>
-{Determine the mean codeword length&nbsp; $L_{\rm M}$&nbsp; for&nbsp; $p_{\rm A} = p_{\rm B} = p_{\rm C} = p_{\rm D} =  1/4$.
+{Determine the average codeword length&nbsp; $L_{\rm M}$&nbsp; for&nbsp; $p_{\rm A} = p_{\rm B} = p_{\rm C} = p_{\rm D} =  1/4$.
 |type="{}"}
-$\text{C1:}\ \ L_{\rm M} \ = \ $  { 2 1% } $\ \rm bit/source symbol$
+$\text{C1:}\ \ L_{\rm M} \ = \ $  { 2 1% } $\ \rm bit/source\hspace{0.15cm} symbol$
-$\text{C2:}\ \ L_{\rm M} \ =  \ $  { 2.25 1% } $\ \rm bit/source symbol$
+$\text{C2:}\ \ L_{\rm M} \ =  \ $  { 2.25 1% } $\ \rm bit/source\hspace{0.15cm} symbol$
-$\text{C3:}\ \ L_{\rm M} \ =  \ $  { 2.25 1% } $\ \rm bit/source symbol$
+$\text{C3:}\ \ L_{\rm M} \ =  \ $  { 2.25 1% } $\ \rm bit/source\hspace{0.15cm} symbol$
 {Which values result for&nbsp; $p_{\rm A} = 1/2, \,  p_{\rm B} = 1/4, \, p_{\rm C} = p_{\rm D} =  1/8$?
 |type="{}"}
-$\text{C1:}\ \ L_{\rm M} \ =  \ $  { 2 1% } $\ \rm bit/source symbol$
+$\text{C1:}\ \ L_{\rm M} \ =  \ $  { 2 1% } $\ \rm bit/source\hspace{0.15cm} symbol$
-$\text{C2:}\ \ L_{\rm M} \ =  \ $  { 1.75 1% } $\ \rm bit/source symbol$
+$\text{C2:}\ \ L_{\rm M} \ =  \ $  { 1.75 1% } $\ \rm bit/source\hspace{0.15cm} symbol$
-$\text{C3:}\ \ L_{\rm M} \ =  \ $  { 2.5 1% } $\ \rm bit/source symbol$
+$\text{C3:}\ \ L_{\rm M} \ =  \ $  { 2.5 1% } $\ \rm bit/source\hspace{0.15cm} symbol$
 {How can you recognise prefix-free codes?
 |type="[]"}
-+ No code word is the beginning of another code word.
++ No codeword is the beginning of another codeword.
 - All codewords have the same length.
-{For the special source symbol sequence&nbsp; $\rm ADBDCBCBADCA$&nbsp;, the code symbol sequence&nbsp; $\rm 001101111001100100111000$ results.
+{For the special source symbol sequence&nbsp; $\rm ADBDCBCBADCA$&nbsp;, the code symbol sequence&nbsp; $\rm 001101111001100100111000$&nbsp; results.
 <br>Which code was used?
 |type="()"}
-+ the code&nbsp;  $\rm C1$,
++ The code&nbsp;  $\rm C1$,
 - the code&nbsp; $\rm C2$.
-{After coding with&nbsp; $\rm C3$&nbsp;, you get&nbsp; $\rm 001101111001100100111000$.&nbsp; What is the corresponding source symbol sequence?
+{After coding with&nbsp; $\rm C3$,&nbsp; you get&nbsp; $\rm 001101111001100100111000$.&nbsp; What is the corresponding source symbol sequence?
 |type="()"}
 - $\rm AACDBACABADAAA$ ...

← Older revision		Revision as of 15:05, 26 June 2021
Line 116:		Line 116:


−	[[Category:Information Theory: Exercises\|^2.1 ~~Allgemeine Beschreibung~~^]]	+	[[Category:Information Theory: Exercises\|^2.1 General Description^]]