Aufgaben:Exercise 1.4Z: Entropy of the AMI Code - Revision history

Javier: Text replacement - "generalis" to "generaliz"

2021-09-22T11:48:09Z

Text replacement - "generalis" to "generaliz"

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

2021-08-16T12:08:07Z

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

Guenter at 12:03, 10 August 2021

2021-08-10T12:03:14Z

Guenter at 15:42, 19 June 2021

2021-06-19T15:42:59Z

Guenter at 15:27, 19 June 2021

2021-06-19T15:27:32Z

Guenter at 15:23, 19 June 2021

2021-06-19T15:23:45Z

Guenter at 15:22, 19 June 2021

2021-06-19T15:22:38Z

Guenter at 15:21, 19 June 2021

2021-06-19T15:21:23Z

Javier: Text replacement - "”" to """

2021-05-28T14:42:37Z

Text replacement - "”" to """

Javier: Text replacement - "„" to """

2021-05-28T14:40:41Z

Text replacement - "„" to """

@@ Line 114: / Line 114: @@
   \hspace{0.15cm} \underline {= 48.8  \,\%}
   \hspace{0.05cm}$ now holds.
-*One can generalise this result.&nbsp; Namely, it holds:
+*One can generalize this result.&nbsp; Namely, it holds:
 :$$(1-0.488) = (1- 0.189) \cdot (1- 0.369)\hspace{0.3cm}
 \Rightarrow\hspace{0.3cm} (1-r_{\rm Codefolge})   = (1-r_{\rm Quelle}) \cdot (1- r_{\rm AMI-Code})

@@ Line 14: / Line 14: @@
-The presented coded signal&nbsp; $c(t)$&nbsp; and the corresponding code symbol sequence&nbsp; $\langle c_\nu \rangle$&nbsp;  with&nbsp; $c_\nu \in \{{\rm P}, {\rm N}, {\rm M}  \}$&nbsp; results from the AMI coding&nbsp; ("Alternate Mark Inversion")&nbsp; according to the following rule:
+The presented coded signal&nbsp; $c(t)$&nbsp; and the corresponding encoded sequence&nbsp; $\langle c_\nu \rangle$&nbsp;  with&nbsp; $c_\nu \in \{{\rm P}, {\rm N}, {\rm M}  \}$&nbsp; results from the AMI coding&nbsp; ("Alternate Mark Inversion")&nbsp; according to the following rule:
 * The binary symbol&nbsp; $\rm L$ &nbsp; &rArr; &nbsp; "Low"&nbsp; is always represented by the ternary symbol&nbsp; $\rm N$ &nbsp; &rArr; &nbsp; "German: Null"&nbsp; &rArr; &nbsp;"Zero".
@@ Line 22: / Line 22: @@
-In this task, the decision content&nbsp; $H_0$&nbsp; and the resulting entropy&nbsp; $H_{\rm C}$&nbsp; of the code symbol sequence&nbsp; $\langle c_\nu \rangle$&nbsp; are to be determined for the three parameter sets mentioned above.&nbsp; The relative redundancy of the code sequence results from this according to the equation
+In this task, the decision content&nbsp; $H_0$&nbsp; and the resulting entropy&nbsp; $H_{\rm C}$&nbsp; of the encoded sequence&nbsp; $\langle c_\nu \rangle$&nbsp; are to be determined for the three parameter sets mentioned above.&nbsp; The relative redundancy of the code sequence results from this according to the equation
 :$$r_{\rm C} = \frac{H_{\rm 0}-H_{\rm C}}{H_{\rm C}}
   \hspace{0.05cm}.$$
@@ Line 51: / Line 51: @@
 <quiz display=simple>
