LDPC码密度进化方法与门限研究

1、    LDPC码密度进化方法与门限研究        徐富兵1,2， 雷 菁1， 李二 时间:2008年07月21日     字 体: 大 中 小        关键词:        ? 摘 要：关键词： LDPC码? 密度进化? 门限值? LDPC码是Gallager提出的

2、逼近香农限的好码134基于消息传递机制的置信传播(Belief Propagation)译码算法提出了密度进化分析(Density Evolution)的思想。通过跟踪译码器中传递消息的概率密度函数在迭代过程中的变化情况，分析译码收敛特性，得到特定信道下的门限值。对于研究译码过程和码的设计，密度进化是一种非常有用的工具。? 在参考文献4中，Richardson等给出了密度进化的直接算法。这种迭代分析方法非常复杂，计算量巨大。为此，Sae-Yang Chung57、Hui Jin6等提出了密度进化的不同实现方法，在计算精度损失可以接受的情况下，极大地提高了分析的效率。本文将基于密度进化的基本理论

3、，讨论其实现方法和在门限判决中的应用。1 LDPC码和密度进化? LDPC码是具有稀疏奇偶校验矩阵的线性分组码。一个LDPC码集可以由一个度分布(,)确定，即由变量节点和校验节点的度分布函数确定：? 其中lmax和rmax分别表示变量节点和校验节点的最大度数。规则码(dv,dc)是一种特殊情形，? LDPC码最常用的译码算法是和积算法(Sum-Product Algorihm)。基于文献4中的无环假设，如果一个规则LDPC码（dv,dc）没有长度小于或等于2l的环，则在l次迭代内，可以假定所有的消息变量是独立的。设u0表示变量节点接收信号的对数似然比(LLR)消息，v和u分别表示变量节点和校验

4、节点发送给各自邻接节点的LLR消息2。则变量节点和校验节点的消息更新规则表示为：? ? 在无环和不同变量节点初始消息u0i,i=1,2,dv-1和vi,i=1,2,dci和vi的概率密度函数变得容易。在译码第k次迭代时，vi和ui的概率密度分别表示为Pk和Qk, k=1,2,。P0表示u0的概率密度，? ? ? 在变量节点和校验节点进行卷积运算的域分别为i+(变量节点域:实数域加上+)和GF(2)×0,(校验节点域:简称G域),利用傅立叶变换计算Qk和Pk时，在两个域之间相互转换，从而使计算过程相当复杂4。? 密度进化的实现主要包括三部分：变量节点域卷积、G域卷积和两个域之间适合卷积

5、的密度函数表达式的相互转换。参考文献5-7对不同的方法作了阐述，具有各自的特点。2.1 离散密度进化(DDE)? 为了计算机仿真处理，对第1节算法中LLR消息、v、u量化处理。设量化比特为q,量化步进为，量化区间为-N,N, N=2q-1-1。如果消息值在范围(n-/2,n+/2)，n是一个整数，当-NnN时，消息量化为n；当n<-N和n>N时，分别量化为-N和N。? pv和pu分别表示离散消息的概率聚集函数(pmf)。由于离散消息都是独立和均匀分布的随机变量，由(1)式易得变量节点的密度进化规则为：借助于快速傅立叶变换(FFT)能够有效实现。? 对校验节点定义如下的二元运算符：?

6、 ? 其中a、b都是离散消息，Q表示量化运算。易知是递归运算，可以推导出校验节点密度进化规则：(pv)。采用查表法计算，加速算法实现。? 对于非规则LDPC码，DDE算法是：? ? 该算法适合各种对称信道，如BSC、BEC、高斯信道等。考虑AWGN信道，LDPC(3,6)规则码，信道噪声方差exact=0.880 913，在不同量化比特情形下求得门限值DDE如表1所示，可见，量化14比特时，结果已相当精确。?2.2 利用对称傅立叶变换(SFT)计算? DDE算法在变量节点域未能充分利用LLR消息概率密度函数f的对称性。在对称信道上传输全1码字时，f对称，从而g(x):=e-1/2x f(x)是

7、偶函数。定义傅立叶变换假设f取值于k，k=-K,0,1,K，对e-1/2 x f(x)填充0，进行22m点离散傅立叶变换(2m+1>K)。实际中，Fg(jw)比Ff(jw)更有优势。首先，前者是实数和关于w的偶函数，便于乘积计算；其次，函数g的尾值呈指数级减少，极大地降低了FFT计算时的混叠现象。这样，不必在每对卷积之后返回实数域，只要在变量节点域卷积结束时返回即可，节省了大量计算。? 在校验节点域，即G域，傅立叶变换定义为：Ff(v):=取值于实数0,KU+。那么傅立叶变换：? ? 现在的难题是如何量化v。根据文献6，实际采用v=e(1+jw)。依照对量化，取w=0 将降低复杂度。?

8、这种算法比DDE更为接近原始的密度进化原理，但达到同样精度需要少得多的计算量。对于规则LDPC(3,6)码，不同量化间隔时的噪声门限SFT如表2所示。?2.3 高斯近似8通过仿真首先发现这个事实。由于LLR消息的分布是相近的，利用对数正态的性质，可以证明在密度进化过程中消息是近似高斯分布的。利用对称条件f(x)=exf(-x)，高斯分布的LLR消息服从N(0,20)。假设AWGN信道噪声均值为0，方差为2，传输全0码字，易知0=2/2。只要确定?滋0就能完整描述概率密度函数。? mv和mu分别表示v和u的均值，则(1)、(2)式两边取均值，化简变换可得：? ? 其近似计算方法是：? ? 用高斯

9、近似算法求得规则LDPC(4,6)码的噪声门限为GA=1.003 6，相应的信噪比Eb/N0=1.729 9。对于不同信噪比的消息概率密度的均值变化如图1所示。当Eb/N0大于门限，k时，均值趋于无穷大，意味着误码率趋于0；当Eb/N0小于门限，k时，均值趋于一个有限固定值，意味着误码率不可能趋于0。Eb/N0值越大，正确译码需要的迭代次数越少。当Eb/N0=1.76时，概率密度分布如图2所示。随着迭代次数的增长，概率分布向正向移动，译码器几乎能够正确译码。?3 仿真和结论? 前面讨论的三种密度进化算法各有特点。根据实际需要，选择合适的算法对LDPC码进行研究。表3给出了不同码率的规则LDPC

10、码采用不同密度进化算法求出的门限值、GA与DDE的距离GA、SFT与DDE的距离SFT以及DDE与香农限C的距离。DDE和SFT两种方法的精度差别不多；高斯近似的精度稍微差些，但其计算量少很多。? 表3中表明，规则码的门限值距离香农限还较远。LDPC码研究重点之一就是利用密度进化算法优化度分布(,)设计好的非规则码，获得距离香农限更近的门限。参考文献5中设计出了=0.004 5dB的非规则码，与香农限的距离已经很小了。? 密度进化方法是现代高级编码研究的重要工具,不仅适用于LDPC码，也可用于Turbo码、MN码等的分析和设计。这种方法的提出，促进了现代高效纠错编码的发展。参考文献1 GALL

11、AGER 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 decod

12、ing. 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 parit

13、y -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.