Improved Capacity Upper Bounds for the Deletion Channel using a Parallelized Blahut-Arimoto Algorithm
arXiv:2604.058678.3
Predicted impact top 77% in IT · last 90 daysOriginality Synthesis-oriented
AI Analysis
This work provides incremental improvements to theoretical bounds in information theory, specifically for researchers studying channel capacities.
The authors tackled the problem of determining the capacity of the binary deletion channel by developing an optimized GPU-parallelized Blahut-Arimoto algorithm, resulting in an improved upper bound of 0.3578(1-d) for deletion probabilities d ≥ 0.64.
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$.