>
> 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
Reply by Dilip V. Sarwate●August 25, 20032003-08-25
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 \
`-' `-' `-' `-' `-' `-'
Reply by Jaco Versfeld●August 25, 20032003-08-25
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?