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

Roni Con; Amir Shpilka; Itzhak Tamo

paper

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

arXiv:2311.02771

Abstract

Constructing Reed--Solomon (RS) codes that can correct insertions and deletions (insdel errors) has been considered in numerous recent works. For the special case of two-dimensional RS-codes, it is known [CST23] that an $[n, 2]_{q}$ RS-code that can correct from $n - 3$ insdel errors satisfies that $q = Ω (n^{3})$ . On the other hand, there are several known constructions of $[n, 2]_{q}$ RS-codes that can correct from $n - 3$ insdel errors, where the smallest field size is $q = O (n^{4})$ . In this short paper, we construct $[n, 2]_{q}$ Reed--Solomon codes that can correct $n - 3$ insdel errors with $q = O (n^{3})$ , thereby resolving the minimum field size needed for such codes.

arXiv admin note: substantial text overlap with arXiv:2107.05699