A Caltech Library Service

On Optimal k-Deletion Correcting Codes

Sima, Jin and Bruck, Jehoshua (2020) On Optimal k-Deletion Correcting Codes. IEEE Transactions on Information Theory . ISSN 0018-9448. (In Press)

[img] PDF - Accepted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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(√log log N) and encoding/decoding algorithms of complexity O(n^(2k+1)).

Item Type:Article
Related URLs:
URLURL TypeDescription
Sima, Jin0000-0003-4588-9790
Bruck, Jehoshua0000-0001-8474-0812
Additional Information:© 2020 IEEE. Manuscript received October 15, 2019; revised June 4, 2020; accepted September 8, 2020. This work was supported in part by NSF grants CCF-1717884 and CCF-1816965. This paper was presented in part at the 2019 IEEE International Symposium on Information Theory. The authors would like to thank the anonymous reviewers for their valuable suggestions that greatly improved the clarity and the organization of the paper.
Funding AgencyGrant Number
Subject Keywords:Deletion codes, Varshamov-Tenengoltz code
Record Number:CaltechAUTHORS:20201008-083807800
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:105909
Deposited By: George Porter
Deposited On:08 Oct 2020 18:11
Last Modified:08 Oct 2020 18:11

Repository Staff Only: item control page