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

Started by 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
```
{"ft_lang_label":"__label__en","ft_lang_prob":0.8859038,"math_prob":0.9984861,"size":3995,"snap":"2021-43-2021-49","text_gpt3_token_len":1327,"char_repetition_ratio":0.1182661,"word_repetition_ratio":0.31909546,"special_character_ratio":0.36545682,"punctuation_ratio":0.14664143,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9999918,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-11-29T04:55:34Z\",\"WARC-Record-ID\":\"<urn:uuid:0ecbb136-a15e-429c-9f5b-4470eef6916a>\",\"Content-Length\":\"43486\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:006e4a68-23e5-4426-b5e6-e0e5e2e7c106>\",\"WARC-Concurrent-To\":\"<urn:uuid:7e7db9be-fb6a-4349-ab87-bddc5a7bd8dc>\",\"WARC-IP-Address\":\"69.16.201.59\",\"WARC-Target-URI\":\"https://www.dsprelated.com/showthread/comp.dsp/20722-1.php\",\"WARC-Payload-Digest\":\"sha1:FGXZ7MMRI7GOVKUDDR25PCINHEEBW5RV\",\"WARC-Block-Digest\":\"sha1:YOOSKTPNGGAANRINBKP6VTTI4PTAJLSY\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-49/CC-MAIN-2021-49_segments_1637964358688.35_warc_CC-MAIN-20211129044311-20211129074311-00535.warc.gz\"}"}