RS(n,k) code for burst error-correction work out

This is a math workout problem that is the math part of my FPGA implementation of another class of BCH code. The math workout of my earlier blog of a binary BCH code of \((n,k,d)=(15,7,5)\) is applicable to this class of code, the RS code which is the non-binary version of BCH code. It will be based on the same primitive polynomial \(h(x)=1+x+x^4\) as the last exercise.

Another important class of BCH codes is RS code. It is a subfield subcode of the binary BCH and has many practical real-life applications. Eventhough its digits in code word are not binary, they have binary representation. This exercise is for \(RS(n=15,k=9,d=7)\) code.

RS field algebra

Most of everything algebra in binary BCH over \(GF(2)=\{0,1\}\) applies to this code. RS code generalized over \(GF(q)\) where \(q\) is power of prime. While the binary BCH, if \(\alpha\) is a primitive elemement in the field \(GF(q=2)\), the binary BCH of \(2t\) error-correction with \(g(x)=m_1(x)m_3(x)\) as its generator polynomial will have \(\{\alpha,\alpha^2,\alpha^3,\alpha^4\}\) as its roots. The RS code generalized over \(GF(2^4)\) will also have \(\{\alpha,\alpha^2,\alpha^3,\alpha^4\}\) as its roots with generator polynomial, \(g(x)=(\alpha+x)(\alpha^2+x)(\alpha^3+x)(\alpha^4+x)\) where the components are chosen from the field elements of \(GF(2^4)[x]\) ie.. subfield subcode.

Some definition

A binary Reed-Solomon code, \(RS(2^r,d)\) is a cyclic code over \(GF(2^r)\) with generator polynomial \(g(x)=(\alpha^{m+1}+x)(\alpha^{m+2}+x) \cdots (\alpha^{m+d-1}+x)\) for some integer \(m\) and some primitive element \(\alpha\) of \(GF(2^r)\).

\(RS(2^r,d)\) code is defined as code having,

\(n = 2^r -1\)
\(k = 2^r - d, n-k = 2t\)
\(codewords = 2^{rk}\)

RS code is a q-ary code and is also an MDS code (\(d=n-k+1\), Singleton bound). In summary, a \(t\) error-correcting RS code over \(GF(q=2^r)\), having \(\alpha\) as its primitive element has generator polynomial,

\begin{align*} g(x) &= (x+\alpha)(x+\alpha^2) \cdots (x+\alpha^{2t}) \\ &=g_0+g_1x+g_2x^2 + \cdots +g_{2t-1}x^{2t-1}+x^{2t} \end{align*}

The elements of \(GF(2^4)\) based on \(p(x)=x^4+x+1\) as generated in the old post is again tabulated below,

word	\(x^i\ mod\ (1+x+x^4)\)	power of \(\alpha\)
0000
1000	1	\(\alpha^0\)
0100	\(x\)	\(\alpha^1\)
0010	\(x^2\)	\(\alpha^2\)
0001	\(x^3\)	\(\alpha^3\)
1100	\(x^4 \equiv 1+x\)	\(\alpha^4\)
0110	\(x^5 \equiv x+x^2\)	\(\alpha^5\)
0011	\(x^6 \equiv x^2+x^3\)	\(\alpha^6\)
1101	\(x^7 \equiv 1+x+x^3\)	\(\alpha^7\)
1010	\(x^8 \equiv 1+x^2\)	\(\alpha^8\)
0101	\(x^9 \equiv x+x^3\)	\(\alpha^9\)
1110	\(x^{10} \equiv 1+x+x^2\)	\(\alpha^{10}\)
0111	\(x^{11} \equiv x+x^2+x^3\)	\(\alpha^{11}\)
1111	\(x^{12} \equiv 1+x+x^2+x^3\)	\(\alpha^{12}\)
1011	\(x^{13} \equiv 1+x^2+x^3\)	\(\alpha^{13}\)
1001	\(x^{14} \equiv 1+x^3\)	\(\alpha^{14}\)

Note that \(\alpha^{15} = \alpha^0 = 1\). As usual, the table above can be easily generated with Octave/MATLAB,

> I=eye(15);I=I(15:-1:1,:);
>> for i=1:15
[q,r(i,:)]=deconv(I(i,:),[1 0 0 1 1]);
end
>> r=mod(r(:,12:15),2)
r =

   0   0   0   1
   0   0   1   0
   0   1   0   0
   1   0   0   0
   ..
   1   0   0   1

where the result row vectors \(r\) are the remainders from the polynomial division.

For \(RS(2^4,5)\), the generator polynomial is,

