Improved Upper and Lower Bounds on the Capacity of the Binary Deletion Channel

The binary deletion channel with deletion probability d (BDC
d
) is a random channel that deletes each bit of its input with probability d. It has been studied extensively as a canonical example of a channel with synchronization errors [1] - [3].Perhaps the most important question regarding the BDC is determining its capacity. Mitzenmacher and Drinea [4] and Kirsch and Drinea [5] show a method by which distributions on run lengths can be converted to codes for the BDC, yielding a lower bound of $\mathcal{C}\left( {{\mathbf{BD}}{{\mathbf{C}}_d}} \right) > 0.1185 \cdot \left( {1 - d} \right)$. Fertonani and Duman [6], Dalai [7] and Rahmati and Duman [8] use computer aided analyses based on the Blahut-Arimoto algorithm to prove an upper bound of $\mathcal{C}\left( {{\mathbf{BD}}{{\mathbf{C}}_d}} \right) < 0.4143 \cdot \left( {1 - d} \right)$ in the high deletion probability regime (d > 0.65).In this paper, we show that the Blahut-Arimoto algorithm can be implemented with a lower space complexity, allowing us to extend the upper bound analyses, and prove an upper bound of $\mathcal{C}\left( {{\mathbf{BD}}{{\mathbf{C}}_d}} \right) < 0.3745 \cdot \left( {1 - d} \right)$ for all d ≥ 0.68. Furthermore, we show that an extension of the Blahut-Arimoto algorithm can be used to select better run length distributions for Mitzenmacher and Drinea’s construction, yielding a lower bound of $\mathcal{C}\left( {{\mathbf{BD}}{{\mathbf{C}}_d}} \right) > 0.1221 \cdot \left( {1 - d} \right)$.