We consider binary deletion channels, where bits are deleted independently with probability d. We extend the framework used to analyze the capacity of binary deletion channels established by Diggavi and Grossglauser [2001], improving on their lower bounds. In Diggavi and Grossglauser, the codewords are generated by a first order Markov chain. Our improvements arise from two considerations. First, Diggavi and Grossglauser consider typical outputs, where an output is typical if an N bit input produces an output of at least N(1-d)(1-/spl epsi/) bits. We provide a stronger notion of a typical output that yields better bounds even for the cases studied in Diggavi and Grossglauser. Second, we consider codewords generated by more general processes than first order Markov chains.
['Eleni Drinea', 'Michael Mitzenmacher']
On lower bounds for the capacity of deletion channels