Aufgaben:Exercise 2.11Z: Erasure Channel for Symbols - Revision history

Guenter at 13:12, 21 October 2022

2022-10-21T13:12:40Z

Guenter at 12:57, 21 October 2022

2022-10-21T12:57:56Z

Guenter at 12:56, 21 October 2022

2022-10-21T12:56:39Z

Noah at 19:44, 5 September 2022

2022-09-05T19:44:10Z

Noah at 19:43, 5 September 2022

2022-09-05T19:43:35Z

Show changes

Guenter at 12:39, 2 September 2022

2022-09-02T12:39:35Z

Guenter: Guenter moved page Aufgaben:Aufgabe 2.11Z: Erasure–Kanal für Symbole to Aufgaben:Exercise 2.11Z: Erasure Channel for Symbols

2022-09-02T12:36:55Z

Guenter moved page Aufgabe 2.11Z: Erasure–Kanal für Symbole to Exercise 2.11Z: Erasure Channel for Symbols

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

2021-05-28T14:29:30Z

Text replacement - "„" to """

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

2021-05-28T14:23:56Z

Text replacement - "”" to """

Javier: Text replacement - "Category:Aufgaben zu Kanalcodierung" to "Category:Channel Coding: Exercises"

2021-03-23T12:50:52Z

Text replacement - "Category:Aufgaben zu Kanalcodierung" to "Category:Channel Coding: Exercises"

@@ Line 61: / Line 61: @@
 ===Solution===
 {{ML-Kopf}}
-'''(1)'''&nbsp; Due to the symmetry of the given BEC model (bit-level erasure channel), the <i>erasure</i> probability is:
+'''(1)'''&nbsp; Due to the symmetry of the given BEC model&nbsp; ("bit-level erasure channel"),&nbsp; the erasure probability is:
 :$$\ {\rm Pr}(y = {\rm E}) = \lambda \ \underline{= 20\%}.$$
-Since code symbols $0$ and $1$ are equally likely, we obtain ${\rm Pr}(y = 0) \ \underline{= 40\%}$ and ${\rm Pr}(y = 1) \ \underline{= 40\%}$ for their probabilities.
+*Since the code symbols&nbsp; $0$&nbsp; and&nbsp; $1$&nbsp; are equally likely,&nbsp; we obtain &nbsp; ${\rm Pr}(y = 0) \ \underline{= 40\%}$ &nbsp; and &nbsp; ${\rm Pr}(y = 1) \ \underline{= 40\%}$ &nbsp; for their probabilities.
-'''(2)'''&nbsp; Without limiting generality, we assume the code symbol $c_{\rm binary} = $ "$00$" to solve this exercise.
+'''(2)'''&nbsp; Without limiting generality,&nbsp; we assume the code symbol&nbsp; $c_{\rm bin} = $ "$00$"&nbsp; to solve this exercise.
-*According to the 2 BEC model, the receive symbol $y_{\rm binary}$ can then be either "$00$" or canceled $(\rm E)$ and it holds:
+*According to the&nbsp; $2$&ndash;BEC model,&nbsp; the received symbol&nbsp; $y_{\rm bin}$&nbsp; can then be either&nbsp; "$00$"&nbsp; or erased&nbsp; $(\rm E)$&nbsp; and it holds:
 :$${\rm Pr}(y_{\rm bin} = "00"\hspace{0.05cm} |\hspace{0.05cm} c_{\rm bin} = "00") \hspace{-0.15cm} \ = \ \hspace{-0.15cm} ( 1 - \lambda)^2 = 0.8^2 = 0.64 = 1 - \lambda_2\hspace{0.3cm}
 \Rightarrow \hspace{0.3cm} \lambda_2 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 1 - ( 1 - \lambda)^2 \hspace{0.15cm}\underline{= 36\%}\hspace{0.05cm}. $$
-*This assumes that an <i>erasure</i> is avoided only if neither of the two bits has been erased.
+*This assumes that an erasure is avoided only if neither of the two bits has been erased.
-'''(3)'''&nbsp; The $\rm RSC \, (255, \, 223, \, 33)_{256}$ is based on the Galois field $\rm GF(256) = GF(2^8) \ \Rightarrow \ \it m = \rm 8$. The result of subtask (2) must now be adapted to this case. For the $8$ BEC holds:
+'''(3)'''&nbsp; The &nbsp; $\rm RSC \, (255, \, 223, \, 33)_{256}$ &nbsp; is based on the Galois field&nbsp; $\rm GF(256) = GF(2^8) \ \Rightarrow \ \it m = \rm 8$.
 :$$1 - \lambda_8 = ( 1 - \lambda)^8 = 0.8^8 \approx 0.168 \hspace{0.3cm} \Rightarrow \hspace{0.3cm}
 \lambda_m = \lambda_8  \hspace{0.15cm}\underline{\approx 83.2\%}\hspace{0.05cm}. $$
