CaltechAUTHORS
  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) https://resolver.caltech.edu/CaltechAUTHORS:20201008-083807800

[img] PDF - Accepted Version
See Usage Policy.

1039Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20201008-083807800

Abstract

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
https://doi.org/10.1109/tit.2020.3028702DOIArticle
ORCID:
AuthorORCID
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.
Funders:
Funding AgencyGrant Number
NSFCCF-1717884
NSFCCF-1816965
Subject Keywords:Deletion codes, Varshamov-Tenengoltz code
Record Number:CaltechAUTHORS:20201008-083807800
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20201008-083807800
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:105909
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:08 Oct 2020 18:11
Last Modified:08 Oct 2020 18:11

Repository Staff Only: item control page