Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published June 2021 | public
Journal Article

On Optimal k-Deletion Correcting Codes

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)).

Additional Information

© 2020 IEEE. Manuscript received October 15, 2019; revised June 4, 2020; accepted September 8, 2020. Date of publication October 5, 2020; date of current version May 20, 2021. 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.

Additional details

Created:
August 20, 2023
Modified:
October 20, 2023