Aufgaben:Exercise 3.13: Code Rate and Reliability - Revision history

Guenter at 11:57, 24 September 2021

2021-09-24T11:57:29Z

Noah at 09:11, 24 September 2021

2021-09-24T09:11:14Z

Guenter at 15:39, 22 September 2021

2021-09-22T15:39:27Z

Guenter at 15:28, 22 September 2021

2021-09-22T15:28:12Z

Guenter at 15:25, 22 September 2021

2021-09-22T15:25:25Z

Guenter at 15:23, 22 September 2021

2021-09-22T15:23:45Z

Guenter at 15:10, 22 September 2021

2021-09-22T15:10:49Z

Guenter at 14:47, 22 September 2021

2021-09-22T14:47:45Z

Guenter at 14:47, 22 September 2021

2021-09-22T14:47:13Z

Noah at 12:27, 20 September 2021

2021-09-20T12:27:55Z

Show changes

← Older revision		Revision as of 11:57, 24 September 2021
Line 117:		Line 117:


−	[[Category:Information Theory: Exercises\|^3.3 ~~Anwendung auf DSÜ-Kanäle~~^]]	+	[[Category:Information Theory: Exercises\|^3.3 Application to Digital Signal Transmission^]]

← Older revision		Revision as of 09:11, 24 September 2021
Line 1:		Line 1:

−	{{quiz-Header\|Buchseite=~~Informationstheorie~~/~~Anwendung auf die Digitalsignalübertragung~~	+	{{quiz-Header\|Buchseite=Information_Theory/Application_to_Digital_Signal_Transmission
	}}		}}

@@ Line 70: / Line 70: @@
 '''(1)'''&nbsp; According to the given equation:
 :$$ p_{\rm B,\hspace{0.05cm} min} = H_{\rm bin}^{-1} \left (1 - \frac{C}{R} \right) = H_{\rm bin}^{-1} (0.75) \hspace{0.05cm}.$$
-From the graph on the data page (blue marking) we can read:  &nbsp; $ p_{\rm B,\hspace{0.05cm} min} \hspace{0.15cm} \underline {=0.215} \hspace{0.05cm}.$
+*From the graph on the data page&nbsp; (blue marking)&nbsp; we can read:  &nbsp;
+:$$ p_{\rm B,\hspace{0.05cm} min} \hspace{0.15cm} \underline {=0.215} \hspace{0.05cm}.$$
@@ Line 79: / Line 79: @@
+'''(3)'''&nbsp;The&nbsp; <u>proposed solutions 2 and 3</u> are correct:
 *For the binary entropy function, by definition:
 :$$H_{\rm bin}( p) = p \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{p} + (1-p) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{1-p}\hspace{0.05cm}.$$
-*Both terms are positive.&nbsp; From this follows the <u>proposed solution 2</u>: &nbsp; $H_{\rm bin}(p) = p · \log_2 \, (1/p)$.
+*Both terms are positive.&nbsp; From this follows the <u>proposed solution 2</u>: &nbsp; $H_{\rm bin}(p) > p · \log_2 \, (1/p)$.
 *The difference is given by the second term of the binary entropy function:
 :$$ H_{\rm bin}( p) - p \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{p} = (1-p) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{1-p}\hspace{0.05cm}.$$
 *This term becomes smaller the smaller&nbsp; $p$&nbsp; is.
-*<u>Proposed solution 3</u> is therefore also correct, as the following calculations show:
+*The&nbsp; <u>proposed solution 3</u> is therefore also correct, as the following calculations show:
 :$$ p_{\rm B} = 10^{-3}\text{:} \hspace{0.3cm} 0.999 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.999}= 1.4420 \cdot 10^{-3} \hspace{0.05cm},$$
 :$$p_{\rm B} = 10^{-4}\text{:} \hspace{0.3cm} 0.9999 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.9999}= 1.4427 \cdot 10^{-4} \hspace{0.05cm},$$
 :$$p_{\rm B} = 10^{-5}\text{:} \hspace{0.3cm} 0.99999 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.99999}= 1.4427 \cdot 10^{-5} \hspace{0.05cm}.$$
 '''(4)'''&nbsp; <u>All proposed solutions</u> are correct:
