FPGA Central

Hi,

How can I prove that the (n,k) RS code book, i.e. all the valid code
words of the specific (n,k) Reed-Solomon code, is an ideal?

The (n,k) RS code has a generator g(x), consisting of n-k consecutive
roots in GF(2^m). (I.e. a valid RS codeword is divisible by g(x))

Also, g(x), the generator polynomial has order n, i.e. g(x) divides
x^n-1.

For an ideal, the following must hold:
A nonempty subset G of a ring R is an ideal of R if:
1. a - b in G whenever a,b in G.
2. da and ad are in G, whenever a in G and d in R.

The first condition is met because of the linearity of Reed-Solomon
codes.
That is, the addition (or subtraction) of any two elements in (n,k) RS
(=> G), will result in another valid codeword (element in G).

The second condition I am not sure how to tackle.
One way that I thought of was to use the remainder theorem. For any
element c in the Ring R, we can express c as c = pq + r, where p,q and
r are in R, with 0 <= deg (r) < deg(p).

If we assume that c = ad, where a in G and d in R, (or c = da, because
the ring GF(2^m)[x] is commutative) and because RS is a cyclic code,
we can divide c by x^n - 1. (The remainder should then give us a valid
codeword)

Thus c = p(x^n-1) + r, where 0 <= deg(r) < deg(x^n-1)
The condition on the degree of r assures that r will have the correct
degree. (p is an arbitrary polynomial)

Also, when deg(ad) < deg(x^n-1), r = ad, and because a is in G, we
have a = p(x)g(x), thus r = [d(x)p(x)]g(x), which is in G.

How can I prove that when deg(ad) >= deg(x^n-1), that r will have the
form g(x)p(x), where g(x) is the generator, and p(x) some polynomial?

[email protected] (Jaco Versfeld) writes:

>How can I prove that the (n,k) RS code book, i.e. all the valid code
>words of the specific (n,k) Reed-Solomon code, is an ideal?

>The (n,k) RS code has a generator g(x), consisting of n-k consecutive
>roots in GF(2^m). (I.e. a valid RS codeword is divisible by g(x))

>Also, g(x), the generator polynomial has order n, i.e. g(x) divides
>x^n-1.

>For an ideal, the following must hold:
>A nonempty subset G of a ring R is an ideal of R if:
>1. a - b in G whenever a,b in G.
>2. da and ad are in G, whenever a in G and d in R.


<<<<<<<<<<<much material snipped>>>>>>>>>>>>

>How can I prove that when deg(ad) >= deg(x^n-1), that r will have the
>form g(x)p(x), where g(x) is the generator, and p(x) some polynomial?


g(x) is a divisor of x^n - 1, and every codeword a(x) is
a multiple of g(x). Thus, for any d(x) such that

deg((a(x).d(x)) > n-1,

we divide a(x).d(x) by x^n - 1 to get a quotient Q(x) and
a remainder r(x) of degree < n. In other words, we have that

a(x).d(x) = Q(x).(x^n - 1) + r(x)

or equivalently, r(x) = a(x).d(x) - Q(x).(x^n - 1). The right
side is a multiple of g(x).....

Hope this helps (and that the query was not from homework....)

--
.-. .-. .-. .-. .-. .-. .-.
/ D \ I / L \ I / P \ / S \ A / R \ W / A \ T / E \
`-' `-' `-' `-' `-' `-'

Jaco Versfeld wrote:

>
> Thus c = p(x^n-1) + r, where 0 <= deg(r) < deg(x^n-1)
> The condition on the degree of r assures that r will have the correct
> degree. (p is an arbitrary polynomial)
>
> Also, when deg(ad) < deg(x^n-1), r = ad, and because a is in G, we
> have a = p(x)g(x), thus r = [d(x)p(x)]g(x), which is in G.
>
> How can I prove that when deg(ad) >= deg(x^n-1), that r will have the
> form g(x)p(x), where g(x) is the generator, and p(x) some polynomial?

So let's collect all the things you have:

1) the polynomial a(x) (just 'a' above) is a multiple of g(x)
2) x^n-1 is a multiple of g(x)
3) r(x) = d(x)a(x)-p(x)(x^n-1)

and you need to prove that r(x) is also a multiple of g(x).

Shouldn't the conclusion be obvious from 1-3 above?

If 'a' is a multiple of 'g', and 'b' is a multiple of 'g', then
surely 'da-pb' is a multiple of 'g' no matter what 'd' and 'p'
are?

Cheers,

Jyrki