我们研究了对抗性纳米孔通道的纠错码，其中一个 $q$-进制字符串首先通过一个具有窗口大小为 $\ell$ 的符号间干扰通道转化为一系列重叠的 $\ell$-mers，然后一个对手通过至多引入 $t$ 次编辑来破坏这一 $\ell$-mer 序列。对于仅删除的纳米孔通道，我们证明了长度为 $n$ 的 $t$-删除纠错码的最优冗余在 $t\log_q n + \Omega(1)$ 与 $2t\log_q n - \log_q \log_2 n + O(1)$ 之间。接下来，我们给出了两个明确的删除纠错构造，适用于 $t \leq \min\{(\ell-1)/2,(\ell+2)/3\}$ 的情况。第一个构造依赖于广义的 Reed-Solomon 码，冗余为 $2t\log_q n + \Theta(\log\log n)$。第二个构造基于 Sidon 集（或更确切地说是 $B_t$ 序列），冗余为 $t\log_q n + \Theta(\log\log n)$，与下界在首阶上匹配。我们进一步将基于 $B_t$ 的方法扩展到编辑通道，允许对 $\ell$-mers 进行插入、删除和替换。在 $t \leq \min\{(\ell-1)/4,(\ell+2)/6\}$ 的范围内，这提供了明确的 $t$-编辑纠错码，其冗余为 $t\log_q n + \Theta(\log\log n)$，这是首阶最优的。
博主点评： 本文在对抗性纳米孔通道中提出的纠错码构造，展示了理论与实践的紧密结合，尤其是在处理编辑操作时的灵活性与效率。对冗余的详细分析为进一步的研究提供了良好的基础，值得关注。