🔢 mathematics

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

该论文通过 GPU 并行化优化了 Blahut-Arimoto 算法，从而为删除概率 $d \geq 0.64$ 的二进制删除信道得出了容量上界不超过 $0.3578(1-d)$ 的新结果。

原作者： Martim Pinto, João Ribeiro

发布于 2026-04-08

📖 1 分钟阅读🧠 深度阅读

原作者： Martim Pinto, João Ribeiro

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文讲述了一个关于**“如何在混乱中找回信息”**的数学难题，以及作者们如何利用超级计算机（GPU）来打破这个难题的旧纪录。

为了让你轻松理解，我们可以把这篇论文的故事想象成一场**“在暴风雨中修补破碎的拼图”**的游戏。

1. 核心难题：被风吹散的拼图（删除信道）

想象你有一串由 0 和 1 组成的密码（比如 10110），你想把它发给朋友。
但是，传输过程中发生了一场“数字风暴”（这就是删除信道）。风暴会随机吹走一些比特（0 或 1），而且不会留下任何标记告诉你少了哪个。

原来的信号：1 0 1 1 0
风暴吹走后：1 _ 1 _ 0 （中间两个被吹走了，但你不知道是第几个被吹走的，只知道剩下的顺序没变）。
接收到的信号：1 1 0

问题在于：朋友收到 1 1 0 后，他完全不知道原始信号是 10110 还是 11100 还是别的什么。这种“同步丢失”让恢复信息变得极其困难。

科学家想知道：在这种混乱的风暴下，我们理论上最多能传输多少信息？这个极限值被称为**“信道容量”**。

2. 过去的困境：算得太慢（Blahut-Arimoto 算法）

为了找到这个极限，数学家发明了一个叫 Blahut-Arimoto (BAA) 的算法。你可以把它想象成一个**“超级拼图计算器”**。

它的工作方式是：尝试无数种可能的原始密码组合，计算哪种组合在风暴后最容易被识别，从而算出最大传输率。
痛点：随着密码变长（比如从 10 位变成 30 位），可能的组合数量会像指数爆炸一样（2 的 30 次方是个天文数字）。
以前的超级计算机就像一只勤劳的蚂蚁，它必须一只一只地数完所有蚂蚁才能算出结果。因为太慢，之前的记录只能算到密码长度为 28 位左右，再长就“算不动”了。

3. 作者的突破：组建“蚂蚁军团”（GPU 并行化）

这篇论文的作者（Martim Pinto 和 João Ribeiro）想：“既然一只蚂蚁太慢，那我们就派成千上万只蚂蚁同时工作！”

他们利用了一种叫 GPU（图形处理器） 的硬件。

CPU（普通电脑芯片） 像是一个聪明的教授，擅长处理复杂的逻辑，但一次只能做一件事。
GPU（显卡芯片） 像是一个拥有几千个工人的建筑工地，虽然每个工人没那么聪明，但它们可以同时搬运成千上万块砖头。

他们的创新点：

并行计算：他们把那个“超级拼图计算器”拆解了。以前是“蚂蚁”一只只算，现在他们让 GPU 上的几千个“线程”（工人）同时去计算不同的拼图可能性。
聪明的枚举（不瞎找）：
- 找子序列（Subsequences）：想象你要从一本厚书里找出所有可能的“短句子”。以前是翻遍全书，现在他们发明了一种**“目录索引法”**（动态规划），直接跳过不需要的部分，只计算可能存在的组合。
- 找超序列（Supersequences）：反过来，如果你手里有 110，要猜它可能来自哪些长句子？他们同样用了一种**“逆向地图”**，高效地生成所有可能的原稿。

4. 成果：打破了旧纪录

通过这种“蚂蚁军团”战术，他们做到了以前做不到的事：

以前：只能算到密码长度 28 位。
现在：成功算到了 31 位（甚至部分算到了 31 位的所有情况）。

这有什么意义？
这就好比以前我们只能预测“短途旅行”的天气，现在能预测“长途旅行”的天气了。

他们发现，当风暴非常猛烈（删除概率很高，比如 64% 的比特被吹走）时，信息传输的极限比之前认为的要更低一点。
具体来说，他们给出了一个新的公式：如果删除概率是 $d$ $d$ ，那么传输率上限大约是 0.3578 × (1 - d)。
- 之前的公式是 0.3745，现在修正为 0.3578。这意味着在极端恶劣的环境下，我们传输信息的能力比想象中还要弱一点点，但这让我们对极限有了更精准的把握。

5. 总结：用“人海战术”攻克数学堡垒

简单来说，这篇论文并没有发明新的数学理论，而是把旧理论用在了新工具上。

比喻：就像以前我们要数清一个巨大图书馆里所有的书，只能一个人一本本地数（旧算法），需要几百年。作者们把图书馆的每本书分给几千个机器人（GPU 并行），并且给机器人配了智能目录（优化算法），结果几天就数完了。
结果：他们把人类对“删除信道”容量的认知边界，从 28 位推到了 31 位，并给出了更精确的“安全传输线”。

这对于未来的DNA 数据存储（因为 DNA 复制过程中经常发生“删除”错误）和深空通信（信号传输中容易丢包）具有重要的指导意义。它告诉我们，在极端混乱的通信环境中，我们到底能走多远。

论文技术总结：基于并行化 Blahut-Arimoto 算法的删除信道容量上界改进

1. 研究背景与问题定义

二进制删除信道 (Binary Deletion Channel, BDC) 是同步错误信道中最简单的模型之一。在该信道中，输入比特串 $x \in \{0, 1\}^n$ 中的每个比特以固定概率 $d$ 被独立删除，输出为输入序列的一个子序列。

