Decoding Reed-Solomon codes up to the Sudan radius with the Euclidean algorithm

Alexander Zeh (1, 2) , Wenhui Li (1)

1 INT - University of Ulm. - Institute of Communications Engineering [Ulm]
2 TANC - Algorithmic number theory for cryptology

We modify the Euclidean algorithm of Feng and Tzeng to decode Reed-Solomon (RS) codes up to the Sudan radius. The basic steps are the virtual extension to an Interleaved RS code and the reformulation of the multi-sequence shift-register problem of varying length to a multi-sequence problem of equal length. We prove the reformulation and analyze the complexity of our new decoding approach. Furthermore, the extended key equation, that describes the multi-sequence problem, is derived in an alternative polynomial way.

Mots clés: Euclidean algorithm; Reed-Solomon code; Sudan radius; multisequence problem; multisequence shift register problem; Reed-Solomon codes; binary sequences; decoding

Domaines: Théorie de l'information [cs.IT]; Théorie de l'information et codage [math.IT]

Alexander Zeh, Wenhui Li. Decoding Reed-Solomon codes up to the Sudan radius with the Euclidean algorithm. IEEE International Symposium on Information Theory and its Applications (ISITA), Oct 2010, Taichung, Taiwan. pp.986-990, ⟨10.1109/ISITA.2010.5649520⟩. ⟨hal-00647597⟩