AWGN下的密度进化：为什么必须追踪LLR分布

第 7 篇已经把 BEC 的极化过程写成了一个很简洁的标量递归：每个子信道只要带着一个擦除率，就能沿着减号或加号分支继续计算。第 8 篇也因此可以直接把这些标量变成可靠性排序，再选择信息位。

到了 AWGN，这条路突然不再够用。接收端看到的不是“收到”或“擦除”两种状态，而是任意实数；同样的平均可靠性，可能来自“多数观测很可靠、少数观测很差”，也可能来自“所有观测都中等可靠”。这两种情况经过 Polar 的减号运算后，结果并不相同。要保留这种差别，就不能只保存一个数，而要保存 LLR 取各种值的概率密度。

这就是密度进化（density evolution，DE）要解决的问题：从物理信道的 LLR 分布出发，逐层计算每个极化子信道的 LLR 分布，最后再从分布中提取可靠性指标并形成排序。

本文继续使用 0-based 索引。接收观测向量写作 $\underline{y}$ ，原始 LLR 向量写作 $\underline{\lambda}$ ；码字比特 $c_i$ 与 BPSK 符号 $x_i$ 分开记号。若把 DE 的结果用于码构造，码长记为 $N=2^n$ ，信息长度记为 $K$ ，码率为 $R=K/N$ ，信息位集合记为 $\mathcal{A}$ 。

BEC 的一个擦除率为什么不足以描述 AWGN

BEC 的输出只有三种可能：收到 0、收到 1，或者擦除。对称输入下，擦除率 $\epsilon$ 已经决定了“当前比特是否还剩信息”，所以 $Z(W)=\epsilon$ ，减号和加号递推可以写成：

z^-=2z-z^2,\qquad z^+=z^2

这里的 $z$ 是一个标量，递推之后仍然是一个标量。AWGN 的输出却是实数 $y\in\mathbb{R}$ 。即使两个子信道的平均错误率或平均 LLR 相同，它们的尾部概率也可能不同，而减号分支恰恰会放大这些尾部的影响。

可以先看一个不涉及具体 Polar 公式的对比。分布 A 让 LLR 大多数时候集中在 $+2$ 附近，偶尔出现很大的负值；分布 B 则始终在 $+1$ 附近波动。两者的均值可以相同，但分布 A 具备左尾离群样本，分布 B 没有。减号运算会把两个 LLR 的符号和幅度一起组合，子信道可靠性不能仅由 LLR 均值完整刻画。

同均值但尾部不同的两种 LLR 分布：分布 A 与分布 B

图中分布 A 取为 $0.9\mathcal{N}(2,0.35^2)+0.1\mathcal{N}(-8,0.70^2)$ ，分布 B 取为 $\mathcal{N}(1,0.55^2)$ ；两者均值都为 1，但 A 在负 LLR 区域保留了 10% 的左尾离群。

因此，AWGN 构造至少要回答两个问题：

一个连续输出信道的可靠性，应该用什么随机变量表示？
两个独立子信道合并后，这个随机变量的分布如何更新？

第一个问题由 LLR 和 L-density 回答，第二个问题由似然比递推回答。

BI-AWGN、BPSK 与噪声方差约定

定义二元输入 $c_i\in\{0,1\}$ 经过 BPSK 映射：

c_i=0\longmapsto x_i=+1,\qquad c_i=1\longmapsto x_i=-1

AWGN 信道写成：

y_i=x_i+n_i,\qquad n_i\sim\mathcal{N}(0,\sigma^2)

这里的 $\sigma^2$ 是每个实信道使用的噪声方差。它不等同于仿真时记录的 SNR；在后文只用 $\sigma^2$ 描述 DE 的初始分布。若以后用 $E_b/N_0$ 或 $E_s/N_0$ 参数化，只需先把它换算成同一套噪声方差约定。

在这个约定下，BI-AWGN 的条件密度为：

W(y\mid c)=\frac{1}{\sqrt{2\pi\sigma^2}}\exp\left(-\frac{\left(y-(1-2c)\right)^2}{2\sigma^2}\right),\qquad c\in\{0,1\}

从似然比推导原始 LLR

LLR 不是把观测值换一个名字，而是把观测对两个输入假设的支持程度写成对数似然比：

