摘 要：详细描述了密度进化（DE）方法的基本原理，比较和分析了离散密度进化(DDE)、对称傅立叶变换" title="傅立叶变换">傅立叶变换(SFT)和高斯" title="高斯">高斯近似(GA)等三种具体算法的特点，并求出AWGN信道下一些度分布的门限值。这对LDPC码理论分析和应用研究具有重要指导作用。
关键词：LDPC码 密度进化 门限值

LDPC码是Gallager提出的逼近香农限的好码^[1]。当码长较长、码型设计适当时，其性能甚至优于Turbo码。Gallager发现了LDPC码的门限现象：若信道噪声" title="信道噪声">信道噪声小于某个固定的门限值，只要码长趋于无穷，则可以达到任意小的误码概率。Richardson等^[3][4]基于消息传递机制的置信传播(Belief Propagation)译码算法提出了密度进化分析(Density Evolution)的思想。通过跟踪译码器中传递消息的概率密度函数在迭代过程中的变化情况，分析译码收敛特性，得到特定信道下的门限值。对于研究译码过程和码的设计，密度进化是一种非常有用的工具。
在参考文献[4]中，Richardson等给出了密度进化的直接算法。这种迭代分析方法非常复杂，计算量巨大。为此，Sae-Yang Chung^[5][7]、Hui Jin^[6]等提出了密度进化的不同实现方法，在计算精度损失可以接受的情况下，极大地提高了分析的效率。本文将基于密度进化的基本理论，讨论其实现方法和在门限判决中的应用。
1 LDPC码和密度进化
LDPC码是具有稀疏奇偶校验矩阵的线性分组码。一个LDPC码集可以由一个度分布(λ,ρ)确定，即由变量节点和校验节点的度分布函数确定：

其中l_max和r_max分别表示变量节点和校验节点的最大度数。规则码(d_v,d_c)是一种特殊情形，

LDPC码最常用的译码算法是和积算法(Sum-Product Algorihm)。基于文献[4]中的无环假设，如果一个规则LDPC码（d_v,d_c）没有长度小于或等于2l的环，则在l次迭代内，可以假定所有的消息变量是独立的。设u₀表示变量节点接收信号的对数似然比(LLR)消息，v和u分别表示变量节点和校验节点发送给各自邻接节点的LLR消息^[2]。则变量节点和校验节点的消息更新规则表示为：

在无环和不同变量节点初始消息u₀服从独立均匀分布(i.i.d.)的假设条件下，易知，u_i,i=1,2,…,d_v-1和v_i,i=1,2,…,d_c也是i.i.d.分布的。这样计算u_i和v_i的概率密度函数变得容易。在译码第k次迭代时，v_i和u_i的概率密度分别表示为P_k和Q_k, k=1,2,…。P₀表示u₀的概率密度，

基于上述的i.i.d.特性，对于k≥1，从(1)式可得:

在变量节点和校验节点进行卷积运算的域分别为i⁺(变量节点域:实数域加上+∞)和GF(2)×[0,∞](校验节点域:简称G域),利用傅立叶变换计算Q_k和P_k时，在两个域之间相互转换，从而使计算过程相当复杂[4]。
2 密度进化算法" title="进化算法">进化算法的实现
密度进化的实现主要包括三部分：变量节点域卷积、G域卷积和两个域之间适合卷积的密度函数表达式的相互转换。参考文献[5-7]对不同的方法作了阐述，具有各自的特点。
2.1 离散密度进化(DDE)
为了计算机仿真处理，对第1节算法中LLR消息、v、u量化处理。设量化比特为q,量化步进为Δ，量化区间为[-N,N], N=2^q-1-1。如果消息值在范围(nΔ-Δ/2,nΔ+Δ/2)，n是一个整数，当-N≤n≤N时，消息量化为n；当n<-N和n>N时，分别量化为-N和N。
p_v和p_u分别表示离散消息的概率聚集函数(pmf)。由于离散消息都是独立和均匀分布的随机变量，由(1)式易得变量节点的密度进化规则为：借助于快速傅立叶变换(FFT)能够有效实现。
对校验节点定义如下的二元运算符Φ：

其中a、b都是离散消息，Q表示量化运算。易知Φ是递归运算，可以推导出校验节点密度进化规则：(pv)。采用查表法计算Φ，加速算法实现。

对于非规则LDPC码，DDE算法是：

该算法适合各种对称信道，如BSC、BEC、高斯信道等。考虑AWGN信道，LDPC(3,6)规则码，信道噪声方差σ_exact=0.880 91^[3]，在不同量化比特情形下求得门限值σ_DDE如表1所示，可见，量化14比特时，结果已相当精确。

