论文标题
具有冗余的显式两台式代码与存在的界限匹配
Explicit two-deletion codes with redundancy matching the existential bound
论文作者
论文摘要
我们给出了长度 - $ n $二进制代码的明确构造，该代码能够纠正两个具有$ 2^n/n^{4+o（1）} $的两个位的删除。这匹配较低的术语，基于无效的代码字选择，生存结果保证了大小$ω（2^n/n/n^4）$的此类代码。我们的构建基于增强具有其他检查方程式的单个删除代码的经典瓦尔沙莫夫 - tenengolts构造。我们还提供了大小$ω（2^n/n^{3+o（1）}）$的二进制代码的明确构造，该代码可以使用尺寸二的列表从两个删除中列表进行解码。以前，即使存在此类代码也不清楚。
We give an explicit construction of length-$n$ binary codes capable of correcting the deletion of two bits that have size $2^n/n^{4+o(1)}$. This matches up to lower order terms the existential result, based on an inefficient greedy choice of codewords, that guarantees such codes of size $Ω(2^n/n^4)$. Our construction is based on augmenting the classic Varshamov-Tenengolts construction of single deletion codes with additional check equations. We also give an explicit construction of binary codes of size $Ω(2^n/n^{3+o(1)})$ that can be list decoded from two deletions using lists of size two. Previously, even the existence of such codes was not clear.
