Skip to Main content Skip to Navigation
New interface
Conference papers

Efficient List-Decoding of Reed-Solomon Codes with the Fundamental Iterative Algorithm

Alexander Zeh 1, 2 Christian Gentner 3 Martin Bossert 2 
1 TANC - Algorithmic number theory for cryptology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
Abstract : In this paper we propose a new algorithm that solves the Guruswami-Sudan interpolation step for Reed-Solomon codes efficiently. It is a generalization of the Feng-Tzeng approach, the so-called fundamental iterative algorithm. From the interpolation constraints of the Guruswami-Sudan principle it is well known that an improvement of the decoding radius can only be achieved, if the multiplicity parameter s is smaller than the list size l. The code length is n and our proposed algorithm has a complexity (without asymptotic assumptions) of O(ls4 n2).}, keywords={Feng-Tzeng approach;Guruswami-Sudan interpolation;Reed-Solomon codes;communication complexity;efficient list-decoding;fundamental iterative algorithm;Reed-Solomon codes;communication complexity;decoding;iterative methods;
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download
Contributor : Alexander Zeh Connect in order to contact the contributor
Submitted on : Friday, December 2, 2011 - 2:03:47 PM
Last modification on : Friday, February 4, 2022 - 3:17:43 AM
Long-term archiving on: : Saturday, March 3, 2012 - 2:31:01 AM


Publisher files allowed on an open archive




Alexander Zeh, Christian Gentner, Martin Bossert. Efficient List-Decoding of Reed-Solomon Codes with the Fundamental Iterative Algorithm. IEEE Information Theory Workshop (ITW), Sep 2010, Taorminia, Italy. pp.130-134, ⟨10.1109/ITW.2009.5351241⟩. ⟨hal-00647592⟩



Record views


Files downloads