FPGA Central

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 = .

[email protected] 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