  We develop several analytical lower bounds on the capacity of binary
insertion and deletion channels by considering independent uniformly
distributed (i.u.d.) inputs and computing lower bounds on the mutual
information between the input and output sequences. For the deletion channel,
we consider two different models: independent and identically distributed
(i.i.d.) deletion-substitution channel and i.i.d. deletion channel with
additive white Gaussian noise (AWGN). These two models are considered to
incorporate effects of the channel noise along with the synchronization errors.
For the insertion channel case we consider the Gallager's model in which the
transmitted bits are replaced with two random bits and uniform over the four
possibilities independently of any other insertion events. The general approach
taken is similar in all cases, however the specific computations differ.
Furthermore, the approach yields a useful lower bound on the capacity for a
wide range of deletion probabilities for the deletion channels, while it
provides a beneficial bound only for small insertion probabilities (less than
0.25) for the insertion model adopted. We emphasize the importance of these
results by noting that 1) our results are the first analytical bounds on the
capacity of deletion-AWGN channels, 2) the results developed are the best
available analytical lower bounds on the deletion-substitution case, 3) for the
Gallager insertion channel model, the new lower bound improves the existing
results for small insertion probabilities.