\lambda(y)=\ln\frac{W(y\mid0)}{W(y\mid1)}

代入上面的两个高斯密度，归一化常数相消，指数部分给出：

\begin{aligned} \lambda(y) &=\frac{(y+1)^2-(y-1)^2}{2\sigma^2}\\ &=\frac{2y}{\sigma^2}. \end{aligned}

所以第 $i$ 个物理信道的原始 LLR 是：

\lambda_i=\frac{2y_i}{\sigma^2}

在全零码字参考下， $c_i=0$ 、 $x_i=+1$ ，于是 $y_i=1+n_i$ ，从而：

\lambda_i\mid(c_i=0)\sim\mathcal{N}\left(\frac{2}{\sigma^2},\frac{4}{\sigma^2}\right)

这个结论只描述最底层的物理信道。Polar 变换把多个物理观测组合成合成子信道之后，LLR 一般不再保持简单的高斯形式，尤其是减号分支。

什么是 L-density

固定全零输入作为参考，并假设递归中已经得到的先前比特判决是正确的。对码长 $N$ 的第 $i$ 个合成子信道，记其 LLR 随机变量为 $L_N^{(i)}$ ；L-density 就是它在该参考条件下的概率密度：

a_i^{(N)}(\ell)=f_{L_N^{(i)}\mid\text{all-zero, previous decisions correct}}(\ell),\qquad\int_{-\infty}^{+\infty}a_i^{(N)}(\ell)\,\mathrm{d}\ell=1

这里的 $\ell$ 是 LLR 可能取到的一个数， $a(\ell)\,\mathrm{d}\ell$ 表示 LLR 落在一个很小区间内的概率。于是， $a$ 记录的不只是平均可靠性，还记录了正负符号、集中程度和尾部。

在二元输入对称信道中，L-density 还满足对称性关系：

a(\ell)=e^{\ell}a(-\ell)

这条关系说明，正 LLR 和负 LLR 的概率不是任意独立的；正值越大，越支持全零参考。它也是许多可靠性积分公式成立的原因。

例如，可以用 Bhattacharyya 型量把整条密度压缩成一个数：

Z(a)=\int_{-\infty}^{+\infty}a(\ell)e^{-\ell/2}\,\mathrm{d}\ell

$Z(a)$ 越小通常表示子信道越可靠，但计算 $Z(a)$ 之前不能跳过密度本身；如果一开始只保留均值，就无法再恢复减号运算需要的分布信息。

加号分支为什么变成 LLR 相加

把两个独立观测对应的 LLR 记为 $L_0$ 和 $L_1$ 。加号子信道中，前一个输入比特作为已知边信息提供给译码器，当前比特在两次观测中以同样的方式出现。似然比因此可以直接相乘：

\frac{W^+(y_0,y_1,u_0\mid0)}{W^+(y_0,y_1,u_0\mid1)} =\frac{W(y_0\mid u_0)W(y_1\mid0)}{W(y_0\mid u_0\oplus1)W(y_1\mid1)}

在本文采用的全零参考下，边信息比特 $u_0=0$ ，右边的两个因子分别是 $e^{L_0}$ 和 $e^{L_1}$ 。取对数后得到：

L^+=L_0+L_1

因此，只要知道 $L_0,L_1$ 的密度 $a_0,a_1$ ，加号分支的密度就是普通卷积：

a^+(\ell)=\int_{-\infty}^{+\infty}a_0(t)a_1(\ell-t)\,\mathrm{d}t

当两个输入密度相同且都是底层 AWGN 密度时，这个卷积仍然是高斯分布。例如 $\sigma^2=1$ 时， $L_0,L_1\sim\mathcal{N}(2,4)$ ，所以 $L^+\sim\mathcal{N}(4,8)$ 。

减号分支为什么出现双曲正切

减号子信道没有把另一个比特作为已知边信息交给译码器。当前比特对应的是两个输入比特的异或，译码器只能把两个观测对这件事的证据合并。设 $L_0,L_1$ 仍是两个物理子信道的 LLR，则似然比的代数整理给出：

L^-=2\operatorname{atanh}\left(\tanh\frac{L_0}{2}\tanh\frac{L_1}{2}\right)

这就是常说的 box-plus 更新。它和加法有本质差别：

