Skip to Main content Skip to Navigation
Journal articles

An Interpolation Procedure for List Decoding Reed--Solomon codes Based on Generalized Key Equations

Alexander Zeh 1, 2 Christian Gentner 3 Daniel Augot 1 
1 TANC - Algorithmic number theory for cryptology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
Abstract : The key step of syndrome-based decoding of Reed--Solomon codes up to half the minimum distance is to solve the so-called Key Equation. List decoding algorithms, capable of decoding beyond half the minimum distance, are based on interpolation and factorization of multivariate polynomials. This article provides a link between syndrome-based decoding approaches based on Key Equations and the interpolation-based list decoding algorithms of Guruswami and Sudan for Reed--Solomon codes. The original interpolation conditions of Guruswami and Sudan for Reed--Solomon codes are reformulated in terms of a set of Key Equations. These equations provide a structured homogeneous linear system of equations of Block-Hankel form, that can be solved by an adaption of the Fundamental Iterative Algorithm. For an $(n,k)$ Reed--Solomon code, a multiplicity $s$ and a list size $\listl$, our algorithm has time complexity \ON{\listl s^4n^2}.
Complete list of metadata

Cited literature [32 references]  Display  Hide  Download
Contributor : Daniel Augot Connect in order to contact the contributor
Submitted on : Monday, October 17, 2011 - 9:32:23 PM
Last modification on : Friday, February 4, 2022 - 3:18:34 AM
Long-term archiving on: : Thursday, November 15, 2012 - 9:51:23 AM


Files produced by the author(s)




Alexander Zeh, Christian Gentner, Daniel Augot. An Interpolation Procedure for List Decoding Reed--Solomon codes Based on Generalized Key Equations. IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2011, 57, pp.5946-5959. ⟨10.1109/TIT.2011.2162160⟩. ⟨inria-00633205⟩



Record views


Files downloads