2.2.3 密度进化与高斯近似算法

密度进化（density evolution,DE）的基本思想是由Gallager[4]提出的。Richardson等[8-9]和Chung等[10]最早利用密度进化分析LDPC码采用BP算法的渐近行为。他们的研究表明，对于许多重要的信道，例如加性白高斯噪声（additive white Gaussian noise,AWGN）信道，当码长无限长时，针对随机构造的 LDPC 码集合，可以用DE算法计算出无差错译码的门限值。因此，DE算法能够比较与分析LDPC码的渐近性能，是一种重要的理论分析工具。

1．密度进化

所谓密度进化，就是在Tanner图上计算与跟踪LLR的概率密度函数（probability density function,PDF）。假设信道LLR的概率密度函数为p(L)；第l次迭代，变量节点到校验节点外信息的PDF为p(Ml)，校验节点到变量节点外信息的PDF为p(El)。随着迭代次数的增加，外信息的PDF会演化。

DE成立的两个独立性假设如下。

（1）信道无记忆，这个假设是指各个接收信号相互独立，因此互不相关。

（2）Tanner图不存在长为2l或更短的环，这样保证了各节点传递的外信息相互独立。

首先，观察(3,6)规则LDPC码的BP译码过程。以某个检验节点为根节点构成的消息传递树如图2-3所示。

如图2-3所示，在一次迭代中，作为根节点的校验节点向连接到它的某个变量节点传递信息，这个变量节点接收到两路校验节点信息以及信道信息后生成外信息，传递到与之相连的下一层的dv-1=2个校验节点。而这两个校验节点又可以进一步扩展 dc-1=5个变量节点。这样经过两次迭代，根节点的信息传递到了(dv-1)(dc-1)= 2 × 5=10个变量节点。注意，在变量节点处的计算还需要考虑信道信息。

一般地，对于(dv,dc)规则LDPC码，BP算法的迭代计算式为

对于变量节点向校验节点传递的消息，由于各消息相互独立，因此外信息的PDF是各个消息PDF的卷积，表示为

其中，*表示卷积运算。由于式（2-32）涉及dv-1个卷积运算，复杂度较高，通常用快速傅里叶变换（fast Fourier transform,FFT）代替，从而降低计算复杂度。

类似地，根据式（2-31），校验节点向变量节点传递的消息可以分解为两部分，即

其中， 是模2加运算，而是普通的代数求和运算。由于各个变量节点输入的外信息相互独立，因此的概率密度函数表示为

上述计算涉及dc-1个卷积运算，也可用FFT代替。

最终，译码比特LLR的PDF可表示为

上述规则LDPC码的PDF计算可以进一步推广到非规则LDPC码。此时变量与校验节点信息的PDF计算式为

由此，DE算法过程可以简述如下。给定一组度分布(λ(x),ρ(x))，针对B-DMC，利用信道对称性条件，假设发送全零码字，给定信道条件，例如二进制输入加性白高斯噪声（binary input additive white Gaussian noise, BI-AWGN）信道的均方根噪声σ，反复进行式（2-27）的概率密度函数迭代运算。当迭代次数充分大时，比特 LLR Λ＜0对应的概率就是译码的差错概率，即。

信噪比（signal-to-noise ratio,SNR）为,BI-AWGN信道下，(3,6)规则LDPC码p(M l)与p(El)演化结果分别如图2-4和图2-5所示。

由图2-4可知，初始分布p(L)为高斯分布，随着迭代次数增加，p(Ml)仍然为高斯分布，并且LLR均值逐渐增大，其小于0的拖尾逐步减少，直至趋于0。

由图2-5可知，在迭代早期，例如第1次迭代，p(El)并不是高斯分布，但随着迭代次数增大，函数形状越来越接近高斯分布，并且随着LLR均值逐渐增大，小于0的拖尾趋于消失。

利用密度进化算法，我们可以针对特定度分布计算其译码无差错的噪声门限。

定义2.3 对于BI-AWGN，噪声门限定义为

仍然以(3,6)规则LDPC码为例，在BI-AWGN信道下，不同信噪比的误码率（bit error ratio,BER）性能如图2-6所示。当（σ=0.881）时，随着迭代次数的增加，误码率不收敛；而当（σ=0.879）时，迭代次数超过100后，误码率已经趋于0。由此可见，噪声门限必然满足0.879＜σ*＜0.881。我们可以通过DE算法确定其精确值为σ*=0.88（）。

码率，反解BI-AWGN信道容量，可以得到极限信噪比，相应的噪声门限σ*=0.978 69。由此可知，(3,6)规则LDPC码的噪声门限与信道容量极限还有很大差距。这种码性能受限的关键原因是度分布过于规则，为了逼近信道容量极限，需要对变量节点、校验节点的度分布进行优化，设计高度不规则的 LDPC 码。研究者借助密度进化工具，采用差分演化或迭代线性规划算法，得到了高性能的度分布。其中最著名的是Chung等[10]基于DE算法得到的优化分布，如式（2-38）所示，其变量节点度分布为2～8 000，具有高度不规则性。

上述分布对应的信噪比，噪声门限σ*=0.978 186 9，与信道容量极限的差距为0.004 5 dB。

需要注意的是，上述分析的是码长与迭代次数趋于无穷大的极限信噪比，即N→∞,l→∞。从渐近性能来看，即使码长无限长、迭代次数无限大，这种不规则LDPC码仍与信道容量极限有0.004 5 dB的差距，因此这种不规则LDPC码只能逼近BI-AWGN信道的容量极限，但严格意义上讲是容量不可达的。从有限码长性能来看，Chung等[10]构造了最大度为100与200的不规则LDPC码，码长N=107，迭代2 000次，误比特率为10-6，距离香农限约0.04 dB，远未达到信道容量极限。

尽管如此，基于DE算法构造渐近性能优越的度分布为设计逼近信道容量极限的 LDPC 码提供了完整的理论框架。沿着这一思路，人们构造了众多的高性能的LDPC码。

2．高斯近似

密度进化是一个良好的理论工具，能够精确分析给定度分布的渐近性能，但其计算结果的准确性依赖于LLR分布的量化精度。一般而言，只有高量化精度才能获得准确的门限值估计，但即使采用FFT，计算复杂度仍然巨大。

作为一种替代分析工具，高斯近似（Gaussian approximation,GA）[11]虽然牺牲了一些准确性，但显著降低了计算复杂度。高斯近似假设变量节点与校验节点的外信息近似服从高斯分布，因此这些信息的方差是均值的一半，它们的概率密度函数完全由均值决定。这样我们只要在迭代过程中跟踪外信息的均值，就能够预测渐近性能。

对于(dv,dc)规则的LDPC码，假设变量节点v与校验节点u消息的均值分别为mv与mu，则第l次迭代变量节点消息的均值递推式为

其中，第0次迭代（即初始分布）对应的校验节点消息均值为0，即。

而校验节点消息的均值递推式为

其中，函数ϕ(x)定义为

在实际应用中，函数ϕ(x)涉及复杂的数值积分，一般采用两段近似公式，即

对于度分布为(λ(x),ρ(x))的非规则LDPC码，其变量节点消息的递推式为

而校验节点消息的递推式为

综上所述，密度进化与高斯近似是两种分析迭代译码渐近性能的理论工具，不仅可以用于 LDPC码的性能分析与优化设计，也可用于 Turbo码的性能分析与设计。