当任一输入 LLR 接近 0 时，乘积接近 0，输出也接近 0；
当两个输入同号时，输出保持这个符号；
当两个输入异号时，较弱的一方会把输出拉向相反方向；
即使两个输入都很大，减号结果的幅度也不会像加号那样简单相加。

如果 $f(\ell_0,\ell_1)$ 表示上面的 box-plus 函数，减号密度只能通过变量变换来写：

a^-(\ell)=\int_{-\infty}^{+\infty}\int_{-\infty}^{+\infty}a_0(\ell_0)a_1(\ell_1)\,\delta\left(\ell-f(\ell_0,\ell_1)\right)\,\mathrm{d}\ell_0\,\mathrm{d}\ell_1

这里的 Dirac $\delta$ 不是为了制造新的近似，而是准确表达“把二维随机变量经过 $f$ 映射到一维后，如何得到输出密度”。困难也正由此产生：加号是卷积，减号是非线性二维映射，二者都不再能由一个简单标量递推完全替代。

密度进化如何逐层传播

有了两条分支的分布运算，Polar 递归就可以从“递推一个数字”改写为“递推一组密度”。底层先放入物理信道密度 $a_0$ ；每向下一层，就把当前节点的密度成对取出，分别计算 $a^-$ 和 $a^+$ ，再按照路径顺序交给下一层。

以 $N=2^n$ 为例，最终得到 $a_0^{(N)},a_1^{(N)},\ldots,a_{N-1}^{(N)}$ 。这里上标表示码长和子信道索引，不表示对密度做普通幂运算。对每个密度再计算 $Z(a_i)$ 、平均 LLR 或互信息估计，最后按明确的排序规则形成可靠性序列 $\boldsymbol{\pi}$ 。

用流程表示，信息在每一层的走向是：

\text{物理信道密度}\longrightarrow\{a^-,a^+\}\longrightarrow\text{下一层密度}\longrightarrow\cdots\longrightarrow\{a_i^{(N)}\}_{i=0}^{N-1}\longrightarrow\boldsymbol{\pi}

这个流程中没有“先猜一个可靠性再套递推”的空缺步骤：可靠性排序是分布传播完成之后的结果。

N=2 的 AWGN 分布递推小例子

取码长 $N=2$ ，并固定 $\sigma^2=1$ 。全零参考下，两个物理信道的 LLR 都服从：

a_0(\ell)=a_1(\ell)=\frac{1}{\sqrt{8\pi}}\exp\left(-\frac{(\ell-2)^2}{8}\right)

加号子信道

由于 $L^+=L_0+L_1$ ，卷积可以直接算出：

a^+(\ell)=\frac{1}{\sqrt{16\pi}}\exp\left(-\frac{(\ell-4)^2}{16}\right),\qquad L^+\sim\mathcal{N}(4,8)

它的均值从 $2$ 增加到 $4$ ，方差从 $4$ 增加到 $8$ 。这只是加号分支的结果，不能把同样的高斯形式直接套到减号分支。

减号子信道

减号分支是：

L^-=2\operatorname{atanh}\left(\tanh\frac{L_0}{2}\tanh\frac{L_1}{2}\right)

为了看清这个映射的形状，可以代入几组确定的输入值。下表中的输出只是 box-plus 对样本对的变换，不是完整的概率分布；完整密度仍需对所有可能的 $(L_0,L_1)$ 按其联合密度积分。

$L_0$	$L_1$	$L^-$ （约）	说明
2	2	1.325	两个正证据合并，但减号结果小于加法结果 4
2	0	0	一个输入没有提供方向信息，异或证据也消失
2	-2	-1.325	符号相反，输出符号由乘积决定，幅度被 box-plus 压缩
5	5	4.307	输入很强时仍然是非线性压缩，而不是简单相加

对应的精确密度是：

a^-(\ell)=\iint a_0(\ell_0)a_1(\ell_1)\,\delta\left(\ell-2\operatorname{atanh}\left(\tanh\frac{\ell_0}{2}\tanh\frac{\ell_1}{2}\right)\right)\,\mathrm{d}\ell_0\,\mathrm{d}\ell_1

