Computer Science – Information Theory
Scientific paper
2011-06-02
Computer Science
Information Theory
16 pages. Extended abstract in Proc. of IEEE Conference on Computational Complexity (CCC), 2011
Scientific paper
Folded Reed-Solomon codes are an explicit family of codes that achieve the optimal trade-off between rate and error-correction capability: specifically, for any $\eps > 0$, the author and Rudra (2006,08) presented an $n^{O(1/\eps)}$ time algorithm to list decode appropriate folded RS codes of rate $R$ from a fraction $1-R-\eps$ of errors. The algorithm is based on multivariate polynomial interpolation and root-finding over extension fields. It was noted by Vadhan that interpolating a linear polynomial suffices if one settles for a smaller decoding radius (but still enough for a statement of the above form). Here we give a simple linear-algebra based analysis of this variant that eliminates the need for the computationally expensive root-finding step over extension fields (and indeed any mention of extension fields). The entire list decoding algorithm is linear-algebraic, solving one linear system for the interpolation step, and another linear system to find a small subspace of candidate solutions. Except for the step of pruning this subspace, the algorithm can be implemented to run in {\em quadratic} time. The theoretical drawback of folded RS codes are that both the decoding complexity and proven worst-case list-size bound are $n^{\Omega(1/\eps)}$. By combining the above idea with a pseudorandom subset of all polynomials as messages, we get a Monte Carlo construction achieving a list size bound of $O(1/\eps^2)$ which is quite close to the existential $O(1/\eps)$ bound (however, the decoding complexity remains $n^{\Omega(1/\eps)}$). Our work highlights that constructing an explicit {\em subspace-evasive} subset that has small intersection with low-dimensional subspaces could lead to explicit codes with better list-decoding guarantees.
No associations
LandOfFree
Linear-algebraic list decoding of folded Reed-Solomon codes 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 Linear-algebraic list decoding of folded Reed-Solomon codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Linear-algebraic list decoding of folded Reed-Solomon codes will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-495376