\begin{align*} g_5(x) &=(\alpha + x)(\alpha^2+x)(\alpha^3+x)(\alpha^4+x) \\ &=x^4 + (\alpha^4 + \alpha^3 + \alpha^2 + \alpha)x^3 + (\alpha^7 + \alpha^6 + \alpha^4 + \alpha^3)x^2 + (\alpha^9 + \alpha^8 +\alpha^7 + \alpha^6)x + \alpha^{10} \end{align*}

By using the tabulated table above for the sum of power of \(\alpha\), the generator polynomial can be simplied, for example, \(\alpha^4+\alpha^3+\alpha^2+\alpha =1+x+x^3+x^2+x=1+x^2+x^3=\alpha^{13}\),

\begin{equation*} g_5(x) = x^4 + \alpha^{13}x^3 + \alpha^6 x^2 + \alpha^3 x + \alpha^{10} \end{equation*}

The generator matrix,

\begin{equation*} G= \left [ \begin{array}{cc} g(x) \\ xg(x) \\ \cdots \\ x^{k-1}g(x) \\ \end{array} \right] = \end{equation*}

\begin{equation*} \left [ \begin{array}{cc} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & \alpha^{13} & \alpha^6 & \alpha^3 & \alpha^{10} \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & \alpha^{13} & \alpha^6 & \alpha^3 & \alpha^{10} & 0 \\ \cdots \\ 1 & \alpha^{13} & \alpha^6 & \alpha^3 & \alpha^{10} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{array} \right] \end{equation*}

An 11-bit symbol input \(u=\alpha \alpha^2 0 1 \alpha^6 0 0 0 0 0 0\) would be encoded by this generator matrix as,

\begin{equation*} v = uG = 0 0 0 0 0 0 \alpha^6 \alpha\ \alpha \alpha \alpha^{14} \alpha^7 \alpha^{13} \alpha^6 \alpha^{11} \end{equation*}

Its corressponding polynomial,

\begin{equation*} v(x) = \alpha^{11}+\alpha^6x+\alpha^{13}x^2+\alpha^7x^3+\alpha^{14}x^4+ \alpha x^5+ \alpha x^6+ \alpha x^7+\alpha^6 x^8 \end{equation*}

For \(\alpha\) as its root, by substituting \(x\) with \(\alpha\), it should produce zero,

\begin{align*} v(\alpha) &= \alpha^{11}+\alpha^7+1+\alpha^{10}+\alpha^3+\alpha^6+\alpha^7+\alpha^8+\alpha^{14} \\ &= \alpha^{11}+1+\alpha^{10}+\alpha^3+\alpha^6+\alpha^8+\alpha^{14} \\ &= 0 \end{align*}

The binary representation of \(v, \hat{v}\) code word would have lenght of \(r(2^r-1) = 60\) bits, that is, \(\hat{v}=\) 0000 0000 ... 1100 1110 where each code symbol is mapped to its respective binary equivalent. It is one the reasons that \(\hat{v}\) performs well as burst error correction code where group of errors occur close together. Clearly \(v\) encode by using \(G\) matrix above is not in in systematic form unless the \(G\) matrix is reformulated into the form of,

\begin{equation*} G = \left[ \begin{array}{c|cc} I_k & P_{n-k} \end{array} \right] \end{equation*}

Encoding by polynomial division will also produce the systematic form. This is similar to binary BCH. Let,

\begin{equation*} u(x) = a_0x + a_1x + a_2x^2 + \cdots + a_{k-1}x^{k-1} \end{equation*}

be the message to be encoded. The \(2t\) parity check digits of the remainder from the division by \(g(x)\) would be,

\begin{equation*} r(x) = b_0x + b_1x + b_2x^2 + \cdots + a_{2t-1}x^{2t-1} \end{equation*}

For \(u=\alpha \alpha^2 0 1 \alpha^6 0 0 0 0 0 0\), encoding in systematic form as \(\frac{x^4u(x)}{g(x)}\) would be,

\begin{equation*} v(x) = \alpha x^{14} + \alpha^2 x^{13} + x^{11} + \alpha^6 x^{10} + \alpha^4 x^3 + \alpha^{11}x^2 + \alpha^8 x \end{equation*}

where the lower degree up to \(n-k-1\) of \(v(x)\) are the parity symbol bits. Verify that \(v(\alpha)\) obtained this way is also zero,

\begin{align*} v(\alpha) &= 1 + 1 + \alpha^{11} + \alpha + \alpha^7 + \alpha ^{13} + \alpha^9 \\ &= \alpha^{11}+ \alpha + \alpha^7 + \alpha^{13} + \alpha^9 \\ & = 0 \end{align*}

