Optimal rate list decoding via derivative codes
Sep 21, 2011
ABSTRACT:
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.
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.