We consider binary error correcting codes when errors are deletions. A basic challenge concerning deletion codes is determining @math , the zero-rate threshold of adversarial deletions, defined to be the supremum of all @math for which there exists a code family with rate bounded away from 0 capable of correcting a fraction @math of adversarial deletions. A recent construction of deletion-correcting codes [ 17] shows that @math , and the trivial upper bound, @math , is the best known. Perhaps surprisingly, we do not know whether or not @math . In this work, to gain further insight into deletion codes, we explore two related error models: oblivious deletions and online deletions, which are in between random and adversarial deletions in power. In the oblivious model, the channel can inflict an arbitrary pattern of @math deletions, picked without knowledge of the codeword. We prove the existence of binary codes of positive rate that can correct any fraction @math of oblivious deletions, establishing that the associated zero-rate threshold @math equals @math . For online deletions, where the channel decides whether to delete bit @math based only on knowledge of bits @math , define the deterministic zero-rate threshold for online deletions @math to be the supremum of @math for which there exist deterministic codes against an online channel causing @math deletions with low average probability of error. That is, the probability that a randomly chosen codeword is decoded incorrectly is small. We prove @math if and only if @math .
To the best of our knowledge, ours is the first work to address both oblivious and online deletions. We feel that given the large gaps in our understanding of coding against adversarial deletions, and the potential of taking advantage of less stringent models of deletion exhibited in this work, further study of these models seems timely and important. In particular, for online deletions as well, the zero-rate threshold is between @math and @math . It is an interesting challenge to ascertain if one can take advantage of the online restriction, and push some of the ideas in @cite_7 and this work, to enable decoding a fraction of online deletions approaching @math .
@cite_7
2952657341
We consider codes over fixed alphabets against worst-case symbol deletions. For any fixed @math , we construct a family of codes over alphabet of size @math with positive rate, which allow efficient recovery from a worst-case deletion fraction approaching @math . In particular, for binary codes, we are able to recover a fraction of deletions approaching @math . Previously, even non-constructively the largest deletion fraction known to be correctable with positive rate was @math , and around @math for the binary case. Our result pins down the largest fraction of correctable deletions for @math -ary codes as @math , since @math is an upper bound even for the simpler model of erasures where the locations of the missing symbols are known. Closing the gap between @math and @math for the limit of worst-case deletions correctable by binary codes remains a tantalizing open question.