Papers › A Note on the Deletion Channel Capacity
A Note on the Deletion Channel Capacity
Mojtaba Rahmati, Tolga M. Duman
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
Memoryless channels with deletion errors as defined by a stochastic channel matrix allowing for bit drop outs are considered in which transmitted bits are either independently deleted with probability d or unchanged with probability 1-d. Such channels are information stable, hence their Shannon capacity exists. However, computation of the channel capacity is formidable, and only some upper and lower bounds on the capacity exist. In this paper, we first show a simple result that the parallel concatenation of two different independent deletion channels with deletion probabilities d₁ and d₂, in which every input bit is either transmitted over the first channel with probability of λ or over the second one with probability of 1-λ, is nothing but another deletion channel with deletion probability of d=λd₁+(1-λ)d₂. We then provide an upper bound on the concatenated deletion channel capacity C(d) in terms of the weighted average of C(d₁), C(d₂) and the parameters of the three channels. An interesting consequence of this bound is that C(λd₁+(1-λ))≤λC(d₁) which enables us to provide an improved upper bound on the capacity of the i.i.d. deletion channels, i.e., C(d)≤0.4143(1-d) for d≥0.65. This generalizes the asymptotic result by Dalai as it remains valid for all d≥0.65. Using the same approach we are also able to improve upon existing upper bounds on the capacity of the deletion/substitution channel.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections