# Coset leader of a coset code of RS codes

Started by September 21, 2005
Hi,

I need some help on a problem regarding coset codes of Reed-Solomon
codes (using GF(2^m)). I will quickly describe the problem.

Define the same_symbol_weight of a codeword c as the maximum number
of same symbols contained in c.

Define the same_symbol_weight of a codebook C as the number of same
symbols of c_s, where c_s is a codeword in C containing the maximum
number of same symbols.

As an example, the same_symbol_weight of the all-zero codeword of an
(n,k) RS code is equal to n.  Also, the same_symbol_weight of the
all e codeword (e \in GF(2^m)) is equal to n.  Thus the
same_symbol_weight of an (n,k) RS codebook is equal to n.

Through simulation, I have found that the minimum same_symbol_weight of
(C + h) is equal to k.  I also found that coset leaders that will give
a same_symbol_weight of k can be constructed by either (x - \alpha^1)(x
- \alpha^2)...(x-\alpha^{n-k-1}) or (x - \alpha^2)(x - \alpha^3)...(x -
\alpha^{n-k}), given that the RS generator polynomial is (x -
\alpha^1)(x - \alpha^2)...(x - \alpha^{n-k}).  [I assume that if the
generator polynomial is constructed with the first factor as (x -
(leaving out the first or last factor) and having the same results,
although I haven't test it yet...]

How can I prove that the above coset leaders will always give a
same_symbol_weight(C+h) of k?  (C is the RS code, h is one of the coset
leaders shown, and same_symbol_weight(C+h) is the same symbol weight of
the coset code (C+h)).

Any help will be greatly appreciated,
Jaco Versfeld


<jaco.versfeld@gmail.com> asked in message

>  I also found that coset leaders that will give
> a same_symbol_weight of k can be constructed by either (x - \alpha^1)(x
> - \alpha^2)...(x-\alpha^{n-k-1}) or (x - \alpha^2)(x - \alpha^3)...(x -
> \alpha^{n-k}), given that the RS generator polynomial is (x -
> \alpha^1)(x - \alpha^2)...(x - \alpha^{n-k}).
>
> How can I prove that the above coset leaders will always give a
> same_symbol_weight(C+h) of k?  (C is the RS code, h is one of the coset
> leaders shown, and same_symbol_weight(C+h) is the same symbol weight of
> the coset code (C+h)).

Here is something to start you on your way to the proof. Your h
(defined in either of the two ways) is a codeword in (in fact, the
generator polynomial of) an (n, k+1) supercode of C.  This
supercode is also an RS code.  Thus, h, a polynomial of
degree n-k-1, has weight n-k (i.e. all coefficients are nonzero) and
hence 0 + h is a word of same-symbol-weight k (there are k zeroes
in it).  So the same-symbol-weight of C + h is at least k.  Now prove
that it cannot be more than k.....

--Dilip Sarwate


Dear Prof Sarwate,

Thank you very much for the hint.

(I had to start to work this year at a large Telecoms company, so I
don't have the time I would like to do research, but in my spare time I
am doing what I can.)

Again, thank you very much
Jaco Versfeld