Lower bounds for the capacity of the deletion channel- 06/16/2006

Eleni Drinea

Consider the simplest channel which introduces deletions: each transmitted bit is independently deleted with probability d. The capacity of this channel, commonly referred to as the binary deletion channel, remains unknown since Dobrushin's introduction of the problem in 1967.

In this talk I will present recent advances on proving lower bounds for the capacity of the binary deletion channel by developing Shannon-style theorems. Previous theoretical approaches for lower bounding the capacity implicitly attempt typical set decoding. The improvements in our work arise from two considerations. First, we explicitly consider typical set decoding, and provide stronger definitions for the sets of typical received sequences and received sequences jointly typical with codewords. Second, we introduce a new framework for generating typical codewords, which allows consideration of more general codebooks, while using our new definitions of typical sets; the analysis in previous frameworks was not amenable to such generalizations.

Our new approach allows for dramatic improvements on the lower bounds. For example, for d>0.65, we surpass a combinatorial upper bound by Ullman for channels with an asymptotic fraction of d synchronization errors; this bound had been previously used as a bound for the deletion channel as it seemed difficult to reach. Moreover, our technique can be applied to analyze more general channels with deletions and/or insertions, when insertions occur in the form of copies; until recently there has not been a general approach for obtaining provable lower bounds on the capacity of specific insertion/deletion channels. By developing a correspondence between the deletion channel and an insertion/deletion channel that we call a Poisson-repeat channel, we derive a simple proof that the capacity of the deletion channel with deletion probability d is at least (1-d)/9, thus within a constant factor of its trivial upper bound of 1-d, which is the capacity of the erasure channel with erasure probability d.

Joint work with Michael Mitzenmacher.