期刊
2020 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT)
卷 -, 期 -, 页码 769-774出版社
IEEE
DOI: 10.1109/isit44484.2020.9173986
关键词
-
资金
- NSF [CCF-1816965, CCF-1717884]
Systematic deletion correcting codes play an important role in applications of document exchange. Yet despite a series of recent advances made in deletion correcting codes, most of them are non-systematic. To the best of the authors' knowledge, the only known deterministic systematic t-deletion correcting code constructions with rate approaching 1 achieve O(t log(2) n) bits of redundancy for constant t, where n is the code length. In this paper, we propose a systematic t-deletion correcting code construction that achieves 4t log n + o(log n) bits of redundancy, which is asymptotically within a factor of 4 from being optimal. Our encoding and decoding algorithms have complexity O(n(2t+1)), which is polynomial for constant t.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据