pith. sign in

arxiv: 2604.05867 · v1 · submitted 2026-04-07 · 💻 cs.IT · math.IT

Improved Capacity Upper Bounds for the Deletion Channel using a Parallelized Blahut-Arimoto Algorithm

Martim Pinto , Jo\~ao Ribeiro This is my paper

Pith reviewed 2026-05-10 18:26 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords binary deletion channelchannel capacityBlahut-Arimoto algorithmupper boundsGPU parallelizationdeletion probabilityinformation theory
0
0 comments X

The pith

The capacity of the binary deletion channel is at most 0.3578 times (1 minus the deletion probability) for deletion probabilities of 0.64 or higher.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The binary deletion channel is a model for communication links that randomly drop symbols, such as in some DNA storage systems or networks with packet loss. Exact capacity calculations for this channel remain difficult, so work focuses on tightening upper and lower bounds. The paper introduces a GPU-parallelized version of the Blahut-Arimoto algorithm to compute sharper upper bounds. These computations establish that the capacity cannot exceed 0.3578(1-d) when the deletion probability d is 0.64 or greater. A sympathetic reader cares because such bounds directly constrain the best possible rates for reliable transmission and help evaluate how close practical codes come to the theoretical limit.

Core claim

By implementing the Blahut-Arimoto algorithm in a parallelized form on GPUs, the authors obtain improved upper bounds on the capacity of the binary deletion channel. Their results show that this capacity is at most 0.3578(1-d) for every deletion probability d at least 0.64.

What carries the argument

The parallelized Blahut-Arimoto algorithm, which iteratively refines input distributions to maximize mutual information and thereby produce capacity upper bounds for the deletion channel.

If this is right

  • For deletion probabilities of 0.64 and above, the maximum reliable rate is limited to at most 35.78 percent of the non-deleted symbols.
  • Any coding scheme for the deletion channel in this regime must respect this tighter linear scaling with (1-d).
  • The bound supplies a concrete benchmark against which existing deletion-correcting codes can be measured for optimality.
  • The same algorithmic approach can be reused to refine capacity estimates at other deletion probabilities or for related loss models.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The GPU parallelization method could be adapted to compute bounds for insertion-deletion channels or other channels with synchronization errors where standard methods scale poorly.
  • If the linear form of the bound persists, it may suggest structural similarities between the deletion channel and certain erasure models that future proofs could exploit.
  • Improved numerical bounds like this one narrow the gap between theory and practice, potentially guiding the choice of block lengths or redundancy levels in real deletion-channel applications.

Load-bearing premise

The parallelized Blahut-Arimoto implementation reaches a numerically valid upper bound on capacity without convergence failures or precision artifacts specific to the deletion channel.

What would settle it

A lower bound or explicit code construction whose achievable rate exceeds 0.3578(1-d) for any single deletion probability d of 0.64 or higher would falsify the claimed upper bound.

read the original abstract

We present an optimized implementation of the Blahut-Arimoto algorithm via GPU parallelization, which we use to obtain improved upper bounds on the capacity of the binary deletion channel. In particular, our results imply that the capacity of the binary deletion channel with deletion probability $d$ is at most $0.3578(1-d)$ for all $d\geq 0.64$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The manuscript presents a GPU-parallelized implementation of the Blahut-Arimoto algorithm and applies it to compute improved numerical upper bounds on the capacity of the binary deletion channel, yielding the specific claim that C(d) ≤ 0.3578(1-d) for all d ≥ 0.64.

Significance. If the numerical results can be shown to rigorously upper-bound the asymptotic capacity, the work would tighten existing upper bounds on deletion-channel capacity and help close the gap with known lower bounds, which remains a central open question in information theory for channels with synchronization errors.

major comments (1)
  1. [Numerical results and algorithm description] The sections describing the parallelized BA implementation and the numerical results (including any tables or figures reporting the value 0.3578): no convergence criteria, a posteriori error bounds, floating-point error analysis, or independent verification against analytical upper bounds are provided. Deletion channels induce variable-length outputs, so the effective DMC has an exponentially growing output alphabet; without explicit control on truncation, early stopping, or parallel reduction errors, it is unclear whether the computed mutual information is guaranteed to be a valid upper bound rather than an optimistic underestimate. This is load-bearing for the headline claim.
