2021/02/07 by Hassan Tavakoli, Tavakoli, Hassan
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced biosensing and bioanalysis techniques #DNA and Biological Computing #Error Correcting Code Techniques #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.2103.11904
openalex publication_date 2021/02/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 γ. 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.