Aufgaben:Exercise 2.6: About the Huffman Coding - Revision history

Hwang at 14:54, 1 November 2022

2022-11-01T14:54:57Z

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

2021-08-16T12:07:57Z

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

Guenter at 14:05, 10 August 2021

2021-08-10T14:05:22Z

Guenter at 13:49, 10 August 2021

2021-08-10T13:49:25Z

Guenter at 13:45, 10 August 2021

2021-08-10T13:45:11Z

Guenter at 13:34, 10 August 2021

2021-08-10T13:34:06Z

Guenter at 12:14, 10 August 2021

2021-08-10T12:14:34Z

Noah at 20:03, 6 August 2021

2021-08-06T20:03:45Z

Noah at 19:52, 4 August 2021

2021-08-04T19:52:48Z

Noah at 20:39, 2 August 2021

2021-08-02T20:39:18Z

@@ Line 7: / Line 7: @@
 :$$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}.$$
-If the symbols are equally probable, i.e.&nbsp; $p_{\rm A} =  p_{\rm B} =$ ... $ = p_{\rm H} = 1/M$ &nbsp; then source coding makes no sense.&nbsp; Already with the dual code&nbsp; $\rm A$&nbsp; &#8594;&nbsp; <b>000</b>,&nbsp; $\rm B$&nbsp; &#8594;&nbsp; <b>001</b>, ... ,&nbsp; $\rm H$&nbsp; &#8594;&nbsp; <b>111</b>, the average codeword length&nbsp; $L_{\rm M}$&nbsp; is its lower bound&nbsp; $H$&nbsp; according to the source coding theorem&nbsp; $(H$ denotes the&nbsp; "source entropy"&nbsp; here$)$:
+If the symbols are equally probable, i.e.&nbsp; $p_{\rm A} =  p_{\rm B} =$ ... $ = p_{\rm H} = 1/M$ &nbsp; then source coding makes no sense.&nbsp; Already with the dual code&nbsp; $\rm A$&nbsp; &#8594;&nbsp; <b>000</b>,&nbsp; $\rm B$&nbsp; &#8594;&nbsp; <b>001</b>, ... ,&nbsp; $\rm H$&nbsp; &#8594;&nbsp; <b>111</b>, the average code word length&nbsp; $L_{\rm M}$&nbsp; is its lower bound&nbsp; $H$&nbsp; according to the source coding theorem&nbsp; $(H$ denotes the&nbsp; "source entropy"&nbsp; here$)$:
 :$$L_{\rm M,\hspace{0.08cm}min} = H = 3 \hspace{0.15cm}{\rm bit/source \:symbol} \hspace{0.05cm}.$$
@@ Line 41: / Line 41: @@
 :'''(c)''' &nbsp; Assignment of the symbols&nbsp; $\rm A$, ... ,&nbsp; $\rm H$&nbsp; to the corresponding Huffman binary sequences.&nbsp; A red connection corresponds to a&nbsp; <b>1</b>, a blue connection to a&nbsp; <b>0</b>.
-You will notice that the average codeword length for Huffman coding,
+You will notice that the average code word length for Huffman coding,
 :$$L_{\rm M} =  \sum_{\mu = 1}^{M}\hspace{0.05cm} p_{\mu} \cdot L_{\mu}, $$
 is only slightly larger than the source entropy&nbsp; $H$.&nbsp; In this equation, the following values apply to the present case:
@@ Line 93: / Line 93: @@
-{What is the average codeword length?
+{What is the average code word length?
 |type="{}"}
 $L_{\rm M} \ = \ $  { 2.73 3% } $\ \rm bit/source \hspace{0.15cm} symbol$
@@ Line 165: / Line 165: @@
-Thus, for the average codeword length (in "bit/source symbol"):
+Thus, for the average code word length (in "bit/source symbol"):
 :$$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}.$$
@@ Line 172: / Line 172: @@
 '''(5)'''&nbsp; Only <u>answer 1</u> is correct:
-*The average codeword length&nbsp; $L_{\rm M}$&nbsp; cannot be smaller than the source entropy&nbsp; $H$.&nbsp; This eliminates answers 2 and 3.
+*The average code word length&nbsp; $L_{\rm M}$&nbsp; cannot be smaller than the source entropy&nbsp; $H$.&nbsp; This eliminates answers 2 and 3.
 *From the given probabilities of occurrence, the source entropy can actually be calculated to&nbsp; $H = 2.71$ bit/source symbol.
 *It can be seen that this Huffman coding almost reaches the given limit&nbsp; ("Source Coding Theorem")&nbsp; $L_{\rm M, \ min } \ge H = 2.71$&nbsp; bit/source symbol.

← Older revision		Revision as of 12:07, 16 August 2021
Line 18:		Line 18:


−	The algorithm is given here without derivation and proof, whereby we restrict ourselves to binary codes   ⇒   the ~~code symbol~~ sequence consists only of zeros and ones:	+	The algorithm is given here without derivation and proof, whereby we restrict ourselves to binary codes   ⇒   the encoded sequence consists only of zeros and ones:

	:'''(1)'''   Order the symbols according to decreasing probabilities of occurrence.		:'''(1)'''   Order the symbols according to decreasing probabilities of occurrence.

@@ Line 93: / Line 93: @@
-{What is the mean codeword length?
+{What is the average codeword length?
 |type="{}"}
 $L_{\rm M} \ = \ $  { 2.73 3% } $\ \rm bit/source \hspace{0.15cm} symbol$
@@ Line 114: / Line 114: @@
 *By comparison with the data sheet, one obtains:
-:Symbol $\rm A$:&nbsp;  <u>Eingang 7</u>,  &nbsp; &nbsp; Symbol $\rm B$:&nbsp;  <u>Eingang 6</u>, &nbsp; &nbsp; Symbol $\rm C$:&nbsp;  <u>Eingang 3</u>, &nbsp; &nbsp; Symbol $\rm D$:&nbsp;  <u>Input 1</u>.
+:Symbol $\rm A$:&nbsp;  <u>Input 7</u>,  &nbsp; &nbsp; Symbol $\rm B$:&nbsp;  <u>Input 6</u>, &nbsp; &nbsp; Symbol $\rm C$:&nbsp;  <u>Input 3</u>, &nbsp; &nbsp; Symbol $\rm D$:&nbsp;  <u>Input 1</u>.
 [[File:EN_Inf_Z_2_6b.png|right|right|frame|Tree diagram adapted to the exercise]]
+'''(2)'''&nbsp; The node&nbsp; $\rm R$&nbsp; is the tree&nbsp; ("root").&nbsp; This is always assigned&nbsp; $\underline{R=1}$,&nbsp; regardless of the occurrence probabilities.
 The following applies to the other values:
@@ Line 135: / Line 133: @@
 :Step 5:&nbsp;&nbsp;&nbsp; $p_{\rm Y} = p_{\rm W} + p_{\rm E} = 0.22 + 0.24   \hspace{0.15cm}\underline{ =0.46}$,
-:Schritt 6:&nbsp;&nbsp;&nbsp; $p_{\rm Z} = p_{\rm X} + p_{\rm D} = 0.29 + 0.25  \hspace{0.15cm}\underline{ =0.54}$.
+:Step 6:&nbsp;&nbsp;&nbsp; $p_{\rm Z} = p_{\rm X} + p_{\rm D} = 0.29 + 0.25  \hspace{0.15cm}\underline{ =0.54}$.
 <br clear=all>
-'''(3)'''&nbsp; The Huffman code for symbol&nbsp; $\rm A$&nbsp; is obtained by tracing the path from the&nbsp; $\rm root$&nbsp; (yellow dot) to symbol &nbsp; $\rm A$&nbsp; and assigning a&nbsp; <b>1</b>&nbsp; to each red connecting line and a&nbsp; <b>0</b> to each blue one..
+'''(3)'''&nbsp; The Huffman code for symbol&nbsp; $\rm A$&nbsp; is obtained by tracing the path from&nbsp; $\rm root$&nbsp; (yellow dot) to symbol &nbsp; $\rm A$&nbsp; and assigning a&nbsp; <b>1</b>&nbsp; to each red line and a&nbsp; <b>0</b> to each blue one.
 * Symbol $\rm A$:&nbsp;&nbsp;&nbsp; red&ndash;red&ndash;red&ndash;blue&ndash;red&#8594; <b><u>11101</u></b>,
@@ Line 158: / Line 156: @@
 '''(4)'''&nbsp; The coding under point&nbsp; '''(3)'''&nbsp; has shown that
-* the symbols&nbsp; $\rm D$&nbsp; and&nbsp; $\rm E$&nbsp; with two bits,
+* the symbols&nbsp; $\rm D$&nbsp; and&nbsp; $\rm E$&nbsp; are each represented with two bits,
 * the symbols&nbsp; $\rm C$,&nbsp; $\rm F$&nbsp; and&nbsp; $\rm G$&nbsp; with three bits,
@@ Line 164: / Line 162: @@
 * the symbols&nbsp; $\rm B$&nbsp;  with four bits,&nbsp; and
-* the symbols&nbsp; $\rm A$&nbsp; and&nbsp; $\rm H$&nbsp; are each represented with five bits
+* the symbols&nbsp; $\rm A$&nbsp; and&nbsp; $\rm H$&nbsp; with five bits.
-are represented.&nbsp; Thus, for the mean codeword length (in "bit/source symbol"):
+Thus, for the average codeword length (in "bit/source symbol"):
 :$$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}.$$