@@ Line 81: / Line 82: @@
-'''(4)'''&nbsp; From the condition $\lambda_m &#8804; 0.2$ it follows directly $1 - \lambda_m &#8805; 0.8$. From this follows further:
+'''(4)'''&nbsp; From the condition &nbsp; $\lambda_m &#8804; 0.2$&nbsp; it follows directly&nbsp; $1 - \lambda_m &#8805; 0.8$.&nbsp; From this follows further:
 :$$( 1 - \lambda)^8 \ge 0.8  \hspace{0.3cm} \Rightarrow \hspace{0.3cm}
 - \lambda \ge 0.8^{0.125} \approx 0.9725 \hspace{0.3cm} \Rightarrow \hspace{0.3cm}\lambda \hspace{0.15cm}
@@ Line 89: / Line 90: @@
 '''(5)'''&nbsp; Here one proceeds as follows:
-*With $\lambda = 0.0275 \Rightarrow \ \lambda_m = 0.2$, $20\%$ of the receiving symbols are <i>erasures</i>.
+*With&nbsp; $\lambda = 0.0275 \Rightarrow \ \lambda_m = 0.2$ &nbsp; &rArr; &nbsp; $20\%$&nbsp; of the received symbols are&nbsp; erasured.
-*The $2^8 = 256$ receiving symbols ($00000000$ &nbsp; ... &nbsp; $11111111$) are all equally likely. It follows:
 :$${\rm Pr}(y_{\rm bin} = 00000000) = \hspace{0.1cm}\text{...} \hspace{0.1cm}= {\rm Pr}(y_{\rm bin} = 11111111)= \frac{0.8}{256}  \hspace{0.15cm}\underline{= 0.3125\%}\hspace{0.05cm}.$$
 {{ML-Fuß}}

@@ Line 23: / Line 23: @@
 Hints:
-* This exercise belongs to the chapter&nbsp; [[Channel_Coding/Reed-Solomon_Decoding_for_the_Erasure_Channel| "Reed&ndash;Solomon Decoding at the Erasure Channel"]].
+* This exercise belongs to the chapter&nbsp; [[Channel_Coding/Reed-Solomon_Decoding_for_the_Erasure_Channel| "Reed&ndash;Solomon Decoding for the Erasure Channel"]].
 * For a code based on&nbsp; ${\rm GF}(2^m)$&nbsp; the outlined&nbsp; $2$&ndash;BEC model is to be extended to&nbsp; $m$&ndash;BEC.

@@ Line 1: / Line 1: @@
 {{quiz-Header|Buchseite=Channel_Coding/Reed-Solomon_Decoding_for_the_Erasure_Channel}}
