Reed Solomon Codes Against Adversarial Insertions and Deletions

DOI10.1109/TIT.2023.3237711arXiv2107.05699MaRDI QIDQ6197481FDOQ6197481

Authors: Roni Con, Amir Shpilka, Itzhak Tamo 

Publication date: 19 March 2024

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

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(logn/loglogn)$ 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^4)$ 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 $Omega(n^3)$.

Full work available at URL: https://arxiv.org/abs/2107.05699

zbMATH Keywords

Reed-Solomon codesinsertion-deletion codes

Mathematics Subject Classification ID

Information and communication theory, circuits (94-XX)

Cited In (1)

• New dimension-independent upper bounds on linear insdel codes

This page was built for publication: Reed Solomon Codes Against Adversarial Insertions and Deletions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6197481)