New Capacity Upper Bounds For Binary Deletion Channel

技术摘要：二进制删除信道的新容量上界

问题定义
本文研究了二进制删除信道（Binary Deletion Channel, BDC），这是一种通信模型，其中输入比特以概率 $d$ 被独立删除，接收方在不知道删除位置的情况下观察剩余的子序列。虽然该信道的容量 $C(d)$ 是有定义的，但不存在闭式表达式。现有文献依赖于上界和下界，显著的现有界限包括当 $d < 0.5$ 时的 $1-h(d)$ 以及当 $d \ge 0.65$ 时的 $0.4143(1-d)$。计算精确容量的主要挑战在于将输入序列映射到输出子序列时的组合歧义性。

方法论
作者提出了两个新的关于 $C(d)$ 的闭式形式上界，两者都利用了作为信道输入的的一阶马尔可夫过程。该方法论基于两个核心直觉：（1）近似 BDC 的辅助信道可以产生有用的界限；（2）输入相关性有助于解码器估计被删除的比特。

1. 辅助信道法（定理 1）：
   作者引入了定长输入 BDC（FI-BDC），其中输入长度固定为 $n$，但输出长度可变。他们专门针对一个两比特 FI-BDC（$n=2$ 的 FI-BDC）进行研究。

   • 他们构建了这个两比特信道的转移矩阵（表 II）。
   • 他们在由 $\gamma$ 参数化（或等效地由重复符号概率 $p_0$ 参数化）的对称一阶马尔可夫输入分布下，推导了该辅助信道的互信息 $I(X; Y)$。
   • 通过求解优化问题，找到了唯一的闭式形式最大值点 $p_0^*(d)$。
   • 最终界限通过利用独立两比特子块间互信息的超加性，将两比特容量按 $1/2$ 进行缩放来推导。

2. 直接互信息近似（定理 2）：
   第二个界限是通过直接近似发送比特与接收比特之间的互信息而得出的。

   • 该方法利用一个辅助侧信息变量来标记最后一个未删除的前驱位置。
   • 所得表达式由马尔可夫相关参数 $\gamma$ 参数化。
   • 与定理 1 不同，该界限并非通过对 $\gamma$ 求最大值得到的；相反，$\gamma$ 被视为一个设计参数或源确定的值。

主要贡献与结果

• 定理 1（闭式界限 1）：
  论文推导出了一个闭式形式上界：
  $$C \le \frac{1}{2}(1 - d)^2 \log_2 \left(1 + 2^{-\frac{2d}{1-d}}\right) + \frac{1 - d^2}{2}$$

  • 优化验证： 作者严格验证了该两比特辅助信道目标函数的严格凹性及其唯一的内部最大值点。他们使用计算机代数系统和数值检查确认了最优输入分布 $p_0^*(d)$ 的闭式解。
  • 单调性： 证明了最优相关参数 $\gamma^*(d)$ 随 $d$ 严格递增，从 $d \to 0$ 时的 $0.5$（独立比特）移动到$d \to 1$时的$1$（完全相关）。这反映了如下直觉：较高的删除概率需要输入中更强的时域相关性以辅助解码。
  • 复杂度： 计算该界限仅需 $O(1)$ 次算术运算，这与以往的界限（例如 Fertonani–Duman）相比，后者需要对指数级大的状态空间进行迭代优化。

• 定理 2（闭式界限 2）：
  论文提出了第二个界限：
  $$C_{BDC} \le (1 - d) \left(1 - H\left(\frac{d(1 - \gamma)}{1 + d(1 - 2\gamma)}\right)\right)$$

  • $\gamma$ 的性质： 作者澄清该界限关于 $\gamma$ 是单调的，不存在内部最大值。因此，$\gamma$ 不是一个优化的变量，而是一个由信源决定或为设计目的而选择的参数。
  • 端点行为： 该界限在 $d=0$（且 $\gamma=0.5$）时正确地降至 $C \le 1$，在 $d=1$（且 $\gamma=1$）时降至 $C=0$。论文建议使用线性插值 $\gamma = 0.5 + d/2$ 来连接这两个端点，并指出这是设计选择而非解析最优。

• 与前人工作的比较：
  论文指出，定理 1 的界限至少与通过定长输入定长输出（FIFO-BDC）辅助信道推导出的界限（引理 1）一样紧致。在原文的图 4 中，第二个界限针对 Fertonani–Duman 和 Dalai 界限进行了评估（尽管此处未重现该图）。

意义与声明
该论文的主要意义在于提供了两个新的闭式形式上界，这些界限具有计算高效性（$O(1)$）且经过解析验证。

• 理论严谨性： 作者强调了对定理 1 优化过程的严格验证，纠正了中间草稿中的一个微小代数错误，并确认了目标函数的严格凹性。
• 参数澄清： 本文的一个关键贡献是澄清了定理 2 中参数 $\gamma$ 的含义。作者明确指出 $\gamma$ 不应被视为近似的最优值，而应被视为一个由信源决定的参数，从而纠正了对公式行为的潜在误解。
• 范围限制： 论文对其研究范围进行了谦逊的定义。它并不声称解决了通用的 BDC 容量问题，也不声称找到了适用于所有容许过程（例如高阶马尔可夫或行程长度编码信源）的最优输入记忆。其结果严格限于用于推导的特定一阶对称马尔可夫族。
• 排除项： 作者明确指出，为了保持解析精度，他们有意排除了某些“统一性”主张、文中未推导的渐近形式以及更广泛的收敛定理。

综上所述，本文通过辅助信道分析和直接互信息近似，提供了计算易行的闭式形式上界，并对涉及的优化步骤进行了数学验证，从而推动了 BDC 研究领域的进展。