Forums

Reed-Solomon: generator matrix and generator polynomial approaches?

Started by Unknown October 26, 2005
Hi,

Where can I find a proof in literature (or maybe someone can show me)
why the following two approaches generate the same (n,k) RS code?

The one approach is to generate the (n,k) RS code by the generator
matrix:

     1    1              1         ...        1
     1 \alpha^1      \alpha^2      ...    \alpha^{n-2}
     1 \alpha^2     (\alpha^2)^2   ...   (\alpha^2)^{n-2}
G =  .
     .
     1 \alpha^{k-1} (\alpha^{k-1})^2 ... (\alpha^{k-1})^{n-2}

(This is an adapted form of Reed and Solomon's original paper back in
the 1960s, where a codeword is defined as:
 c = (p(\alpha^0), p(\alpha^1), ... , p(\alpha^{n-2}),

where p(x) is the message polynomial of degree k-1.)

The second approach is to generate the (n,k) RS code by the generator
polynomial:

g(x) = (x - \alpha^1)(x - \alpha^2)...(x - alpha^{n-k})

Any suggestions or help will greatly be appreciated ( and I do
appologise if this seems trivial or like homework)

Jaco Versfeld

jaco.versfeld@gmail.com wrote:
> Hi, > > Where can I find a proof in literature (or maybe someone can show me) > why the following two approaches generate the same (n,k) RS code? > > The one approach is to generate the (n,k) RS code by the generator > matrix: > > 1 1 1 ... 1 > 1 \alpha^1 \alpha^2 ... \alpha^{n-2} > 1 \alpha^2 (\alpha^2)^2 ... (\alpha^2)^{n-2} > G = . > . > 1 \alpha^{k-1} (\alpha^{k-1})^2 ... (\alpha^{k-1})^{n-2} > > (This is an adapted form of Reed and Solomon's original paper back in > the 1960s, where a codeword is defined as: > c = (p(\alpha^0), p(\alpha^1), ... , p(\alpha^{n-2}),
Below I will call this a c-word associated with p.
> > where p(x) is the message polynomial of degree k-1.) > > The second approach is to generate the (n,k) RS code by the generator > polynomial: > > g(x) = (x - \alpha^1)(x - \alpha^2)...(x - alpha^{n-k}) > > Any suggestions or help will greatly be appreciated
Glad to see that you are taking this seriously. Some properties of RS codes are easy to prove using the other representation, some using the other... I'm assuming that alpha is of order n (usually meaning that n=q-1, and alpha is a primitive element of GF(q)). In order to compare the two representation we need to transform a c-word (c_0,c_1,...c_{n-1}) into a polynomial c(x)=c_0 + c_1 x + c_2 x^2 + c_3x^3 + ... + c_{n-1}x^{n-1} as required by the cyclic representation. We do this for each row of G only. This suffices by linearity. As the easiest example case let us consider the first row of G. It is the c-word associated to the constant polynomial p(x)=1. In the cyclic representation this becomes c(x)=1+x+x^2+...+x^{n-1} = (1-x^n)/(1-x). The polynomial x^n-1 factors into linear factors as follows x^n-1=(x-1)(x-alpha)(x-alpha^2)...(x-alpha^{n-1}) (alpha^n=1 is used here!!!), so we immediately see that c(x) is a multiple of g(x), and hence belongs to the cyclic code generated by g. Let us next consider row number t+1. It is the c-word associated to the monomial p(x)=x^t. In the cyclic representation this generator (call it c_t) becomes c_t(x)=1+(alpha^t x)+(alpha^t x)^2+...+(alpha^t x)^{n-1}. As above we see that this polynomial is equal c_t(x)=(x^n-1)/(alpha^t x -1)= =alpha^(-t) (x^n-1)/(x-alpha^(-t)). Observe that alpha^(-t)=alpha^(n-t) here. Using the same factorization of x^n-1 as in the case t=1 gives that c_t(x) is a constant multiple of the product (x-1)(x-alpha)(x-alpha^2)...(x-alpha^{n-t-1})(x-alpha^{n-t+1}...(x-alpha^{n-1}) (here the factor x-alpha^{n-t} is missing). Again we immediately see that this is a multiple of g, IF AND ONLY IF t<k. To summarize: the code generated by G is a subcode of the cyclic code generated by g. As they both have the same dimension k, they must be equal. Cheers, Jyrki Lahtonen, Turku, Finland
Thank you very much.

Warm regards here from sunny South Africa
Jaco