Optimal Two-Dimensional Reed–Solomon Codes Correcting Insertions and Deletions

Constructing Reed–Solomon (RS) codes that can correct insertions and deletions (insdel errors) has been considered in numerous recent works. Our focus in this paper is on the special case of two-dimensional RS-codes that can correct from <inline-formula> <tex-math notation="LaTeX">$n-3$ </tex-math></inline-formula> insdel errors, the maximal possible number of insdel errors a two-dimensional linear code can recover from. It is known that an <inline-formula> <tex-math notation="LaTeX">$[n], [2]_{q}$ </tex-math></inline-formula> RS-code that can correct from <inline-formula> <tex-math notation="LaTeX">$n-3$ </tex-math></inline-formula> insdel errors satisfies that <inline-formula> <tex-math notation="LaTeX">$q=\Omega (n^{3})$ </tex-math></inline-formula>. On the other hand, there are several known constructions of <inline-formula> <tex-math notation="LaTeX">$[n], [2]_{q}$ </tex-math></inline-formula> RS-codes that can correct from <inline-formula> <tex-math notation="LaTeX">$n-3$ </tex-math></inline-formula> insdel errors, where the smallest field size is <inline-formula> <tex-math notation="LaTeX">$q=O(n^{4})$ </tex-math></inline-formula>. In this short paper, we construct <inline-formula> <tex-math notation="LaTeX">$[n], [2]_{q}$ </tex-math></inline-formula> Reed–Solomon codes that can correct <inline-formula> <tex-math notation="LaTeX">$n-3$ </tex-math></inline-formula> insdel errors with <inline-formula> <tex-math notation="LaTeX">$q=O(n^{3})$ </tex-math></inline-formula>, thereby resolving the minimum field size needed for such codes.