Skip to Main content Skip to Navigation
Journal articles

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

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

https://hal.inria.fr/inria-00633205
Contributor : Daniel Augot <>
Submitted on : Monday, October 17, 2011 - 9:32:23 PM
Last modification on : Thursday, March 5, 2020 - 6:23:19 PM
Long-term archiving on: : Thursday, November 15, 2012 - 9:51:23 AM

Files

BlockHankel_hal.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

603

Files downloads

359