基于BP算法的LDPC码性能仿真

淮南师范学院 王千春

前言

1965年Gallager在他提出了Gallager码，当时人们对他的发现没有任何重视，认为他是天方夜谭，以至于这么伟大的发现在当时被忽视了，由于科学技术的进步和相关理论的发展，后人发现他在和其他译码相结合的情况下可以接近于香农极限，因为LDPC码有着划时代的意义。LDPC码的特点是，比之前的译码方法更加灵活，接近于香农极限，在即将到来的5G时代，LDPC码必将通过它独特的优势，为人类进入新的信息时代做出贡献[1]。

1.LDPC码的原理

LDPC代码是一个非常特殊的线性分组码。通过生成矩阵G，必须将线性分组码的信息s转换为转移码t，并且对应于G的校验矩阵H满足H×t = 0。LDPC码验证矩阵的0个元素分量的个数大于非零元素的个数，属于稀疏矩阵范畴[2]。

LDPC码包括常规和非常规两种编码形式。假设LDPC码的验证矩阵B是J×K的满秩矩阵，则LDPC码长度为J，验证位K，则信息位是H= j-k，码率r= h/ k。用Tanner图表示如图1所示。所谓的信息点（比特点）即是下边N个节点所代表的N个码字。因此，非规则码包括规则码，是它的一个特例。

图1 校验矩阵对应的Tanner图

2.LDPC码校验矩阵构造

在介绍LDPC码校验矩阵的构造之前，首先阐述一下girth的概念。图2中，粗线部分构成了长度为6的环，其中最短环的环长称为该图的girth。girth是构造校验矩阵的非常重要的指标[3]。二部图中girth的值越大，校验矩阵的性能就越好，一般要求girth最小为6。

图2 校验矩阵的随机构造

本文采用Gallager构造法，Gallager基于GF（2）域上定义的（n，j，k）LDPC码，其校验矩阵H的构造如下：

（1）将Gallager码的监督矩阵按行划分成j个部分（每部分包含相同的行数），每一部分的每一列中只包含一个“1”。

（2）第一部分构造的矩阵中，“1”比特在行中按降幂排列，在第一行中，第1到k个元素为“1”，其余为0；在第2行中，从第k+1到2k个元素为“1”，其余为0；如此安排，第i行中，从第k+1到第i个元素为“1”，其余为0。

（3）其余j-1部分的构造是对第一部分进行列的随机重排。

该构造法可以保证每列有j个“1”，每行有k个“1”。图3给出了由Gallager构造法构造的（20，3，4）的LDPC码校验矩阵，码长为20，j=3，k=4。

图3 Gallager构造的（30，5，6）的LDPC码校验矩阵

3.LDPC码的编码

本文采用随机构造的LDPC码的LU分解法[4]。对于LU分解法的想法，在I是非特异性队伍的情况下，I可以分解为上三角队U和下三角队L的积，L和U也是MxN维的稀疏排列。

基本步骤如下：

（1）对H矩阵进行LU分解，得到重排后的H、B、L、U。

（2）计算Z=BS。

（3）解方程得到Y，其中Y是M维列向量。

（4）通过反向消除法求解UC = Y，得到C。

LU分解的一个基本算法如下所示：

（1）设U和L为全零矩阵。

（2）设F=H。

（3）for i=1 to m

在F矩阵中找到同一列的非零元素。

对矩阵F和H的行列进行重新组合，注意此元素必须位于他之前的位置，不可变化。

（4）把B矩阵设置为重排后的H矩阵最后N-M列。

4.LDPC码的译码

LDPC码的迭代译码方法是LDPC码能够得以迅速发展的主要原因，该译码方法使得LDPC码不仅描述简单，译码复杂度低，而且可以并行操作，便于硬件实现，具有接近Shannon极限的优异性能。

译码采用UMP BP-Based算法（最小和或最大积），LLR BP算法中节点[5]可变化为：

由于：

所以：

UMP（Uniformly Most Powerful）BP-Based算法又称为最小和（Min Sum）算法或最大积（Max Product）算法，该算法是用式来处理LLR BP算法中校验节点的消息，此时校验节点的迭代只有比较算法和加法运算，计算的复杂度就大大降低了。对于加性高斯白噪声信道，该算法不需要信道估计。

5.LDPC码的仿真

在其他条件一定时，将码长设置为300、500以及1000，列重和迭代次数分别设置为2和20，进行仿真，得到的结果如图4所示。

图4 码长不同时的仿真结果

从图4的仿真图像可以清楚地看出：在相同的SNR件下，LDPC码的性能与代码成正比，但与具有任何数值的情况相比，误码率不会根据代码长度的变化而改变，但是如果信噪比是与高于特定数值的情况相比，误码率开始显明显着上升。这是因为代码具有上限，随着码长的增加，编码的繁琐程度也不断提高，此时性能的增加便不会很明显。

简言之，在相同的信噪比下，LDPC码的性能与码长成正比，但是一旦信噪比低于某个值，误码率不会随着代码长度而改变。但当信噪比高于某个值时，误码率开始迅速增加。这是因为任何代码长度都有其自己理论上的编码上限。

当列重和代码长度选择一定值时，Matlab软件选择三次不同的迭代次数进行多次迭代。20，40，列重选择2，代码长度选择500，仿真结果如图7所示。

图5 迭代次数不同时的影响

从图5所示的仿真结果可以看出：在相同的信噪比下，LDPC码的性能与迭代次数成正比。然而，虽然误码率和迭代次数之间的关系成正比，但是实验发现，当迭代次数已经改变到上限时，继续增加，误码率不改变，在这种情况下，系统延时变长，并且即使LDPC码的性能不受影响，系统的准确度也会降低。