Reed Solomon Codes Against Adversarial Insertions and Deletions
Roni Con, Amir Shpilka, Itzhak Tamo
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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$n^{O(k)}$ </tex-math></inline-formula> there are <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$[n,k]$ </tex-math></inline-formula> Reed-Solomon codes that can decode from <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$n-2k+1$ </tex-math></inline-formula> insdel errors and hence attain the half-Singleton bound. We also give a deterministic construction of such codes over much larger fields (of size <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$n^{k^{O(k)}}$ </tex-math></inline-formula> ). Nevertheless, for <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$k=O(\log n /\log \log n)$ </tex-math></inline-formula> our construction runs in polynomial time. For the special case <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$k=2$ </tex-math></inline-formula> , which received a lot of attention in the literature, we construct an <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$[n], [2]$ </tex-math></inline-formula> Reed-Solomon code over a field of size <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(n^{4})$ </tex-math></inline-formula> that can decode from <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$n-3$ </tex-math></inline-formula> insdel errors. Earlier constructions required an exponential field size. Lastly, we prove that any such construction requires a field of size <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\Omega (n^{3})$ </tex-math></inline-formula> .