@@ Line 174: / Line 172: @@
 '''(5)'''&nbsp; Only <u>answer 1</u> is correct:
-*The mean codeword length&nbsp; $L_{\rm M}$&nbsp; cannot be smaller than the source entropy&nbsp; $H$.&nbsp; This eliminates answers 2 and 3.
+*The average codeword length&nbsp; $L_{\rm M}$&nbsp; cannot be smaller than the source entropy&nbsp; $H$.&nbsp; This eliminates answers 2 and 3.
 *From the given probabilities of occurrence, the source entropy can actually be calculated to&nbsp; $H = 2.71$ bit/source symbol.
-*It can be seen that this Huffman coding almost reaches the given limitnbsp; (source coding theorem)&nbsp; $L_{\rm M, \ min } \ge H = 2.71$&nbsp; bit/source symbol.
+*It can be seen that this Huffman coding almost reaches the given limit&nbsp; ("Source Coding Theorem")&nbsp; $L_{\rm M, \ min } \ge H = 2.71$&nbsp; bit/source symbol.
 {{ML-Fuß}}

@@ Line 95: / Line 95: @@
 {What is the mean codeword length?
 |type="{}"}
-$L_{\rm M} \ = \ $  { 2.73 3% } $\ \rm bit/source \:symbol$
+$L_{\rm M} \ = \ $  { 2.73 3% } $\ \rm bit/source \hspace{0.15cm} symbol$
 {What is the source entropy&nbsp; $H$?
 |type="()"}
-+ $H = 2.71\ \rm  bit/source \:symbol.$
++ $H = 2.71\ \rm  bit/source \hspace{0.15cm}symbol.$
-- $H = 2.75\ \rm  bit/source \:symbol.$
+- $H = 2.75\ \rm  bit/source \hspace{0.15cm}symbol.$
-- $H = 3.00\ \rm  bit/source \:symbol.$
+- $H = 3.00\ \rm  bit/source \hspace{0.15cm}symbol.$