-*The expression&nbsp; $R/C$&nbsp; gives the upper bound according to the inverse channel coding theorem.&nbsp; For&nbsp; $p_{\rm B} = 10^{ –3 }$&nbsp;, the following bound is obtained:
+*The expression&nbsp; $R/C$&nbsp; gives the upper bound according to the inverse channel coding theorem.&nbsp;
 :$$R/C ≤ 1.01154  \hspace{0.5cm} ⇒ \hspace{0.5cm}  R/C - 1 ≤ 1.154 · 10^{ –2 }.$$
 * Proposition 2 takes into account the approximation according to subtask&nbsp; '''(3)'''&nbsp;.&nbsp; Since the denominator is now increased,&nbsp; $R′/C < R/C$, for example, applies for
 :$$p_{\rm B} = 10^{ –3 }\text{:}\hspace{0.5cm} R′/C = 1.01007 · 10^{ –2 }.$$
 : This is also an upper bound, somewhat safer than the first bound&nbsp; $R/C$.
-* The bound&nbsp; $R′′ < R′$&nbsp; is obtained by replacing&nbsp; $1/(1 – ε)$&nbsp; by&nbsp; $1 + ε$&nbsp; ersetzt&nbsp; $(ε$&nbsp; is positive$)$.&nbsp; For example, for&nbsp; $p_{\rm B} = 10^{–3}$&nbsp; one now obtains
+* The bound&nbsp; $R′′ < R′$&nbsp; is obtained by replacing&nbsp; $1/(1 – ε)$&nbsp; by&nbsp; $1 + ε$&nbsp; $(ε$&nbsp; is positive$)$.&nbsp; For example, for&nbsp; $p_{\rm B} = 10^{–3}$&nbsp; one obtains
 :$$R′′/C = 1.00997 \hspace{0.5cm}  ⇒ \hspace{0.5cm}  R′′/C - 1 ≤ 0.997 · 10^{–2}.$$
