Guess & Check Codes for Deletions, Insertions, and Synchronization
Guess & Check Codes for Deletions, Insertions, and Synchronization
复制标题
DOI：
10.1109/tit.2018.2841936
复制
发表时间：
2017-05
影响因子：
2.5
通讯作者：
Serge Kas Hanna;Salim el Rouayheb
中科院分区：
文献类型：
--
作者：
Serge Kas Hanna;Salim el Rouayheb
我们考虑构建可以纠正长度为 $n$ 位的任意二进制字符串中发生的 $\delta $ 删除的代码的问题。 Varshamov–Tenengolts (VT) 码可追溯到 1965 年，是零错误单删除 $(\delta =1)$ 校正码，并具有渐近最优冗余。寻找 $\delta \geq 2$ 删除的相似代码仍然是一个悬而未决的问题。在本文中，我们通过假设 $\delta $ 删除（或插入）的位置独立于码字来放宽标准零错误（即最坏情况）解码要求。我们的贡献是一个新的显式代码系列，我们称之为猜测和检查（GC）代码，它可以以高概率纠正最多恒定数量的 $\delta $ 删除（或插入）。 GC代码是系统的；并具有确定性多项式时间编码和解码算法。我们还描述了 GC 代码在文件同步中的应用。
We consider the problem of constructing codes that can correct $\delta $ deletions occurring in an arbitrary binary string of length $n$ bits. Varshamov–Tenengolts (VT) codes, dating back to 1965, are zero-error single deletion $(\delta =1)$ correcting codes and have an asymptotically optimal redundancy. Finding similar codes for $\delta \geq 2$ deletions remains an open problem. In this paper, we relax the standard zero-error (i.e., worst-case) decoding requirement by assuming that the positions of the $\delta $ deletions (or insertions) are independent of the code word. Our contribution is a new family of explicit codes, that we call Guess & Check (GC) codes, that can correct with high probability up to a constant number of $\delta $ deletions (or insertions). GC codes are systematic; and have deterministic polynomial time encoding and decoding algorithms. We also describe the application of GC codes to file synchronization.