论文标题
t残局 - 插入式纠正代码
t-Deletion-s-Insertion-Burst Correcting Codes
论文作者
论文摘要
在基于DNA的存储和通信系统中的应用中，我们同时研究了删除和插入错误。特别是，我们研究了一种名为$ t $ -doletion- $ s $ s $ insertion-burst（$（t，s）$ - 短爆发）的错误类型，这是Schoeny {\ it等人提出的$（2,1）$ - 爆发错误的概括。 al}。此类错误删除了$ t $ cotaine符号，并在同一坐标处插入一个任意长度$ s $的序列。我们在可以纠正$（t，s）$ - 爆发错误的二进制代码大小上提供了一个球形的上限，表明此类代码的冗余至少为$ \ log n+t-1 $。对于$ t \ geq 2s $，给出了带有冗余$ \ log n+（t-s-1）\ log \ log \ log \ log n+o（1）$的二进制$（t，s）$的明确构造。特别是，我们构建了一个二进制$（3,1）$ - 爆发校正代码，最多$ \ log n+9 $，最佳达到常数。
Motivated by applications in DNA-based storage and communication systems, we study deletion and insertion errors simultaneously in a burst. In particular, we study a type of error named $t$-deletion-$s$-insertion-burst ($(t,s)$-burst for short) which is a generalization of the $(2,1)$-burst error proposed by Schoeny {\it et. al}. Such an error deletes $t$ consecutive symbols and inserts an arbitrary sequence of length $s$ at the same coordinate. We provide a sphere-packing upper bound on the size of binary codes that can correct a $(t,s)$-burst error, showing that the redundancy of such codes is at least $\log n+t-1$. For $t\geq 2s$, an explicit construction of binary $(t,s)$-burst correcting codes with redundancy $\log n+(t-s-1)\log\log n+O(1)$ is given. In particular, we construct a binary $(3,1)$-burst correcting code with redundancy at most $\log n+9$, which is optimal up to a constant.
