Algorithm

Discrete mathematics

Theoretical computer science

Operating system

Set (abstract data type)

Computer science

Binary logarithm

Code (set theory)

Decoding methods

Mathematics

Artificial intelligence

Combinatorics

Encoding (memory)

Programming language

Redundancy (engineering)

Asymptotically optimal algorithm

Constant (computer programming)

Systematic deletion correcting codes play an important role in applications of document exchange. Yet despite a series of recent advances made in deletion correcting codes, most of them are non-systematic. To the best of the authors' knowledge, the only known deterministic systematic t-deletion correcting code constructions with rate approaching 1 achieve O(t log <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> n) bits of redundancy for constant t, where n is the code length. In this paper, we propose a systematic t-deletion correcting code construction that achieves 4t log n + o(log n) bits of redundancy, which is asymptotically within a factor of 4 from being optimal. Our encoding and decoding algorithms have complexity O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2t+1</sup> ), which is polynomial for constant t.

Optimal Systematic t-Deletion Correcting Codes