@@ Line 58: / Line 58: @@
 ** [[Information_Theory/Entropiecodierung_nach_Huffman#The_Huffman_algorithm|The Huffman algorithm]],
 **[[Information_Theory/Entropiecodierung_nach_Huffman#Representation_of_the_Huffman_code_as_a_tree_diagram|Representation of the Huffman code as a tree diagram]].
-*To check your results, please refer to the interaction modules given here in two versions:
+*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 3: / Line 3: @@
 }}
-[[File:EN_Inf_A_2_6_v2.png|right|frame|Tree diagram of the <br>Huffman method]]
+[[File:EN_Inf_A_2_6_v2.png|right|frame|Tree diagram of the Huffman method]]
-We consider here a source symbol sequence&nbsp; $\langle q_\nu  \rangle$&nbsp; with symbol range&nbsp; $M = 8$:
+We consider here a source symbol sequence&nbsp; $\langle q_\nu  \rangle$&nbsp; with symbol set size&nbsp; $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}.$$
-If the symbols are equally probable, i.e.&nbsp; $p_{\rm A} =  p_{\rm B} =$ ... $ = p_{\rm H} = 1/M$ then source coding makes no sense.&nbsp; Already with the dual code&nbsp; $\rm A$&nbsp; &#8594;&nbsp; <b>000</b>,&nbsp; $\rm B$&nbsp; &#8594;&nbsp; <b>001</b>, ... ,&nbsp; $\rm H$&nbsp; &#8594;&nbsp; <b>111</b>, the mean codeword length&nbsp; $L_{\rm M}$&nbsp; is its lower bound&nbsp; $H$&nbsp; according to the source coding theorem&nbsp; $(H$ denotes the <i>source entropy</i>$ here)$:
+If the symbols are equally probable, i.e.&nbsp; $p_{\rm A} =  p_{\rm B} =$ ... $ = p_{\rm H} = 1/M$ &nbsp; then source coding makes no sense.&nbsp; Already with the dual code&nbsp; $\rm A$&nbsp; &#8594;&nbsp; <b>000</b>,&nbsp; $\rm B$&nbsp; &#8594;&nbsp; <b>001</b>, ... ,&nbsp; $\rm H$&nbsp; &#8594;&nbsp; <b>111</b>, the average codeword length&nbsp; $L_{\rm M}$&nbsp; is its lower bound&nbsp; $H$&nbsp; according to the source coding theorem&nbsp; $(H$ denotes the&nbsp; "source entropy"&nbsp; here$)$:
 :$$L_{\rm M,\hspace{0.08cm}min} = H = 3 \hspace{0.15cm}{\rm bit/source \:symbol} \hspace{0.05cm}.$$
-However, let the symbol probabilities in this task be given as follows:
+However, let the symbol probabilities be given as follows:
 :$$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}.$$
-*So here we have a redundant message source that can be compressed by Huffman coding.
+*So here we have a redundant  source that can be compressed by Huffman coding.
 *This algorithm was published by&nbsp; [https://en.wikipedia.org/wiki/David_A._Huffman David Albert Huffman]&nbsp; &ndash; shortly after Shannon's groundbreaking work on information theory &ndash; and allows the construction of optimal prefix-free codes.
@@ Line 26: / Line 26: @@
 :'''(3)''' &nbsp;  Repeat steps&nbsp; '''(1)'''&nbsp; and&nbsp; '''(2)''', until only two (combined) symbols remain.
-:'''(4)''' &nbsp;  Binary code the more probable set of symbols with&nbsp; <b>1</b>&nbsp;, the other set with&nbsp; <b>0</b>.
+:'''(4)''' &nbsp;  Binary encode the more probable set of symbols with&nbsp; <b>1</b>&nbsp;, the other set with&nbsp; <b>0</b>.
 :'''(5)''' &nbsp;  Step by step (from bottom to top) add&nbsp; <b>1</b>&nbsp; or&nbsp; <b>0</b>  to the split partial codes.
@@ Line 37: / Line 37: @@
 :'''(a)''' &nbsp; Assign the symbols&nbsp; $\rm A$, ... , $\rm H$&nbsp; to the inputs labelled&nbsp; '''[1]''', ... , '''[8]'''&nbsp;.
-:'''(b)''' &nbsp; Determination of the sum probabilities&nbsp; $U$, ... ,&nbsp; $Z$&nbsp; and&nbsp; $R$&nbsp; (<i>root</i>).
+:'''(b)''' &nbsp; Determination of the sum probabilities&nbsp; $U$, ... ,&nbsp; $Z$&nbsp; and&nbsp; $R$&nbsp; ("root").
-:'''(c)''' &nbsp; Assignment of the symbols&nbsp; $\rm A$, ... ,&nbsp; $\rm H$&nbsp; to the corresponding Huffman binary sequences. A red connection corresponds to a&nbsp; <b>1</b>, a blue connection to a&nbsp; <b>0</b>.
+:'''(c)''' &nbsp; Assignment of the symbols&nbsp; $\rm A$, ... ,&nbsp; $\rm H$&nbsp; to the corresponding Huffman binary sequences.&nbsp; A red connection corresponds to a&nbsp; <b>1</b>, a blue connection to a&nbsp; <b>0</b>.
-You will notice that the mean codeword length is
+You will notice that the average codeword length for Huffman coding,
-:$$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}, $$
-for Huffman coding is only slightly larger than the source entropy&nbsp; $H$.&nbsp; IIn this equation, the following values apply to the present case:
+is only slightly larger than the source entropy&nbsp; $H$.&nbsp; In this equation, the following values apply to the present case:
 *$M = 8$,&nbsp;  $p_1 = p_{\rm A}$,&nbsp; ... ,&nbsp; $p_8 = p_{\rm H}$.
 *The respective number of bits of the code symbols for&nbsp; $\rm A$, ... ,&nbsp; $\rm H$&nbsp; is denoted by&nbsp; $L_1$, ... ,&nbsp; $L_8$&nbsp;.