这个表达式已经是 $N=2$ 的完整密度递推：加号密度有闭式高斯结果，减号密度则由二维积分给出。它也解释了 DE 的必要性：如果只记住两个输入的均值 $2$ ，无法从均值恢复上表中的符号冲突、零值和非线性压缩。

离散化、卷积与数值复杂度

连续密度无法在计算机中逐点保存，实际 DE 通常先截取有限 LLR 区间 $[-L_{\max},L_{\max}]$ ，再划分成宽度为 $\Delta \ell$ 的网格。第 $k$ 个网格保存的是区间概率质量 $p[k]$ ，而不是某一点的函数值：

p[k]\approx\int_{k\Delta \ell-\Delta \ell/2}^{k\Delta \ell+\Delta \ell/2}a(\ell)\,\mathrm{d}\ell

这样做有三个直接好处：所有数组元素非负，数组总和可以检查归一化，分支递推也能转化成有限次加法。

加号分支在离散网格上是概率质量卷积：

p^+[k]=\sum_j p_0[j]p_1[k-j]

超出 $[-L_{\max},L_{\max}]$ 的质量需要明确处理：可以累积到边界桶，也可以丢弃后重新归一化，但不能不记录就假定它不存在。减号分支则遍历 $(j_0,j_1)$ ，把网格代表点经过 box-plus 映射，再把结果质量累加到最近的输出桶；映射结果落在两个桶之间时，也可以按距离分配给相邻桶，以降低量化误差。

一个只保留核心步骤的伪代码如下。注释里的“输入密度”指的是已经归一化的概率质量数组；实际工程还要补上尾部处理、插值和数值溢出保护。

// 用离散概率质量表示一个 L-density，grid[k] 是第 k 个桶的 LLR 代表值。
function plus_density(p0, p1):
    // 加号对应 LLR 相加，因此使用离散卷积。
    p_plus = zero_array()
    for j0 in all_bins:
        for j1 in all_bins:
            k = bin_of(grid[j0] + grid[j1])
            p_plus[k] += p0[j0] * p1[j1]
    return normalize_and_handle_tail(p_plus)

// 减号对应 box-plus，不能把均值相加代替二维映射。
function minus_density(p0, p1):
    // 每一对输入桶代表一块联合概率质量。
    p_minus = zero_array()
    for j0 in all_bins:
        for j1 in all_bins:
            value = 2 * atanh(tanh(grid[j0] / 2) * tanh(grid[j1] / 2))
            k = bin_of(value)
            p_minus[k] += p0[j0] * p1[j1]
    return normalize_and_handle_tail(p_minus)

若网格有 $M$ 个桶，加号的直接卷积和减号的逐对映射通常都是 $O(M^2)$ 。加号可以使用 FFT 卷积降到约 $O(M\log M)$ ，减号仍需处理二维映射，通常是 DE 的主要开销。码长从 $2^n$ 增加时，递归层数增加，节点数量也增加，所以严格 DE 更适合用作高精度基准，而不是所有场景下的在线构造器。

离散化还有两个容易被忽略的误差来源： $\Delta \ell$ 太大时，box-plus 映射会被粗略量化； $L_{\max}$ 太小时，强正或强负 LLR 的尾部会被截断。增大区间和细化网格会提高精度，但也会增加内存和运行时间。

DE 输出如何变成可靠性排序

密度进化的输出是每个索引一条 L-density，而构造器需要的是有序序列。中间还必须明确“用什么数衡量可靠性”。例如用 Bhattacharyya 型量时，对第 $i$ 个子信道计算：

Z_i=\int_{-\infty}^{+\infty}a_i^{(N)}(\ell)e^{-\ell/2}\,\mathrm{d}\ell

然后定义排序序列 $\boldsymbol{\pi}=(\pi_0,\ldots,\pi_{N-1})$ ，满足：

Z_{\pi_0}\le Z_{\pi_1}\le\cdots\le Z_{\pi_{N-1}}

也就是说， $Z$ 从小到大排列， $\pi_0$ 是最可靠的索引。给定信息长度 $K$ 后，取排序序列中排在前面的 $K$ 个索引：

\mathcal{A}=\{\pi_0,\pi_1,\ldots,\pi_{K-1}\},\qquad\mathcal{A}^c=[0,N-1]\setminus\mathcal{A}