-{Let the source symbols be equally probable&nbsp; $(p_{\rm L} =  p_{\rm H}= 1/2)$.&nbsp; What is the entropy&nbsp; $H_{\rm C}$&nbsp; of the code symbol sequence&nbsp; $\langle c_\nu \rangle$?
+{Let the source symbols be equally probable&nbsp; $(p_{\rm L} =  p_{\rm H}= 1/2)$.&nbsp; What is the entropy&nbsp; $H_{\rm C}$&nbsp; of the encoded sequence&nbsp; $\langle c_\nu \rangle$?
 |type="{}"}
 $H_{\rm C} \ = \ $ { 1 3% } $\ \rm bit/ternary \ symbol$
-{What is the relative redundancy of the code symbol sequence?
+{What is the relative redundancy of the encoded sequence?
 |type="{}"}
 $r_{\rm C} \ =  \ $ { 36.9 3% } $\ \rm \%$
-{For the binary source,&nbsp; $p_{\rm L}  = 1/4$ &nbsp;and&nbsp; $p_{\rm H}  = 3/4$.&nbsp; What is the entropy of the code symbol sequence?
+{For the binary source,&nbsp; $p_{\rm L}  = 1/4$ &nbsp;and&nbsp; $p_{\rm H}  = 3/4$.&nbsp; What is the entropy of the encoded sequence?
 |type="{}"}
 $H_{\rm C} \ = \ $ { 0.811 3% } $\ \rm bit/ternary \ symbol$
-{What is the relative redundancy of the code symbol sequence?
+{What is the relative redundancy of the encoded sequence?
 |type="{}"}
@@ Line 87: / Line 87: @@
 ===Solution===
 {{ML-Kopf}}
-'''(1)'''&nbsp; Since the AMI code neither adds new information nor causes information to disappear, the entropy&nbsp; $H_{\rm C}$&nbsp; of the code symbol sequence&nbsp; $\langle c_\nu \rangle$&nbsp; is equal to the source entropy&nbsp; $H_{\rm Q}$.&nbsp;
+'''(1)'''&nbsp; Since the AMI code neither adds new information nor causes information to disappear, the entropy&nbsp; $H_{\rm C}$&nbsp; of the encoded sequence&nbsp; $\langle c_\nu \rangle$&nbsp; is equal to the source entropy&nbsp; $H_{\rm Q}$.&nbsp;
 *Therefore, for equally probable and statistically independent source symbols, the following holds:
 :$$H_{\rm Q}     {= 1 \,{\rm bit/binary \ symbol}} \hspace{0.3cm} \Rightarrow\hspace{0.3cm} H_{\rm C}    \hspace{0.15cm} \underline {= 1 \,{\rm bit/ternary \ symbol}}

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

−	{{quiz-Header\|Buchseite=~~Informationstheorie~~/~~Nachrichtenquellen mit Gedächtnis~~	+	{{quiz-Header\|Buchseite=Information_Theory/Discrete_Sources_with_Memory
	}}		}}

@@ Line 53: / Line 53: @@
 {Let the source symbols be equally probable&nbsp; $(p_{\rm L} =  p_{\rm H}= 1/2)$.&nbsp; What is the entropy&nbsp; $H_{\rm C}$&nbsp; of the code symbol sequence&nbsp; $\langle c_\nu \rangle$?
 |type="{}"}
-$H_{\rm C} \ = \ $ { 1 3% } $\ \rm bit/ternary symbol$
+$H_{\rm C} \ = \ $ { 1 3% } $\ \rm bit/ternary \ symbol$
@@ Line 63: / Line 63: @@
 {For the binary source,&nbsp; $p_{\rm L}  = 1/4$ &nbsp;and&nbsp; $p_{\rm H}  = 3/4$.&nbsp; What is the entropy of the code symbol sequence?
 |type="{}"}
-$H_{\rm C} \ = \ $ { 0.811 3% } $\ \rm bit/ternary symbol$
+$H_{\rm C} \ = \ $ { 0.811 3% } $\ \rm bit/ternary \ symbol$
@@ Line 74: / Line 74: @@
 {Calculate the approximation&nbsp; $H_{\rm 1}$&nbsp; of the code entropy for&nbsp; $p_{\rm L} = 1/4$ &nbsp;and&nbsp; $p_{\rm H} = 3/4$.
 |type="{}"}
-$H_{\rm 1} \ = \ $ { 1.56 3% } $\ \rm bit/ternary symbol$
+$H_{\rm 1} \ = \ $ { 1.56 3% } $\ \rm bit/ternary \ symbol$
 {Calculate the approximation&nbsp; $H_{\rm 1}$&nbsp; of the code entropy for&nbsp; $p_{\rm L} = 3/4$ &nbsp;and&nbsp; $p_{\rm H} = 1/4$.
 |type="{}"}
-$H_{\rm 1} \ = \ $ { 1.06 3% } $\ \rm bit/ternary symbol$
+$H_{\rm 1} \ = \ $ { 1.06 3% } $\ \rm bit/ternary \ symbol$
@@ Line 89: / Line 89: @@
 '''(1)'''&nbsp; Since the AMI code neither adds new information nor causes information to disappear, the entropy&nbsp; $H_{\rm C}$&nbsp; of the code symbol sequence&nbsp; $\langle c_\nu \rangle$&nbsp; is equal to the source entropy&nbsp; $H_{\rm Q}$.&nbsp;
 *Therefore, for equally probable and statistically independent source symbols, the following holds:
-:$$H_{\rm Q}     {= 1 \,{\rm bit/binary&nbsp;symbol}} \hspace{0.3cm} \Rightarrow\hspace{0.3cm} H_{\rm C}    \hspace{0.15cm} \underline {= 1 \,{\rm bit/ternary&nbsp;symbol}}
+:$$H_{\rm Q}     {= 1 \,{\rm bit/binary \ symbol}} \hspace{0.3cm} \Rightarrow\hspace{0.3cm} H_{\rm C}    \hspace{0.15cm} \underline {= 1 \,{\rm bit/ternary \ symbol}}
   \hspace{0.05cm}.$$
@@ Line 105: / Line 105: @@
 :$$H_{\rm Q}  =   \frac{1}{4} \cdot {\rm log}_2\hspace{0.05cm} (4) + \frac{3}{4} \cdot
 {\rm log}_2\hspace{0.1cm} (4/3)
-  {= 0.811 \,{\rm bit/binary symbol}} \hspace{0.3cm}
+  {= 0.811 \,{\rm bit/binary \ symbol}} \hspace{0.3cm}
-\Rightarrow\hspace{0.3cm} H_{\rm C}  = H_{\rm Q}   \hspace{0.15cm} \underline {= 0.811 \,{\rm bit/ternary symbol}}
+\Rightarrow\hspace{0.3cm} H_{\rm C}  = H_{\rm Q}   \hspace{0.15cm} \underline {= 0.811 \,{\rm bit/ternary \ symbol}}
   \hspace{0.05cm}.$$
@@ Line 114: / Line 114: @@
   \hspace{0.15cm} \underline {= 48.8  \,\%}
   \hspace{0.05cm}$ now holds.
-*One can generalise this result. Namely, it holds:
+*One can generalise this result.&nbsp; Namely, it holds:
 :$$(1-0.488) = (1- 0.189) \cdot (1- 0.369)\hspace{0.3cm}
 \Rightarrow\hspace{0.3cm} (1-r_{\rm Codefolge})   = (1-r_{\rm Quelle}) \cdot (1- r_{\rm AMI-Code})
@@ Line 124: / Line 124: @@
 :$$p_{\rm N} = p_{\rm L} = 1/4\hspace{0.05cm},\hspace{0.2cm}p_{\rm P} = p_{\rm M} = p_{\rm H}/2 = 3/8\hspace{0.3cm}
 \Rightarrow\hspace{0.3cm} H_1  = {1}/{4} \cdot {\rm log}_2\hspace{0.1cm} (4) +
-\cdot {3}/{8} \cdot {\rm log}_2\hspace{0.1cm}(8/3)  \hspace{0.15cm} \underline {= 1.56 \,{\rm bit/ternary symbol}}
+\cdot {3}/{8} \cdot {\rm log}_2\hspace{0.1cm}(8/3)  \hspace{0.15cm} \underline {= 1.56 \,{\rm bit/ternary \ symbol}}
   \hspace{0.05cm}.$$
@@ Line 130: / Line 130: @@
 '''(6)'''&nbsp; Now the probabilities of occurrence of the ternary symbols are &nbsp;  $p_{\rm N} = 3/4$&nbsp; sowie&nbsp; $p_{\rm P} = p_{\rm M} =1/8$.&nbsp; Thus:
 :$$H_1  = {3}/{4} \cdot {\rm log}_2\hspace{0.1cm} (4/3) +
-\cdot {1}/{8} \cdot {\rm log}_2\hspace{0.1cm}(8)  \hspace{0.15cm} \underline {= 1.06 \,{\rm bit/ternary symbol}}
+\cdot {1}/{8} \cdot {\rm log}_2\hspace{0.1cm}(8)  \hspace{0.15cm} \underline {= 1.06 \,{\rm bit/ternary \ symbol}}
   \hspace{0.05cm}.$$
@@ Line 138: / Line 138: @@
 *For both parameter combinations, however, the same applies:
 :$$H_0  = 1.585 \,{\rm bit/symbol}\hspace{0.05cm},\hspace{0.2cm}H_{\rm C} =
-  \lim_{k \rightarrow \infty } H_k = 0.811 \,{\rm bit/Symbol}
+  \lim_{k \rightarrow \infty } H_k = 0.811 \,{\rm bit/symbol}
   \hspace{0.05cm}.$$
 It follows from this: <br>
-*If one considers two message sources&nbsp; $\rm Q1$&nbsp; and&nbsp; $\rm Q2$&nbsp; with the same symbol range&nbsp; $M$ &nbsp; &#8658; &nbsp; decision content&nbsp; $H_0 = \rm const.$, whereby the first-order entropy approximation&nbsp; $\rm Q1$&nbsp; is clearly greater for source&nbsp; $(H_1)$&nbsp; than for source&nbsp; $\rm Q2$, one cannot conclude from this by any means that the entropy of&nbsp; $\rm Q1$&nbsp; is actually greater than the entropy of $\rm Q2$.&nbsp;
+*If one considers two message sources&nbsp; $\rm Q1$&nbsp; and&nbsp; $\rm Q2$&nbsp; with the same symbol set size&nbsp; $M$ &nbsp; &#8658; &nbsp; decision content&nbsp; $H_0 = \rm const.$, whereby the first order entropy approximation&nbsp; $(H_1)$&nbsp;  is clearly greater for source&nbsp; $\rm Q1$&nbsp; than for source&nbsp; $\rm Q2$, one cannot conclude from this by any means that the entropy of&nbsp; $\rm Q1$&nbsp; is actually greater than the entropy of $\rm Q2$.&nbsp;
 *Rather, one must
 :* calculate enough entropy approximations&nbsp; $H_1$,&nbsp; $H_2$,&nbsp; $H_3$,&nbsp; ...  for both sources and
-:* determine from them (graphically or analytically) the limit value of&nbsp; $H_k$&nbsp; for&nbsp; $k \to \infty$&nbsp; .
+:* determine from them&nbsp; (graphically or analytically)&nbsp; the limit value of&nbsp; $H_k$&nbsp; for&nbsp; $k \to \infty$.
-*Only then is a final statement about the entropy ratios possible.
+*Only then a final statement about the entropy ratios is possible.
 {{ML-Fuß}}

@@ Line 36: / Line 36: @@
 *Reference is made in particular to the page&nbsp;  [[Information_Theory/Discrete_Sources_with_Memory#The_entropy_of_the_AMI_code|The entropy of the AMI code]].
-*In general, the following relations exist between the decision content&nbsp; $H_0$,&nbsp; the entropy&nbsp; $H$&nbsp; $($here equal to&nbsp; $H_{\rm C})$&nbsp; und den Entropienäherungen:
+*In general, the following relations exist between the decision content&nbsp; $H_0$,&nbsp; the entropy&nbsp; $H$&nbsp; $($here equal to&nbsp; $H_{\rm C})$&nbsp; and the entropy approximations:
 :$$H \le \ \text{...} \  \le H_3 \le H_2 \le H_1 \le H_0
   \hspace{0.05cm}.$$
-*In&nbsp; [[Aufgaben:1.4_Entropienäherungen_für_den_AMI-Code|task 1.4]]&nbsp; for equally probable symbols&nbsp; $\rm L$&nbsp; and&nbsp; $\rm H$&nbsp; the entropy approximations were calculated as follows (each in "bit/symbol"):
+*In&nbsp; [[Aufgaben:Exercise_1.4:_Entropy_Approximations_for_the_AMI_Code|Exercise 1.4]]&nbsp;&nbsp;  the entropy approximations were calculated for equally probable symbols&nbsp; $\rm L$&nbsp; and&nbsp; $\rm H$&nbsp; as follows (each in "bit/symbol"):
 :$$H_1 = 1.500\hspace{0.05cm},\hspace{0.2cm} H_2 = 1.375\hspace{0.05cm},\hspace{0.2cm}H_3 = 1.292
   \hspace{0.05cm}.$$

@@ Line 34: / Line 34: @@
 ''Hints:''
 *This task belongs to the chapter&nbsp; [[Information_Theory/Discrete_Sources_with_Memory|Discrete Sources with Memory]].
-*Reference is made in particular to the page&nbsp;  [[Information_Theory/Discrete_Sources_with_Memory#The_entropy_of_the_AMI_code]].
+*Reference is made in particular to the page&nbsp;  [[Information_Theory/Discrete_Sources_with_Memory#The_entropy_of_the_AMI_code|The entropy of the AMI code]].
 *In general, the following relations exist between the decision content&nbsp; $H_0$,&nbsp; the entropy&nbsp; $H$&nbsp; $($here equal to&nbsp; $H_{\rm C})$&nbsp; und den Entropienäherungen:

@@ Line 4: / Line 4: @@
 [[File:P_ID2249__Inf_A_1_4.png|right|frame|Binary source signal (top) and <br>ternary encoder signal (bottom)]]
-We assume similar prerequisites as in&nbsp; [[Aufgaben:1.4_Entropienäherungen_für_den_AMI-Code|task 1.4]]&nbsp;: &nbsp;
+We assume similar prerequisites as in&nbsp; [[Aufgaben:Exercise_1.4:_Entropy_Approximations_for_the_AMI_Code|Exercise 1.4]]&nbsp;: &nbsp;
-A binary source provides the source symbol sequence&nbsp; $\langle q_\nu \rangle$&nbsp;  with&nbsp; $q_\nu \in \{ {\rm L}, {\rm H} \}$, where there are no statistical ties between the individual sequence elements.
+A binary source provides the source symbol sequence&nbsp; $\langle q_\nu \rangle$&nbsp;  with&nbsp; $q_\nu \in \{ {\rm L}, {\rm H} \}$, where there are no statistical bindings between the individual sequence elements.
 For the symbol probabilities, let:
@@ Line 14: / Line 14: @@
-The presented code signal&nbsp; $c(t)$&nbsp; and the corresponding symbol sequence&nbsp; $\langle c_\nu \rangle$&nbsp;  with&nbsp; $c_\nu \in \{{\rm P}, {\rm N}, {\rm M}  \}$&nbsp; results from the AMI coding&nbsp; (<i>Alternate Mark Inversion</i>)&nbsp; according to the following rule:
+The presented coded signal&nbsp; $c(t)$&nbsp; and the corresponding code symbol sequence&nbsp; $\langle c_\nu \rangle$&nbsp;  with&nbsp; $c_\nu \in \{{\rm P}, {\rm N}, {\rm M}  \}$&nbsp; results from the AMI coding&nbsp; ("Alternate Mark Inversion")&nbsp; according to the following rule:
-* The binary symbol&nbsp; $\rm L$ &nbsp;&rArr;&nbsp; <i>Low</i>&nbsp; is always represented by the ternary symbol&nbsp; $\rm N$ &nbsp;&rArr;&nbsp; <i>Null</i>&nbsp;.
+* The binary symbol&nbsp; $\rm L$ &nbsp; &rArr; &nbsp; "Low"&nbsp; is always represented by the ternary symbol&nbsp; $\rm N$ &nbsp; &rArr; &nbsp; "German: Null"&nbsp; &rArr; &nbsp;"Zero".
-* The binary symbol&nbsp; $\rm H$ &nbsp;&rArr;&nbsp; <i>High</i>&nbsp; is also coded deterministically but alternately (hence the name "AMI") by the symbols&nbsp; $\rm P$ &nbsp;&rArr;&nbsp; <i>Plus</i>&nbsp; and&nbsp; $\rm M$ &nbsp;&rArr;&nbsp; <i>Minus</i>&nbsp;.
+* The binary symbol&nbsp; $\rm H$ &nbsp; &rArr; &nbsp; "High"&nbsp; is also encoded deterministically but alternately&nbsp; (hence the name "Alternate Mark Inversion")&nbsp; by the symbols&nbsp; $\rm P$ &nbsp;&rArr;&nbsp; "Plus"&nbsp; and&nbsp; $\rm M$ &nbsp;&rArr;&nbsp; "Minus".
 In this task, the decision content&nbsp; $H_0$&nbsp; and the resulting entropy&nbsp; $H_{\rm C}$&nbsp; the code symbol sequence&nbsp; $\langle c_\nu \rangle$&nbsp; are to be determined for the three parameter sets mentioned above.&nbsp; The relative redundancy of the code sequence results from this according to the equation
 :$$r_{\rm C} = \frac{H_{\rm 0}-H_{\rm C}}{H_{\rm C}}
   \hspace{0.05cm}.$$
@@ Line 31: / Line 33: @@
 ''Hints:''
-*The task belongs to the chapter&nbsp; [[Information_Theory/Nachrichtenquellen_mit_Gedächtnis|Sources with Memory]].
+*This task belongs to the chapter&nbsp; [[Information_Theory/Discrete_Sources_with_Memory|Discrete Sources with Memory]].
 *Reference is made in particular to the page&nbsp;  [[Information_Theory/Nachrichtenquellen_mit_Gedächtnis#The_Entropy_of_the_AMI_code|The Entropy of the AMI code]].

@@ Line 17: / Line 17: @@
 * The binary symbol&nbsp; $\rm L$ &nbsp;&rArr;&nbsp; <i>Low</i>&nbsp; is always represented by the ternary symbol&nbsp; $\rm N$ &nbsp;&rArr;&nbsp; <i>Null</i>&nbsp;.
-* The binary symbol&nbsp; $\rm H$ &nbsp;&rArr;&nbsp; <i>High</i>&nbsp; is also coded deterministically but alternately (hence the name &bdquo;AMI&rdquo;) by the symbols&nbsp; $\rm P$ &nbsp;&rArr;&nbsp; <i>Plus</i>&nbsp; and&nbsp; $\rm M$ &nbsp;&rArr;&nbsp; <i>Minus</i>&nbsp;.
+* The binary symbol&nbsp; $\rm H$ &nbsp;&rArr;&nbsp; <i>High</i>&nbsp; is also coded deterministically but alternately (hence the name "AMI&rdquo;) by the symbols&nbsp; $\rm P$ &nbsp;&rArr;&nbsp; <i>Plus</i>&nbsp; and&nbsp; $\rm M$ &nbsp;&rArr;&nbsp; <i>Minus</i>&nbsp;.
@@ Line 37: / Line 37: @@
 :$$H \le \ \text{...} \  \le H_3 \le H_2 \le H_1 \le H_0
   \hspace{0.05cm}.$$
-*In&nbsp; [[Aufgaben:1.4_Entropienäherungen_für_den_AMI-Code|task 1.4]]&nbsp; for equally probable symbols&nbsp; $\rm L$&nbsp; and&nbsp; $\rm H$&nbsp; the entropy approximations were calculated as follows (each in &bdquo;bit/symbol&rdquo;):
+*In&nbsp; [[Aufgaben:1.4_Entropienäherungen_für_den_AMI-Code|task 1.4]]&nbsp; for equally probable symbols&nbsp; $\rm L$&nbsp; and&nbsp; $\rm H$&nbsp; the entropy approximations were calculated as follows (each in "bit/symbol&rdquo;):
 :$$H_1 = 1.500\hspace{0.05cm},\hspace{0.2cm} H_2 = 1.375\hspace{0.05cm},\hspace{0.2cm}H_3 = 1.292
   \hspace{0.05cm}.$$