WorksComputer Science
Optimal Ordering-Free Two-Dimensional Insdel Reed-Solomon Codes via Cross-Ratios
Abstract
Insertion-deletion (insdel) codes correct synchronization errors. By the half-Singleton bound, an code has minimum insdel distance at most . The smallest field size of two-dimensional Reed–Solomon (RS) codes attaining this bound is . Unlike the minimum Hamming distance, the minimum insdel distance of an RS code depends on the ordering of its evaluation points. An evaluation set is called ordering-free if every ordering of its points gives an RS code attaining the half-Singleton bound. In this paper, we first show that for every code attaining the half-Singleton bound is an RS code, and hence . Secondly, we show that an ordering-free evaluation set with points in satisfies , and that it has at most points if for a prime power . Finally, by using cross-ratios, we construct an ordering-free evaluation set with points in for every prime power . Hence, the bound is attained for . Moreover, the constructed set is even robust against permutations combined with insdel errors.