Computer Science – Information Theory
Scientific paper
2010-11-04
IEEE Transactions on Information Theory, vol. 57, no. 10, pp. 6718 - 6728, 2011
Computer Science
Information Theory
Corrected Definition 2.3. Accepted for publication in IEEE Transactions on Information Theory
Scientific paper
10.1109/TIT.2011.2165803
In this paper we present a minimal list decoding algorithm for Reed-Solomon (RS) codes. Minimal list decoding for a code $C$ refers to list decoding with radius $L$, where $L$ is the minimum of the distances between the received word $\mathbf{r}$ and any codeword in $C$. We consider the problem of determining the value of $L$ as well as determining all the codewords at distance $L$. Our approach involves a parametrization of interpolating polynomials of a minimal Gr\"obner basis $G$. We present two efficient ways to compute $G$. We also show that so-called re-encoding can be used to further reduce the complexity. We then demonstrate how our parametric approach can be solved by a computationally feasible rational curve fitting solution from a recent paper by Wu. Besides, we present an algorithm to compute the minimum multiplicity as well as the optimal values of the parameters associated with this multiplicity which results in overall savings in both memory and computation.
Ali Mortuza
Kuijper Margreta
No associations
LandOfFree
A parametric approach to list decoding of Reed-Solomon codes using interpolation 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 A parametric approach to list decoding of Reed-Solomon codes using interpolation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A parametric approach to list decoding of Reed-Solomon codes using interpolation will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-145198