期刊
IEEE TRANSACTIONS ON INFORMATION THEORY
卷 65, 期 1, 页码 3-15出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2018.2841936
关键词
Coding theory; deletions; insertions; file synchronization; systematic codes
资金
- NSF [CCF 15-26875]
- Division of Computing and Communication Foundations
- Direct For Computer & Info Scie & Enginr [1817634] Funding Source: National Science Foundation
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 >= 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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据