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

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\ge 0.64$.

27 pages. Shortened version to appear at ISIT 2026