Definition of GRS codes

[David Lucas]

While working on key equation decoding for GRS codes, using [1] as reference, I noticed it requires to inverse the evaluation points ([1], p195). It works for Roth's definition of GRS codes ([1], pp147-148) as he defines the evaluation points as n non-zero distinct elements of some finite field, where n is the length of the code.

But in the definition I chose (from [2], p50),evaluation points are defined as n distinct elements of some finite field.

On wikipedia, which seems to rely on Mc Williams & Sloane definition [3], definition of GRS is the same as [2].

Am I missing something, or is there several ways to define these codes? And in that case, which definition should we pick?

• [1] Introduction to Coding Theory, Ron Roth, Cambridge University Press, 2006
• [2] A course in error-correcting codes, Jørn Justesen, Tom Høholdt, EMS editions, 2004
• [3] https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction#Reed_.26_Solomon.27s_original_view:_The_codeword_as_a_sequence_of_values

[Johan Rosenkilde]

This is, as many things in coding theory, up for debate. But you are right: if you use 0 as evaluation point, the syndrome key equation no longer works. (there is a way to make still it work, actually, and we could discuss whether to implement that. I don't know of any reference to that though. It's just something that I discovered once.)

In my nomenclature, I speak of the "Gao key equation". This works for any choice of evaluation points.

My opinion is the following: The definition of GRS codes should allow 0 as evaluation point. For GRS codes using 0 as evaluation point, the syndrome key equation decoder should not be available.

[Johan Rosenkilde]

I feel it is stupid to say that a Generalized RS code does not include the obvious generalisation of having 0 as evaluation point. Roth did it in his book because it makes his presentation more streamlined, I bet. But these are sometimes called "extended" GRS codes, I think.

One can also allow evaluation at "the point at infinity" (this would be the leading coefficient of the message polynomial). That is sometimes called "(doubly) extended GRS codes". For these codes, I think even more decoders stop working. Basically, I think one needs to implement a bit of extra logic in any decoder to make it work. I would vote for making these a class for themselves ExtendedGeneralizedReedSolomonCodes.

[David Lucas]

Agreed.

I forgot to post in this issue, I checked in Mc Williams-Sloane this morning (which, I think is the reference) and they include 0 as an evaluation point too. So I definitely tend to accept 0 as an evaluation points.

As for my Key Equation decoder, it works using syndrome polynomial and early terminated extended Euclidean algorithm. I guess I'll just add a check at construction time that returns an exception if one tries to create such a decoder with a GRS code including a 0 in its evaluation points.

[Johan Rosenkilde]

Makes good sense, yes.