Capacity of the Binary Deletion Channel

A survey of results for deletion channels and related synchronization channels

Michael Mitzenmacher (2009)

Probability Surveys

📍 Section 7 (“Upper bounds on the capacity of deletion channels”), Open Questions (third bullet: “Tighten the gaps for the asymptotic behavior for the deletion channel as $p$ goes to 0 and $p$ goes to 1”), p. 22.

Optimal coding for the binary deletion channel with small deletion probability

Yashodhan Kanoria, Andrea Montanari (2013)

IEEE Transactions on Information Theory

📍 Section I (Introduction), Theorem 1 (capacity asymptotics as d → 0 and d → 1), p. 6192.

Capacity upper bounds for the deletion channel

Mahdi Cheraghchi (2020)

IEEE Transactions on Information Theory

📍 Section II (Main results), Theorem 1 (improved numerical upper bounds on C(d) for all d ∈ (0,1)), pp. 2–4.