Reed Solomon Encoding

Question

I am trying to understand how Reed Solomon encoding works. Specifically, I am trying to re-generate the example shown in http://www.mathworks.com/help/comm/ref/integerinputrsencoder.html and check if my understanding of Reed Solomon encoding matches with the generated outputs of Matlab.

Assume,

M = 3. N = 7. K = 5. We operate in GF(8)

input message, U = [2 3 5 2 0]

corresponding output codeword, C = [2 3 5 2 0 1 4].

Matlab used default primitives and generator polymonials to generate this output codeword.

Matlab’s default primitive polynomial for GF(8) is D^3 + D + 1.

Matlab’s default generator polynomial for (N = 7, K = 5) reed Solomon code is: G = [1 6 3].

The associated code to generate C from U is following:

% Code starts

clear all ; close all ; clc ;

M = 3 ;

N = 7 ;

K = 5 ;

U = gf([2 3 5 2 0],M);

G = rsgenpoly(7,5) ;

C = rsenc(U,N,K,G)

% Code finishes

I want to know how Matlab is encoding U using Reed-Solomon encoding. I want to generate an output codeword C’ from U and G myself and check if it matches with C.

Based on my understanding of Reed Solomon coding, the polynomials associated with U and G are following:

Input polynomial, u(x) = 2 * x^4 + 3 * x^3 + 5 * x^2 + 2 * x

Generator polynomial, g(x) = x^2 + 6 * x + 3

If I multiply these two polynomials to get output codeword polynomial c’(x), I get the following:

c’(x) = u(x) * g(x)

= (2 * x^4 + 3 * x^3 + 5 * x^2 + 2 * x ) * (x^2 + 6 * x + 3)

= 2 * x^6 + 15 * x^5 + 29 * x^4 + 41 * x^3 + 27 * x^2 + 6 * x … (Line a)

= 2 * x^6 + 7 * x^5 + 5 * x^4 + x^3 + 3 * x^2 + 6 * x . … (Line b)

Here, Line a and b are equivalent under GF(8).

From line b, C’ = [2 7 5 1 3 6 0] But the entries of C’ do not match that of C, which is the output codeword generated by Matlab.

I want to know what mistake I am making. I want to know how I can get the actual value of C from U and G.

Any suggestion will be very appreciated.

Thanks,

Nazmul

Answer 1

The encoder that MATLAB is using creates a systematic cyclic code as you can see by looking at the codeword created: the first 5 symbols are the information symbols.

Your information polynomial is $u(x) = u_4x^4+u_3x^3+u_2x^2+u_1x+u_0$. The codeword polynomial is obtained as follows.

• Multiply $u(x)$ by $x^2 = x^{N-K}$ to get $x^2u(x) = u_4x^6+u_3x^5+u_2x^4+u_1x^3+u_0x^2$.

• Divide $x^2u(x)$ by $g(x) = x^2 + g_1x + g_0$ to get a quotient $q(x)$ of degree $2$ and a remainder $r(x) = r_1x+r_0$ of degree $1$ or less. The quotient is not needed and can be discarded. In fact, most encoders don't explicitly compute the quotient.

• The codeword $c(x)$ is $$x^2u(x) - r(x) = x^2u(x) + r(x) = (u_4x^6+u_3x^5+u_2x^4+u_1x^3+u_0x^2) + r_1x + r_0$$ because addition and subtraction are the same operation (XOR) in GF$(8)$.

The key idea is that the symbols $r_0$ and $r_1$ are added to $x^2u(x)$ in exactly those positions where $x^2u(x)$ has zero coefficients and so they appear "in the clear" as parity checks that follow the $5$ information symbols.

So why does all this work? We have, by construction, that $x^2u(x) = q(x)g(x) + r(x)$ and so it must be that $x^2u(x)-r(x) = x^2u(x)+r(x)$ is a multiple $q(x)g(x)$ of the generator polynomial, and hence is a codeword in the cyclic code generated by $g(x)$.

Your method of simply multiplying $u(x)$ by $g(x)$ also creates a codeword in the cyclic code generated by $g(x)$ but it does not give a systematic codeword in which we can identify the information symbols and parity check symbols via their positions in the codeword.