尽管 BDC 与二进制擦除信道 (BEC) 结构相似，但 BDC 的容量 $C(d)$ 至今仍未被精确求解。现有的研究主要集中在推导容量的上下界。

核心挑战：BDC 导致发送端和接收端之间的同步丢失（接收端不知道第 $i$ 个输出比特对应输入中的哪个比特），这使得计算互信息变得极其困难。
现有方法：目前获得 BDC 容量上界的主流方法是数值近似“有限长度”版本的 BDC 容量 $C_n(d)$ 。根据不等式 $C(d) \le \frac{1}{n}C_n(d)$ ，通过计算较大 $n$ 值下的 $C_n(d)$ 可以得到更紧的上界。
计算瓶颈：计算 $C_n(d)$ 通常使用 Blahut-Arimoto 算法 (BAA)。然而，BAA 的时间和空间复杂度随输入长度 $n$ 呈指数级增长（输入字母表大小为 $2^n$ ，输出为 $2^{n+1}-1$ ）。之前的最佳工作（Rubinstein 和 Con, 2023）受限于内存和计算时间，仅能将 $n$ 扩展到 28，且在某些参数下无法计算。

2. 方法论与优化策略

本文提出了一种基于 GPU 并行化 的优化 Blahut-Arimoto 算法实现，旨在突破 $n=28$ 的限制，将计算能力扩展至 $n=31$ 。主要技术贡献包括：

2.1 GPU 并行化架构

利用 CUDA 内核将 BAA 迭代中的关键步骤并行化：

并行计算辅助函数 $W^{(t)}(x)$ ：在 BAA 的每次迭代中，需要计算所有输入分布 $x$ 的辅助值。作者将不同的输入 $x$ 分配给不同的 GPU 线程块（Block），并在每个块内将求和项（遍历所有输出 $y$ ）分配给多个线程（Thread）并行计算。
并行计算输出分布 $Y^{(t)}(y)$ ：类似地，将不同的输出 $y$ 分配给不同的块，并行计算其对应的输入超序列（supersequences）。

2.2 高效枚举子序列与超序列

为了在有限的 GPU 显存下高效处理，作者设计了基于动态规划的枚举算法，避免了存储巨大的查找表：

子序列枚举 (Subsequence Enumeration)：
- 问题：给定输入 $x$ 和长度 $k$ ，需要遍历所有 $\binom{n}{k}$ 个子序列以计算转移概率。
- 方法：提出了 stringUnrank 算法。利用预计算的 NextPos（下一个位置）和 Count（计数）表，通过“解排名”（unranking）技术，根据给定的秩 $j$ 直接构造第 $j$ 个字典序子序列。
- 优势：每个 CUDA 线程只需枚举约 $N_{x,k}/1024$ 个子序列，时间复杂度从单线程的 $O(N_{x,k})$ 降低为 $O(N \cdot k)$ ，且仅需 $O(nk)$ 的额外空间。
超序列枚举 (Supersequence Enumeration)：
- 问题：计算输出分布 $Y^{(t)}(y)$ 时，需要遍历所有长度为 $n$ 的超序列。
- 方法：提出了 RecSuperSeq 算法。首先枚举“未匹配比特”的子集（即超序列中不属于原序列 $y$ 的部分），然后基于该子集构造唯一的超序列。
- 优势：同样实现了 $O(n)$ 的构造时间，并完美适配 GPU 的并行架构。

2.3 结合 Rubinstein-Con 的优化

继承了 Rubinstein 和 Con (2023) 的“循环嵌套”优化思想，利用分治策略（将输入字符串分为两半）和预计算的小规模转移概率表，进一步加速转移概率 $P(y|x)$ 的计算，避免了 $O(nk)$ 的重复动态规划计算。

3. 主要成果与结果

3.1 计算规模突破

输入长度扩展：成功计算了 $n \le 29$ 的所有 $C_{n,k}$ 值，以及 $n=31$ 且 $k \le 18$ 的 $C_{31,k}$ 值。
硬件环境：使用 NVIDIA RTX 5070 Ti GPU。对于 $n=29$ ，计算耗时约 5 天；对于 $n=31$ 的部分参数，耗时约一周。
精度控制：大多数计算设置收敛阈值 $a=0.005$ ，确保结果误差在可控范围内。

3.2 容量上界改进

利用计算得到的 $C_{n,k}$ 值，通过凸组合（Lemma 2）推导出了 BDC 容量 $C(d)$ 的新上界：

高噪声区域 ( $d \ge 0.64$ )：结合 Rahmati 和 Duman (2015) 的渐近结果，得出：
$C(d) \le 0.3578(1-d), \quad \forall d \ge 0.64$
对比提升：这一结果显著优于之前的最佳上界（Rubinstein & Con, 2023 给出的 $C(d) \le 0.3745(1-d)$ ，且仅适用于 $d \ge 0.68$ ）。

3.3 数据发布

所有用于计算上界的代码和结果已公开在 GitHub 仓库中，供社区复现和进一步研究。

4. 意义与影响

理论突破：在 BDC 容量这一长期未决的开放问题上取得了实质性进展，特别是在高删除概率（高噪声）区域，提供了目前最紧的线性上界。
算法创新：展示了 GPU 并行计算在解决大规模信息论优化问题中的巨大潜力。通过巧妙的“解排名”算法和动态规划结合，成功克服了 GPU 显存限制，解决了传统 BAA 无法处理的大规模 $n$ 值问题。
工程启示：为 DNA 数据存储等新兴技术中的同步错误信道编码设计提供了更精确的理论边界，有助于评估实际编码方案的效率极限。

总结：本文通过创新的 GPU 并行化策略和高效的枚举算法，将 BDC 容量上界的计算能力从 $n=28$ 提升至 $n=31$ ，并显著改进了高噪声环境下的容量上界估计，是信息论与高性能计算结合的一个典范。