Forums

Proving that the codebook of an (n,k) RS code is an ideal?

Started by Jaco Versfeld August 25, 2003
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?
jaco_versfeld@hotmail.com (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
Thanks a lot