Computer Science – Information Theory
Scientific paper
2011-06-20
Computer Science
Information Theory
11 pages
Scientific paper
The classical family of $[n,k]_q$ Reed-Solomon codes over a field $\F_q$ consist of the evaluations of polynomials $f \in \F_q[X]$ of degree $< k$ at $n$ distinct field elements. In this work, we consider a closely related family of codes, called (order $m$) {\em derivative codes} and defined over fields of large characteristic, which consist of the evaluations of $f$ as well as its first $m-1$ formal derivatives at $n$ distinct field elements. For large enough $m$, we show that these codes can be list-decoded in polynomial time from an error fraction approaching $1-R$, where $R=k/(nm)$ is the rate of the code. This gives an alternate construction to folded Reed-Solomon codes for achieving the optimal trade-off between rate and list error-correction radius. Our decoding algorithm is linear-algebraic, and involves solving a linear system to interpolate a multivariate polynomial, and then solving another structured linear system to retrieve the list of candidate polynomials $f$. The algorithm for derivative codes offers some advantages compared to a similar one for folded Reed-Solomon codes in terms of efficient unique decoding in the presence of side information.
Guruswami Venkatesan
Wang Carol
No associations
LandOfFree
Optimal rate list decoding via derivative 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 Optimal rate list decoding via derivative codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal rate list decoding via derivative codes will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-256082