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?
Proving that the codebook of an (n,k) RS code is an ideal?
Started by ●August 25, 2003
Reply by ●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 ●August 25, 20032003-08-25
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
Reply by ●August 26, 20032003-08-26