-[[File:P_ID2543__KC_Z_2_11.png|right|frame|Erase channel for symbols: $m$-BEC]]
+[[File:P_ID2543__KC_Z_2_11.png|right|frame|Erasure channel for symbols:&nbsp; "m&ndash;BEC"]]
-The channel model&nbsp; [[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Erasure_Channel_.E2.80.93_BEC|"Binary Erasure Channel"]]&nbsp; (BEC) describes a bit-level erasure channel:
+The channel model&nbsp; [[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Erasure_Channel_.E2.80.93_BEC|"Binary Erasure Channel"]]&nbsp; $\rm (BEC)$ describes a bit-level erasure channel:
-*A binary symbol&nbsp; $0$&nbsp; or&nbsp; $1$&nbsp; is correctly transmitted with probability&nbsp; $1 - \lambda$&nbsp; and marked as an erasure&nbsp; $\lambda$&nbsp; with probability&nbsp; $\rm E$.
+*A binary symbol&nbsp; $(0$&nbsp; or&nbsp; $1)$&nbsp; is correctly transmitted with probability&nbsp; $1 - \lambda$&nbsp; and marked as an erasure&nbsp; "$\rm E$"&nbsp; with probability&nbsp; $\lambda$.
-*In contrast to&nbsp; [[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Symmetric_Channel_.E2.80.93_BSC| "Binary Symmetric Channel"]]&nbsp; (BSC), corruptions&nbsp; $(0 &#8594 1, \ 1 &#8594; 0)$&nbsp; cannot occur here.
-A Reed&ndash;Solomon code is based on a Galois field&nbsp; ${\rm GF}(2^m)$&nbsp; with integer&nbsp; $m$. Thus, each code symbol&nbsp; $c$&nbsp; can be represented by&nbsp; $m$ bits&nbsp;. If one wants to apply the BEC&ndash;model here, one has to modify it to the&nbsp; $m\text{-BEC}$ model&nbsp; as shown in the diagram below for&nbsp; $m = 2$&nbsp;:
+A Reed&ndash;Solomon code is based on a Galois field &nbsp; ${\rm GF}(2^m)$ &nbsp; with integer&nbsp; $m$.&nbsp; Thus,&nbsp; each code symbol &nbsp; $c$ &nbsp; can be represented by&nbsp; $m$&nbsp; bits.&nbsp; If one wants to apply the BEC model here,&nbsp; one has to modify it to the&nbsp; "$m$&ndash;BEC"&nbsp; model&nbsp; as shown in the diagram below for&nbsp; $m = 2$:
-*All code symbols &ndash; in binary representation&nbsp; $00, \ 01, \ 10, \ 11$&nbsp; &ndash; are transmitted correctly with probability&nbsp; $1 - \lambda_2$&nbsp;.
+*All code symbols &nbsp; $($in binary representation&nbsp; $00, \ 01, \ 10, \ 11)$ &nbsp; are transmitted correctly with probability&nbsp; $1 - \lambda_2$&nbsp;.
 *Thus, the probability of an erased symbol&nbsp; is $\lambda_2$.
 *Note that already a single erased bit leads to the erased received symbol&nbsp; $y = \rm E$&nbsp;.
@@ Line 21: / Line 24: @@
 Hints:
 * This exercise belongs to the chapter&nbsp; [[Channel_Coding/Reed-Solomon_Decoding_for_the_Erasure_Channel| "Reed&ndash;Solomon Decoding at the Erasure Channel"]].
 * For a code based on&nbsp; ${\rm GF}(2^m)$&nbsp; the outlined&nbsp; $2$ BEC model is to be extended to&nbsp; $m$ BEC.
-*The erasure probability of this model is then denoted by&nbsp; $\lambda_m$&nbsp;.
+* For a code based on&nbsp; ${\rm GF}(2^m)$&nbsp; the outlined&nbsp; $2$&ndash;BEC model is to be extended to&nbsp; $m$&ndash;BEC.
 *For the first subtasks, always&nbsp; $\lambda = 0.2$ for the erasure probability of the basic model according to the upper graph.
@@ Line 30: / Line 36: @@
 ===Questions===
 <quiz display=simple>
-{$\lambda = 0.2$ is valid. With what probabilities do the possible received values occur in the&nbsp; BEC basic model&nbsp;?
+{$\lambda = 0.2$&nbsp; is valid.&nbsp; With what probabilities do the possible received values occur in the&nbsp; BEC basic model&nbsp;?
 |type="{}"}
 ${\rm Pr}(y = 0) \ = \ ${ 40 3% } $\ \%$
@@ Line 36: / Line 42: @@
 ${\rm Pr}(y = {\rm 1}) \ = \ ${ 40 3% } $\ \%$
-{What is the erasure probability&nbsp; $\lambda_2$&nbsp; at symbol level&nbsp; $(2$ BEC model$)$ when the RS code is based on&nbsp; $\rm GF(2^2)$&nbsp; $(\lambda = 0.2)$?
+{$\lambda = 0.2$&nbsp; is valid.&nbsp; What is the erasure probability&nbsp; $\lambda_2$&nbsp; at symbol level&nbsp; $(2$&ndash;BEC model$)$&nbsp; when the Reed-Solomon code is based on&nbsp; $\rm GF(2^2)$?
 |type="{}"}
 $\lambda_2 \ = \ ${ 36 3% } $\ \%$
-{What is the erasure probability&nbsp; $\lambda_m$ when the&nbsp; $m$ BEC model&nbsp; is fitted to the&nbsp; $\rm RSC \, (255, \, 223, \, 33)_{256}$&nbsp; $(\lambda = 0.2)$?
+{$\lambda = 0.2$&nbsp; is valid.&nbsp; What is the erasure probability&nbsp; $\lambda_m$,&nbsp; when the&nbsp; $m$&ndash;BEC model&nbsp; is fitted to the&nbsp; $\rm RSC \, (255, \, 223, \, 33)_{256}$?
 |type="{}"}
 $\lambda_m \ = \ ${ 83.2 3% } $\ \%$
-{What is the maximum allowed erasure probability&nbsp; $\lambda$&nbsp; in&nbsp; BEC basic model&nbsp; for&nbsp; $\lambda_m &#8804; 0.2$&nbsp; to hold?
+{What is the maximum allowed erasure probability&nbsp; $\lambda$&nbsp; of the&nbsp; "BEC basic model"&nbsp; for&nbsp; $\lambda_m &#8804; 0.2$&nbsp; to hold?
 |type="{}"}
 ${\rm Max} \ \big[\lambda\big ] \ = \ ${ 2.75 3% } $\ \%$
-{What is the probability of receiving the "zero symbol" in this case?
+{What is the probability of receiving the&nbsp;  "zero symbol"&nbsp; in this case?
 |type="{}"}
 ${\rm Pr}(y_{\rm bin} = 00000000) \ = \ ${ 0.3125 3% } $\ \%$

@@ Line 83: / Line 83: @@
 '''(5)'''&nbsp; Here one proceeds as follows:
-*Mit $\lambda = 0.0275 \ \Rightarrow \ \lambda_m = 0.2$ sind $20\%$ der Empfangssymbole <i>Erasures</i>.
+*With $\lambda = 0.0275 \Rightarrow \ \lambda_m = 0.2$, $20\%$ of the receiving symbols are <i>erasures</i>.
-*Die  $2^8 = 256$ Empfangssymbole ($00000000$ &nbsp; ... &nbsp;  $11111111$) sind alle gleichwahrscheinlich. Daraus folgt:
+*The $2^8 = 256$ receiving symbols ($00000000$ &nbsp; ... &nbsp; $11111111$) are all equally likely. It follows:
 :$${\rm Pr}(y_{\rm bin} = 00000000) = \hspace{0.1cm}\text{...} \hspace{0.1cm}= {\rm Pr}(y_{\rm bin} = 11111111)= \frac{0.8}{256}  \hspace{0.15cm}\underline{= 0.3125\%}\hspace{0.05cm}.$$
 {{ML-Fuß}}

← Older revision		Revision as of 12:39, 2 September 2022
Line 90:		Line 90:


−	[[Category:Channel Coding: Exercises\|^2.4 ~~RS–Decodierung bei Auslöschungen~~^]]	+	[[Category:Channel Coding: Exercises\|^2.4 Reed-Solomon Decoding at the BEC^]]

@@ Line 48: / Line 48: @@
 ${\rm Max} \ \big[\lambda\big ] \ = \ ${ 2.75 3% } $\ \%$
-{Mit welcher Wahrscheinlichkeit wird in diesem Fall das &bdquo;Nullsymbol" empfangen?
+{Mit welcher Wahrscheinlichkeit wird in diesem Fall das "Nullsymbol" empfangen?
 |type="{}"}
 ${\rm Pr}(y_{\rm bin} = 00000000) \ = \ ${ 0.3125 3% } $\ \%$
@@ Line 61: / Line 61: @@
-'''(2)'''&nbsp; Ohne Einschränkung der Allgemeingültigkeit gehen wir zur Lösung dieser Aufgabe vom Codesymbol $c_{\rm binär} = $ &bdquo;$00$" aus.
+'''(2)'''&nbsp; Ohne Einschränkung der Allgemeingültigkeit gehen wir zur Lösung dieser Aufgabe vom Codesymbol $c_{\rm binär} = $ "$00$" aus.
-*Entsprechend dem 2&ndash;BEC&ndash;Modell kann dann das Empfangssymbol $y_{\rm binär}$ entweder &bdquo;$00$" oder ausgelöscht $(\rm E)$ sein und es gilt:
+*Entsprechend dem 2&ndash;BEC&ndash;Modell kann dann das Empfangssymbol $y_{\rm binär}$ entweder "$00$" oder ausgelöscht $(\rm E)$ sein und es gilt:
 :$${\rm Pr}(y_{\rm bin} = "00"\hspace{0.05cm} |\hspace{0.05cm} c_{\rm bin} = "00") \hspace{-0.15cm} \ = \ \hspace{-0.15cm} ( 1 - \lambda)^2 = 0.8^2 = 0.64 = 1 - \lambda_2\hspace{0.3cm}
 \Rightarrow \hspace{0.3cm} \lambda_2 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 1 - ( 1 - \lambda)^2 \hspace{0.15cm}\underline{= 36\%}\hspace{0.05cm}. $$

← Older revision		Revision as of 12:50, 23 March 2021
Line 90:		Line 90:


−	[[Category:~~Aufgaben zu Kanalcodierung~~\|^2.4 RS–Decodierung bei Auslöschungen^]]	+	[[Category:Channel Coding: Exercises\|^2.4 RS–Decodierung bei Auslöschungen^]]