LDPC编译码仿真

LDPC编译码及误码率的仿真 摘要：低密度奇偶校验(LDPC)码是一种基于稀疏奇偶校验矩阵的线性分组码。由于LDPC码是性能接近Shannon极限的好码,并且具有较强的纠错能力、较大的灵活性和较低的译码复杂度,使它成为近年来编码领域研究的一个热点,在通信的多个领域得到了应用。 本文主要对LDPC码的编译码算法进行研究。首先,介绍LDPC的相关基本概念，其次,阐述了LDPC码的性能特点、发展应用以及LDPC码的基本理论知识。最后在译码算法上,简单对BP译码算法进行了介绍和仿真分析。 关键词：LDPC码；编码；BP译码； Simulation of LDPC encoding and decoding and bit error rate Abstract: Low-density Parity-check (LDPC) codes are one kind of linear block codes approaching Shannon limit based on sparse parity-check matrices. They are with excellent error correcting ability, flexibility, and low decoding complexity. So they are becoming a power competitor in the coding research field, and have been successfully applied in various fields of communications recently. In this paper, the encoding and decoding algorithms for LDPC codes are mainly studied. Firstly, it introduces the basic concepts of LDPC; secondly, the properties, developments and applications of LDPC codes are presented; finally, for the decoding algorithm, BP decoding algorithm is simply introduced and simulated analysis. Key s: LDPC, coding, BP decoding. 1  引言 自信道编码理论提出以来，如何构造一个逼近信道容量限的实用好码成了众多学者竞相研究的课题，并逐渐形成信息论的一个重要分支[1]。五十多年来，人们构造实用好码的探索基本上是按照香农所提出的基本条件的后两条为主线展开的。 1962年，Gallager在他的博士论文中提出了二元正则LDPC码，也被称为Gallager码[2]。Gallager证明了这类码具有很好的汉明距离特性，是满足GV限的渐进好码，经过迭代译码可以获得依码字长度指数降低的比特错误概率，但限于当时的计算能力，LDPC码被认为不是实用码，在很长一段时间没有受到人们的重视。需要指出的是，在LDPC码被遗忘的这30多年中，Zyablov和Pinsker以及Tanner却在不同的领域直接或间接地对LDPC码做着研究，这些研究成果，对于LDPC码的研究发展，起着举足轻重的作用。 Turbo码的发现引发了众多学者对LDPC码的研究兴趣。Mackay和Neal利用随机构造的Tanner图研究了LDPC码的性能[3]，发现采用和积译码算法的正则LDPC码具有和Turbo码相似的译码性能，在长码上甚至超过了Turbo码，这一结果引起了信道编码界的极大关注。 为了探讨LDPC码的优异性能，本文对LDPC码的编译码过程进行简单地仿真和分析。 2  LDPC编译码算法原理 2.1 LDPC码基本概念 LDPC码是线性分组码的一种，所以可以根据低密度稀疏校验矩阵H或者生成矩阵G来定义[4]。LDPC码的校验矩阵H中每行和每列里1的个数相对于矩阵的行数和列数来说，非常少，这就是稀疏校验矩阵固有的低密度特性，也是LDPC码区别于其他线性分组码最大的特点。 每行每列中1的个数固定的LDPC码称为规则码。一个长为n的低密度奇偶校验码与稀疏校验矩阵 相对应，可用 表示，即每行有q个1，每列有p个1。 的密度r定义为 中1的数目与行数目或列数目的比值，记为 。如果 矩阵是满秩的，那么由该稀疏校验矩阵定义的LDPC码的码率为 。此外，为了保证LDPC码译码性能， 矩阵任意两行或任意两列相重叠非零元素个数不大于1。图2-1所示为二元H（10，2，4）规则LDPC码的稀疏校验矩阵[5]。 图 2-1 H（10，2，4）规则LDPC码的稀疏校验矩阵 稀疏校验矩阵 也可以用二分图表示出来。二分图最早由Tanner提出，所以二分图又称为Tanner图。于是，我们可以用Tanner图来表示一个LDPC码。具体表示方法如下：用一个顶点集来表示编码后的比特，顶点个数等于码长n。每个顶点和每个码元比特一一对应，称为变量节点或者信息节点[6]。用另一个顶点集表示校验约束，顶点的个数等于校验方程的个数，也就是稀疏校验矩阵的行数m。一个顶点对应一个校验约束，称为校验节点。若稀疏校验矩阵第 行第 列的相应元素为1，则表示第 个码元比特参与了第 个校验约束，在Tanner图中相应的信息节点和校验节点之间连接一条边。这样就能得到和稀疏校验矩阵一一对应的Tanner图。图2-2所示为H（10，2，4）的规则LDPC码的Tanner图表 示。 图 2-2  H（10，2，4）规则LDPC码的Tanner图表示 2.2 LDPC编码 为了构造LDPC码，我们需要对信息序列 进行编码，得到相应的码字 。因此，我们得设法从校验矩阵 得到生成矩阵 ，然后根据 得到编码后的码字 。但是，求得的生成矩阵 一般都不是稀疏矩阵，所以运算量和存储量都很大，对实际应用造成了很大困难。因此，研究的重点就落在如何直接通过校验矩阵 来生成相应的码字 。本文主要应用Mackay构造方法[7]。在此规定 矩阵为m行n列，记为 。 Mackay 构造LDPC的方法是基于Tanner图的，其方法的关键是要消除Tanner图中的短循环。Tanner图中倘若存在短循环会增大误码率，从而影响LDPC码的译码。Mackay的构造方法就是要使校验矩阵 对应的Tanner图中存在的短循环数量尽可能的少，确保构造的 中，任意两列之间的重叠数不大于1。 对于 ，Mackay提出的四种构造方法依次为： 构造1：基本构造方法。矩阵 由随机构造得出，确保 每列中的“1”一样多，也就是列重 固定，同时，每列中的“1”要做到均匀分布，并且不存在长度为4的短循环，也就是任意两列元素的重叠数不大于1.他在论文中证明了 =3时的译码效果能够达到最好。 构造2：校验矩阵 中有m/2列的列重 为2，由两个（m/2）×(m/2)阶的单位矩阵上下摆放，余下n-m/2列按照构造1的方法进行。同时仍要保证任意两列之间的重叠不大于1。 构造3、构造4：分别在构造1和构造2方法构造的校验矩阵 的基础上，删除一些产生短循环的列，保证 所对应的Tanner图中最短循环的长度不大于某个值。 Mackay构造的LDPC码的校验矩阵,除去了长为4的短循环,能提高译码的准确度,利于译码的实现,但是也有可能会引入低重码字。 2.3 LDPC BP译码算法 LDPC码有很多种译码方法。根据消息迭代过程中传送消息的不同形式，可以将LDPC的译码方法分为硬判决译码和软判决译码。硬判决译码计算比较简单，但性能稍差，主要包括：MLG算法、WMLG算法、BF算法、WBF算法等；软判决译码计算比较复杂，但性能较好，主要包括：BP算法、min-sum算法、Normalized BP-based算法、LP算法。BP译码可以分为概率BP算法和LLR BP算法。概率BP算法的消息是用概率形式表示,是BP算法的通用形式,可以适用非二进制的LDPC码的译码。对二进制LDPC码, 消息可以表示为对数似然比形式,相应的译码算法称为LLR BP译码。 本文使用概率BP算法[8]： BP算法是消息传递（Message Passing）算法在LDPC译码中的应用。BP算法是基于Tanner图的迭代译码算法。在迭代过程中，可靠性信息通过Tanner图上的边在信息节点和校验节点之间来回传递，经过多次迭代后趋于一个稳定的值，由此获得最佳判决。研究表明，当LDPC码相应的Tanner图不存在环的情况下，BP译码算法收敛于其后验概率。 为了方便描述，首先说明在BP算法中所涉及的各符号的含义： 设 表示与校验节点 相连的所有的信息节点 的集合，即 ， 表示集合 去掉信息节点 。设 表示与信息节点 相连的所有的校验节点 的集合，即 ， 表示集合 中去掉校验节点 。 设 表示不考虑比特之间的相关性，仅仅根据比特 取值为 的概率， 取值为‘0’或者‘1’。显然有 。可以把 当做是信息节点 的固有性质。 设 表示基于接收序列并根据校验节点集合 的信息而得出的信息节点 的概率。 取值为‘0’或者‘1’。同样有 。可以认为 是信息节点 向校验节点 传递的信息。 设 表示当比特 ，并给定其他比特的一组概率 时，校验节点 对应的校验方程成立的概率。 可以认为是校验节点 向信息节点 传递的信息。 各符号之间的关系式如式（2-1）（2-2）（2-3）所示： （2-1） （2-2） （2-3） 对于高斯白噪声信道，噪声功率为 ，在BPSK调制方式下，有： ，       （2-4） 完整的BP算法，对于满足 的 和 执行如下步骤： (1) 初始化： ，                               （2-5） (2) 校验节点更新： ，                 （2-6） (3) 变量节点更新： ，   （2-7） 其中 是一个使得等式 成立的值。 (4) 后验概率更新： ， 。              （2-8） 其中 是一个使得等式 成立的值。 (5) 比特判决：如果 ，则判决 ；否则，判决 。 其中 ， 。 若 ，则表示译码正确，结束译码，否则，重复步骤（2）~（5），直至译码正确或者迭代次数达到所设定的上限值。 3  高斯信道下LDPC编译码算法仿真 下面对LDPC码译码算法仿真中主要采用BPSK编码，信道采用高斯白噪声信道。 先对数据通过生成矩阵G进行编码，进行BPSK调制，送入高斯白噪声信道，通过校验矩阵H进行译码操作。其中生成矩阵的构造采用Mackay构造法。利用概率BP算法译码，并且计算出误码率。在仿真过程主要通过对不同码率的码进行编码译码的过程和对比分析。 码率为1/2，码长为512的误码率仿真图3-1如下所示： 图 3-1  码率为1/2的LDPC码译码误码率图 码率为2/3，码长为384的仿真结果图3-2如下所示： 图 3-2  码率为2/3的LDPC码译码误码率图 码率为0.75，码长为340的仿真结果如图3-3所示： 图 3-3  码率为3/4的LDPC码译码误码率图 三种码型的对比如图3-4所示： 图 3-4  三种码型的译码误码率对比 从仿真结果可以看出在低信噪比的情况下码率为1/2码，码长为512的码性能最好，平均误比特率降到 以下，而另外两种码型性能不是很好，尤其码率为3/4，码长为340的码，基本没什么纠错能力。但是总体来说，仿真结果并不是很理想，而由于数据量的问题导致代码运行时间很长，还有优化的空间。 4  结论 本文简单地对LDPC编码译码算法在高斯加性信道下进行Matlab仿真，并且对三种不同码型进行比较分析，得出码率对LDPC译码的误码性能的影响，可知短码性能不如长码，码率越高，性能越差。但是仿真过程存在不少问题。运行时间长，可重入性不强，需要改进，而且可以增加对迭代次数的探讨。但是总体来说，基本实现了对LDPC编译码的仿真，加深了对LDPC译码算法的理论学习。 参考文献 ［1］ 董同昕，陈为刚，柳元．LDPC码改进的量化自适应偏移最小和算法［J］．计算机工程与应用，2014，50（41）：203～206 ［2］ 曹海燕，李君，韦岗．低密度校验码（LDPC 码）［J］．电路与系统学报，2008，12（2）：95～102 ［3］ 李昂，罗汉文，陈强．基于置信传播的LDPC 码译码算法［J］．计算机工程，2005，31（20）：38～40 ［4］ 董同昕．LDPC 码低复杂度译码算法研究［D］．［硕士学位论文］．天津大学．2010 ［5］ 曹雪虹，张宗橙．信息论与编码［M］．清华大学大学出版社．2009 ［6］ 王新梅，肖国镇．纠错码原理与方法［M］．西安电子科技大学出版社．2004 ［7］ 甘毅．LDPC码编译码算法研究［D］．［硕士学位论文］．南京理工大学．2010 ［8］ 刘磊．多元LDPC码奇偶校验矩阵的构造方法、编码算法及量化［D］．［硕士学位论文］．中山大学．2009