A new bound for the capacity of the deletion channel with high deletion probabilities

Abstract

Let $C(d)$ be the capacity of the binary deletion channel with deletion probability $d$. It was proved by Drinea and Mitzenmacher that, for all $d$, $C(d)/(1-d)\ge 0.1185$. Fertonani and Duman recently showed that ${\mathrm{limsup}}_{d\to 1}C(d)/(1-d)\le 0.49$. In this paper, it is proved that ${\lim }_{d\to 1}C(d)/(1-d)$ exists and is equal to ${\inf }_{d}C(d)/(1-d)$. This result suggests the conjecture that the curve $C(d)$ my be convex in the interval $d\in [0,1]$. Furthermore, using currently known bounds for $C(d)$, it leads to the upper bound ${\lim }_{d\to 1}C(d)/(1-d)\le 0.4143$.

arXiv commentISIT 2011, the first draft contained an error in some expressions (a log(n) in place of log(n+1))

Cited by in corpus (2)

• Optimal coding for the deletion channel with small deletion probability
• Modeling and Information Rates for Synchronization Error Channels