Channel Coding/Reed-Solomon Decoding for the Erasure Channel - Revision history

Hwang at 10:36, 24 November 2022

2022-11-24T10:36:14Z

Hwang at 10:34, 24 November 2022

2022-11-24T10:34:01Z

Hwang at 20:40, 23 November 2022

2022-11-23T20:40:03Z

Guenter at 14:13, 20 October 2022

2022-10-20T14:13:28Z

Guenter at 13:45, 20 October 2022

2022-10-20T13:45:11Z

Guenter at 12:32, 20 October 2022

2022-10-20T12:32:34Z

Guenter at 12:31, 20 October 2022

2022-10-20T12:31:11Z

Guenter at 11:57, 20 October 2022

2022-10-20T11:57:35Z

Guenter at 14:34, 8 October 2022

2022-10-08T14:34:28Z

Noah at 20:39, 3 September 2022

2022-09-03T20:39:17Z

← Older revision		Revision as of 10:36, 24 November 2022
Line 13:		Line 13:

	# This chapter is based on the  [[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Erasure_Channel_.E2.80.93_BEC\| $\text{BEC model}$]]  ("Binary Erasure Channel"),  which marks an uncertain bit as  "erasure"  $\rm E$.		# This chapter is based on the  [[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Erasure_Channel_.E2.80.93_BEC\| $\text{BEC model}$]]  ("Binary Erasure Channel"),  which marks an uncertain bit as  "erasure"  $\rm E$.
−	# In contrast to the  [[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Symmetric_Channel_.E2.80.93_BSC\|$\text{BSC model}$]]  ("Binary Symmetric Channel") and   [[Channel_Coding/Channel_Models_and_Decision_Structures#~~AWGN_channel_at_Binary_Input~~\|$\text{AWGN model}$]]  ("Additive White Gaussian Noise"),   bit errors  $(y_i ≠ c_i)$  are excluded here.	+	# In contrast to the  [[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Symmetric_Channel_.E2.80.93_BSC\|$\text{BSC model}$]]  ("Binary Symmetric Channel") and   [[Channel_Coding/Channel_Models_and_Decision_Structures#AWGN_channel_at_binary_input\|$\text{AWGN model}$]]  ("Additive White Gaussian Noise"),   bit errors  $(y_i ≠ c_i)$  are excluded here.

@@ Line 44: / Line 44: @@
 :*If the number&nbsp; $e$&nbsp; of erasures in the vector &nbsp; $\underline{y}$ &nbsp; is sufficiently small,&nbsp; the entire code word can be found with certainty: &nbsp; $(\underline{z}=\underline{c})$.
 :*If too many symbols of the received word&nbsp; $\underline{y}$&nbsp; are erased,&nbsp; the decoder reports that this word cannot be decoded.&nbsp; It may then be necessary to send this sequence again. <br>
-*In the case of the&nbsp; "m-BEC"&nbsp; model,&nbsp; an error decision&nbsp; $(\underline{z} \ne\underline{c})$&nbsp; is excluded &nbsp; &#8658; &nbsp; '''block error probability'''&nbsp; ${\rm Pr}(\underline{z}\ne\underline{c}) = 0$ &nbsp; &#8658; &nbsp; ${\rm Pr}(\underline{v}\ne\underline{u}) = 0$.
+*In the case of the&nbsp; "m-BEC"&nbsp; model,&nbsp; an error decision&nbsp; $(\underline{z} \ne\underline{c})$&nbsp; is excluded &nbsp; &#8658; &nbsp; &raquo;'''block error probability'''&laquo;&nbsp; ${\rm Pr}(\underline{z}\ne\underline{c}) = 0$ &nbsp; &#8658; &nbsp; ${\rm Pr}(\underline{v}\ne\underline{u}) = 0$.
 :*The reconstructed information word results according to the block diagram&nbsp; $($yellow background$)$&nbsp; to&nbsp; $\underline{v} = {\rm enc}^{-1}(\underline{z})$.
 :*With the generator matrix&nbsp; $\boldsymbol{\rm G}$&nbsp; can also be written for this:

@@ Line 12: / Line 12: @@
 [[File:EN_KC_T_2_4_S1_2neu.png|right|frame|Transmission system with Reed-Solomon coding/decoding and erasure channel|class=fit]]
