期刊
IEEE TRANSACTIONS ON INFORMATION THEORY
卷 69, 期 1, 页码 169-186出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2022.3202856
关键词
Synchronization errors; optimal codes; efficient encoding/decoding
This work investigates the problem of designing low-redundancy codes for correcting a combination of deletions, substitutions, and adjacent transpositions in DNA-based data storage. The authors make progress in three variations, constructing linear-time encodable and decodable codes with nearly optimal redundancy for single edit errors, single deletions or adjacent transpositions, and a combination of a deletion and a substitution. The results match or approach the existing theoretical bounds.
consider the problem of designing low-redundancy codes in settings where one must correct deletions in conjunction with substitutions or adjacent transpositions; a combination of errors that is usually observed in DNA-based data storage. One of the most basic versions of this problem was settled more than 50 years ago by Levenshtein, who proved that binary Varshamov-Tenengolts codes correct one arbitrary edit error, i.e., one deletion or one substitution, with nearly optimal redundancy. However, this approach fails to extend to many simple and natural variations of the binary single-edit error setting. In this work, we make progress on the code design problem above in three such variations: 1) We construct linear-time encodable and decodable length -n non binary codes correcting a single edit error with nearly optimal redundancy log n + O(log log n), providing an alternative simpler proof of a result by Cai et al. (IEEE Trans. Inf. Theory 2021). This is achieved by employing what we call weighted VT sketches, a new notion that may be of independent interest. 2) We show the existence of a binary code correcting one deletion or one adjacent transposition with nearly optimal redundancy log n + O(log log n). 3) We construct linear-time encodable and list-decodable binary codes with list-size 2 for one deletion and one substitution with redundancy 4 log n + O(log log n). This matches the Gilbert-Varshamov existential bound up to an O(log log n) additive term.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据