Reed-Solomon Decoding for the Erasure Channel

From LNTwww
< Channel Coding
Revision as of 11:34, 24 November 2022 by Hwang (talk | contribs)

  1. Channel Coding
  2. Reed–Solomon–Codes and Their Decoding
  3. Reed-Solomon Decoding for the Erasure Channel

Block diagram and requirements for Reed-Solomon error detection


In the  "Decoding at the Binary Erasure Channel"  chapter we showed for the binary block codes,  which calculations the decoder has to perform to decode from an incomplete received word  $\underline{y}$  the transmitted code word  $\underline{x}$  in the best possible way.  In the Reed–Solomon chapter we renamed  $\underline{x}$  to  $\underline{c}$.

Transmission system with Reed-Solomon coding/decoding and erasure channel
  1. This chapter is based on the  $\text{BEC model}$  ("Binary Erasure Channel"),  which marks an uncertain bit as  "erasure"  $\rm E$. 
  2. In contrast to the  $\text{BSC model}$  ("Binary Symmetric Channel") and   $\text{AWGN model}$  ("Additive White Gaussian Noise"),   bit errors  $(y_i ≠ c_i)$  are excluded here.


Each bit of a received word

  • thus matches the corresponding bit of the code word  $(y_i = c_i)$,  or
  • is already marked as a cancellation  $(y_i = \rm E)$.


The graphic shows the block diagram,  which is slightly different from the model in chapter  $\text{Decoding oflinear block codes}$:

  • Since Reed–Solomon codes are linear block codes,  the information word  $\underline{u}$  and the code word  $\underline{c}$  are also related via the generator matrix  $\boldsymbol{\rm G}$  and following equation:
\[\underline {c} = {\rm enc}(\underline {u}) = \underline {u} \cdot { \boldsymbol{\rm G}} \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}.\]
  • For the individual symbols of information block and code word,  Reed–Solomon coding applies:
\[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}. \]
  • Each code symbol  $c_i$  is thus represented by  $m ≥ 2$  binary symbols.  For comparison:   For the binary block codes hold  $q=2$,  $m=1$  and the code word length  $n$  is freely selectable.
  • When encoding at symbol level,  the BEC model must be extended to the  "m-BEC model": 
  • With probability  $\lambda_m ≈ m \cdot\lambda$  a code symbol  $c_i$  is erased  $(y_i = \rm E)$  and it holds  ${\rm Pr}(y_i = c_i) = 1 - \lambda_m$. 
  • For more details on the conversion of the two models,  see  "Exercise 2.11Z".
  • In the following, we deal only with the block  "code word finder"  $\rm (CWF)$,  which extracts from the received vector  $\underline{y}$  the vector  $\underline{z} ∈ \mathcal{C}_{\rm RS}$:
  • If the number  $e$  of erasures in the vector   $\underline{y}$   is sufficiently small,  the entire code word can be found with certainty:   $(\underline{z}=\underline{c})$.
  • If too many symbols of the received word  $\underline{y}$  are erased,  the decoder reports that this word cannot be decoded.  It may then be necessary to send this sequence again.
  • In the case of the  "m-BEC"  model,  an error decision  $(\underline{z} \ne\underline{c})$  is excluded   ⇒   »block error probability«  ${\rm Pr}(\underline{z}\ne\underline{c}) = 0$   ⇒   ${\rm Pr}(\underline{v}\ne\underline{u}) = 0$.
  • The reconstructed information word results according to the block diagram  $($yellow background$)$  to  $\underline{v} = {\rm enc}^{-1}(\underline{z})$.
  • With the generator matrix  $\boldsymbol{\rm G}$  can also be written for this:
\[\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}. \]

Decoding procedure using the RSC (7, 3, 5)8 as an example


In order to be able to represent the Reed–Solomon decoding at the extinction channel as simply as possible, we start from a concrete task:

  • A Reed–Solomon code with parameters  $n= 7$,  $k= 3$  and  $q= 2^3 = 8$ is used.
  • Thus,  for the information word  $\underline{u}$  and the code word  $\underline{c}$:
\[\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}.\]
  • The parity-check matrix  $\boldsymbol{\rm H}$  is:
\[{ \boldsymbol{\rm H}} = \begin{pmatrix} 1 & \alpha^1 & \alpha^2 & \alpha^3 & \alpha^4 & \alpha^5 & \alpha^6\\ 1 & \alpha^2 & \alpha^4 & \alpha^6 & \alpha^1 & \alpha^{3} & \alpha^{5}\\ 1 & \alpha^3 & \alpha^6 & \alpha^2 & \alpha^{5} & \alpha^{1} & \alpha^{4}\\ 1 & \alpha^4 & \alpha^1 & \alpha^{5} & \alpha^{2} & \alpha^{6} & \alpha^{3} \end{pmatrix}\hspace{0.05cm}. \]

⇒   For example,  the received vector 

$$\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)$$

  is assumed here. Then holds:

  • Since the erasure channel produces no errors,  four of the code symbols are known to the decoder:
\[c_0 = \alpha^1 \hspace{0.05cm},\hspace{0.2cm} c_1 = 1 \hspace{0.05cm},\hspace{0.2cm} c_4 = \alpha^2 \hspace{0.05cm},\hspace{0.2cm} c_6 = \alpha^5 \hspace{0.05cm}.\]
  • It is obvious that the block  "code word finder"  $\rm (CWF)$  is to provide a vector of the form   $\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)$   with  $z_2,\hspace{0.03cm}z_3,\hspace{0.03cm}z_5 \in \rm GF(2^3)$.
  • But since the code word  $\underline {z}$  found by the decoder is also supposed to be a valid Reed–Solomon code word   ⇒   $\underline {z} ∈ \mathcal{C}_{\rm RS}$,  it must hold as well:
\[{ \boldsymbol{\rm H}} \cdot \underline {z}^{\rm T} = \underline {0}^{\rm T} \hspace{0.3cm} \Rightarrow \hspace{0.3cm} \begin{pmatrix} 1 & \alpha^1 & \alpha^2 & \alpha^3 & \alpha^4 & \alpha^5 & \alpha^6\\ 1 & \alpha^2 & \alpha^4 & \alpha^6 & \alpha^1 & \alpha^{3} & \alpha^{5}\\ 1 & \alpha^3 & \alpha^6 & \alpha^2 & \alpha^{5} & \alpha^{1} & \alpha^{4}\\ 1 & \alpha^4 & \alpha^1 & \alpha^{5} & \alpha^{2} & \alpha^{6} & \alpha^{3} \end{pmatrix} \cdot \begin{pmatrix} c_0\\ c_1\\ z_2\\ z_3\\ c_4\\ z_5\\ c_6 \end{pmatrix} = \begin{pmatrix} 0\\ 0\\ 0\\ 0 \end{pmatrix} \hspace{0.05cm}. \]
  • This gives four equations for the unknowns  $z_2$,  $z_3$  and  $z_5$.  With unique solution – and only with such – the decoding is successful and one can then say with certainty that indeed   $\underline {c} = \underline {z} $   was sent.


Solution of the matrix equations using the example of the RSC (7, 3, 5)8


Thus,  it is necessary to find the admissible code word  $\underline {z}$  that satisfies the determination equation 

$$\boldsymbol{\rm H} \cdot \underline {z}^{\rm T}. $$
  • For convenience,  we split the vector  $\underline {z}$  into two partial vectors, viz.
  1. the vector   $\underline {z}_{\rm E} = (z_2, z_3, z_5)$   of the erased symbols  $($subscript  "$\rm E$"  for  "erasures"$)$,
  2. the vector   $\underline {z}_{\rm K} = (c_0, c_1,c_4, c_6)$   of known symbols  $($subscript  "$\rm K$"  for  "korrect"   ⇒   "correct" $)$.

  • With the associated partial matrices  $($each with  $n-k = 4$  rows$)$
\[{ \boldsymbol{\rm H}}_{\rm E} = \begin{pmatrix} \alpha^2 & \alpha^3 & \alpha^5 \\ \alpha^4 & \alpha^6 & \alpha^{3} \\ \alpha^6 & \alpha^2 & \alpha^{1} \\ \alpha^1 & \alpha^{5} & \alpha^{6} \end{pmatrix} \hspace{0.05cm},\hspace{0.4cm} { \boldsymbol{\rm H}}_{\rm K} \begin{pmatrix} 1 & \alpha^1 & \alpha^4 & \alpha^6\\ 1 & \alpha^2 & \alpha^1 & \alpha^{5}\\ 1 & \alpha^3 & \alpha^{5} & \alpha^{4}\\ 1 & \alpha^4 & \alpha^{2} & \alpha^{3} \end{pmatrix}\]
the equation of determination is thus:
\[{ \boldsymbol{\rm H}}_{\rm E} \cdot \underline {z}_{\rm E}^{\rm T} + { \boldsymbol{\rm H}}_{\rm K} \cdot \underline {z}_{\rm K}^{\rm T} = \underline {0}^{\rm T} \hspace{0.5cm} \Rightarrow \hspace{0.5cm} { \boldsymbol{\rm H}}_{\rm E} \cdot \underline {z}_{\rm E}^{\rm T} = - { \boldsymbol{\rm H}}_{\rm K} \cdot \underline {z}_{\rm K}^{\rm T}\hspace{0.05cm}. \]
  • Since for all elements  $z_i ∈ {\rm GF}(2^m)$   ⇒   the  $\text{additive inverse}$  ${\rm Inv_A}(z_i)= (- z_i) = z_i$  holds in the same way
