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

1. Problem Statement

The paper addresses the long-standing open problem of determining the capacity of the Binary Deletion Channel (BDC).

• The BDC Model: A channel where an input bitstring $x \in \{0, 1\}^n$ is transmitted, and each bit is independently deleted with probability $d$. The output is the remaining subsequence.
• The Challenge: Unlike the Binary Erasure Channel (where deleted bits are marked with a "?"), the BDC causes a loss of synchronization. The receiver does not know which input bit corresponds to a specific output bit. This makes the calculation of mutual information and channel capacity analytically intractable.
• Current State: While lower bounds exist, the best known upper bounds rely on numerically approximating the capacity of "finite-length" versions of the channel ($C_n(d)$) and using the inequality $C(d) \leq \frac{1}{n}C_n(d)$.
• The Bottleneck: Calculating $C_n(d)$ requires the Blahut-Arimoto Algorithm (BAA). However, the BAA's time and space complexity scale exponentially with the input length $n$ (specifically $O(2^n)$ for input alphabet size). Previous state-of-the-art implementations (Rubinstein and Con, 2023) were limited to $n \approx 28$ due to memory and computational constraints, preventing tighter bounds for larger $n$.

2. Methodology

The authors propose a highly optimized implementation of the BAA tailored for the deletion channel, leveraging GPU parallelization and dynamic programming to overcome previous scalability barriers.

A. Algorithmic Optimizations

The core of their approach involves optimizing the iterative steps of the BAA, specifically the computation of the auxiliary function $W^{(t)}(x)$ and the channel output distribution $Y^{(t)}(y)$.

1. GPU Parallelization (CUDA):

   • The authors map the BAA iterations to CUDA kernels.
   • Parallelization Strategy: Instead of processing one input string $x$ at a time, they assign each distinct input $x$ to a separate GPU block. Within each block, up to 1024 threads work in parallel.
   • Task Decomposition: For a given $x$, the calculation of $\log W^{(t)}(x)$ involves a sum over all possible output subsequences $y$. The threads partition the set of subsequences $S_{x,k}$ and compute partial sums in parallel, which are then reduced to a final value.

2. Efficient Subsequence Enumeration (Unranking):

   • A naive approach would require storing all subsequences or iterating through them inefficiently. The authors implement a dynamic programming-based unranking algorithm (Algorithm 4).
   • Pre-computed Tables: They use two tables, NextPos (finding the next occurrence of 0 or 1) and Count (counting valid subsequences of a given length starting from a specific index).
   • Complexity: This allows a thread to generate the $j$-th lexicographical subsequence of length $k$ in $O(k)$ time without storing the entire list of subsequences, drastically reducing memory usage.

3. Efficient Supersequence Enumeration:

   • Similarly, for computing output probabilities $Y^{(t)}(y)$, the algorithm must enumerate length-$n$ supersequences of an output $y$.
   • They use a recursive method (Algorithm 6) that maps an index to a specific supersequence by first selecting a subset of "unmatched" bit positions and then filling the rest. This is also $O(n)$ per thread.

4. Hybrid Approach with Rubinstein-Con:

   • The authors retain the "loop-nest" optimization and cache-based transition probability computation from Rubinstein and Con (2023). They pre-compute transition probabilities for smaller sub-channels ($n' \approx n/2$) to avoid recalculating them from scratch, combining this with their new parallel enumeration techniques.

3. Key Contributions

• GPU-Accelerated BAA: The first implementation of the Blahut-Arimoto algorithm for the BDC that fully leverages GPU parallelism to handle the massive state space.
• Extended Input Lengths: The method successfully computes capacity approximations for input lengths up to $n = 31$ (specifically $C_{31,k}$ for $k \leq 18$), surpassing the previous limit of $n=28$.
• New Upper Bounds: By computing $C_{n,k}$ for larger $n$, the authors derive significantly tighter upper bounds on the asymptotic capacity $C(d)$.
• Asymptotic Improvement: They establish a new linear bound for the high-noise regime ($d \to 1$).

4. Results

The authors report improved upper bounds for the capacity $C(d)$ across the range of deletion probabilities.

• High-Noise Regime ($d \geq 0.64$):
  • By combining their improved bound at $d=0.64$ with a result from Rahmati and Duman (2015), they prove:
    $$C(d) \leq 0.3578(1 - d) \quad \text{for all } d \geq 0.64$$
  • Comparison: This improves upon the previous best bound of $0.3745(1-d)$ (valid for $d \geq 0.68$) established by Rubinstein and Con.
• Specific Bounds:
  • They computed upper bounds for $C_{29,k}$ for all $1 \leq k \leq 28$ and $C_{31,k}$ for $1 \leq k \leq 18$.
  • For $n=29$, computations took up to 5 days on an RTX 5070 Ti GPU, with iterations taking ~400 seconds for $k \approx n/2$.
  • For $n=31$, the complexity increased significantly, requiring higher tolerance thresholds for $k \geq 14$ due to iteration times exceeding 800 seconds.

5. Significance

• Tightening the Gap: The binary deletion channel capacity is one of the most famous open problems in information theory. This work narrows the gap between the known lower and upper bounds, particularly in the high-deletion probability regime where the channel is most difficult to utilize.
• Methodological Advancement: The paper demonstrates that specialized GPU parallelization combined with combinatorial enumeration techniques (unranking) can overcome the exponential memory barriers that have limited information-theoretic research for decades.
• Practical Implications: As DNA-based data storage becomes a reality, understanding the limits of synchronization channels (like the BDC) is critical for designing efficient coding schemes. The improved bounds provide a more accurate target for code designers.
• Reproducibility: The authors have made their implementation publicly available on GitHub, facilitating further research and verification.

In summary, Pinto and Ribeiro successfully pushed the boundaries of numerical capacity estimation for the deletion channel by transforming a memory-bound sequential problem into a parallelizable GPU task, yielding the tightest known upper bounds for the BDC capacity to date.