Optimal rate list decoding via derivative codes
arXiv:1106.3951
Abstract
The classical family of Reed-Solomon codes over a field $\F_q$ consist of the evaluations of polynomials $f \in \F_q[X]$ of degree at distinct field elements. In this work, we consider a closely related family of codes, called (order ) {\em derivative codes} and defined over fields of large characteristic, which consist of the evaluations of as well as its first formal derivatives at distinct field elements. For large enough , we show that these codes can be list-decoded in polynomial time from an error fraction approaching , where 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 . 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.
11 pages