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
2 INT - University of Ulm. - Institute of Communications Engineering [Ulm]
3 DLR - German Aerospace Center

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}.

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

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, 2011, 57, pp.5946-5959. ⟨10.1109/TIT.2011.2162160⟩. ⟨inria-00633205⟩