Sage GRSKeyEquationSyndromeDecoder could be enhanced to handle a zero

[Jeff Reid]

In the source file 

https://github.com/sagemath/sage/blob/develop/src/sage/coding/grs_code.py

codes.decoders.GRSKeyEquationSyndromeDecoder

line 2063:

raise ValueError("Impossible to use this decoder over a GRS code which contains 0 amongst its evaluation points")

The decoder can be enhanced to handle a 0 in the set of evaluation points.

This was a self-discovery, so I don't know if this is documented anywhere else.

I added a section to the Wikipedia Reed Solomon talk page that describes

how to handle a zero in the set of evaluation points, giving it the same capabilty

as the Berlekamp Welch and Gao decoders.

https://en.wikipedia.org/wiki/Talk:Reed%E2%80%93Solomon_error_correction#Original_view_syndrome_decoder

I'd also like to know who (or what group) invented this decoder. I've found several

documents, but none of them state who the author of this decoder is. It seems it

first appeared around 2015.

[P Purkayastha]

Hi Jeff,

 You can use git blame on github to trace the history of any file. This appears to be the first commit: https://github.com/sagemath/sage/commit/d854eb899cbe3affffe9e7a17a07def3fbcb37b6

Cheers,

  Punarbasu

--
You received this message because you are subscribed to the Google Groups "sage-coding-theory" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-coding-the...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/sage-coding-theory/89c8a40d-36d9-4dbc-b69f-9ef325df601dn%40googlegroups.com.

[Dima Pasechnik]

Just to add, the person who wrote most of this code, David Lucas, does
not seem to be traceable today.
He hasn't contributed to SageMath after 2017, when he moved to do a
PhD (I think) elsewhere in France.

> To view this discussion visit https://groups.google.com/d/msgid/sage-coding-theory/CADZU3NaYGd48KwRiz-uvhoOFOswu2aErY-1P3A39EoyOLfg2qw%40mail.gmail.com.

[Jeff Reid]

Thanks for the replies. I wasn't expecting a response from what use to be usenet (last post here was 2021), 

so I also posted an issue at github:

https://github.com/sagemath/sage/issues/40624

I was aware that David Lucas and David Joyner were both involved in grs_code.py and sent an email to both. I got

a reply from David Joyner, to post here at google groups.  Although they added

GRSKeyEquationSyndromeDecoder

to Sage grs_code.py, I'm not sure who invented the algorithm or when. Doing a web search, it's mentioned

in other documents unrelated to Sage, such as:

https://users.math.msu.edu/users/halljo/classes/codenotes/GRS.pdf

The next reference dates back to 1992, but unless I buy the PDF, I can't be sure it is not a reference to 

the BCH style encoding by a fixed generator polynomial, which these days use Berlekamp Massey or

Sugiyama decoders.

https://globals.ieice.org/en_transactions/fundamentals/10.1587/e75-a_8_1026/_p

The Sage grs_code.py implements decoders for RS original encoding scheme, Berlekamp Welch (1986),

Gao (2002), and the syndrome decoder. 

The other mystery is it didn't take much to add post correction code to handle a set of evaluation points that

includes zero, but I haven't seen this documented anywhere, so at this point it is a self-discovery.

Jeff

[Jeff Reid]

Follow up - I found the 1992 paper, just one page, and it''s about generalized syndromes for what Wiki calls "BCH view" encoding,

not what Wiki calls "original view" encoding, so it does not apply here.

https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction#Simple_encoding_procedure:_The_message_as_a_sequence_of_coefficients

(with codewords as a sequence of values).

https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction#The_BCH_view:_The_codeword_as_a_sequence_of_coefficients

Jeff

On Saturday, August 23, 2025 at 12:05:15 PM UTC-7 dim...@gmail.com wrote:

[Dima Pasechnik]

On Tue, Aug 26, 2025 at 3:01 AM Jeff Reid <jeff...@jeffareid.net> wrote:
>
> Thanks for the replies. I wasn't expecting a response from what use to be usenet (last post here was 2021),
> so I also posted an issue at github:
>
> https://github.com/sagemath/sage/issues/40624
>
> I was aware that David Lucas and David Joyner were both involved in grs_code.py and sent an email to both. I got
> a reply from David Joyner, to post here at google groups. Although they added
>
> GRSKeyEquationSyndromeDecoder
>
> to Sage grs_code.py, I'm not sure who invented the algorithm or when. Doing a web search, it's mentioned
> in other documents unrelated to Sage, such as:
>
> https://users.math.msu.edu/users/halljo/classes/codenotes/GRS.pdf
>
> The next reference dates back to 1992, but unless I buy the PDF, I can't be sure it is not a reference to
> the BCH style encoding by a fixed generator polynomial, which these days use Berlekamp Massey or
> Sugiyama decoders.
>
> https://globals.ieice.org/en_transactions/fundamentals/10.1587/e75-a_8_1026/_p

for me this URL returns "Forbidden" - can you provide a proper
reference via DOI or just text entry?

> To view this discussion visit https://groups.google.com/d/msgid/sage-coding-theory/4dbdaed1-a34d-4e59-8195-590827c6c35cn%40googlegroups.com.

[David Joyner]

On Tue, Aug 26, 2025 at 11:46 AM Dima Pasechnik <dim...@gmail.com> wrote:

On Tue, Aug 26, 2025 at 3:01 AM Jeff Reid <jeff...@jeffareid.net> wrote:
>
> Thanks for the replies. I wasn't expecting a response from what use to be usenet (last post here was 2021),
> so I also posted an issue at github:
>
> https://github.com/sagemath/sage/issues/40624
>
> I was aware that David Lucas and David Joyner were both involved in grs_code.py and sent an email to both. I got
> a reply from David Joyner, to post here at google groups.  Although they added
>
> GRSKeyEquationSyndromeDecoder
>
> to Sage grs_code.py, I'm not sure who invented the algorithm or when. Doing a web search, it's mentioned
> in other documents unrelated to Sage, such as:
>
> https://users.math.msu.edu/users/halljo/classes/codenotes/GRS.pdf
>
> The next reference dates back to 1992, but unless I buy the PDF, I can't be sure it is not a reference to
> the BCH style encoding by a fixed generator polynomial, which these days use Berlekamp Massey or
> Sugiyama decoders.
>
> https://globals.ieice.org/en_transactions/fundamentals/10.1587/e75-a_8_1026/_p

for me this URL returns "Forbidden" - can you provide a proper
reference via DOI or just text entry?

title: Generalized Syndrome Polynomials for Decoding Reed-Solomon Codes
authors: Kiyomichi ARAKI, Ikuo FUJITA

Publication IEICE TRANSACTIONS on Fundamentals Vol.E75-A No.8 pp.1026-1029

Summary :
In this letter, a generalized syndrome polynomial is proposed from which several decoding key-equations for Reed-Solomon codes can be derived systematically. These equations are always solved by the extended Euclidean algorithm.

 

To view this discussion visit https://groups.google.com/d/msgid/sage-coding-theory/CAAWYfq08mpco%2BOUQ_qQ26h0pJpqD-iMpd2ARR0BbmVEZWpE%3D3w%40mail.gmail.com.

[Jeff Reid]

To clarify my prior comment, the 1992 paper: Generalized Syndrome Polynomials for Decoding Reed-Solomon Codes, is used for codewords that are a set of coefficients to a polynomial. The syndrome decoder I'm referring to is used for codewords that are a set of values.  In this case, a search found a match for "generalized syndrome" as opposed to "generalized Reed Solomon" syndrome.