Optimal Rate List Decoding via Derivative Codes
Optimal Rate List Decoding via Derivative Codes
复制标题
通过导数码进行最优速率列表解码
DOI：
10.1007/978-3-642-22935-0_50
复制
发表时间：
2011
影响因子：
2.5
通讯作者：
Carol Wang
中科院分区：
文献类型：
--
作者：
V. Guruswami;Carol Wang
[n，k] q的经典家族在字段FQ上的代码由n个不同的场元素的多项式f∈FQ[x]的评估组成。在大型特征的字段中定义的代码（阶）代码，其中包括F的评估以及其第一个M -1正式衍生物在N不同的字段元素上。这些代码可以在多项式时间内从1-r的错误分数中列出，其中r = k/（nm）是代码的速率。 - 速率和列表误差校正半径之间。
我们的解码算法是线性的，涉及求解一个线性系统以插值多元多项式，然后求解另一个结构化的线性系统以检索候选多项式f的列表，与衍生物的算法相比。在存在侧面信息的情况下，根据有效的独特解码来折叠的芦苇 - 固体代码。
The classical family of [n, k]q Reed-Solomon codes over a field Fq consist of the evaluations of polynomials f ∈ Fq[X] of degree < k at n distinct field elements. In this work, we consider a closely related family of codes, called (order m) 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.