Lower bounds for the capacity of channels with i.i.d. deletions and insertions

Consider the simplest channel which introduces deletions; or binary i.i.d. deletion channel: each transmitted bit is independently deleted with probability d. The capacity C del of this channel remains unknown since Dobrushin's introduction of the problem in 1967. The topic of this thesis is provable lower bounds for Cdel by developping Shannon-style theorems. Although this implies that the codes considered in this work are of no practical interest, practical codes are not required to prove capacity bounds. Moreover, existing lower bounds for the capacity of this channel arising from the study of the performance of efficient codes are significantly below the theoretical bounds we prove.;Previous theoretical approaches to lower bound C del implicitly attempt typical set decoding. The improvements in our work arise in two ways. First, we explicitly consider typical set decoding, thus establishing that one clear way to improve capacity lower bounds is to refine the definitions of the typical sets. We start by refining the definition of the typical received sequence after the i.i.d. deletion channel, by observing further structural properties of the received sequence. Then we refine the decoding algorithm by using a more sophisticated set of received sequences jointly typical with a codeword. Second, we introduce a new framework for generating 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 approach allows for dramatic improvements on the lower bounds. Moreover, for d > 0.65, we surpass a combinatorial upper bound for channels with an asymptotic fraction of d synchronization errors.;Another advantage of our framework is that it can be applied to analyze more general channels. Specifically, we consider the i.i.d. channel with deletions and insertions, where insertions only occur in the form of copies. We provide a general lower bound for the capacity of this channel (under the assumption of geometrically decreasing tails for the insertion distribution). We then use this result to show that Cdel > (1- d)/9, via a reduction argument.