← 研踪 PaperTrailarXiv:2611.21275 · v1
Optimal Ordering-Free Two-Dimensional Insdel Reed-Solomon Codes via Cross-Ratios
首次提交 2026-11-16 23:45
版本更新 2026-11-16 23:45
雷达观测 2026-11-17 16:10
摘要
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.
作者备注:16 pages
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-16 23:45 · 最新观测版本
Optimal Ordering-Free Two-Dimensional Insdel Reed-Solomon Codes via Cross-Ratios
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.
查看此版本解读 →查看此版本原文 ↗