Optimal Two-Dimensional Reed–Solomon Codes Correcting Insertions and Deletions
Roni Con, Amir Shpilka, Itzhak Tamo · IEEE Transactions on Information Theory · 2024
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 fromn- 3 insdel errors, the maximal possible number of insdel errors a two-dimensional linear code can recover from. It is known (by settingk= 2 in the lower bound [10, Proposition 37]) that an [n, 2]qRS-code that can correct fromn-3 insdel errors satisfies thatq= Ω(n3). On the other hand, there are several known constructions of [n, 2]qRS-codes that can correct fromn-3 insdel errors, where the smallest field size isq=O(n4). In this short paper, we construct [n, 2]qReed–Solomon codes that can correctn-3 insdel errors withq=O(n3), thereby resolving the minimum field size needed for such codes.