A link between Guruswami-Sudan's list-decoding and decoding of interleaved Reed-Solomon codes

Alexander Zeh (1, 2) , Christian Senger (2)

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

The Welch-Berlekamp approach for Reed-Solomon (RS) codes forms a bridge between classical syndrome-based decoding algorithms and interpolation-based list-decoding procedures for list size ℓ = 1. It returns the univariate error-locator polynomial and the evaluation polynomial of the RS code as a y-root. In this paper, we show the connection between the Welch-Berlekamp approach for a specific Interleaved Reed-Solomon code scheme and the Guruswami-Sudan principle. It turns out that the decoding of Interleaved RS codes can be formulated as a modified Guruswami-Sudan problem with a specific multiplicity assignment. We show that our new approach results in the same solution space as the Welch-Berlekamp scheme. Furthermore, we prove some important properties.

Mots clés: decoding; irs; list

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

Alexander Zeh, Christian Senger. A link between Guruswami-Sudan's list-decoding and decoding of interleaved Reed-Solomon codes. IEEE International Symposium on Information Theory (ISIT), Jun 2010, Austin, United States. pp.1198-1202, ⟨10.1109/ISIT.2010.5513427⟩. ⟨hal-00647609⟩