-* $R′′′$&nbsp; according to the last suggestion is identical to&nbsp; $R′′$&nbsp; and well suited for rollover calculations with integer exponent&nbsp; $i$&nbsp;.&nbsp; <br>For the logarithm to the base ten, the numerical value&nbsp; $\lg(2) ≈ 0.30103 applies.$
+* $R′′′$&nbsp; according to the last suggestion is identical to&nbsp; $R′′$&nbsp; and well suited for rollover calculations with integer exponent&nbsp; $i$&nbsp;.&nbsp; <br>For the logarithm to the base ten, the numerical value&nbsp; $\lg(2) ≈ 0.30103$&nbsp; applies.
@@ Line 110: / Line 109: @@
 * of the first bound&nbsp; $(R/C-1)$&nbsp; and
 * of the last approximation&nbsp;  $(R'''/C-1)$.&nbsp;
 One can see the good agreement of both specifications.

@@ Line 44: / Line 44: @@
 $p_{\text{B, min}} \ = \ $ { 0.215 3% }
-{At what rate&nbsp; $R$&nbsp; can you transmit over a channel with channel capacity&nbsp; $\underline{C = 0.5 \ \rm (bit)}$&nbsp; for a given marginal error probability&nbsp; $p_{\rm B}$&nbsp;?
+{At what rate&nbsp; $R$&nbsp; you can transmit over a channel with capacity&nbsp; $\underline{C = 0.5 \ \rm (bit)}$&nbsp; for a given marginal error probability&nbsp; $p_{\rm B}$&nbsp;?
 |type="{}"}
 $p_{\rm B} = 0.10\text{:} \hspace{0.5cm}R_{\rm max} \ = \ $ { 0.942 3% }
@@ Line 50: / Line 50: @@
-{What is the relation between&nbsp;$H_{\rm bin}(p)$&nbsp; and the approximation&nbsp;$p · \log_2 (1/p)$?
+{What is the relation between&nbsp;$H_{\rm bin}(p)$&nbsp; and the approximation&nbsp; $p · \log_2 (1/p)$?
 |type="[]"}
 - &nbsp;$H_{\rm bin}(p) < p · \log_2 \, (1/p)$ is valid.

@@ Line 31: / Line 31: @@
 *The exercise belongs to the chapter&nbsp; [[Information_Theory/Anwendung_auf_die_Digitalsignalübertragung|Application to digital signal transmission]].
 *Reference is made in particular to the page&nbsp;    [[Information_Theory/Anwendung_auf_die_Digitalsignalübertragung#Rate.2C_channel_capacity_and_bit_error_probability|Rate, channel capacity and bit error probability]].
-*The values of the binary entropy function are provided, for example, by the (German language) interactive SWF applet<br> &nbsp; &nbsp; [[Applets:Entropien_von_Nachrichtenquellen|Entropien und Näherungen von digitalen Nachrichtenquellen]] &nbsp; &rArr; &nbsp;  "Entropy and approximations of digital sources".
+*The values of the binary entropy function are provided, for example, by the&nbsp; (German language)&nbsp; interactive SWF applet<br> &nbsp; &nbsp; [[Applets:Entropien_von_Nachrichtenquellen|Entropien und Näherungen von digitalen Nachrichtenquellen]] &nbsp; &rArr; &nbsp;  "Entropies and approximations of digital sources".

← Older revision		Revision as of 14:47, 22 September 2021
Line 9:		Line 9:

	The inverse of the channel coding theorem states that no error-free transmission is possible with a rate  $R > C$.  There is then no coding system with a vanishingly small error probability, no matter how elaborate and sophisticated the coding.		The inverse of the channel coding theorem states that no error-free transmission is possible with a rate  $R > C$.  There is then no coding system with a vanishingly small error probability, no matter how elaborate and sophisticated the coding.
		+

	Rather, two bounds can be specified for the case  $R > C$ :		Rather, two bounds can be specified for the case  $R > C$ :

@@ Line 4: / Line 4: @@
 [[File:P_ID2805__Inf_A_3_12.png|right|frame|Binary entropy function]]
-&nbsp; [https://en.wikipedia.org/wiki/Claude_Shannon Claude E. Shannon]&nbsp; channel coding theorem states, among other things, that a channel can be used to transmit with an arbitrarily small block error probability as long as the code rate&nbsp; $R$&nbsp; is not greater than the channel capacity&nbsp; $C$.&nbsp; However, this result can only be achieved with channel coding for very large block lengths:&nbsp; $n → ∞$, which is associated with an arbitrarily large effort.
+[https://en.wikipedia.org/wiki/Claude_Shannon Claude E. Shannon's]&nbsp; channel coding theorem states,&nbsp; among other things,&nbsp; that a channel can be used to transmit with an arbitrarily small block error probability as long as the code rate&nbsp; $R$&nbsp; is not greater than the channel capacity&nbsp; $C$.&nbsp; However,&nbsp; this result can only be achieved with channel coding for very large block lengths:&nbsp; $n → ∞$, which is associated with an arbitrarily large effort.
 This statement is based on information-theoretical laws that Shannon himself established.&nbsp; However, Shannon does not say what this "infinitely good" channel coding must look like, he only proves that it exists.
-The inverse of the channel coding theorem states that no error-free transmission is possible with a rate&nbsp; $R > C$&nbsp; keine fehlerfreie Übertragung möglich ist.&nbsp; There is then no coding system with a vanishingly small error probability, no matter how elaborate and sophisticated the coding.
+The inverse of the channel coding theorem states that no error-free transmission is possible with a rate&nbsp; $R > C$.&nbsp; There is then no coding system with a vanishingly small error probability, no matter how elaborate and sophisticated the coding.
 Rather, two bounds can be specified for the case&nbsp; $R > C$&nbsp;:
-*If one transmits via a&nbsp; ''discrete memoryless channel''&nbsp; $\rm (DMC)$&nbsp; with a rate&nbsp; $R$&nbsp; greater than the channel capacity&nbsp; $C$, there is a lower bound for the bit error probability:
+*If one transmits via a&nbsp; "discrete memoryless channel"&nbsp; $\rm (DMC)$&nbsp; with a rate&nbsp; $R$&nbsp; greater than the channel capacity&nbsp; $C$,&nbsp; there is a lower bound for the bit error probability:
 :$$ p_{\rm B} \ge H_{\rm bin}^{-1} \left (1 - {C}/{R} \right) > 0 \hspace{0.05cm}.$$
-*If the bit error probability is not to exceed the value&nbsp; $p_{\rm B}$&nbsp; after the best possible decoding, the rate must not exceed a certain limit:
+*If the bit error probability is not to exceed the value&nbsp; $p_{\rm B}$&nbsp; after best possible decoding, the rate must not exceed a certain limit:
 :$$ R \le \frac{C}{1 - H_{\rm bin}( p_{\rm B})} \hspace{0.05cm}.$$
-In this exercise, these equations are to be calculated using the&nbsp; [[Information_Theory/Ged%C3%A4chtnislose_Nachrichtenquellen#Binary_entropy_function|binary entropy function]]
+In this exercise,&nbsp; these equations are to be evaluated numerically using the&nbsp; [[Information_Theory/Ged%C3%A4chtnislose_Nachrichtenquellen#Binary_entropy_function|binary entropy function]]
-:$$ H_{\rm bin}( p) = p \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{p} + (1-p) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{1-p}$$
+:$$ H_{\rm bin}( p) = p \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{p} + (1-p) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{1-p}.$$
-can be evaluated numerically.&nbsp; This is sketched above.&nbsp; Because of&nbsp; $0 < p_B ≤ 1$&nbsp; and&nbsp; $0 < C/R < 1$&nbsp; the argument of the function&nbsp; $H_{\rm bin}(⋅)$&nbsp; nd its inverse function&nbsp; $H_{\rm bin}^{ –1 }(⋅)$&nbsp; is always between&nbsp; $0$&nbsp; and&nbsp; $1$.
+$H_{\rm bin}(p)$&nbsp; is sketched above.&nbsp; Because of&nbsp; $0 < p_B ≤ 1$&nbsp; and&nbsp; $0 < C/R < 1$&nbsp; the argument of the function&nbsp; $H_{\rm bin}(⋅)$&nbsp; and its inverse&nbsp; $H_{\rm bin}^{ –1 }(⋅)$&nbsp; is always between&nbsp; $0$&nbsp; and&nbsp; $1$.
@@ Line 50: / Line 50: @@
 {What is the relation between&nbsp;$H_{\rm bin}(p)$&nbsp; and the approximation&nbsp;$p · \log_2 (1/p)$?
 |type="[]"}
-- &nbsp; &nbsp;$H_{\rm bin}(p) < p · \log_2 \, (1/p)$ is valid.
+- &nbsp;$H_{\rm bin}(p) < p · \log_2 \, (1/p)$ is valid.
-+ &nbsp;$H_{\rm bin}(p) = p · \log_2 \, (1/p)$ is valid.
++ &nbsp;$H_{\rm bin}(p) > p · \log_2 \, (1/p)$ is valid.
 + $H_{\rm bin}(p) - p · \log_2 \, (1/p)$&nbsp; becomes smaller the smaller&nbsp;$p$&nbsp; is.