An Improved Bound on the Fraction of Correctable Deletions

Abstract: We consider codes over fixed alphabets against worst-case symbol deletions. For any fixed

k g e 2

, we construct a family of codes over alphabet of size

k

with positive rate, which allow efficient recovery from a worst-case deletion fraction approaching

1 - f r a c 2 k + s q r t k

. In particular, for binary codes, we are able to recover a fraction of deletions approaching

1 / (s q r t 2 + 1) = s q r t 2 - 1 a p p r o x 0.414

. Previously, even non-constructively the largest deletion fraction known to be correctable with positive rate was

1 - T h e t a (1 / s q r t k)

, and around

0.17

for the binary case. Our result pins down the largest fraction of correctable deletions for

k

-ary codes as

1 - T h e t a (1 / k)

, since

1 - 1 / k

is an upper bound even for the simpler model of erasures where the locations of the missing symbols are known. Closing the gap between

(s q r t 2 - 1)

and

1 / 2

for the limit of worst-case deletions correctable by binary codes remains a tantalizing open question.

Cited In (4)

This page was built for publication: An Improved Bound on the Fraction of Correctable Deletions