Correcting bursty and localized deletions using guess & check codes
Correcting bursty and localized deletions using guess & check codes
复制标题
使用猜测纠正突发和局部删除
DOI：
10.1109/allerton.2017.8262712
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
S. E. Rouayheb
中科院分区：
文献类型：
--
作者：
Serge Kas Hanna;S. E. Rouayheb
我们考虑构造二进制码的问题，以纠正在码字的某个部分先验未知的局部缺失。我们研究的模型是当δ≤w缺失发生在最大w位大小的窗口时。这些δ缺失不一定是连续的，但仅限于大小为w的窗口。局部缺失模型是突发模型的推广，其中所有被删除的位都是连续的。在这项工作中，我们提出了新的显式代码，基于Guess & Check代码族[1,2]，可以高概率地纠正δ≤w的缺失，这些缺失定位在大小不超过w = O （log k）的窗口内，其中k是信息消息的长度。这些码具有确定的多项式时间编码和解码方案。这些代码的冗余度是c log k + w + 1，其中c是表示代码参数的常数。
We consider the problem of constructing binary codes for correcting deletions that are localized within a certain part of the codeword that is unknown a priori. The model that we study is when δ ≤ w deletions occur in a window of size at most w bits. These δ deletions are not necessarily consecutive, but are restricted to a window of size w. The localized deletions model is a generalization of the bursty model, where all the deleted bits are consecutive. In this work we propose new explicit codes, based on the family of Guess & Check codes [1,2], that can correct, with high probability, δ ≤ w deletions that are localized within a window of size at most w = O (log k), where k is the length of the information message. These codes have deterministic polynomial time encoding and decoding schemes. The redundancy of these codes is c log k + w + 1, where c is a constant representing a code parameter.