低密度奇偶校验码译码算法及其性能仿真研究

陈静

（六六ΟΟ八部队 天津 300250）

低密度奇偶校验码 （Low-Density Parity-Check codes，LDPC码）是目前通信纠错码领域的热门研究之一，是第四代移动通信系统强有力的竞争者[1-3]。它的编码增益接近香农极限，硬件复杂度又低于turbo码，因此无论在理论上还是在未来通信系统中，低密度奇偶校验码都有着广泛的应用前景。

LDPC码译码算法中性能最好的是连续性的 BP（Belief Propagation）算法[4-5]，BP算法本质上是并行算法，有利用硬件的并行实现，减少译码时延。文章对译码方法中的典型算法（BF算法和BP算法）和一种改进的对数域算法（APP-LLR算法）进行了仿真研究，比较并分析了信噪比、码长和迭代次数等参数对译码性能影响。

1 LDPC码的译码与仿真

LDPC的译码算法大体上可以分为两大类：基于树形图的硬判决译码算法和软输入/软输出的软判决译码算法[6]。硬判决算法简单可行但性能不够好，适合校验集比较小的情况；软判决主要是基于消息传递（Message Passing）的置信传播算法[7]。

1.1 LDPC码的硬判决译码

1.1.1 比特翻转（Bit_Flip ，BF）算法译码复杂度

当传输中发生可检测错误时，反应在特征子s=（s1，s2，…，sM）上将有失败的校验，也就是某些特征子比特等于“1”。比特翻转算法就是基于改变接收信息中的比特来减少失败校验的数目，从而得到正确的译码信息。

首先，译码器检验所有的校验位，如果某信息位上不符合校验约束的数目超过一个设定的固定值δ时，就改变这个信息位的值。在重新得到这些新的信息位值之后，重新计算所有的校验位并改变新的需要改变的比特值。依次重复直到满足所有的校验约束条件。显然，这是一种迭代算法。参数δ，被称为BF算法的门限。应该优化门限使得错误性能得到改善并减少计算全部校验特征子的数目。门限依赖于码的度分布和信噪比。设码字向量x经过BSC信道接收的硬判决值为，s为伴随式向量，比特反转（BF）译码算法可简单描述为：

首先计算方程s=zHT，统计每位接收值yi不满足校验方程的个数。

找出不满足校验方程最多的zi，如不满足的个数大于δ，将其翻转，得到新的向量z′。

判断条件：由向量z′代替计算方程s=zHT，如s=0则正确译码输出。否则重复1-3步，反复迭代，直到迭代至最大迭代次数。

由于校验矩阵为稀疏矩阵，而且一般为随机构成，所以参与每个校验方程的比特很少，且这些比特在码字上分布很分散，那么任一校验方程所含的比特要么无错，要么以很高概率出现只有一个比特错误，BF算法就可以有效地进行纠错。即使某一校验方程发生多于一个错误，纠错仍可以进行。如图1所示为某一比特位d的校验集合的树型结构。最底层的根节点表示比特d，从d出发的每一条边表示d参与的校验方程。每一层横线的节点表示参与该校验方程的其他比特，依次类推到第二层、第三层。假设节点d和e出错，那么在第一次译码中，第二层正确节点会纠正错误节点。进而在下一步译码过程中节点d也会被纠正。由此得出：由于树形结构，不与节点d直接相连的比特对节点d的纠正也有帮助。

图1 校验集合树Fig.1 Check-collection tree

图2为在不同信噪比下采用比特翻转（BF）算法译码的误码率性能仿真结果。此处采用的是码型为（512，3，6）码。BF算法容易实现，对硬件复杂度要求不高，但是译码性能较差，当翻转次数增多时，易产生误翻转的现象。从图2可以看出，BF算法整体性能较差，当信噪比从0~3 dBm时，误码率变化范围比较小，而且比较大。但误码率整体随信噪比增大而减小，实际情况也应该如此。

图2 BF算法译码信噪比性能仿真Fig.2 BF algorithm decoding SNR performance simulation

1.1.2 LDPC码的软判决译码算法