@@ Line 53: / Line 53: @@
-Hints:
+<u>Hints:</u>
 *The exercise belongs to the chapter&nbsp; [[Information_Theory/Entropiecodierung_nach_Huffman|Entropy Coding according to Huffman]].
 *In particular, reference is made to the pages&nbsp;
 ** [[Information_Theory/Entropiecodierung_nach_Huffman#The_Huffman_algorithm|The Huffman algorithm]],
 **[[Information_Theory/Entropiecodierung_nach_Huffman#Representation_of_the_Huffman_code_as_a_tree_diagram|Representation of the Huffman code as a tree diagram]].
-*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 interaction modules given here in two versions:

← Older revision		Revision as of 12:14, 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 110: / Line 110: @@
 ===Solution===
 {{ML-Kopf}}
-'''(1)'''&nbsp; Vor dem Huffman&ndash;Algorithmus müssen die Symbole nach ihren Auftrittswahrscheinlichkeiten sortiert werden.
+'''(1)'''&nbsp; Before the Huffman algorithm, the symbols must be sorted according to their probabilities of occurrence.
-*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).
+*Since the two least likely symbols are already combined in the first step, the probabilities of occurrence decrease from top to bottom <br>(from left to right in the diagram for this sample solution).
-*Durch Vergleich mit dem Angabenblatt erhält man:
+*By comparison with the data sheet, one obtains:
-:Symbol $\rm A$:&nbsp;  <u>Eingang 7</u>,  &nbsp; &nbsp; Symbol $\rm B$:&nbsp;  <u>Eingang 6</u>, &nbsp; &nbsp; Symbol $\rm C$:&nbsp;  <u>Eingang 3</u>, &nbsp; &nbsp; Symbol $\rm D$:&nbsp;  <u>Eingang 1</u>.
+:Symbol $\rm A$:&nbsp;  <u>Eingang 7</u>,  &nbsp; &nbsp; Symbol $\rm B$:&nbsp;  <u>Eingang 6</u>, &nbsp; &nbsp; Symbol $\rm C$:&nbsp;  <u>Eingang 3</u>, &nbsp; &nbsp; Symbol $\rm D$:&nbsp;  <u>Input 1</u>.
-[[File:EN_Inf_Z_2_6b.png|right|right|frame|An die Aufgabe angepasstes Baumdiagramm]]
+[[File:EN_Inf_Z_2_6b.png|right|right|frame|Tree diagram adapted to the exercise]]
 P_ID2452__Inf_A_2_6a.png
-'''(2)'''&nbsp; Der Knoten&nbsp; $\rm R$&nbsp; ist die Baumwurzel&nbsp; (<i>Root</i>).&nbsp; Dieser ist stets mit&nbsp; $\underline{R=1}$&nbsp; belegt, unabhängig von den Auftrittswahrscheinlichkeiten.
+'''(2)'''&nbsp; The node&nbsp; $\rm R$&nbsp; is the tree&nbsp; (<i>root</i>).&nbsp; This is always assigned&nbsp; $\underline{R=1}$&nbsp;, regardless of the occurrence probabilities.
-Für die weiteren Werte gilt:
+The following applies to the other values:
-:Schritt 1:&nbsp;&nbsp;&nbsp; $p_{\rm U} = p_{\rm A} + p_{\rm H} = 0.04 + 0.03 \hspace{0.15cm}\underline{ =0.07}$,
+:Step 1:&nbsp;&nbsp;&nbsp; $p_{\rm U} = p_{\rm A} + p_{\rm H} = 0.04 + 0.03 \hspace{0.15cm}\underline{ =0.07}$,
-:Schritt 2:&nbsp;&nbsp;&nbsp; $p_{\rm V} = p_{\rm U} + p_{\rm B} = 0.07 + 0.08 \hspace{0.15cm}\underline{ =0.15}$,
+:Step 2:&nbsp;&nbsp;&nbsp; $p_{\rm V} = p_{\rm U} + p_{\rm B} = 0.07 + 0.08 \hspace{0.15cm}\underline{ =0.15}$,
-:Schritt 3:&nbsp;&nbsp;&nbsp; $p_{\rm W} = p_{\rm F} + p_{\rm G} = 0.12 + 0.10 \hspace{0.15cm}\underline{ =0.22}$,
+:Step 3:&nbsp;&nbsp;&nbsp; $p_{\rm W} = p_{\rm F} + p_{\rm G} = 0.12 + 0.10 \hspace{0.15cm}\underline{ =0.22}$,
-:Schritt 4:&nbsp;&nbsp;&nbsp; $p_{\rm X} = p_{\rm V} + p_{\rm C} = 0.15 + 0.14  \hspace{0.15cm}\underline{ =0.29}$,
+:Step 4:&nbsp;&nbsp;&nbsp; $p_{\rm X} = p_{\rm V} + p_{\rm C} = 0.15 + 0.14  \hspace{0.15cm}\underline{ =0.29}$,
-:Schritt 5:&nbsp;&nbsp;&nbsp; $p_{\rm Y} = p_{\rm W} + p_{\rm E} = 0.22 + 0.24   \hspace{0.15cm}\underline{ =0.46}$,
+:Step 5:&nbsp;&nbsp;&nbsp; $p_{\rm Y} = p_{\rm W} + p_{\rm E} = 0.22 + 0.24   \hspace{0.15cm}\underline{ =0.46}$,
 :Schritt 6:&nbsp;&nbsp;&nbsp; $p_{\rm Z} = p_{\rm X} + p_{\rm D} = 0.29 + 0.25  \hspace{0.15cm}\underline{ =0.54}$.
 <br clear=all>
-'''(3)'''&nbsp; Den Huffman&ndash;Code für das Symbol&nbsp; $\rm A$&nbsp; erhält man, wenn man den Weg von der&nbsp; $\rm Root$&nbsp; (gelber Punkt) zum Symbol&nbsp; $\rm A$&nbsp; zurückverfolgt und jeder roten Verbindungslinie eine&nbsp; <b>1</b>&nbsp; zuordnet, jeder blauen eine&nbsp; <b>0</b>.
+'''(3)'''&nbsp; The Huffman code for symbol&nbsp; $\rm A$&nbsp; is obtained by tracing the path from the&nbsp; $\rm root$&nbsp; (yellow dot) to symbol &nbsp; $\rm A$&nbsp; and assigning a&nbsp; <b>1</b>&nbsp; to each red connecting line and a&nbsp; <b>0</b> to each blue one..
-* Symbol $\rm A$:&nbsp;&nbsp;&nbsp; rot&ndash;rot&ndash;rot&ndash;blau&ndash;rot &#8594; <b><u>11101</u></b>,
+* Symbol $\rm A$:&nbsp;&nbsp;&nbsp; red&ndash;red&ndash;red&ndash;blue&ndash;red&#8594; <b><u>11101</u></b>,
-* Symbol $\rm B$:&nbsp;&nbsp;&nbsp; rot&ndash;rot&ndash;rot&ndash;rot &#8594; <b><u>1111</u></b>,
+* Symbol $\rm B$:&nbsp;&nbsp;&nbsp; red&ndash;red&ndash;red&ndash;red &#8594; <b><u>1111</u></b>,
-* Symbol $\rm C$:&nbsp;&nbsp;&nbsp; rot&ndash;rot&ndash;blau &#8594; <b><u>110</u></b>,
+* Symbol $\rm C$:&nbsp;&nbsp;&nbsp; red&ndash;red&ndash;blue &#8594; <b><u>110</u></b>,
-* Symbol $\rm D$:&nbsp;&nbsp;&nbsp; rot&ndash;blau&ndash; &#8594; <b><u>10</u></b>,
+* Symbol $\rm D$:&nbsp;&nbsp;&nbsp; red&ndash;blue&ndash; &#8594; <b><u>10</u></b>,
-* Symbol $\rm E$:&nbsp;&nbsp;&nbsp; blau&ndash;rot &#8594; <b>01</b>,
+* Symbol $\rm E$:&nbsp;&nbsp;&nbsp; blue&ndash;red &#8594; <b>01</b>,
-* Symbol $\rm F$:&nbsp;&nbsp;&nbsp; blau&ndash;blau&ndash;rot &#8594; <b>001</b>,
+* Symbol $\rm F$:&nbsp;&nbsp;&nbsp; blue&ndash;blue&ndash;red &#8594; <b>001</b>,
-* Symbol $\rm G$:&nbsp;&nbsp;&nbsp; blau&ndash;blau&ndash;blau &#8594; <b>000</b>,
+* Symbol $\rm G$:&nbsp;&nbsp;&nbsp; blue&ndash;blue&ndash;blue &#8594; <b>000</b>,
-* Symbol $\rm H$:&nbsp;&nbsp;&nbsp; rot&ndash;rot&ndash;rot&ndash;blau&ndash;blau &#8594; <b>11100</b>.
+* Symbol $\rm H$:&nbsp;&nbsp;&nbsp; red&ndash;red&ndash;red&ndash;blue&ndash;blue &#8594; <b>11100</b>.
-'''(4)'''&nbsp; Die Codierung unter Punkt&nbsp; '''(3)'''&nbsp; hat ergeben, dass
+'''(4)'''&nbsp; The coding under point&nbsp; '''(3)'''&nbsp; has shown that
-* die Symbole&nbsp; $\rm D$&nbsp; und&nbsp; $\rm E$&nbsp; mit zwei Bit,
+* the symbols&nbsp; $\rm D$&nbsp; and&nbsp; $\rm E$&nbsp; with two bits,
-* die Symbole&nbsp; $\rm C$,&nbsp; $\rm F$&nbsp; und&nbsp; $\rm G$&nbsp; mit drei Bit,
+* the symbols&nbsp; $\rm C$,&nbsp; $\rm F$&nbsp; and&nbsp; $\rm G$&nbsp; with three bits,
-* das Symbol&nbsp; $\rm B$&nbsp;  mit vier Bit,&nbsp; und
+* the symbols&nbsp; $\rm B$&nbsp;  with four bits,&nbsp; and
-* die Symbole&nbsp; $\rm A$&nbsp; und&nbsp; $\rm H$&nbsp; jeweils mit fünf Bit
+* the symbols&nbsp; $\rm A$&nbsp; and&nbsp; $\rm H$&nbsp; are each represented with five bits
-dargestellt werden.&nbsp; Damit erhält man für die mittlere Codewortlänge (in "bit/Quellensymbol&dquo;):
+are represented.&nbsp; Thus, for the mean codeword length (in "bit/source symbol&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
 \hspace{0.15cm}\underline{= 2.73}\hspace{0.05cm}.$$
@@ Line 173: / Line 173: @@
-'''(5)'''&nbsp; Richtig ist allein die <u>Antwort 1</u>:
+'''(5)'''&nbsp; Only <u>answer 1</u> is correct:
-*Die mittlere Codewortlänge&nbsp; $L_{\rm M}$&nbsp; kann nicht kleiner sein als die Quellenentropie&nbsp; $H$.&nbsp; Damit scheiden die Antworten 2 und 3 aus.
+*The mean codeword length&nbsp; $L_{\rm M}$&nbsp; cannot be smaller than the source entropy&nbsp; $H$.&nbsp; This eliminates answers 2 and 3.
-*Aus den vorgegebenen Auftrittswahrscheinlichkeiten kann   die Quellenentropie tatsächlich  zu&nbsp; $H = 2.71$ bit/Quellensymbol berechnet werden.
+*From the given probabilities of occurrence, the source entropy can actually be calculated to&nbsp; $H = 2.71$ bit/source symbol.
-*Man erkennt, dass diese Huffman&ndash;Codierung die vorgegebene Grenze&nbsp; (Quellencodierungstheorem)&nbsp; $L_{\rm M, \ min } \ge H = 2.71$&nbsp; bit/Quellensymbol nahezu erreicht.
+*It can be seen that this Huffman coding almost reaches the given limitnbsp; (source coding theorem)&nbsp; $L_{\rm M, \ min } \ge H = 2.71$&nbsp; bit/source symbol.
 {{ML-Fuß}}