On the Equivalence of Sudan-Decoding and Decoding via Virtual Extension to an Interleaved Reed-Solomon Code

Alexander Zeh (1, 2) , Sabine Kampf (2) , Martin Bossert (2)

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

In this paper we investigate two new decoding schemes for Reed-Solomon codes, which allow to decode beyond half the minimum distance. One is Sudan's list-decoding principle, based on interpolation with a degree-restricted bivariate polynomial. We show a syndrome-based approach of it. We compare Sudan's procedure with a scheme that is based on an extension to Interleaved Reed-Solomon codes. We present theoretical parallels and outline both algorithms in a unique comparable way. Furthermore, we show the connection of both schemes to the classical Linear Feedback Shift Register analysis. Afterwards, we compare the performance of the considered schemes.

Mots clés: fia; reed-solomon; register; shift; sudan; posted-at = 2010-03-09 12:21:19

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

Alexander Zeh, Sabine Kampf, Martin Bossert. On the Equivalence of Sudan-Decoding and Decoding via Virtual Extension to an Interleaved Reed-Solomon Code. International ITG Conference on Source and Channel Coding (SCC), Jan 2010, Siegen, Germany. pp.1-6. ⟨hal-00647618⟩