On the exact decoding error probability exponent of the random coding on BSC

技术摘要：关于二进制对称信道随机编码精确解码错误概率指数的研究

问题陈述
本文解决了确定二进制对称信道（BSC）上随机编码解码错误概率精确渐近行为的基本问题，该信道的交叉概率为 $p$（$0 \le p \le 1/2$）。具体而言，文章研究了随机编码指数 $E_r(R)$，其定义为当码长 $n \to \infty$ 时，速率为 $R$、长度为 $n$ 的码的期望解码错误概率的指数衰减率。虽然该指数在高于临界速率 $R_{cr}(p)$ 的速率下已被充分理解，但在低速率（$R < R_{cr}(p)$）下的行为在历史上仅由下界描述，使得精确的渐近形式成为一个未决问题。

方法论
作者对最大似然解码场景中的后验概率进行了概率分析。核心方法论包括：

1. 后验概率公式化：决策规则以概率 $\pi_i$ 的后验概率形式表述。如果传输码字的后验概率 $\pi_m$ 低于 $1/2$，则发生错误，这等价于所有其他码字的加权距离之和超过传输码字的加权距离的条件。
2. 随机和分析：证明依赖于随机和 $S(z, M, n) = \sum_{j=1}^M z^{d(y, x_j)}$ 的分布，其中 $z = p/q$，$d$ 为汉明距离。作者利用了一个先前建立的结果（参考文献 [7] 中的定理 2），即该和以高概率集中在其均值 $M z^{n/2}$ 附近。
3. 渐近最大化：错误概率表示为传输码字距离的期望。指数是通过对可能的归一化距离 $b$ 最大化特定函数 $f_2(p, R, b)$ 推导出来的。该最大化过程根据速率 $R$、临界速率 $R_{cr}(p)$ 和新定义的速率 $R_{crit}(p)$ 之间的关系分为不同情况。

主要贡献与结果
主要贡献是推导出了所有速率 $0 \le R \le C(p)$ 下随机编码指数 $E_r(R)$ 的精确公式，解决了此前在低速率下存在的歧义。

文章引入了一个新的临界速率 $R_{crit}(p)$，定义为：
$$R_{crit}(p) = (\sqrt{q} - \sqrt{p})^2 \frac{\ln(q/p)}{2(\sqrt{q} + \sqrt{p})}$$
其中 $q = 1-p$。结果表明，当 $0 < p < 1/2$ 时，$R_{crit}(p) < R_{cr}(p)$。

精确指数 $E_r(R)$ 由分段函数 $g(p, R)$ 给出：

1. 低速率区域（$0 \le R \le R_{crit}(p)$）：
   $$E_r(R) = 2R - \ln 2 + 2h(r_0) + \ln(\sqrt{pq})$$
   其中 $r_0 = \frac{1}{2} + \frac{R}{\ln(p/q)}$，$h(x)$ 为二元熵函数。
2. 中速率区域（$R_{crit}(p) \le R \le R_{cr}(p)$）：
   $$E_r(R) = \ln 2 - 2\ln(\sqrt{q} + \sqrt{p}) - R$$
3. 高速率区域（$R_{cr}(p) \le R \le C(p)$）：
   $$E_r(R) = E_{sp}(R)$$
   其中 $E_{sp}(R)$ 是标准的球包指数。

意义与主张
本文将自己定位为对先前工作（特别是参考文献 [5]）的补充，该工作探讨了 $E_r(R)$ 在低速率下的弱点是否是边界技术的产物。通过提供精确的渐近形式，作者证明了先前已知的下界在低速率区域的随机编码指数中确实是松散的。

作者强调了两个具体的重要点：

1. 精确性与边界：虽然 $R \ge R_{crit}(p)$ 的关系已知为下界，但本文确立了整个速率范围的精确等式。
2. 非参数形式：引用 R. Gallager 的观察，即 BSC 的 $E_r(R)$ 此前仅能以参数形式表达，作者指出推导出的公式 (8)–(10) 提供了指数的直接非参数表达式，前提是接受自然表示 $R = \ln 2 - h(\delta_R)$。

文章得出结论，推导出的公式 $g(p, R)$ 代表了 BSC 随机编码指数的精确渐近形式，填补了低速率下信道编码极限理论理解的空白。