论文标题
最佳代码纠正可变长度的删除爆发
Optimal Codes Correcting a Burst of Deletions of Variable Length
论文作者
论文摘要
在本文中，我们提出了有效的编码和可解码的代码构建，该代码构建能够校正最多$ k $的长度删除。此代码的冗余是$ \ log n+k（k+1）/2 \ log \ log \ log n+c_k $，对于某些常数$ c_k $，仅取决于$ k $，因此缩放优越。代码可以分为两个主要组件。首先，我们施加了一个约束，该约束可以将删除的爆发定位到大约$ \ log n $的大小间隔。然后，借助爆发的大约位置，我们使用几个{移动的varshamov-tenengolts}代码来纠正删除的爆发，这只需要少量的冗余，因为该位置已经知道，最多已知的间隔很小。最后，我们展示了如何有效地编码和解码代码。
In this paper, we present an efficiently encodable and decodable code construction that is capable of correction a burst of deletions of length at most $k$. The redundancy of this code is $\log n + k(k+1)/2\log \log n+c_k$ for some constant $c_k$ 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 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.