\[{ \boldsymbol{\rm H}}_{\rm E} \cdot \underline {z}_{\rm E}^{\rm T} = { \boldsymbol{\rm H}}_{\rm K} \cdot \underline {z}_{\rm K}^{\rm T} = \begin{pmatrix} 1 & \alpha^1 & \alpha^4 & \alpha^6\\ 1 & \alpha^2 & \alpha^1 & \alpha^{5}\\ 1 & \alpha^3 & \alpha^{5} & \alpha^{4}\\ 1 & \alpha^4 & \alpha^{2} & \alpha^{3} \end{pmatrix} \cdot \begin{pmatrix} \alpha^1\\ 1\\ \alpha^{2}\\ \alpha^{6} \end{pmatrix} = \hspace{0.45cm}... \hspace{0.45cm}= \begin{pmatrix} \alpha^3\\ \alpha^{4}\\ \alpha^{2}\\ 0 \end{pmatrix} \hspace{0.05cm}.\]
  • The right–hand side of the equation results for the considered example   ⇒   $\underline {z}_{\rm K} = (c_0, c_1,c_4, c_6)$  and is based on the polynomial   $p(x) = x^3 + x +1$,  which leads to the following powers  $($in   $\alpha)$ :
\[\alpha^3 =\alpha + 1\hspace{0.05cm}, \hspace{0.3cm} \alpha^4 = \alpha^2 + \alpha\hspace{0.05cm}, \hspace{0.3cm} \alpha^5 = \alpha^2 + \alpha + 1\hspace{0.05cm}, \hspace{0.3cm} \alpha^6 = \alpha^2 + 1\hspace{0.05cm}, \hspace{0.3cm} \alpha^7 \hspace{-0.15cm} = \hspace{-0.15cm} 1\hspace{0.05cm}, \hspace{0.3cm} \alpha^8 = \alpha^1 \hspace{0.05cm}, \hspace{0.3cm} \alpha^9 = \alpha^2 \hspace{0.05cm}, \hspace{0.3cm} \alpha^{10} = \alpha^3 = \alpha + 1\hspace{0.05cm},\hspace{0.1cm} \text{...}\]
  • Thus,  the matrix equation for determining the vector  $\underline {z}_{\rm E}$  we are looking for:
\[\begin{pmatrix} \alpha^2 & \alpha^3 & \alpha^5 \\ \alpha^4 & \alpha^6 & \alpha^{3} \\ \alpha^6 & \alpha^2 & \alpha^{1} \\ \alpha^1 & \alpha^{5} & \alpha^{6} \end{pmatrix} \cdot \begin{pmatrix} z_2\\ z_3\\ z_5 \end{pmatrix} \stackrel{!}{=} \begin{pmatrix} \alpha^3\\ \alpha^{4}\\ \alpha^{2}\\ 0 \end{pmatrix} \hspace{0.05cm}. \]
  • Solving this matrix equation  $($most easily by program$)$,  we get
\[z_2 = \alpha^2\hspace{0.05cm},\hspace{0.25cm}z_3 = \alpha^1\hspace{0.05cm},\hspace{0.25cm}z_5 = \alpha^5 \hspace{0.5cm} \Rightarrow \hspace{0.5cm}\underline {z} = \left ( \hspace{0.05cm} \alpha^1, \hspace{0.05cm}1, \hspace{0.05cm}\alpha^2, \hspace{0.05cm}\alpha^1, \hspace{0.05cm}\alpha^2, \hspace{0.05cm}\alpha^5, \hspace{0.05cm}\alpha^5 \hspace{0.05cm}\right ) \hspace{0.05cm}.\]
  • The result is correct,  as the following control calculations show:
\[\alpha^2 \cdot \alpha^2 + \alpha^3 \cdot \alpha^1 + \alpha^5 \cdot \alpha^5 = \alpha^4 + \alpha^4 + \alpha^{10} = \alpha^{10} = \alpha^3\hspace{0.05cm},\]
\[\alpha^4 \cdot \alpha^2 + \alpha^6 \cdot \alpha^1 + \alpha^3 \cdot \alpha^5 = (\alpha^2 + 1) + (1) + (\alpha) = \alpha^{2} + \alpha = \alpha^4\hspace{0.05cm},\]
\[\alpha^6 \cdot \alpha^2 + \alpha^2 \cdot \alpha^1 + \alpha^1 \cdot \alpha^5 = (\alpha) + (\alpha + 1) + (\alpha^2 + 1) = \alpha^{2} \hspace{0.05cm},\]
\[\alpha^1 \cdot \alpha^2 + \alpha^5 \cdot \alpha^1 + \alpha^6 \cdot \alpha^5 = (\alpha + 1) + (\alpha^2 + 1) + (\alpha^2 + \alpha) = 0\hspace{0.05cm}.\]
$$\underline {v} = \underline {z} \cdot \boldsymbol{\rm G}^{\rm T} = (\alpha^1,\hspace{0.05cm}1,\hspace{0.05cm}\alpha^3).$$

Exercises for the chapter


Exercise 2.11: Reed-Solomon Decoding according to "Erasures"

Exercise 2.11Z: Erasure Channel for Symbols



Retrieved from "http://en.lntwww.de/index.php?title=Channel_Coding/Reed-Solomon_Decoding_for_the_Erasure_Channel&oldid=50420"
  • Powered by MediaWiki