LDPC码软译码算法译码复杂度较高，但可以获得更好的译码性能，并且可以通过基于置信传播（Belief Propagation，BP）算法的迭代译码来实现。由于BP算法中涉及到许多非线性的运算，为减小运算复杂度，一些简化的软译码算法被陆续的提出，其中包括迭代后验概率 （after iteration posterior probability，APP）译码算法、基于BP的最小和或最大积译码算法（UMP BP）、归一化的BP译码算法以及改进的BP译码算法（Improved BP）等[8]。

假定一个校验矩阵H来决定一个LDPC码字。集合M（n）表示与比特节点n相连的校验节点的集合。M（n）m表示集合M（n）中不包含校验节点m的集合；N（m）表示与校验节点m相连的比特节点的集合。N（m） 表示N（m）集合不包含比特节点n的集合。

1.1.3 对数域BP译码算法

概率域译码需要大量的乘法，复杂度较高，如果概率消息用似然比表示，则得到基于对数域的置信传播算法（Loglikehood-ratio-based-progration，LLR BP算法），即将译码转化到对数域中进行，大量的乘法运算可以变化为加法运算，从而减少运算时间。

则LLR-BP算法译码过程如下：

初始化：计算信道传递给变量节点的初始概率似然比消息 L（Pi），i=1，2，3，…N。 然后对每一个变量节点 i∈C（i）和其相邻的校验节点，设定变量节点传向校验节点的初始消息：

迭代处理

步骤1：校验节点消息处理。

对所有的校验节点j和其相邻的变量节点i∈R（j），第 l次迭代时，计算变量节点传向校验节点的消息

或：

步骤2：变量节点消息处理

对所有的变量节点i和其相邻的校验节点 i∈R（j），第 l次迭代时，计算校验节点传向变量节点的消息

步骤3：译码判决。

对所有变量节点计算硬判决消息

停止迭代

若Hc^i=0或者达到最大迭代次数，则运算结束，否则从步骤1继续迭代。图3为在不同信噪比下采用对数域BP算法译码的误码率性能仿真结果。此处采用的码型为（512，3，6）LDPC码。

由于BP算法是基于软判决和消息传递设计的，它们的性能相对上图的BF算法而言，性能有了非常明显的提高。从图2可以看出的确如此，信噪比在0~3 dB变化中，BF算法误码率下降程度低，且比较大。BP算法在信噪比为3 dB时，误码率基本达到了10-4数量级，这样的译码效果是以前许多纠错码型无法达到的，完全体现了LDPC码的优越性能。

图3 对数域BP算法译码信噪比性能仿真Fig.3 BP algorithm in log-domain decoding SNR performance simulation

1.1.4 迭代APP算法

在对数域BP算法变量节点的处理中，虽然只有加法运算，但可以进一步降低算法的实现复杂度。

在LLR-BP算法，迭代处理过程中，将步骤1：校验节点消息处理中的 L（qij）用 L（qi）代替，即 L（qi）不仅用于硬判决，而且用于求解校验消息，其他步骤同LLR-BP算法。此时BP算法简化为迭代的APP（A Posteriori Probability）算法。这样计算，传递的变量消息之间引进了相关性，传递的变量消息就不再是外部消息，但是此时仅仅需要计算和存储一个变量消息的数值，可以大大降低算法的复杂度。

图4为在不同信噪比下采用迭代APPBP算法译码的误码率性能仿真结果。此处采用的码型为（512，3，6）LDPC码。

图4 APPBP算法译码信噪比性能仿真Fig.4 APP BP algorithm decoding SNR performance simulation

从图4可看出当信噪比大于2.5 dB时，此种算法的优越性逐渐体现出来，当信噪比为3 dB时，用此种算法译码得出的结果误码率在10-4数量级以下，而对数域BP算法译码的结果误码率要大于10-4数量级。

图5是以上3种算法译码仿真结果对比示意图，由于BF算法误码率随信噪比的增加下降幅度小，故在图中趋于一条直线，而迭代APP算法在信噪比较大时对比对数域BP算法才有了一定优势。

图5 对数域BP、APP算法译码仿真结果对比Fig.5 Contrast between BF algorithm in log-domain and APP algorithm decoding simulation results

2 参数对LDPC码译码算法性能影响的仿真分析

以迭代APP算法为例，考虑了影响算法性能的两个参数：码长和迭代次数对译码性能的影响。如图6所示，是编码码长分别为 L=126，L=256，L=512，L=1024时 LDPC 码译码的性能对比。

图6 不同编码长度的LDPC码的性能对比Fig.6 The performance of the different length coding of LDPC codes

由图6中不同码长的仿真结果可以看出，码长是影响LDPC码性能的一个重要因素，随着码长的增长，LDPC码的误码性能越来越好。在信噪比为3 dB时，码长为1024的码比长为126的码在误码率上低了差不多一个数量级。同时也可以看到，当信噪比比较小的时候，增加码长对误码性能改善不大。码长的增加在一定程度上提高了误码性能，但也不能无限增大，因为译码复杂度是和码长有关的，随着码长增加，译码复杂度势必会增大。而且由于LDPC码是分组码，只有整个序列都译完才能得到译码输出，故增大编码码长会使译码时间延长。

在译码环节中一个重要的参数就是迭代次数。对于不同的LDPC码，除了要考虑其误码率性能，另外也要考虑其译码的复杂度。由于LDPC码的译码算法都是并行的迭代译码算法，所以译码的迭代次数是衡量译码复杂度、影响译码性能的一个重要参数，最好能取得译码性能和复杂度之间的均衡。

图7为不同迭代数的LDPC码迭代APP译码算法的性能。 选用的码型为（256，3，6），迭代次数分别为 1、2、5、10 和20次。从图7可以看出，随着迭代次数增加，误码性能会逐渐提高，迭代次数为1的性能最差，为20的性能最好。在信噪比为3 dB时，只有20次迭代译码的误码率达到了10-3数量级，而其他迭代次数都大于这个数量级。

图7 不同译码迭代次数的误码性能Fig.7 The ber performance of different decoding iterations

从图7中观察到，开始随着迭代次数的增加 （1次到5次），LDPC码的性能显著改善，这是因为经过迭代，比特节点和校验节点更充分地利用了外部信息，从而做出了更准确的判断，但是随着迭代次数不断增多（10次到20次），译码性能提高的趋势越来越缓慢。这是因为经过多次迭代后，外部信息具有很强的相关性，不能提供更新的纠错信息。但LDPC译码时，并不是每次都要达到译码迭代次数的上限，在满足校验等式就可以终止迭代，尽管如此在译码时，仍应权衡迭代次数和复杂度，以便能够在可接受的复杂度下取得较好的译码性能。

3 结束语

文中针对LDPC码译码算法进行仿真，比较了不同算法、不同码长和不同迭代次数情况下译码效果。结果表明，硬判决译码算法的误码性能对比软判决算法效果相差很大，但由于其译码复杂度和对硬件要求低，所以它仍会被使用。仿真还表明，误码率会随着码长和迭代次数的增加而减小，但它们都会增加译码的复杂度，故在译码时应权衡误码率和复杂度的关系。

[1]张用宇，吴东伟，左丽芬，等.低密度奇偶校验码构造及编译码研究进展[J].电讯技术.2012，52（8）:1395-1343.ZHANG Yong-yu，WU Dong-wei，ZUO Li-fen，et al.Survey on construction，encoding and eecoding of low-density parity-check codes[J].Telecommunication Engineering，2012，52（8）:1395-1343.

[2]陈为刚，殷柳国，陆建华.低密度奇偶校验码迭代译码算法的误码平台特性[J].清华大学学报：自然科学版，2009，49（1）:61-64.CHEN Weig-ang，YIN Liu-guo，LU Jian-hua.Error floor properties of low-density parity-check codes using iterative decoding algorithms[J].J Tsinghua Univ （Sci&Tech ），2009，49（1）:61-64.

[3]Fossorier M.Iterative reliablity-based decoding of low density parity check codes[J].IEEE J.Selcet.Areas Commun，2001（19）:908-917.

[4]董磊.低密度奇偶校验码编译码原理及实现 [D].西安：西安电子科技大学，2007.

[5]Jilei Hou，Paul H.Siegel，Laurence B.Performance Analysis and Code Optimization of Low Density Parity-Check Codes Codes on Rayleigh Fading Channels[J].IEEE Journal Select Areas in Communications.2001，19（5）:924-934.

[6]李晋.低密度奇偶校验码及其并行级联构造的研究[D].南京:东南大学，2006.

[7]徐进廷.LDPC码译码算法研究与仿真[D].兰州:兰州大学，2009.

[8]袁东风，张海刚.LDPC码理论与应用[M].北京:人民邮电出版社，2008.