New Capacity Upper Bounds For Binary Deletion Channel

This paper considers a binary channel with deletions.

We derive two closed-form upper bounds on the capacity of the binary deletion channel (BDC).

The first bound is obtained by computing the capacity of an auxiliary channel, the two-bit Fixed-length-Input BDC (FI-BDC), and showing that this auxiliary capacity upper-bounds the capacity of the BDC.

The second bound is obtained by approximating the mutual information between sent and received bits directly, yielding a closed-form expression parameterized by a first-order Markov correlation parameter $\gamma$.

Both bounds use a first-order Markov process for the channel input.

We verify Theorem~1's optimization from first principles, directly from the two-bit auxiliary channel's transition matrix rather than from the mutual-information expression alone: the underlying objective is strictly concave with a unique interior maximizer, and the resulting closed-form bound is confirmed correct.

The second proposed upper bound is evaluated against the Fertonani--Duman and Dalai bounds in Fig.~4.