-# This chapter  based on the&nbsp; [[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Erasure_Channel_.E2.80.93_BEC| "BEC model"]]&nbsp; ("Binary Erasure Channel"),&nbsp; which marks an uncertain bit as&nbsp; "erasure"&nbsp; $\rm E$.&nbsp;
+# This chapter is based on the&nbsp; [[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Erasure_Channel_.E2.80.93_BEC| $\text{BEC model}$]]&nbsp; ("Binary Erasure Channel"),&nbsp; which marks an uncertain bit as&nbsp; "erasure"&nbsp; $\rm E$.&nbsp;
-# In contrast to the&nbsp; [[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Symmetric_Channel_.E2.80.93_BSC| "BSC model"]]&nbsp; ("Binary Symmetric Channel") and &nbsp; [[Channel_Coding/Channel_Models_and_Decision_Structures#AWGN_channel_at_Binary_Input| "AWGN model"]]&nbsp; ("Additive White Gaussian Noise"), &nbsp; bit errors&nbsp; $(y_i &ne; c_i)$&nbsp; are excluded here.
+# In contrast to the&nbsp; [[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Symmetric_Channel_.E2.80.93_BSC|$\text{BSC model}$]]&nbsp; ("Binary Symmetric Channel") and &nbsp; [[Channel_Coding/Channel_Models_and_Decision_Structures#AWGN_channel_at_Binary_Input|$\text{AWGN model}$]]&nbsp; ("Additive White Gaussian Noise"), &nbsp; bit errors&nbsp; $(y_i &ne; c_i)$&nbsp; are excluded here.
@@ Line 23: / Line 23: @@
-The graphic shows the block diagram,&nbsp; which is slightly different from the model in chapter&nbsp; [[Channel_Coding/Decoding_of_Linear_Block_Codes#Block_diagram_and_requirements|"Decoding oflinear block codes"]]:
+The graphic shows the block diagram,&nbsp; which is slightly different from the model in chapter&nbsp; [[Channel_Coding/Decoding_of_Linear_Block_Codes#Block_diagram_and_requirements|$\text{Decoding oflinear block codes}$]]:
 *Since Reed&ndash;Solomon codes are linear block codes,&nbsp; the information word&nbsp; $\underline{u}$&nbsp; and the code word&nbsp; $\underline{c}$&nbsp; are also related via the generator matrix&nbsp; $\boldsymbol{\rm G}$&nbsp; and following equation:
@@ Line 149: / Line 149: @@
 { \boldsymbol{\rm H}}_{\rm K} \cdot \underline {z}_{\rm K}^{\rm T}\hspace{0.05cm}.  </math>
-*Since for all elements&nbsp; $z_i &#8712; {\rm GF}(2^m)$ &nbsp; &rArr; &nbsp; the&nbsp; [[Channel_Coding/Some_Basics_of_Algebra#Definition_of_a_Galois_field |"additive inverse"]]&nbsp; ${\rm Inv_A}(z_i)= (- z_i) = z_i$&nbsp; holds in the same way
+*Since for all elements&nbsp; $z_i &#8712; {\rm GF}(2^m)$ &nbsp; &rArr; &nbsp; the&nbsp; [[Channel_Coding/Some_Basics_of_Algebra#Definition_of_a_Galois_field |$\text{additive inverse}$]]&nbsp; ${\rm Inv_A}(z_i)= (- z_i) = z_i$&nbsp; holds in the same way
 ::<math>{ \boldsymbol{\rm H}}_{\rm E} \cdot \underline {z}_{\rm E}^{\rm T} =
@@ Line 222: / Line 222: @@
 (\alpha + 1) + (\alpha^2 + 1) + (\alpha^2 + \alpha) = 0\hspace{0.05cm}.</math>
-*The corresponding information word is obtained with the&nbsp; [[Channel_Coding/General_Description_of_Linear_Block_Codes#Code_definition_by_the_generator_matrix| "Generator Matrix"]]&nbsp; $\boldsymbol{\rm G}$:
+*The corresponding information word is obtained with the&nbsp; [[Channel_Coding/General_Description_of_Linear_Block_Codes#Code_definition_by_the_generator_matrix| $\text{generator matrix}$]]&nbsp; $\boldsymbol{\rm G}$:
 :$$\underline {v} = \underline {z} \cdot \boldsymbol{\rm G}^{\rm T} = (\alpha^1,\hspace{0.05cm}1,\hspace{0.05cm}\alpha^3).$$

@@ Line 118: / Line 118: @@
 == Solution of the matrix equations using the example of the RSC (7, 3, 5)<sub>8</sub> ==
 <br>
-Thus, it is necessary to find the admissible codeword&nbsp; $\underline {z}$ that satisfies the determination equation&nbsp; $\boldsymbol{\rm H} \cdot \underline {z}^{\rm T} $&nbsp; satisfies. For convenience, we split the vector&nbsp; $\underline {z}$&nbsp; into two partial vectors, viz.
+Thus,&nbsp; it is necessary to find the admissible code word&nbsp; $\underline {z}$&nbsp; that satisfies the determination equation&nbsp;
-*the vector&nbsp; $\underline {z}_{\rm E} = (z_2, z_3, z_5)$&nbsp; of the erased symbols&nbsp; (index "$\rm E$" for <i>erasures</i>&nbsp;),<br>
+:$$\boldsymbol{\rm H} \cdot \underline {z}^{\rm T}. $$
-*the vector&nbsp; $\underline {z}_{\rm K} = (c_0, c_1,c_4, c_6)$&nbsp; of known symbols&nbsp; (index "$\rm K$" for <i>correct</i>&nbsp;).<br><br>
+*With the associated partial matrices&nbsp; $($each with&nbsp; $n-k = 4$&nbsp; rows$)$
 ::<math>{ \boldsymbol{\rm H}}_{\rm E} =
@@ Line 140: / Line 141: @@
 \end{pmatrix}</math>
-the equation of determination is thus:
+:the equation of determination is thus:
 ::<math>{ \boldsymbol{\rm H}}_{\rm E} \cdot \underline {z}_{\rm E}^{\rm T} +
@@ Line 148: / Line 149: @@
 { \boldsymbol{\rm H}}_{\rm K} \cdot \underline {z}_{\rm K}^{\rm T}\hspace{0.05cm}.  </math>
-*Since for all elements&nbsp; $z_i &#8712; {\rm GF}(2^m)$&nbsp; the&nbsp; [[Channel_Coding/Some_Basics_of_Algebra#Definition_of_a_Galois_field |"additive inverse"]]&nbsp; ${\rm Inv_A}(z_i)= (- z_i) = z_i$&nbsp; holds in the same way
+*Since for all elements&nbsp; $z_i &#8712; {\rm GF}(2^m)$ &nbsp; &rArr; &nbsp; the&nbsp; [[Channel_Coding/Some_Basics_of_Algebra#Definition_of_a_Galois_field |"additive inverse"]]&nbsp; ${\rm Inv_A}(z_i)= (- z_i) = z_i$&nbsp; holds in the same way
 ::<math>{ \boldsymbol{\rm H}}_{\rm E} \cdot \underline {z}_{\rm E}^{\rm T} =
@@ Line 172: / Line 173: @@
 \hspace{0.05cm}.</math>
-*The right-hand side of the equation results for the considered example &nbsp; &#8658; &nbsp; $\underline {z}_{\rm K} = (c_0, c_1,c_4, c_6)$&nbsp; and is based on the polynomial&nbsp; $p(x) = x^3 + x +1$, which leads to the following powers $($in&nbsp; &nbsp;$\alpha)$&nbsp;:
+*The right&ndash;hand side of the equation results for the considered example &nbsp; &#8658; &nbsp; $\underline {z}_{\rm K} = (c_0, c_1,c_4, c_6)$&nbsp; and is based on the polynomial &nbsp; $p(x) = x^3 + x +1$,&nbsp; which leads to the following powers&nbsp; $($in&nbsp; &nbsp;$\alpha)$&nbsp;:
 ::<math>\alpha^3 =\alpha + 1\hspace{0.05cm},
@@ Line 183: / Line 184: @@
 \hspace{0.3cm} \alpha^{10} = \alpha^3 =   \alpha + 1\hspace{0.05cm},\hspace{0.1cm} \text{...}</math>
-*Thus, the matrix equation for determining the vector we are looking for&nbsp; $\underline {z}_{\rm E}$:
+*Thus,&nbsp; the matrix equation for determining the vector&nbsp; $\underline {z}_{\rm E}$&nbsp; we are looking for:
 ::<math>\begin{pmatrix}
@@ Line 204: / Line 205: @@
 \hspace{0.05cm}. </math>
-*Solving this matrix equation (most easily by program), we get
+*Solving this matrix equation&nbsp; $($most easily by program$)$,&nbsp; we get
 ::<math>z_2 = \alpha^2\hspace{0.05cm},\hspace{0.25cm}z_3 = \alpha^1\hspace{0.05cm},\hspace{0.25cm}z_5 = \alpha^5
@@ Line 210: / Line 211: @@
 \hspace{0.05cm}.</math>
-*The result is correct, as the following control calculations show:
+*The result is correct,&nbsp; as the following control calculations show:
 ::<math>\alpha^2 \cdot \alpha^2 + \alpha^3 \cdot \alpha^1 + \alpha^5 \cdot \alpha^5 =
@@ Line 221: / Line 222: @@
 (\alpha + 1) + (\alpha^2 + 1) + (\alpha^2 + \alpha) = 0\hspace{0.05cm}.</math>
-*The corresponding information word is obtained with the&nbsp; [[Channel_Coding/General_Description_of_Linear_Block_Codes#Code_definition_by_the_generator_matrix| "Generator Matrix"]]&nbsp; $\boldsymbol{\rm G}$&nbsp; to&nbsp; $\underline {v} = \underline {z} \cdot \boldsymbol{\rm G}^{\rm T} = (\alpha^1,\hspace{0.05cm}1,\hspace{0.05cm}\alpha^3)$.<br>
+*The corresponding information word is obtained with the&nbsp; [[Channel_Coding/General_Description_of_Linear_Block_Codes#Code_definition_by_the_generator_matrix| "Generator Matrix"]]&nbsp; $\boldsymbol{\rm G}$:
 == Exercises for the chapter ==

@@ Line 38: / Line 38: @@
 *Each code symbol&nbsp; $c_i$&nbsp; is thus represented by&nbsp; $m &#8805; 2$&nbsp; binary symbols.&nbsp; For comparison: &nbsp; For the binary block codes hold&nbsp; $q=2$,&nbsp; $m=1$&nbsp; and the code word length&nbsp; $n$&nbsp; is freely selectable.<br>
-*When encoding at symbol level,&nbsp; the BEC model must be extended to the&nbsp; "$m$-BEC model":&nbsp;
+*When encoding at symbol level,&nbsp; the BEC model must be extended to the&nbsp; "m-BEC model":&nbsp;
-:*With probability&nbsp; $\lambda_m &asymp; m \cdot\lambda$&nbsp; a code symbol&nbsp; $c_i$&nbsp; is erased&nbsp; $(y_i = \rm E)$&nbsp; and it holds&nbsp; ${\rm Pr}(y_i = c_i) = 1 - \lambda_m$.
+:*With probability&nbsp; $\lambda_m &asymp; m \cdot\lambda$&nbsp; a code symbol&nbsp; $c_i$&nbsp; is erased&nbsp; $(y_i = \rm E)$&nbsp; and it holds&nbsp; ${\rm Pr}(y_i = c_i) = 1 - \lambda_m$.&nbsp;
 :*For more details on the conversion of the two models,&nbsp; see&nbsp; [[Aufgaben:Exercise_2.11Z:_Erasure_Channel_for_Symbols|"Exercise 2.11Z"]].<br>
+*In the following, we deal only with the block&nbsp; "code word finder"&nbsp; $\rm (CWF)$,&nbsp; which extracts from the received vector&nbsp; $\underline{y}$&nbsp; the vector&nbsp; $\underline{z} &#8712; \mathcal{C}_{\rm RS}$:
 :*If the number&nbsp; $e$&nbsp; of erasures in the vector &nbsp; $\underline{y}$ &nbsp; is sufficiently small,&nbsp; the entire code word can be found with certainty: &nbsp; $(\underline{z}=\underline{c})$.
-In the following, we deal only with the block&nbsp; "code word finder"&nbsp; $\rm (CWF)$,&nbsp; which extracts from the received vector&nbsp; $\underline{y}$&nbsp; the vector&nbsp; $\underline{z} &#8712; \mathcal{C}_{\rm RS}$:
+:*If too many symbols of the received word&nbsp; $\underline{y}$&nbsp; are erased,&nbsp; the decoder reports that this word cannot be decoded.&nbsp; It may then be necessary to send this sequence again. <br>
-:*If the number&nbsp; $e$&nbsp; of erasures in the vector &nbsp; $\underline{y}$ &nbsp; is sufficiently small,&nbsp; the entire code word can be found with certainty: &nbsp; $(\underline{z}=\underline{c})$&nbsp;.<br>
+*In the case of the&nbsp; "m-BEC"&nbsp; model,&nbsp; an error decision&nbsp; $(\underline{z} \ne\underline{c})$&nbsp; is excluded &nbsp; &#8658; &nbsp; '''block error probability'''&nbsp; ${\rm Pr}(\underline{z}\ne\underline{c}) = 0$ &nbsp; &#8658; &nbsp; ${\rm Pr}(\underline{v}\ne\underline{u}) = 0$.
+:*The reconstructed information word results according to the block diagram&nbsp; $($yellow background$)$&nbsp; to&nbsp; $\underline{v} = {\rm enc}^{-1}(\underline{z})$.
-:*If too many symbols of the received word&nbsp; $\underline{y}$&nbsp; are erased,&nbsp; the decoder reports that this word cannot be decoded.&nbsp; It may then be necessary to send this sequence again. <br><br>
+:*With the generator matrix&nbsp; $\boldsymbol{\rm G}$&nbsp; can also be written for this:
+:::<math>\underline {c} = \underline {u} \cdot { \boldsymbol{\rm G}}
 \hspace{0.3cm} \Rightarrow  \hspace{0.3cm}\underline {z} = \underline {\upsilon} \cdot { \boldsymbol{\rm G}}
 \hspace{0.3cm} \Rightarrow  \hspace{0.3cm}\underline {\upsilon} = \underline {z} \cdot { \boldsymbol{\rm G}}^{\rm T}
 \hspace{0.05cm}. </math>
-== Procedure using the RSC as an example (7, 3, 5)<sub>8</sub> ==
+== Decoding procedure using the RSC (7, 3, 5)<sub>8</sub> as an example  ==
 <br>
 In order to be able to represent the Reed&ndash;Solomon decoding at the extinction channel as simply as possible, we start from a concrete task:
-A Reed&ndash;Solomon code with parameters&nbsp; $n= 7$,&nbsp; $k= 3$&nbsp; and&nbsp; $q= 2^3 = 8$ is used.
+*A Reed&ndash;Solomon code with parameters&nbsp; $n= 7$,&nbsp; $k= 3$&nbsp; and&nbsp; $q= 2^3 = 8$ is used.
 ::<math>\underline {u} = (u_0, u_1, u_2) \hspace{0.05cm},\hspace{0.15cm}
 \underline {c} = (c_0, c_1, c_2,c_3,c_4,c_5,c_6)\hspace{0.05cm},\hspace{0.15cm}
 u_i, c_i \in {\rm GF}(2^3) = \{0, 1,  \alpha, \alpha^2, \text{...}\hspace{0.05cm} , \alpha^6\}
-\hspace{0.05cm},</math>
+\hspace{0.05cm}.</math>
-and the parity-check matrix&nbsp; $\boldsymbol{\rm H}$&nbsp; is:
+*The parity-check matrix&nbsp; $\boldsymbol{\rm H}$&nbsp; is:
 ::<math>{ \boldsymbol{\rm H}} =
@@ Line 81: / Line 74: @@
 \end{pmatrix}\hspace{0.05cm}. </math>
-For example, the received vector&nbsp; $\underline {y}  = (\alpha, \hspace{0.03cm} 1, \hspace{0.03cm}{\rm E}, \hspace{0.03cm}{\rm E}, \hspace{0.03cm}\alpha^2,{\rm E}, \hspace{0.03cm}\alpha^5)$&nbsp; is assumed here. Then holds:
+&rArr; &nbsp; For example,&nbsp; the received vector&nbsp;
-*Since the erasure channel produces no errors, four of the code symbols are known to the decoder:
+:$$\underline {y}  = (\alpha, \hspace{0.03cm} 1, \hspace{0.03cm}{\rm E}, \hspace{0.03cm}{\rm E}, \hspace{0.03cm}\alpha^2,{\rm E}, \hspace{0.03cm}\alpha^5)$$
 ::<math>c_0 = \alpha^1 \hspace{0.05cm},\hspace{0.2cm}
@@ Line 90: / Line 85: @@
 \hspace{0.05cm}.</math>
-*It is obvious that the block "code word finder" &ndash; in the block diagram is denoted by&nbsp; '''CWF''''&nbsp; a vector of the form&nbsp; $\underline {z} = (c_0, \hspace{0.03cm}c_1, \hspace{0.03cm}z_2, \hspace{0.03cm}z_3,\hspace{0.03cm}c_4,\hspace{0.03cm}z_5,\hspace{0.03cm}c_6)$&nbsp; is to be supplied with&nbsp; $z_2,\hspace{0.03cm}z_3,\hspace{0.03cm}z_5 \in \rm GF(2^3)$.<br>
+*It is obvious that the block&nbsp; "code word finder"&nbsp; $\rm (CWF)$&nbsp; is to provide a vector of the form &nbsp; $\underline {z} = (c_0, \hspace{0.03cm}c_1, \hspace{0.03cm}z_2, \hspace{0.03cm}z_3,\hspace{0.03cm}c_4,\hspace{0.03cm}z_5,\hspace{0.03cm}c_6)$ &nbsp;  with&nbsp; $z_2,\hspace{0.03cm}z_3,\hspace{0.03cm}z_5 \in \rm GF(2^3)$.<br>
-*But since the codeword&nbsp; $\underline {z}$&nbsp; found by the decoder is also supposed to be a valid Reed&ndash;Solomon code word &nbsp; &#8658; &nbsp; $\underline {z} &#8712; \mathcal{C}_{\rm RS}$, must hold as well:
+*But since the code word&nbsp; $\underline {z}$&nbsp; found by the decoder is also supposed to be a valid Reed&ndash;Solomon code word &nbsp; &#8658; &nbsp; $\underline {z} &#8712; \mathcal{C}_{\rm RS}$,&nbsp; it must hold as well:
 ::<math>{ \boldsymbol{\rm H}} \cdot \underline {z}^{\rm T} = \underline {0}^{\rm T}  \hspace{0.3cm} \Rightarrow \hspace{0.3cm}
@@ Line 117: / Line 112: @@
 \hspace{0.05cm}. </math>
-*This gives four equations for the unknowns&nbsp; $z_2$,&nbsp; $z_3$&nbsp; and &nbsp;$z_5$. With unique solution &ndash; and only with such &ndash; the decoding is successful and one can then say with certainty that indeed&nbsp; $\underline {c} = \underline {z} $&nbsp; was sent.<br><br>
+*This gives four equations for the unknowns&nbsp; $z_2$,&nbsp; $z_3$&nbsp; and &nbsp;$z_5$.&nbsp; With unique solution &ndash; and only with such &ndash; the decoding is successful and one can then say with certainty that indeed &nbsp; $\underline {c} = \underline {z} $ &nbsp; was sent.<br><br>

← Older revision		Revision as of 12:32, 20 October 2022
Line 13:		Line 13:

	# This chapter based on the  [[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Erasure_Channel_.E2.80.93_BEC\| "BEC model"]]  ("Binary Erasure Channel"),  which marks an uncertain bit as  "erasure"  $\rm E$.		# This chapter based on the  [[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Erasure_Channel_.E2.80.93_BEC\| "BEC model"]]  ("Binary Erasure Channel"),  which marks an uncertain bit as  "erasure"  $\rm E$.
−	# In contrast to the  [[Channel_Coding/~~Signal_classification~~#Binary_Symmetric_Channel_.E2.80.93_BSC\| "BSC model"]]  ("Binary Symmetric Channel") and   [[Channel_Coding/Channel_Models_and_Decision_Structures#AWGN_channel_at_Binary_Input\| "AWGN model"]]  ("Additive White Gaussian Noise"),   bit errors  $(y_i ≠ c_i)$  are excluded here.	+	# In contrast to the  [[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Symmetric_Channel_.E2.80.93_BSC\| "BSC model"]]  ("Binary Symmetric Channel") and   [[Channel_Coding/Channel_Models_and_Decision_Structures#AWGN_channel_at_Binary_Input\| "AWGN model"]]  ("Additive White Gaussian Noise"),   bit errors  $(y_i ≠ c_i)$  are excluded here.

@@ Line 23: / Line 23: @@
-The diagram shows the block diagram, which is slightly different from the model in chapter&nbsp; [[Channel_Coding/Decoding_of_Linear_Block_Codes#Block_diagram_and_requirements|"Decoding linear block codes"]]:
+The graphic shows the block diagram,&nbsp; which is slightly different from the model in chapter&nbsp; [[Channel_Coding/Decoding_of_Linear_Block_Codes#Block_diagram_and_requirements|"Decoding oflinear block codes"]]:
-*Since Reed&ndash;Solomon codes are linear block codes, information word&nbsp; $\underline{u}$&nbsp; and code word&nbsp; $\underline{c}$&nbsp; are also related here via the generator matrix $\boldsymbol{\rm G}$ and the following equation:
+*Since Reed&ndash;Solomon codes are linear block codes,&nbsp; the information word&nbsp; $\underline{u}$&nbsp; and the code word&nbsp; $\underline{c}$&nbsp; are also related via the generator matrix&nbsp; $\boldsymbol{\rm G}$&nbsp; and following equation:
 ::<math>\underline {c} = {\rm enc}(\underline {u}) = \underline {u} \cdot { \boldsymbol{\rm G}}
-\hspace{0.3cm} {\rm mit}  \hspace{0.3cm}\underline {u} = (u_0, u_1,\hspace{0.05cm}\text{ ... }\hspace{0.1cm}, u_i, \hspace{0.05cm}\text{ ... }\hspace{0.1cm}, u_{k-1})\hspace{0.05cm}, \hspace{0.2cm}
+\hspace{0.3cm} {\rm with}  \hspace{0.3cm}\underline {u} = (u_0, u_1,\hspace{0.05cm}\text{ ... }\hspace{0.1cm}, u_i, \hspace{0.05cm}\text{ ... }\hspace{0.1cm}, u_{k-1})\hspace{0.05cm}, \hspace{0.2cm}
 \underline {c} = (c_0, c_1, \hspace{0.05cm}\text{ ... }\hspace{0.1cm}, c_i, \hspace{0.05cm}\text{ ... }\hspace{0.1cm}, c_{n-1})
 \hspace{0.05cm}.</math>
-*For the individual symbols of information block and code word, Reed&ndash;Solomon coding applies:
+*For the individual symbols of information block and code word,&nbsp; Reed&ndash;Solomon coding applies:
-::<math>u_i \in {\rm GF}(q)\hspace{0.05cm},\hspace{0.2cm}c_i \in {\rm GF}(q)\hspace{0.3cm}{\rm mit}\hspace{0.3cm} q = n+1 = 2^m
+::<math>u_i \in {\rm GF}(q)\hspace{0.05cm},\hspace{0.2cm}c_i \in {\rm GF}(q)\hspace{0.3cm}{\rm with}\hspace{0.3cm} q = n+1 = 2^m
 \hspace{0.3cm} \Rightarrow  \hspace{0.3cm} n = 2^m - 1\hspace{0.05cm}. </math>
-*Each code symbol&nbsp; $c_i$&nbsp; is thus represented by&nbsp; $m &#8805; 2$&nbsp; binary symbols (bits). For comparison: &nbsp; For the binary block codes&nbsp; $q=2$,&nbsp; $m=1$&nbsp; and the code word length&nbsp; $n$&nbsp; is freely selectable.<br>
+*Each code symbol&nbsp; $c_i$&nbsp; is thus represented by&nbsp; $m &#8805; 2$&nbsp; binary symbols.&nbsp; For comparison: &nbsp; For the binary block codes hold&nbsp; $q=2$,&nbsp; $m=1$&nbsp; and the code word length&nbsp; $n$&nbsp; is freely selectable.<br>
-*When coding at symbol level, the BEC model must be extended to&nbsp; $m$ BEC model. With probability&nbsp; $\lambda_m &asymp; m \cdot\lambda$&nbsp; a code symbol&nbsp; $c_i$&nbsp; is erased&nbsp; $(y_i = \rm E)$&nbsp; and it holds&nbsp; ${\rm Pr}(y_i = c_i) = 1 - \lambda_m$. For more details on the conversion of the two models, see the&nbsp; [[Aufgaben:Exercise_2.11Z:_Erasure_Channel_for_Symbols|"Exercise 2.11Z"]].<br>
+*When encoding at symbol level,&nbsp; the BEC model must be extended to the&nbsp; "$m$-BEC model":&nbsp;
-*If too many symbols of the received word&nbsp; $\underline{y}$&nbsp; are erased, the decoder reports that this word cannot be decoded and may send the sequence again.<br><br>
+In the following, we deal only with the block&nbsp; "code word finder"&nbsp; $\rm (CWF)$,&nbsp; which extracts from the received vector&nbsp; $\underline{y}$&nbsp; the vector&nbsp; $\underline{z} &#8712; \mathcal{C}_{\rm RS}$:
 In the case of the erasure channel&nbsp; ($m$ BEC)&nbsp; unlike the &nbsp;$m$ BSC, which is described in the chapter&nbsp; [[Channel_Coding/Error_Correction_According_to_Reed-Solomon_Coding|"Error correction after Reed-Solomon coding"]]&nbsp; applies, an error decision&nbsp; $(\underline{z} \ne\underline{c})$&nbsp; is excluded &nbsp; &#8658; &nbsp; Block error probability&nbsp; ${\rm Pr}(\underline{z}\ne\underline{c}) = 0$ &nbsp; &#8658; &nbsp; ${\rm Pr}(\underline{v}\ne\underline{u}) = 0$.

@@ Line 6: / Line 6: @@
 }}
-== Block diagram and requirements for RS fault detection ==
+== Block diagram and requirements for Reed-Solomon error detection ==
 <br>
-In the&nbsp; [[Channel_Coding/Decoding_of_Linear_Block_Codes#Decoding_at_the_Binary_Erasure_Channel|"Decoding at the Binary Erasure Channel"]]&nbsp; chapter we showed for the binary block codes which calculations the decoder has to perform to decode from an incomplete received word&nbsp; $\underline{y}$&nbsp; the transmitted code word&nbsp; $\underline{x}$&nbsp; in the best possible way. In the Reed&ndash;Solomon chapter we renamed&nbsp; $\underline{x}$&nbsp; to&nbsp; $\underline{c}$&nbsp;.
+In the&nbsp; [[Channel_Coding/Decoding_of_Linear_Block_Codes#Decoding_at_the_Binary_Erasure_Channel|"Decoding at the Binary Erasure Channel"]]&nbsp; chapter we showed for the binary block codes,&nbsp; which calculations the decoder has to perform to decode from an incomplete received word&nbsp; $\underline{y}$&nbsp; the transmitted code word&nbsp; $\underline{x}$&nbsp; in the best possible way.&nbsp; In the Reed&ndash;Solomon chapter we renamed&nbsp; $\underline{x}$&nbsp; to&nbsp; $\underline{c}$.
-This is also based on the [[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Erasure_Channel_.E2.80.93_BEC| "BEC Channel Model]"]&nbsp; (<i>Binary Erasure Channel</i>&nbsp;), which marks an uncertain bit as&nbsp; <i>erasure</i>&nbsp; $\rm E$&nbsp;. In contrast to&nbsp; [[Channel_Coding/Signal_classification#Binary_Symmetric_Channel_.E2.80.93_BSC| BSC]]&nbsp; (<i>Binary Symmetric Channel</i>&nbsp;) and&nbsp; [[Channel_Coding/Channel_Models_and_Decision_Structures#AWGN_channel_at_Binary_Input| AWGN]]&nbsp; (<i>Additive White Gaussian Noise</i>&nbsp;) bit errors&nbsp; $(y_i &ne; c_i)$&nbsp; are excluded here. Each bit of a received word
+[[File:EN_KC_T_2_4_S1_2neu.png|right|frame|Transmission system with Reed-Solomon coding/decoding and erasure channel|class=fit]]
 *thus matches the corresponding bit of the code word&nbsp; $(y_i = c_i)$, or
 *is already marked as a cancellation&nbsp; $(y_i = \rm E)$.<br>
 The diagram shows the block diagram, which is slightly different from the model in chapter&nbsp; [[Channel_Coding/Decoding_of_Linear_Block_Codes#Block_diagram_and_requirements|"Decoding linear block codes"]]:

← Older revision		Revision as of 14:34, 8 October 2022
Line 15:		Line 15:


−	[[File:~~P ID2544 KC T 2 4 S1 v2~~.png\|center\|frame\|Transmission system with Reed-Solomon coding/decoding and erasure channel\|class=fit]]	+	[[File:EN_KC_T_2_4_S1_2neu.png\|center\|frame\|Transmission system with Reed-Solomon coding/decoding and erasure channel\|class=fit]]

	The diagram shows the block diagram, which is slightly different from the model in chapter  [[Channel_Coding/Decoding_of_Linear_Block_Codes#Block_diagram_and_requirements\|"Decoding linear block codes"]]:		The diagram shows the block diagram, which is slightly different from the model in chapter  [[Channel_Coding/Decoding_of_Linear_Block_Codes#Block_diagram_and_requirements\|"Decoding linear block codes"]]:

@@ Line 221: / Line 221: @@
 == Exercises for the chapter ==
 <br>
-[[Aufgaben:2.11_RS–Decodierung_nach_„Erasures”|Aufgabe 2.11: RS–Decodierung nach „Erasures”]]
+[[Aufgaben:Exercise_2.11:_Reed-Solomon_Decoding_according_to_"Erasures"|Exercise 2.11: Reed-Solomon Decoding according to "Erasures"]]
-[[Aufgaben:2.11Z_Erasure–Kanal_für_Symbole|Aufgabe 2.11Z: Erasure–Kanal für Symbole]]
+[[Aufgaben:Exercise_2.11Z:_Erasure_Channel_for_Symbols|Exercise 2.11Z: Erasure Channel for Symbols]]
 {{Display}}