Reed Solomon Codes Against Adversarial Insertions and Deletions

2021/07/12 by Roni Con, Con, Roni, Amir Shpilka +3 · 4 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Cellular Automata and Applications #Coding theory and cryptography #DNA and Biological Computing #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.IT #math.IT

paper · pdf · doi:10.48550/arxiv.2107.05699

The previous version was split into two different papers. This paper concerns the performance of Reed Solomon codes against insertions and deletions

openalex publication_date 2021/07/12 · arxiv created 2022/01/16 · arxiv updated 2022/01/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this work, we study the performance of Reed--Solomon codes against adversarial insertion-deletion (insdel) errors. We prove that over fields of size n^O(k) there are [n,k] Reed-Solomon codes that can decode from n-2k+1 insdel errors and hence attain the half-Singleton bound. We also give a deterministic construction of such codes over much larger fields (of size n^k^O(k)). Nevertheless, for k=O(log n /loglog n) our construction runs in polynomial time. For the special case k=2, which received a lot of attention in the literature, we construct an [n,2] Reed-Solomon code over a field of size O(n⁴) that can decode from n-3 insdel errors. Earlier constructions required an exponential field size. Lastly, we prove that any such construction requires a field of size Ω(n³).

Cited by

• Improved Constructions of Linear Codes for Insertions and Deletions
• Linear List Decodable Edit-Correcting Codes with Rate Approaching 1
• Decoding Insertions/Deletions via List Recovery
• Explicit and Efficient Constructions of linear Codes Against Adversarial Insertions and Deletions

Related

• Optimal Two-Dimensional Reed--Solomon Codes Correcting Insertions and Deletions
• Reed-Solomon Codes Against Insertions and Deletions: Full-Length and Rate-1/2 Codes
• Explicit Constructions of Two-Dimensional Reed-Solomon Codes in High Insertion and Deletion Noise Regime
• Random Reed-Solomon Codes Achieve the Half-Singleton Bound for Insertions and Deletions over Linear-Sized Alphabets
• Bounds and Constructions for Insertion and Deletion Codes