1. $(n,\; k)$ $t$-error-correcting RS code

RS codes are non binary codes with code symbols from a Galois field of $q$ elements $GF(q)$. From coding theory, if $p$ is a prime number and $q$ is any power of $p$, there are codes with code symbols from a $q$-symbol alphabet. These codes are called $q$-ary BCH codes.

The filed $GF(2^m)$ is formed by a primitive polynomial of degree $m$ with $\alpha$ as the primitive element of the field. $\alpha$ is called the $n^{th}$ root of unity in $GF(2^m)$ since $\alpha^n=1$ for $n=2^m-1$. With $q=2^m$, the code symbols of an RS code are $\alpha^i,\; i=\infty,\; 1,\; 2,\; …,\; 2^m-2$, which are the $2^m$ distinct elements of $GF(2^m)$. Note that $\alpha^{\infty}=0$.

Let $m_0$, $d$, $S$, and $t$ be any positive integers, and $\alpha$ be an element of $GF(q^S)$. There exists a $q$-ary BCH code of length $n=q^S-1$ symbols that corrects any combination of $t$ or fewer errors and requires no more than $2tS$ parity-check symbols. Let $g(X)$ be a polynomial of lowest degree over $GF(q)$ and select $q=2^m$. The code generated by $g(X)$ is a cyclic BCH code and has

$\alpha^{m_0},\; \alpha^{m_0+1},\; …,\; \alpha^{m_0+d-2}$

as roots. The special q-ary BCH code, for which $S=m_0=1$ and $d=2t+1$, is called the RS code. The roots of the RS code are

$\color{red}{ \alpha,\; \alpha^2,\; \alpha^3,\; …,\; \alpha^{2t}}$

Since the minimum polynomial with root of $\alpha^j$ is simply $(x+\alpha^j)$, the generator polynomial $g(X)$ of a $t$-error-correcting RS code of length $2^m-1$ is

$g(X)=(X+\alpha)(X+\alpha^2)\; …\; (X+\alpha^{2t})$

2. Encoding

$q(X)$: quotient of $\frac{X^{n-k}M(X)}{g(X)}$

$r(X)$: remainder of $\frac{X^{n-k}M(X)}{g(X)}$

$X^{n-k}M(X)=q(X)g(X)+r(X)$

$\color{red}{C(X)=X^{n-k}M(X)\; +\; (X^{n-k}M(X))\; mod\; g(X) = X^{n-k}M(X)+r(X)\; =\; q(X)g(X)}$

The codewords consist of all multiples of $g(X)$. The degree of $g(X)$ is $2t$ and its roots are $\alpha,\; \alpha^2,\; …\; \alpha^{2t}$. Since every codeword is some multiples of $g(X)$, $\alpha,\; \alpha^2,\; …\; \alpha^{2t}$ are also roots of every codeword.

3. Decoding

The decoding procedure involves finding not only the error locations, but the error values as well.

Let $C(X)$ be the transmitted codeword, $E(X)$ be the channel noise error pattern, and $R(X)$ be the received codeword:

$R(X)=C(X)+E(X)$

The error pattern $E(X)$ can be described by a list of values and locations of its nonzero components. Error location will be given in terms of an error-location number, which is simply $\alpha^j$ for the $(n-j)^{th}$ symbol. Let $X_j$ be the error location number and $e_j$ be the error value. Then for each nonzero component of $E(X)$, a pair of field elements $(x_j,\; e_j)$ is required to describe the error. If $E(X)$ has $p$ errors, then $p$ pairs of $(x_j,\; e_j)$ are required. Any decoding procedure is a procedure for locating these $p$ pairs of $(x_j,\; e_j)$ if $p\; \le\; t$.

Assume that $E(X)$ is an error pattern of $p$ errors at locations $j_1,\; j_2,\; …,\; j_p$. Then

$\color{red} {E(X)=e_{j_1}x_{j_1}+e_{j_2}x_{j_2} +\; …\; e_{j_p}x_{j_p}}$

where $p\; \le\; t$ and $0\; \le\; j_1\; <\; j_2\; <\; …\; j_p\; \le\; n-1$

The first step in decoding is to check whether $R(X)$ is a codeword by calculating the syndrome. If the syndrome is zero, then either $R(X)$ actually has no errors or $R(X)$ has an undetectable error. In either case, $R(X)$ is accepted as no error. A nonzero syndrome indicates that an error has been detected; the error may or may not be correctable. For the RS codes, the syndrome is defined as a vector $S$ with $2t$ components:

$E13: \; S_i=R(\alpha^i)=r_0+r_1\alpha^i+r_2(\alpha^i)^2+\; …\; + r_{n-1}(\alpha^i)^{n-1},\; i=1,\;2,\;3,\; …\; 2t$

Also,

$\color{red} {S_i=R(\alpha^i)=C(\alpha^i)+E(\alpha^i)=0+E(\alpha^i)=\sum_{k=1}^pe_{j_k}x_{j_k}^i}$

I.e.,

$\color{red} {S_i=e_{j_1}(\alpha^{j_1})^i\; +\; e_{j_2}(\alpha^{j_2})^i\; +\; …\; +\; e_{j_p}(\alpha^{j_p})^i,\; i=1,\; 2\; 3\; ,\; …\; 2t}$

Expanding equation gives the results

$S_1\; = \; e_{j_1}\alpha^{j_1} + e_{j_2}\alpha^{j_2}+\; … \; +e_{j_p}\alpha^{j_p}$

