Aufgaben:Exercise 3.10Z: BSC Channel Capacity - Revision history

Guenter at 15:07, 27 September 2021

2021-09-27T15:07:16Z

Guenter at 11:55, 24 September 2021

2021-09-24T11:55:43Z

Guenter at 10:34, 22 September 2021

2021-09-22T10:34:35Z

Guenter at 10:21, 22 September 2021

2021-09-22T10:21:25Z

Guenter at 10:19, 22 September 2021

2021-09-22T10:19:33Z

Guenter at 10:18, 22 September 2021

2021-09-22T10:18:09Z

Javier: Text replacement - "optimis" to "optimiz"

2021-09-21T12:51:00Z

Text replacement - "optimis" to "optimiz"

Noah at 11:15, 14 September 2021

2021-09-14T11:15:42Z

Show changes

Guenter: Guenter moved page Aufgaben:Aufgabe 3.10Z: BSC–Kanalkapazität to Aufgaben:Exercise 3.10Z: BSC Channel Capacity

2021-07-22T14:51:34Z

Guenter moved page Aufgabe 3.10Z: BSC–Kanalkapazität to Exercise 3.10Z: BSC Channel Capacity

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

2021-05-28T14:32:00Z

Text replacement - "”" to """

@@ Line 3: / Line 3: @@
 }}
-[[File:P_ID2789__Inf_Z_3_9.png|right|frame|Entropies of&nbsp; "BC"&nbsp; and&nbsp; "BSC"]]
+[[File:EN_Inf_Z_3_9_A.png|right|frame|Entropies of&nbsp; "BC"&nbsp; and&nbsp; "BSC"]]
 The channel capacity&nbsp; $C$&nbsp; was defined by&nbsp; [https://en.wikipedia.org/wiki/Claude_Shannon Claude E. Shannon]&nbsp; as the maximum mutual information, whereby the maximization refers solely to the source statistics:
 :$$ C = \max_{P_X(X)} \hspace{0.15cm} I(X;Y) \hspace{0.05cm}$$

← Older revision		Revision as of 11:55, 24 September 2021
Line 104:		Line 104:


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

@@ Line 62: / Line 62: @@
 ===Solution===
 {{ML-Kopf}}
-'''(1)'''&nbsp; <u>Proposed solution 2</u> is correct, as the following calculation shows:
+'''(1)'''&nbsp; The&nbsp; <u>proposed solution 2</u> is correct, as the following calculation shows:
 :$$H(Y \hspace{-0.1cm}\mid \hspace{-0.1cm} X) = p_0 \cdot (1 - \varepsilon) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{1 - \varepsilon} + p_0 \cdot \varepsilon \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{\varepsilon} +p_1 \cdot \varepsilon \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{\varepsilon} + p_1 \cdot (1 - \varepsilon) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{1 - \varepsilon} $$
 :$$\Rightarrow \hspace{0.3cm} H(Y \hspace{-0.1cm}\mid \hspace{-0.1cm} X) =  (p_0 + p_1) \cdot \left [ \varepsilon \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{\varepsilon} + (1 - \varepsilon) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{1 - \varepsilon} \right ] \hspace{0.05cm}.$$
-*With&nbsp; $p_0 + p_1 = 1$&nbsp;  and the binary entropy function&nbsp; $H_{\rm bin}$&nbsp; , one obtains the proposed result: &nbsp; $H(Y \hspace{-0.1cm}\mid \hspace{-0.1cm} X) = H_{\rm bin}(\varepsilon)\hspace{0.05cm}.$
+*With&nbsp; $p_0 + p_1 = 1$&nbsp;  and the binary entropy function&nbsp; $H_{\rm bin}$,&nbsp;  one obtains the proposed result: &nbsp; $H(Y \hspace{-0.1cm}\mid \hspace{-0.1cm} X) = H_{\rm bin}(\varepsilon)\hspace{0.05cm}.$
-*For&nbsp; $ε = 0.1$&nbsp; we get&nbsp; $H(Y|X) = 0.4690 \ \rm bit$.&nbsp; The same value stands for all&nbsp; $p_0$&nbsp; in the given table.
+*For&nbsp; $ε = 0.1$&nbsp; we get&nbsp; $H(Y|X) = 0.4690 \ \rm bit$.&nbsp; The same value stands for&nbsp; $p_0=0.50$&nbsp; in the given table.
-*From the table one can also see that for the BSC model (blue background) as well as for the more general (asymmetric) BC model (red background) the equivocation&nbsp; $H(X|Y)$&nbsp; depends on the source symbol probabilities&nbsp; $p_0$&nbsp; and&nbsp; $p_1$&nbsp;. It follows that proposed solution 1 cannot be correct.
+*From the table one can also see that for the BSC model (blue background) as well as for the more general (asymmetric) BC model (red background) <br>the equivocation&nbsp; $H(X|Y)$&nbsp; depends on the source symbol probabilities&nbsp; $p_0$&nbsp; and&nbsp; $p_1$.&nbsp; It follows that proposed solution 1 cannot be correct.
 *The irrelevance&nbsp; $H(Y|X)$&nbsp; is independent &nbsp; of the source statistics, so that solution proposal 3 can also be excluded.
@@ Line 74: / Line 74: @@
 '''(2)'''&nbsp;  <u>All given alternative solutions</u> are correct:
-*The channel capacity is defined as the maximum mutual information, where the maximisation has to be done with respect to&nbsp; $P_X = (p_0, p_1)$&nbsp;:
+*The channel capacity is defined as the maximum mutual information, where the maximization has to be done with respect to&nbsp; $P_X = (p_0, p_1)$&nbsp;:
 :$$C = \max_{P_X(X)} \hspace{0.15cm} I(X;Y) \hspace{0.05cm}.$$
 *The equation is generally valid, i.e. also for the unbalanced binary channel highlighted in red.
-*The mutual information can be calculated, for example, as&nbsp; $I(X;Y) = H(Y) - H(Y \hspace{-0.1cm}\mid \hspace{-0.1cm} X)\hspace{0.05cm}$,&nbsp; where according to subtask&nbsp; '''(1)'''&nbsp; the term&nbsp; $H(Y \hspace{-0.1cm}\mid \hspace{-0.1cm} X)\hspace{0.05cm}$&nbsp; is independent of&nbsp; $p_0$&nbsp; or&nbsp; $p_1 = 1- p_0$&nbsp;.
+*The mutual information can be calculated, for example, as&nbsp; $I(X;Y) = H(Y) - H(Y \hspace{-0.1cm}\mid \hspace{-0.1cm} X)\hspace{0.05cm}$,&nbsp; <br>where according to subtask&nbsp; '''(1)'''&nbsp; the term&nbsp; $H(Y \hspace{-0.1cm}\mid \hspace{-0.1cm} X)\hspace{0.05cm}$&nbsp; is independent of&nbsp; $p_0$&nbsp; or&nbsp; $p_1 = 1- p_0$&nbsp;.
 *The maximum mutual information thus results exactly when the sink entropy&nbsp; $H(Y)$&nbsp; is maximum.&nbsp; This is the case for&nbsp; $p_0 = p_1 = 0.5$:
 :$$H(X) = H(Y) =  1 \ \rm bit.$$
@@ Line 91: / Line 91: @@
 * for&nbsp; $ε = 0.1$&nbsp; (considered so far): <br> &nbsp; &nbsp; $C = 0.531\ \rm  (bit)$  &nbsp; &rArr; &nbsp;   dot with green filling,
 * for&nbsp; $ε = 0.5$&nbsp; (completely disturbed): <br> &nbsp; &nbsp; $C = 0\ \rm  (bit)$   &nbsp; &rArr; &nbsp;  dot with grey filling.
 '''(4)'''&nbsp;  From the graph one can see that from an information-theoretical point of view&nbsp; $ε = 1$&nbsp; is identical to&nbsp; $ε = 0$&nbsp;:
 :$$C_{\rm BSC} \big |_{\hspace{0.05cm}\varepsilon \hspace{0.05cm} = \hspace{0.05cm}1} \hspace{0.05cm}= C_{\rm BSC} \big |_{\hspace{0.05cm}\varepsilon \hspace{0.05cm} = \hspace{0.05cm}0} \hspace{0.15cm} \underline {=1\,{\rm (bit)}} \hspace{0.05cm}.$$
-*The channel only carries out a renaming here.&nbsp; This is called "mapping".
+*The channel only carries out a renaming here.&nbsp; This is called&nbsp; "mapping".
 *Every&nbsp; $0$&nbsp; becomes a&nbsp; $1$&nbsp; and every&nbsp; $1$&nbsp; becomes a&nbsp; $0$.&nbsp; Accordingly:
 :$$C_{\rm BSC} \big |_{\hspace{0.05cm}\varepsilon \hspace{0.05cm} = \hspace{0.05cm}0.9} \hspace{0.05cm}= C_{\rm BSC} \big |_{\hspace{0.05cm}\varepsilon \hspace{0.05cm} = \hspace{0.05cm}0.1} \hspace{0.15cm} \underline {=0.531\,{\rm (bit)}} \hspace{0.05cm}$$

@@ Line 26: / Line 26: @@
 Hints:
 *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#Kanalkapazit.C3.A4t_eines_Bin.C3.A4rkanals|Channel capacity of a binary channel]].
+*Reference is made in particular to the page&nbsp;    [[Information_Theory/Application_to_Digital_Signal_Transmission#Channel_capacity_of_a_binary_channel|Channel capacity of a binary channel]].

@@ Line 13: / Line 13: @@
 :$$C_{\rm BC} = \hspace{-0.05cm} \max_{P_X(X)} \hspace{0.1cm} I(X;Y) \big |_{p_0 \hspace{0.05cm} = \hspace{0.05cm}0.55} \hspace{0.05cm}=\hspace{0.05cm} 0.5779\,{\rm bit} \hspace{0.05cm}.$$
-In the lower graph (blue background), the same information-theoretical quantities are given for the&nbsp; [[Channel_Coding/Kanalmodelle_und_Entscheiderstrukturen#Binary_Symmetric_Channel_.E2.80.93_BSC|Binary Symmetric Channel]]&nbsp;  $\rm (BSC)$&nbsp; with the falsification probabilities&nbsp; $ε_0 = ε_1 = ε = 0.1$,&nbsp; which was also assumed for&nbsp; [[Aufgaben:3.10_Transinformation_beim_BSC| Exercise 3.10]].
+In the lower graph (blue background), the same information-theoretical quantities are given for the&nbsp; [[Channel_Coding/Kanalmodelle_und_Entscheiderstrukturen#Binary_Symmetric_Channel_.E2.80.93_BSC|Binary Symmetric Channel]]&nbsp;  $\rm (BSC)$&nbsp; with the falsification probabilities&nbsp; $ε_0 = ε_1 = ε = 0.1$,&nbsp; which was also assumed for&nbsp; [[Aufgaben:Exercise_3.10:_Mutual_Information_at_the_BSC| Exercise 3.10]].
 In the present exercise you are

@@ Line 3: / Line 3: @@
 }}
-[[File:P_ID2789__Inf_Z_3_9.png|right|frame|Entropies of the „BC” and „BSC” models]]
+[[File:P_ID2789__Inf_Z_3_9.png|right|frame|Entropies of&nbsp; "BC"&nbsp; and&nbsp; "BSC"]]
-The channel capacity&nbsp; $C$&nbsp; was defined by&nbsp; [https://en.wikipedia.org/wiki/Claude_Shannon Claude E. Shannon]&nbsp; as the maximum mutual information, whereby the maximisation refers solely to the source statistics:
+The channel capacity&nbsp; $C$&nbsp; was defined by&nbsp; [https://en.wikipedia.org/wiki/Claude_Shannon Claude E. Shannon]&nbsp; as the maximum mutual information, whereby the maximization refers solely to the source statistics:
 :$$ C = \max_{P_X(X)} \hspace{0.15cm} I(X;Y) \hspace{0.05cm}$$
 In the binary channel with the probability function&nbsp; $P_X(X) = \big [p_0, \ p_1 \big]$&nbsp; only one parameter is optimizable, for example &nbsp; $p_0$.&nbsp; The probability for a&nbsp; $1$&nbsp; is thus also fixed: &nbsp;  $p_1 = 1 - p_0.$
@@ Line 10: / Line 10: @@
 The upper graph (reddish background) summarises the results for the&nbsp; [[Information_Theory/Anwendung_auf_die_Digitalsignalübertragung#Channel_capacity_of_a_binary_channel|asymmetric binary channel]]&nbsp; with&nbsp; $ε_0 = 0.01$&nbsp; and&nbsp; $ε_1 = 0.2$&nbsp;, which was also considered in the theory section.
-The maximisation leads to the result&nbsp; $p_0 = 0.55$ &nbsp; &rArr; &nbsp; $p_1 = 0.45$,&nbsp;, and one obtains for the channel capacity:
+The maximization leads to the result&nbsp; $p_0 = 0.55$ &nbsp; &rArr; &nbsp; $p_1 = 0.45$,&nbsp; and one obtains for the channel capacity:
 :$$C_{\rm BC} = \hspace{-0.05cm} \max_{P_X(X)} \hspace{0.1cm} I(X;Y) \big |_{p_0 \hspace{0.05cm} = \hspace{0.05cm}0.55} \hspace{0.05cm}=\hspace{0.05cm} 0.5779\,{\rm bit} \hspace{0.05cm}.$$
-In the lower graph (blue background), the same information-theoretical quantities are given for the &nbsp; &rArr; &nbsp; [[Channel_Coding/Kanalmodelle_und_Entscheiderstrukturen#Binary_Symmetric_Channel_.E2.80.93_BSC|Binary Symmetric Channel]]&nbsp;  (BSC) with the corruption probabilities&nbsp; $ε_0 = ε_1 = ε = 0.1$&nbsp; , which was also assumed fore&nbsp; [[Aufgaben:3.10_Transinformation_beim_BSC| Exercise 3.10]]&nbsp;.
+In the lower graph (blue background), the same information-theoretical quantities are given for the&nbsp; [[Channel_Coding/Kanalmodelle_und_Entscheiderstrukturen#Binary_Symmetric_Channel_.E2.80.93_BSC|Binary Symmetric Channel]]&nbsp;  $\rm (BSC)$&nbsp; with the falsification probabilities&nbsp; $ε_0 = ε_1 = ε = 0.1$,&nbsp; which was also assumed for&nbsp; [[Aufgaben:3.10_Transinformation_beim_BSC| Exercise 3.10]].
-In the present exercise you are to
-:* analyse the entropies&nbsp; $H(X)$,&nbsp; $H(Y)$,&nbsp; $H(X|Y)$&nbsp; and&nbsp; $H(Y|X)$,
+In the present exercise you are
-:* optimize the source parameter &nbsp;$p_0$&nbsp; with respect to maximum mutual information &nbsp;$I(X; Y)$&nbsp;,
+:* to analyze the entropies&nbsp; $H(X)$,&nbsp; $H(Y)$,&nbsp; $H(X|Y)$&nbsp; and&nbsp; $H(Y|X)$,
-:* thus determine the channel capacity &nbsp;$C(ε)$&nbsp;, as well as
+:* to optimize the source parameter &nbsp;$p_0$&nbsp; with respect to maximum mutual information &nbsp;$I(X; Y)$&nbsp;,
-:* give a closed equation for &nbsp;$C(ε)$&nbsp; by generalisation for the BSC channel model&nbsp; $($initially for&nbsp; $ε = 0.1)$.
+:* to determine the channel capacity &nbsp;$C(ε)$&nbsp;,
@@ Line 25: / Line 26: @@
 Hints:
 *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#Kanalkapazit.C3.A4t_eines_Bin.C3.A4rkanals|Channel capacity of a binary channe]].
+*Reference is made in particular to the page&nbsp;    [[Information_Theory/Anwendung_auf_die_Digitalsignalübertragung#Kanalkapazit.C3.A4t_eines_Bin.C3.A4rkanals|Channel capacity of a binary channel]].
@@ Line 41: / Line 42: @@
 {Which statements are true for the channel capacity&nbsp; $C_{\rm BSC}$&nbsp; of the BSC model?
 |type="[]"}
-+ The channel capacity is equal to the maximum transinformation.
++ The channel capacity is equal to the maximum mutual information.
-+ For the BSC, maximisation leads to the result &nbsp;$p_0 = p_1 = 0.5$.
++ For the BSC, maximization leads to the result &nbsp;$p_0 = p_1 = 0.5$.
 + For&nbsp; $p_0 = p_1 = 0.5$&nbsp; &nbsp;,&nbsp; $H(X) = H(Y) = 1 \ \rm bit$.

← Older revision	Revision as of 14:51, 22 July 2021
(No difference)

@@ Line 96: / Line 96: @@
 '''(4)'''&nbsp;  Aus der Grafik erkennt man, dass aus informationstheoretischer Sicht&nbsp; $ε = 1$&nbsp; identisch mit&nbsp; $ε = 0$&nbsp; ist:
 :$$C_{\rm BSC} \big |_{\hspace{0.05cm}\varepsilon \hspace{0.05cm} = \hspace{0.05cm}1} \hspace{0.05cm}= C_{\rm BSC} \big |_{\hspace{0.05cm}\varepsilon \hspace{0.05cm} = \hspace{0.05cm}0} \hspace{0.15cm} \underline {=1\,{\rm (bit)}} \hspace{0.05cm}.$$
-*Der Kanal nimmt hier nur eine Umbenennung vor.&nbsp; Man spricht von "Mapping&rdquo;.
+*Der Kanal nimmt hier nur eine Umbenennung vor.&nbsp; Man spricht von "Mapping".
 * Aus jeder&nbsp; $0$&nbsp; wird eine&nbsp; $1$&nbsp; und aus jeder&nbsp; $1$&nbsp; eine&nbsp; $0$.&nbsp; Entsprechend gilt:
 :$$C_{\rm BSC} \big |_{\hspace{0.05cm}\varepsilon \hspace{0.05cm} = \hspace{0.05cm}0.9} \hspace{0.05cm}= C_{\rm BSC} \big |_{\hspace{0.05cm}\varepsilon \hspace{0.05cm} = \hspace{0.05cm}0.1} \hspace{0.15cm} \underline {=0.531\,{\rm (bit)}} \hspace{0.05cm}$$