For \(RS(2^4,7)\), the generator polynomial is,

\begin{align*} g_7(x) &=(\alpha + x)(\alpha^2+x)(\alpha^3+x)(\alpha^4+x)(\alpha^5+x)(\alpha^6+x) \\ &= x^6 + (\alpha+\alpha^2+\alpha^3+\alpha^4+\alpha^5+\alpha^6)x^5 + (\alpha^3+\alpha^4+\alpha^7+\alpha^{10}+\alpha^{11})x^4 + \\ & (\alpha^6+\alpha^7+\alpha^9+\alpha^{10}+\alpha^{11}+\alpha^{12}+\alpha^{14}+\alpha^0)x^3 + \\ & (\alpha^{10}+\alpha^{11}+\alpha^{14}+\alpha^2+\alpha^3)x^2 + \\ & (\alpha^0+\alpha+\alpha^2+\alpha^3+\alpha^4+\alpha^5)x + \alpha^6 \end{align*}

Using the tabulated table above to reduce \(g_7(x)\) to,

\begin{equation*} g_7(x)= x^6 + \alpha^{10}x^5 + \alpha^{14}x^4 + \alpha^4 x^3 + \alpha^6 x^2 + \alpha^9 x + \alpha^6 \end{equation*}

To verify that this is correct, substitute \(x\) by any of its roots will yield zero, for example, \(g(\alpha^2) = 0\). This is the generator for RS code having \(t=3, n=15, k=9\), but can be shortened without compromising its error correcting capability which is quite usual in practice and I will shorten it for my implementation. The systematic form of the generator matrix for this \(g_7(x)\) is,

\begin{equation*} G = \left[ \begin{array}{c|cc} I_k & P_{n-k} \end{array} \right] =\left[ \begin{array}{c|c} I_{9 \times 9} & P_{9 \times 6} \end{array} \right] =\left[ \begin{array}{c|cc} & \alpha^9 & \alpha^4 & \alpha^8 & \alpha^{13} & 1 & \alpha^3 \\ & \alpha^{12} & 1 & \alpha^{13} & \alpha^{10} & \alpha^8 & \alpha^{13} \\ & \alpha^7 & \alpha^7 & \alpha^{13} & \alpha^4 & \alpha^9 & \alpha^{10} \\ & \alpha^4 & \alpha & \alpha^4 & \alpha^3 & \alpha^2 & \alpha^{10} \\ I_k & \alpha^4 & \alpha^9 & \alpha^9 & \alpha^5 & \alpha^{12} & \alpha^{14} \\ & \alpha^8 & \alpha^7 & 1 & \alpha^8 & \alpha^{12} & \alpha^7 \\ & \alpha & \alpha^7 & \alpha^9 & \alpha^{10} & \alpha^{11} & \alpha^3 \\ & \alpha^{12} & \alpha^{14} & \alpha^8 & \alpha^3 & \alpha^{12} & \alpha \\ & \alpha^{10} & \alpha^{14} & \alpha^4 & \alpha^6 & \alpha^9 & \alpha^6 \\ \end{array} \right] \end{equation*}

where the \(P\) matrix is obtained by polynomial division in similar way that was done for the cyclic BCH code.

Encoder

b'\nn "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">\n\n\n\n'

Each \(a_i\) represents an n-tuples \(\alpha^i\) coefficient of the multiplier and each of \(b_i\) represents the symbol shift register at each stage. It is worth noting that, unlike the binary BCH, none of the coefficients of \(g(x)\) can be zero. The encoder block can also be used for decoding this RS code as well.

For \(u=0 0 0 0 \alpha \alpha^2 0 1 \alpha^6\), encoding in systematic form as \(\frac{x^6u(x)}{g(x)}\) would yield, \(v = 0 0 0 0 \alpha \alpha^2 0 1 \alpha^6 \alpha^6 \alpha 1 \alpha^6 \alpha^9 \alpha^5\) or in polynomial form,

\begin{equation*} v(x) = \alpha x^{10} + \alpha^2 x^9 + x^7 + \alpha^6 x^6 + \alpha^6 x^5 + \alpha x^4 + x^3 + \alpha^6x^2 + \alpha^9 x + \alpha^5 \end{equation*}

or v = 0000.. _0000_0010_0100_0000_0001_1100_1100_0010_0001_1100_1010_0110.

For a hexadecimal value of 0x2badbeef, \(u=\alpha \alpha^7 \alpha^9 \alpha^{13} \alpha^7 \alpha^{11} \alpha^{11} \alpha^{12}\), the encoded parity portion will be, \(p=\alpha^{13} \alpha^{12} \alpha^8 \alpha^7 0 \alpha^5\). The output is the concatenated 32-bit input and 24-bit parity check bits ie.. 0x2badbeef_df5b06.