$S_2\; = \; e_{j_1}(\alpha^{j_1})^2 + e_{j_2}(\alpha^{j_2})^2+\; … \; +e_{j_p}(\alpha^{j_p})^2$

$\qquad\qquad\qquad\qquad ...$

$S_{2t}\; = \; e_{j_1}{(\alpha^{j_1})}^{2t} + e_{j_2}(\alpha^{j_2})^{2t}+\; … \; +e_{j_p}(\alpha^{j_p})^{2t}$

Those $2t$ nonlinear equations (power-sum symmetric functions) relate the $2t$ unknown quantities of $S_i$ to $2p$ unknowns consisting of $p$ unknown locations and $p$ unknown error values. Any error correction procedure is a method of solving this set of equations for the $p$ pairs of $(e_{j_x}, \alpha^{j_x}),\; x=1,\; 2,\; …,\; p$. Once $\alpha^{j_1},\; \alpha^{j_2},\; …,\; \alpha^{j_p}$ are found, the powers $j_1,\; j_2,\; …,\; j_p$ will indicate the error locations in $E(X)$. In general, there might be many error patterns that satisfy the $2t$ equations. If $p\; \le\; t$, then the error pattern with the smallest $p$ is the actual error pattern.

For notational convenience, let

$\beta_x\; =\; \alpha^{j_x},\; x=1, 2,\; …\; p$

Next, let the error location polynomial be defined as follows:

$\sigma(X)\; =\; (1+\beta_1X)(1+\beta_2X)\; …\; (1+\beta_pX)$

$\qquad\;\;\; = \sigma_0\; +\; \sigma_1X\; +\; \sigma_2X^2\; +\; …\; +\; \sigma_pX^p$

where

$\qquad \sigma_0\; =\; 1$

$\qquad \sigma_1\; =\; \beta_1\; +\; \beta_2\; +\; …\; +\; \beta_p$

$\qquad \sigma_2\; =\; \beta_1\beta_2\; +\; \beta_1\beta_3\; +\; …\; +\; \beta_{p-1}\beta_p$

$\qquad \sigma_3\; =\; \beta_1\beta_2\beta_3\; +\; \beta_1\beta_2\beta_3\; +\; …\; +\; \beta_{p-2}\beta_{p-1}\beta_p$

$\qquad \sigma_p\; =\; \beta_1\beta_2\beta_3\; …\; \beta_p$

The roots of $\sigma(X)$ are $\beta_1^{-1},\; \beta_2^{-2},\; …\; \beta_p^{-1}$, which are the inverses of the error location numbers. It can be seen that the coefficients of $\sigma(X)$ are related to the syndrome components $S_i,\; i=1,2,\; …\; 2t$. The coefficients $\sigma_1,\; \sigma_2,\; …\; \sigma_p$ are known as elementary symmetric functions of $\beta_1,\; \beta_2,\; …,\; \beta_p$. Therefore, if it is psbl to find $\sigma(X)$ from the syndrome components, the error location numbers can be found and the error pattern $E(X)$ can be determined.

Decoding procedure consists of four major steps:

S1: calculate the syndrome $S\; =\; (S_1,\; S_2,\; …\; S_{2t})$ from $R(X)$

S2: calculate the error location polynomial $\sigma(X)$ from $S$

S3: determine the error locations $X_j$ by finding the roots of $\sigma(X)$

S4: calculate the error value $e_j$ from $X_j$ and $S$

There are two methods for calculating the syndrome ($S$): the standard method, and the shift register method. The standard method uses equation $E13$ because this is the way the syndrome is defined. The shift register method uses the $g(X)$ encoding shift register.

For larger $t(t\; \ge\; 4)$, the best way to calculate the syndrome is to use the $g(X)$ shift register. This will result in some saving in logic because this shift register is already used for encoding. However, the $S$ calculated by $g(X)$ is not the same as the $S$ calculated by $R(\alpha^i)$ of Equation $E13$, but they are related.

From Equation $E13$, let $S\; =\; (S_1,\; S_2,\; …,\; S_{2t})$ be the syndrome calculated by $R(\alpha^i)$ with $S_i\; =\; R(\alpha^i),\; i=1,2,\; …\; 2t$. Let

$S^*\; =\; (S_1^*,\; S_2^*,\; …,\; S_{2t}^*)$

be the remainder calculated by dividing $R(X)$ by $g(X)$. The remainder $S^*$ is another form of the syndrome but $S^*\; \ne\; S$. Using the Euclidean division algorithm, the result of $R(X)/g(X)$ is

$R(X)\; =\; Q(X)g(X)\; +\; S^*(X)$

where $Q(X)$ is the quotient and

$S^*(X)\; =\; S_1^*\; +\; S_2^*X\; +\; S_3^*X^2\; +\; …\; +\; S_{2t}^*X^{2t-1}$

is the remainder. Substituting $X$ by $\alpha^i$ gives the result

$R(\alpha^i)\; =\; Q(\alpha^i)g(\alpha^i)\; +\; S^*(\alpha^i)\; =\; S^*(\alpha^i)$

The relationship between $S$ and $S*$ is

$S_i\;\;\; =\; S^*(\alpha^i)$

$\qquad = S_1^*\; +\; S_2^*(\alpha^i)\; +\; S_3^*(\alpha^i)^2\; +\; …\; +\; S_{2t}^*(\alpha^i)^{2t-1},\; i=1,2,\; …\; 2t$

References

[1]. [A decoding procedure for the Reed-Solomon codes][http://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/19780022919.pdf]