期刊
IEEE TRANSACTIONS ON INFORMATION THEORY
卷 67, 期 6, 页码 3360-3375出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2020.3028702
关键词
Deletion codes; Varshamov-Tenengoltz code
资金
- NSF [CCF-1717884, CCF-1816965]
The study introduces a k-deletion correcting code with optimal redundancy for constant k, and presents encoding/decoding algorithms with low complexity.
Levenshtein introduced the problem of constructing k-deletion correcting codes in 1966, proved that the optimal redundancy of those codes is O(k log N) for constant k, and proposed an optimal redundancy single-deletion correcting code (using the so-called VT construction). However, the problem of constructing optimal redundancy k-deletion correcting codes remained open. Our key contribution is a major step towards a complete solution to this longstanding open problem for constant k. We present a k-deletion correcting code that has redundancy 8k log N + o(log N) when k = o(root log log N) and encoding/decoding algorithms of complexity O(N2k+1).
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据