The same result can be obtained by using the \(G\) matrix, for example, the fist parity check symbol can be obtained by mutiplying the input word with the first column of the \(P\) matrix,

\begin{align*} p_1 &= \alpha^{13} + \alpha^{14} + \alpha^{13} + \alpha^2 + 1 + \alpha^{12} + \alpha^8 + \alpha^7 \\ &= \alpha^2 + \alpha^{14} + \alpha^{11} + \alpha^{11} \\ &= \alpha^{13} \\ &= d (hex) \end{align*}

\(p_2 .. p_6\) can be computed the same way to eventually produce the parity check hdf5b06 for this input word. Note: Since the input word is 32-bit (8 symbols), the multiplication only accounts for row 2 to row 9 of the \(G\) matrix.

Multiplication of \(GF(2^4)\) elements

For some \(\beta=[\beta_0 \beta_1 \beta_2 \beta_3 ]\), multiplied by some element of \(GF(2^4)\), for example,

\begin{equation*} \beta \alpha = [\beta_3 \, \beta_2 \, \beta_1 \, \beta_0 ] \left [ \begin{array}{cc} 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ \end{array} \right] = [\beta_2 \, \beta_1 \, (\beta_0+\beta_3) \, \beta_3] \end{equation*}

If \(\beta = \alpha^6 = \{1 1 0 0\}\), the product, \(\alpha^6 \alpha = \{1 0 1 1\} = \alpha^7\). In general,

\begin{equation*} \beta \alpha^p = [\beta_0 \, \beta_1 \, \beta_2 \, \beta_3 ] \left [ \begin{array}{cc} \alpha^p \\ \alpha^{p+1} \\ \alpha^{p+2} \\ \alpha^{p+3} \\ \end{array} \right] = [c_0 \, c_1 \, c_2 \, c_3] \end{equation*}

For \(g_7(x)\), the multiplication circuit by its coefficients can be formed as follow,

\begin{align*} \beta \alpha^4 &= [\beta_3 \beta_2 \beta_1 \beta_0] \left [ \begin{array}{cc} 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ \end{array} \right] \\ & = [(\beta_3+\beta_2) (\beta_2+\beta_1) (\beta_3+\beta_1+\beta_0) (\beta_3+\beta_0)] \\ \\ \beta \alpha^6 &= [(\beta_3+\beta_1+\beta_0) (\beta_2+\beta_0) (\beta_3+\beta_1) (\beta_2+\beta_1)] \\ \beta \alpha^9 &= [(\beta_3+\beta_2+\beta_0) (\beta_3+\beta_2+\beta_1) (\beta_3+\beta_2+\beta_1+\beta_0) (\beta_3+\beta_1)] \\ \beta \alpha^{10} &= [(\beta_3+\beta_2+\beta_1) (\beta_3+\beta_2+\beta_1+\beta_0) (\beta_2+\beta_1+\beta_0) (\beta_3+\beta_2+\beta_0)] \\ \beta \alpha^{14} &= [\beta_0 \beta_3 \beta_2 (\beta_1+\beta_0)] \end{align*}

So if \(\beta = \alpha^2\) is multiplied by \(\alpha^9\), I can use the formula above to achieve the desired mutiplication result by simple modulo sum,

\begin{align*} \beta \alpha^9 = [ 0 1 0 0 ] \alpha^9 &= [ (0+1+0) (0+1+0) (0+1+0+0) (0+0) ] mod(2) \\ &= [1 1 1 0] \\ &= \alpha^{11} \end{align*}

For Verilog, all of these coefficient multiplications can be a modeled by the simple modules that can be instantiated as the components of the RS encoder.

By definition, a t-error-correcting BCH code of lengt \(2^m-1\) having a binary n-tuple \(u(X)=u_0+u_1+\cdots+u_{n-1}\) is a code word iff \(u(X)\) has \(\alpha,\alpha^2, \cdots,\alpha^{2t}\) as roots, that is,

\begin{equation*} u(\alpha^i) = u_o + u_1(\alpha^i) + u_2(\alpha^{2i}) + \cdots + u_{n-1}(\alpha^{(n-1)i}) = 0 \end{equation*}

and for this exercise,

\begin{align*} u(\alpha) = u_o + u_1(\alpha) + u_2(\alpha^2) + \cdots + u_{n-1}(\alpha^{14}) = 0 \\ u(\alpha^3) = u_o + u_1(\alpha^3) + u_2(\alpha^{6}) + \cdots + u_{n-1}(\alpha^{42}) = 0 \\ \end{align*}

