



















The performance of Reed--Solomon codes (RS codes, for short) in the presence of insertion and deletion errors has attracted growing attention in recent literature. In this work, we further study this intriguing mathematical problem, focusing on two regimes. First, we study the question of how well full-length RS codes perform against insertions and deletions. For 2-dimensional RS codes, we provide a complete characterization of codes that cannot correct even a single insertion or deletion. Furthermore, we prove that for sufficiently large field size~$q$, nearly all full-length $2$-dimensional RS codes can correct up to $(1 - δ)q$ insertion and deletion errors for any $0 < δ< 1$. Extending beyond the 2-dimensional case, we show that for any $k \ge 2$, there exists a full-length $k$-dimensional RS code capable of correcting $q / (10k)$ insertion and deletion errors, provided $q$ is large enough. Second, we focus on rate $1/2$ RS codes that can correct a single insertion or deletion error. We present a polynomial-time algorithm that constructs such codes over fields of size $q = Θ(k^4)$. This result matches the existential bound given in \cite{con2023reed}.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。