2.2 利用对称傅立叶变换(SFT)计算
DDE算法在变量节点域未能充分利用LLR消息概率密度函数f的对称性。在对称信道上传输全1码字时，f对称，从而g(x):=e^-1/2xf(x)是偶函数。定义傅立叶变换假设f取值于kδ，k=-K,…,0,1,…,K，对e^{-1/2 x}f(x)填充0，进行2^2m点离散傅立叶变换(2^m+1>K)。实际中，F_g(jw)比F_f(jw)更有优势。首先，前者是实数和关于w的偶函数，便于乘积计算；其次，函数g的尾值呈指数级减少，极大地降低了FFT计算时的混叠现象。这样，不必在每对卷积之后返回实数域，只要在变量节点域卷积结束时返回即可，节省了大量计算。
在校验节点域，即G域，傅立叶变换定义为：Ff(v):=取值于实数[0,Kδ]U+∞。那么傅立叶变换：

现在的难题是如何量化v。根据文献[6]，实际采用v=e^α(1+jw)。依照δ对α量化，取w=0 将降低复杂度。
这种算法比DDE更为接近原始的密度进化原理，但达到同样精度需要少得多的计算量。对于规则LDPC(3,6)码，不同量化间隔时的噪声门限σ_SFT如表2所示。

2.3 高斯近似
如果信道是AWGN，消息的概率密度是近似高斯分布" title="高斯分布">高斯分布的。Wiberg^[8]通过仿真首先发现这个事实。由于LLR消息的分布是相近的，利用对数正态的性质，可以证明在密度进化过程中消息是近似高斯分布的。利用对称条件f(x)=e^xf(-x)，高斯分布的LLR消息服从N(μ₀,2μ₀)。假设AWGN信道噪声均值为0，方差为σ²，传输全0码字，易知μ₀=2/σ²。只要确定?滋0就能完整描述概率密度函数。
m_v和m_u分别表示v和u的均值，则(1)、(2)式两边取均值，化简变换可得：

其近似计算方法是：

用高斯近似算法求得规则LDPC(4,6)码的噪声门限为σ_GA=1.003 6，相应的信噪比E_b/N₀=1.729 9。对于不同信噪比的消息概率密度的均值变化如图1所示。当E_b/N₀大于门限，k→∞时，均值趋于无穷大，意味着误码率趋于0；当E_b/N₀小于门限，k→∞时，均值趋于一个有限固定值，意味着误码率不可能趋于0。E_b/N₀值越大，正确译码需要的迭代次数越少。当E_b/N₀=1.76时，概率密度分布如图2所示。随着迭代次数的增长，概率分布向正向移动，译码器几乎能够正确译码。

3 仿真和结论
前面讨论的三种密度进化算法各有特点。根据实际需要，选择合适的算法对LDPC码进行研究。表3给出了不同码率的规则LDPC码采用不同密度进化算法求出的门限值、σ_GA与σ_DDE的距离Δ_GA、σ_SFT与σ_DDE的距离Δ_SFT以及σ_DDE与香农限σ_C的距离Δ_σ。DDE和SFT两种方法的精度差别不多；高斯近似的精度稍微差些，但其计算量少很多。

表3中Δ_σ表明，规则码的门限值距离香农限还较远。LDPC码研究重点之一就是利用密度进化算法优化度分布(λ,ρ)设计好的非规则码，获得距离香农限更近的门限。参考文献[5]中设计出了Δ_σ=0.004 5dB的非规则码，与香农限的距离已经很小了。
密度进化方法是现代高级编码研究的重要工具,不仅适用于LDPC码，也可用于Turbo码、MN码等的分析和设计。这种方法的提出，促进了现代高效纠错编码的发展。
参考文献
[1] GALLAGER R G. Low-Density Parity-Check codes.Cambridge, MA:MIT Press, 1963.
[2] MACKAY D J C. Good error-correcting codes based on very sparse matrices. IEEE Trans, Inf. Theory, 1999,45(3):399-431.
[3] RICHARDSON T J, URBANKE R L. The capacity of low-density parity-check codes under message-passing decoding. IEEE Trans. Information Theory, 2001,47(2):599-618.
[4] RICHARDSON T, SHOKROLLAHI A,URABANKE R. Design of capacity- approaching irregular low-density parity-check codes. IEEE Trans. Inform. Theory, 2001,47(2):619-637.
[5] CHUNG S Y, FORNEY G D, RICHARDSON J,et al. On the design of low-density parity -check codes within 0.0045 db of the Shannon limit. IEEE Communications Letters, 2001,5(2):58-60.
[6] JIN H, RICHARDSON T. A new fast density evolution.IEEE Information Theory Workshop, Punta del Este, Uruguay, 2006:13-17.
[7] CHUNG S Y, RICHARDSON T J, URBANKE R L. Analysis of sum-product decoding of low-density paritycheck codes using a Gaussian approximation. IEEE Trans. Inform. Theory,2001,47(2):657-670.
[8] WIBERG N. Codes and decoding on general graphs. Ph.D. Dissertation, Department of Electrical Engineering, Linkoping University, 1996.