Combinatorics

Discrete mathematics

Redundancy (engineering)

Mathematics

Operating system

Algorithm

Levenshtein distance

Computer science

Decoding methods

Binary logarithm

IEEE Transactions on Information Theory

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 8 klog N + o(log N) when k = o(√{loglog N}) and encoding/decoding algorithms of complexity O(N <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2 k+1</sup> ).

On Optimal <i>k</i>-Deletion Correcting Codes

On Optimal k-Deletion Correcting Codes