Optimal Codes Correcting a Burst of Deletions of Variable Length
Optimal Codes Correcting a Burst of Deletions of Variable Length
复制标题
纠正可变长度突发删除的最佳代码
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
N. Polyanskii
中科院分区：
文献类型：
--
作者：
A. Lenz;N. Polyanskii
在本文中，我们提出了一个有效的可编码和可解码的代码结构，是能够纠正的长度最多为k的删除突发。这个码的冗余度是log n + k（k + 1）/2 log log n + ck，对于某个常数ck，它只依赖于k，因此是缩放最优的。代码可以分为两个主要部分。首先，我们施加了一个约束，允许我们定位的删除到一个区间的大小大致log n的突发。然后，与知识的大致位置的突发，我们使用几个移位Varshamov-Tenengolts代码来纠正突发的删除，这只需要少量的冗余，因为位置已经知道了一个小的间隔大小。最后，我们展示了如何有效地编码和解码的代码。
In this paper, we present an efficiently encodable and decodable code construction that is capable of correcting a burst of deletions of length at most k. The redundancy of this code is log n + k(k + 1)/2 log log n + ck for some constant ck that only depends on k and thus is scaling-optimal. The code can be split into two main components. First, we impose a constraint that allows us to locate the burst of deletions up to an interval of size roughly log n. Then, with the knowledge of the approximate location of the burst, we use several shifted Varshamov-Tenengolts codes to correct the burst of deletions, which only requires a small amount of redundancy since the location is already known up to an interval of small size. Finally, we show how to efficiently encode and decode the code.
最佳文档交换以及插入和删除的新代码
DOI：
10.1109/focs.2019.00029
发表时间：
2019
期刊：
IEEE Symposium on Foundations of Computer Science
影响因子：
--
作者：
Haeupler, Bernhard
通讯作者：
Haeupler, Bernhard