Optimal k-Deletion Correcting Codes

Jump to other IT Society Websites:

Optimal k-Deletion Correcting Codes


Creation Date: Jul 07, 2019

Published In: Jul 2019

Paper Type: Conference Paper

Book Title: Proceedings of the 2019 IEEE International Symposium on Information Theory

Address: Paris, France


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), 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 solution to this long-standing open problem. We present a k-deletion correcting code that has redundancy 8k log n + o(log n) and encoding/decoding algorithms of complexity O(n 2k+1 ) for constant k.

IEEE Explore link: https://ieeexplore.ieee.org/document/8849750

Award(s) Received: