低密度奇偶校验码译码算法性能分析及仿真.docVIP

低密度奇偶校验码译码算法性能分析及仿真 　　摘要：讨论了置信传播（BP）译码算法和在该算法基础上衍生的两种译码算法，对数似然率（LLR-BP）算法和最小和（Min-sum）算法；分析了三种译码算法的性能，并对分析结果进行了仿真验证。结果表明，在译码性能上LLR-BP算法与BP算法相当，前者比后者算法要简单，Min-sum算法虽然较BP和LLR-BP算法相比，损失了一定误码性能，但易于硬件实现，实用性较强。 　　关键词：LDPC码 信道编码 差错控制 纠错编码 计算机仿真 　　中图分类号：TN91 文献标识码：A 文章编号：1007-9416（2016）05-0000-00 　　低密度奇偶校验码（LDPC）是一种线性分组纠错码，当其采用迭代译码算法时，如和积（sum-product） 译码算法，具有逼近Shannon限的良好性能，其译码算法复杂度随码长呈线性增长，非常适合并行实现。正因如此，LDPC码受到了业界的广泛关注，已广泛应用于移动通信、光纤通信、卫星测控通信和数字视频等领域[1] [2]。 　　构造LDPC码时，其校验矩阵中的非零元素往往很少，正是由于校验矩阵具有这种稀疏的特性，因此出现了多种高效的译码算法，且纠错能力较强。LDPC译码采用的是消息传递（MP）算法，其基本算法有比特翻转（BF）算法和置信传播（BP）算法。BF算法只进行比特位的翻转等几种简单的运算，复杂度较低，因此硬件实现简单，但其性能相对较低，适用于硬件条件受限而性能要求较低的场合；而BP算法是将接收到的信息在变量节点和校验节点之间进行迭代运算，从而获得最大编码增益，因此具有很好的性能，同时复杂度也较高，广泛应用于对性能有较高要求的场合。 　　本文在介绍低密度校验编码的基础上，研究了置信传播（BP）算法、对数似然率（LLR-BP）算法、最小和（Min-sum）算法等三种译码算法，并对各种算法的复杂度、工程实现的难易度和优缺点进行分析，并对分析结果进行仿真验证。 　　1 低密度校验编码 　　LDPC编码的首要条件是构造一个符合条件的稀疏校验矩阵。根据校验矩阵结构不同，通常把LDPC码分为规则LDPC码和不规则LDPC码。规则LDPC码的校验矩阵每行每列的非零元素相同，而不规则LDPC码不受此规则限制。无论哪种，好的LDPC码，必须围绕无短环、无低码重码字、码间最小距离尽可能大的原则构造校验矩阵[3]。 　　传统的编码方法是将稀疏奇偶校验矩阵H经过高斯消元处理转换为生成矩阵G，再根据G来进行编码。如此的编码方法其生成矩阵的稀疏性难以保证，且会导致编码的运算和存储复杂性大大增加。对于线性编码来说，校验矩阵为H，编码后码字为c，则由校验等式性质H?c’=0，所以可以用校验矩阵直接编码，主要的编码方法有高斯消去的直接编码，LU分解编码，部分迭代编码算法等。本文仿真采用高斯消去的直接编码，将m?n校验矩阵H通过高斯消元和列变换改成如下形式H=[I|P]，I为m?m单位矩阵，P为m?（n-m）矩阵，编码后码字c写成c=[s|u]形式，u为输入码字，s为校验码字，由校验等式H?c’=0得，I?s’+P?u’=0，即s’=P?u’，则由c=[u s]可得编码后码字。 　　2 LDPC码译码算法 　　LDPC译码算法是以迭代运算为主，主要是基于二分图[6]结构的消息传递算法。二分图与校验矩阵H相对应，包含三种元素，方形节点、圆形节点及连接方形节点和圆形节点之间的边，对于M×N的校验矩阵H，方形节点Vc=（c0，c1，…，cM-1）称为校验节点，对应于校验矩阵中的列，圆形节点Vs=（s0，s1，…，sN-1）称为变量节点，对应于校验矩阵中的行。如果校验矩阵中的非零位于第i行第j列，则校验节点ci和变量节点sj之间存在一条边，如图1所示，为5×10的校验矩阵二分图表示。LDPC译码时各个节点的置信消息需要在变量节点和校验节点之间互相传递。 　　3 译码算法性能分析及计算机仿真 　　从第二节对三种译码算法的分析来看，LLR-BP译码算法虽然与BP算法接近，但是，由于其运算是在对数域进行，因此复杂度有所降低；而MIN_SUM算法则通过采用近似运算来降低复杂度，但是，近似运算导致了该算法性能会有所损耗。 　　3.1三种译码算法复杂度比较 　　文献[6]对概率域BP译码算法、LLR_BP译码算法和Min-sum译码算法的计算复杂度进行了对比，各种算法都是针对码率为1/2的（n，2p，p）规则LDPC码进行分析的。如表1所示。 　　由表1可以看出，在计算复杂度方面，BP算法最为复杂，LLR-BP算法次之，Min-sum算法计算量是最小的。 　　3.2三种译码算法性能比较 　　为了对BP算法、LLR_BP算法和MIN_SUM三种译码算法的性能进行