Two Deletion Correcting Codes from Indicator Vectors
Two Deletion Correcting Codes from Indicator Vectors
复制标题
指示向量的两个删除校正代码
DOI：
10.1109/isit.2018.8437868
复制
发表时间：
2020
影响因子：
2.5
通讯作者：
Raviv, N. and
中科院分区：
文献类型：
--
作者：
Sima, J.;Raviv, N. and
几十年来，实现删除纠错码的能力建设一直是一个令人困惑的挑战。Brakensiek等人最近的一项突破，以及DNA存储方面的新应用，重新点燃了人们对这个长期存在的开放性问题的兴趣。尽管最近取得了一些进展，但现有代码中的冗余量仍远未达到最佳状态。提出了一种构造二元双缺失纠错码的新方法。通过这种方法，奇偶校验符号是从编码消息的指示向量（即，指示某些模式位置的向量）而不是从消息本身计算出来的。最有趣的是，宇称符号和正确性证明是对Varshamov-Tenengolts构造中对应符号的直接推广。我们的技术需要7 log(n) + o（log(n)）个冗余位来编码一个n位的消息，这比以前的结构更接近于最优。编码和解码算法的时间复杂度为0 (n)。
Construction of capacity achieving deletion correcting codes has been a baffling challenge for decades. A recent breakthrough by Brakensiek et al., alongside novel applications in DNA storage, have reignited the interest in this longstanding open problem. In spite of recent advances, the amount of redundancy in existing codes is still orders of magnitude away from being optimal. In this paper, a novel approach for constructing binary two-deletion correcting codes is proposed. By this approach, parity symbols are computed from indicator vectors (i.e., vectors that indicate the positions of certain patterns) of the encoded message, rather than from the message itself. Most interestingly, the parity symbols and the proof of correctness are a direct generalization of their counterparts in the Varshamov-Tenengolts construction. Our techniques require 7 log (n)+ o(log(n)) redundant bits to encode an n-bit message, which is closer to optimal than previous constructions. Moreover, the encoding and decoding algorithms have O(n) time complexity.
影响因子：
2.5
作者：
F. Palunčić;K. Abdel;H. C. Ferreira;W. A. Clarke
通讯作者：
W. A. Clarke
DOI：
10.1109/isit.2000.866296
发表时间：
1994-06
期刊：
2000 IEEE International Symposium on Information Theory (Cat. No.00CH37060)
影响因子：
--
作者：
A. Helberg;H. C. Ferreira
通讯作者：
A. Helberg;H. C. Ferreira