note that the power of \(\alpha\) will wrap on this finite field, for example, \(\alpha^{18} = \alpha^{15} \alpha^3 = \alpha^{3}\). Put it in matrix form,

\begin{equation*} ( u_{n-1} \cdots u_1 u_0) \left [ \begin{array}{cc} \alpha^{14} & (\alpha^2)^{14} \cdots & (\alpha^6)^{14} \\ \cdots & \cdots & \cdots \\ \alpha & \alpha^2 \cdots & \alpha^6 \\ 1 & 1 \cdots & 1 \end{array} \right] = 0 \end{equation*}

The equation above is in the form,

\begin{equation*} UH^t = 0 \end{equation*}

Burst error-correcting capability

The burst length \(l\) is defined as a vector whose zero components are confined to \(l\) consecutive positions, for example, the zero code vector of length 9 would be something like this ..0_1110_1110_1000_0000.

For this RS code workout, it is capable of correction the burst lenght, \(l\ge9\) because for \(RS(2^r,2t+1), l \ge r(t-1)+1\) . My implementation will show that it can indeed forward-error-correcting such burst error. The length here is binary bit length, but it is confined within three symbols of this q-ary code which is also its limit, twelve bits.

Decoder and errors locator

I will reuse the same algorithm that I used before and it will work just as well for this RS workout exercise. The only exception is that I that I am dealing with the 4-tuple symbols, not plain binary bits.

Let \(w(x)\) be the received code word where \(w(x)=u(x)+e(x)\). \(u(x)\) and \(e(x)\) are the transmitted code word and error respectively.

. Calculate syndrome \(s(x) = w(x)\ mod\ g(x)\)

. For \(i \ge 0\), calculate \(s_i(x)=x^i s(x)\ mod\ g(x)\) until \(s_j(x)\) is found with \(degree(s_j(x))) \le l-1\). I can instead use the weight of the symbols, \(weight(s_j(x)) \le 2t\). This should work as well.

. Once \(s_j(x)\) is located, \(e(x)=x^{n-j}s_j(x)\ mod\ (x^n + 1)\) are the most likely error symbols .

Every algorithm is iterative as far as division is involved. The iteration for this one is at most \(2t\) because if there are \(\nu \le t\) error positions, the iteration is \(\nu + t\).

Again, assume the transmitted code word is as shown in the encoder section ( v = 0000_0000_0000_0010__0100_0000_0001_1100__1100_0010_0001_1100_1010_0110 or h0002_401C ), but with three symbols error in the message area of code,h0AC2_421c,

\begin{equation*} w(x) = \underline{\alpha^9 x^{12} + \alpha^6 x^{11}} + \alpha x^{10} + \alpha^2 x^9 + \underline{\alpha x^8} + x^7 + \alpha^6 x^6 + \alpha^6 x^5 + \alpha x^4 + x^3 + \alpha^6x^2 + \alpha^9 x + \alpha^5 \end{equation*}

The computed syndrome is h76_0523, or in polynomial form,

\begin{align*} s(x)= w(x)\ mod\ g(x) = \alpha^{10}x^5 +\alpha^5 x^4 + \alpha^8 x^2 + \alpha x^2 + \alpha^4 \\ s_1(x) = x s(x)\ mod\ g(x) = \alpha^4 x^4 + \alpha^6 x^3 + \alpha \\ \end{align*}

weight of \(s_1(x) \le t\) is reached, \(j=1\).

The most likely code word is therefore, \(w(x)\) plus the shifted value of \(s_1(x)\). In this example, it corrects 3 symbols or 12 binary bits for a 36 bits encoded codeword (plus partity check bits) . I will shorten it to 32 bits when implementating this RS code without impairing its FEC capability.

Summary

RS code is one class of powerful forward-error-correcting code and it has wide variety of applications such as those found in communication systems and in data storage subsystems. Knowing the basic mathematic behind it, one can implement RS code of any \(GF(2^r)\) field. Math is everything and everything is math. It is generally recognized that it is dangerous to apply any part of science without undertanding what is behind the theory (Richard W. Hamming).

There are many excellent text books and articles on this subject. Listed in the reference are only a few that I have. For EE, [CIT003] is a very well known text book on this subject.

The HDL implementation of this FEC exercise is RS burst error FEC

Reference

CIT001: Digital Communications Fundamentals and Applications, 2nd Ed, Bernard Sklar.
CIT002: Coding Theory The Essentials, D.G Hoffman, 1991.
CIT003: Error Control Coding Fundamental And Applications, Shu Lin, Daniel J. Costello Jr, 1983