Computer Science – Information Theory
Scientific paper
2011-10-18
Computer Science
Information Theory
IEEE Transactions on Information Theory (2011)
Scientific paper
10.1109/TIT.2011.2162160
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}.
Augot Daniel
Gentner Christian
Zeh Alexander
No associations
LandOfFree
An Interpolation Procedure for List Decoding Reed--Solomon codes Based on Generalized Key Equations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with An Interpolation Procedure for List Decoding Reed--Solomon codes Based on Generalized Key Equations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Interpolation Procedure for List Decoding Reed--Solomon codes Based on Generalized Key Equations will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-290486