2011/06/20 by Venkatesan Guruswami, Carol Wang, Guruswami, Venkatesan +1 · 1 citation
Computer Science · Engineering · Mathematics · #Coding theory and cryptography #Computational Complexity (cs.CC) #Cryptographic Implementations and Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.CC #cs.DS #cs.IT #graph theory and CDMA systems #math.IT
paper · pdf · doi:10.48550/arxiv.1106.3951
11 pages
arxiv created 2011/06/20 · openalex publication_date 2011/06/20 · arxiv updated 2015/03/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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) \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.