如果改用平均 LLR，则应先说明平均值从大到小排序；如果改用互信息估计，则应说明从大到小排序。集合 $\mathcal{A}$ 本身没有顺序，只有 $\boldsymbol{\pi}$ 是排序序列。

为什么 GA 能接在 DE 后面

严格 DE 保留整条 L-density，因此信息最完整；高斯近似（GA）则主动假设密度可以由少量参数近似表示。全零参考下常见的对称高斯形式为：

L\approx\mathcal{N}(\mu,2\mu)

加号分支在高斯假设下只需把均值相加，减号分支再用 $\phi$ 函数近似 box-plus 对分布的作用。于是，GA 不是凭空发明另一套 Polar 递推，而是把 DE 的“分布传播”压缩成“参数传播”。

这也解释了两种方法的分工：DE 可以用来检查离散化误差、验证排序和建立基准；GA 用更低的计算代价完成大多数 AWGN 构造。下一篇会专门说明高斯假设、 $\phi$ 递推以及 design-SNR $\rho_{\mathrm{des}}$ 如何进入工程构造；实际仿真信噪比仍记为 $\rho_{\mathrm{sim}}$ 。

常见误区

第一，把 AWGN 的 $y_i$ 直接当作 LLR。 $y_i$ 是接收观测，LLR 是 $\lambda_i=2y_i/\sigma^2$ ；当噪声方差改变时，同一个观测值对应的 LLR 也会改变。

第二，只追踪 LLR 均值就称为严格 DE。均值递推属于 GA 或其它矩近似；严格 DE 追踪的是完整 L-density。

第三，把减号分支写成 $L_0-L_1$ 或 $L_0+L_1$ 。减号的正确更新是 box-plus，符号冲突和接近零的输入都必须保留下来。

第四，把 $N=2$ 的减号输出也写成高斯分布。即使两个输入都是高斯，经过双曲正切变换后一般也不是高斯；只有通过数值积分、采样或离散化，才能得到它的分布近似。

第五，忽略离散化的尾部质量。截取 $[-L_{\max},L_{\max}]$ 后，必须记录边界桶、重新归一化或报告被截断的质量，否则每一层递推的总概率会悄悄偏离 1。

小结

BEC 可以用一个擦除率递推，是因为它的输出状态结构足以由这个标量概括；AWGN 的连续输出没有这个性质。通过 BPSK 和噪声方差约定，物理信道观测先变成原始 LLR：

\lambda_i=\frac{2y_i}{\sigma^2}

在全零参考下，底层 LLR 是高斯分布；Polar 合并之后，加号分支满足：

L^+=L_0+L_1

减号分支满足：

L^-=2\operatorname{atanh}\left(\tanh\frac{L_0}{2}\tanh\frac{L_1}{2}\right)

因此，密度进化逐层传播 L-density，再由 $Z_i$ 或其它明确指标形成可靠性排序。 $N=2$ 的例子显示：加号密度可以保留为高斯闭式，减号密度必须通过二维变量变换得到；离散网格把这一步变成可执行的卷积和桶映射，但同时引入网格、截断和尾部归一化误差。

从 DE 到 GA 的关系也由此变得清楚：GA 是对分布演化的受控压缩，不是把 AWGN 不加说明地当成 BEC。

参考

E. Arıkan, “Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels,” IEEE Transactions on Information Theory, vol. 55, no. 7, pp. 3051–3073, Jul. 2009, doi: 10.1109/TIT.2009.2021379.
R. Mori and T. Tanaka, “Performance and construction of polar codes on symmetric binary-input memoryless channels,” IEEE Transactions on Information Theory, vol. 59, no. 5, pp. 2883–2901, May 2013, doi: 10.1109/TIT.2013.2248212.
I. Tal and A. Vardy, “How to construct polar codes,” IEEE Transactions on Information Theory, vol. 59, no. 10, pp. 6562–6582, Oct. 2013, doi: 10.1109/TIT.2013.2272694.
S. B. Korada, E. Şaşoğlu, and R. Urbanke, “Polar Codes: Characterization of Exponent, Bounds, and Constructions,” IEEE Transactions on Information Theory, vol. 56, no. 12, pp. 6253–6264, Dec. 2010, doi: 10.1109/TIT.2010.2080990.