minor comments (1)
  1. [Abstract] The abstract states the new bound but does not reference the best prior analytical or numerical upper bounds, making it harder to gauge the magnitude of the improvement.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript and for identifying the need for greater transparency in the numerical aspects of our work. The concern about ensuring the computed values constitute rigorous upper bounds is well-taken, and we address it directly below while committing to revisions that strengthen the presentation.

read point-by-point responses

  1. Referee: [Numerical results and algorithm description] The sections describing the parallelized BA implementation and the numerical results (including any tables or figures reporting the value 0.3578): no convergence criteria, a posteriori error bounds, floating-point error analysis, or independent verification against analytical upper bounds are provided. Deletion channels induce variable-length outputs, so the effective DMC has an exponentially growing output alphabet; without explicit control on truncation, early stopping, or parallel reduction errors, it is unclear whether the computed mutual information is guaranteed to be a valid upper bound rather than an optimistic underestimate. This is load-bearing for the headline claim.

    Authors: We agree that the manuscript would be improved by explicit documentation of these elements. The parallelized Blahut-Arimoto procedure is applied to a finite-state approximation of the deletion channel in which the output alphabet is truncated by discarding sequences whose probability falls below a threshold chosen to ensure the approximation error is controlled; the resulting mutual information is then used to upper-bound the true capacity. In the revised version we will add a new subsection titled 'Implementation Details, Convergence, and Error Analysis' that specifies: the exact truncation rule and its effect on the mutual information (with a proof sketch that the truncated channel yields a valid upper bound), the convergence criterion (relative change in the Blahut-Arimoto objective below 10^{-8} sustained for 50 iterations), floating-point safeguards (double-precision arithmetic with cross-checks on a CPU reference implementation for small instances), and a posteriori bounds obtained from the duality gap. We will also include a table comparing our numerical values against all previously published analytical upper bounds for deletion probabilities where such bounds exist. These additions will make the headline claim fully supported by the reported computations. revision: yes

Circularity Check

0 steps flagged

No significant circularity: numerical upper bounds computed directly via parallelized Blahut-Arimoto

full rationale

The paper's central result is obtained by executing a GPU-parallelized Blahut-Arimoto algorithm on a model of the deletion channel to produce numerical upper bounds on mutual information, from which the inequality C(d) ≤ 0.3578(1-d) for d ≥ 0.64 is inferred. This is a direct computational output rather than an analytical derivation. No step matches the enumerated circularity patterns: there is no self-definitional relation (e.g., a quantity defined using the bound it supports), no fitted parameter renamed as a prediction, and no load-bearing self-citation whose justification reduces to the present work. The method relies on the established properties of the BA algorithm applied at larger scale; the specific constant 0.3578 emerges from the run, not by construction from the claimed bound itself. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

The central claim rests on the numerical output of the parallelized Blahut-Arimoto algorithm applied to the deletion channel; the constant 0.3578 is the sole computed quantity.

free parameters (1)
  • 0.3578 = 0.3578
    Numerical coefficient obtained from running the algorithm to produce the stated upper bound.
axioms (1)
  • domain assumption The Blahut-Arimoto algorithm produces valid upper bounds on the capacity of the binary deletion channel when properly implemented.
    Standard assumption in information theory for using the algorithm on discrete channels.

pith-pipeline@v0.9.0 · 5352 in / 1157 out tokens · 54247 ms · 2026-05-10T18:26:19.607058+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

3 extracted references · 3 canonical work pages

  1. [1]

    GPU code for computing capacity upper bounds for the binary deletion channel.https://doi.org/10.5281/zenodo.19453272,

    [Pin26] Martim Pinto. GPU code for computing capacity upper bounds for the binary deletion channel.https://doi.org/10.5281/zenodo.19453272,

    work page doi:10.5281/zenodo.19453272

  2. [2]

    23 Table 1: Upper bounds onC29,k. k Upper bound onC29,k 1 1.0000 2 1.1898 3 1.5165 4 1.8137 5 2.0916 6 2.3761 7 2.6647 8 2.9598 9 3.2663 10 3.5867 11 3.9247 12 4.2841 13 4.6727 14 5.0930 15 5.5573 16 6.0713 17 6.6464 18 7.2964 19 8.0364 20 8.8850 21 9.8659 22 11.0096 23 12.3545 24 13.9487 25 15.8526 26 18.1454 27 20.9387 28 24.4132 29 29.0000 Table 2: Upp...

    work page 2005

  3. [3]

    0.2015 0.55 0.1652 (n=

    work page 2015