一种新颖的并行级联LDPC码译码算法*

范文同，马林华，林志国

（1.空军工程大学航空航天工程学院，西安　710038；2.空军工程大学装备管理与安全工程学院，西安　710051）



一种新颖的并行级联LDPC码译码算法*

范文同1，马林华1，林志国2

（1.空军工程大学航空航天工程学院，西安710038；2.空军工程大学装备管理与安全工程学院，西安710051）

摘要：针对传统的并行级联低密度奇偶校验码（PCGC）译码算法采用串行算法导致译码延迟大，难以在实时通信系统中应用的问题，提出了一种新颖的PCGC码译码算法，该算法通过对各子码进行并行消息迭代，对相同的信息位进行变量消息联合更新，实现了PCGC码的并行译码。理论分析和仿真结果表明，提出的PCGC码译码算法相较于传统译码算法译码延迟降低，信噪比较低时误码率性能弱于后者，信噪比较高时，误码率性能优于后者。

关键词：译码，延迟，误码率，联合，并行级联低密度奇偶校验码

0　引言

LDPC码［1］是迄今为止发现的最接近香农限的好码之一［2］。随着计算机技术的飞速发展和硬件集成技术的提高，LDPC码优异的纠错性能吸引了诸多学者的研究，其工程化应用研究也逐渐兴起［3-5］。目前，LDPC码已被WiMAX、DVB-S2等通信标准作为信道纠错码字［6-7］。

PCGC码是一种将LDPC码运用于并行级联编码结构而得到的编码方式。文献［8］首次提出了并行级联LDPC码的概念，并给出了编译码结构；文献［9］在并行级联译码中引入了最小和译码算法，降低了译码复杂度；文献［10］提出了两种低复杂度的并行级联码译码迭代终止准则，降低了译码器时延；文献［11］构造了结构化的并行级联码，提高了编译码的效率；文献［12］在传统并行级联码编码结构的基础上，将信息位复制2份编码传输，高信噪比下性能得到了提高；文献［13］采用两个相同的子码构造并行级联码结构。相较于文献［8］中传统的PCGC码，文献［12-13］都是通过改变或限制PCGC码结构来获得更好的译码性能。文献［13］还通过部分并行译码，比传统译码算法提高了译码收敛速率。传统的PCGC码译码算法采用的是子码串行译码算法，延迟较大，难以在低延迟应用场合如实时通信系统中应用，且相较于文献［12-13］的误码率性能也较差。

本文针对PCGC码传统译码算法中存在的上述问题，提出了一种新的译码算法，通过对各子码进行并行的消息迭代，对相同的信息位进行变量消息联合更新，实现了PCGC码的并行译码，降低了译码延迟。仿真结果表明，本文提出的算法进一步提升了较高信噪比下的误码率性能。

1并行级联LDPC码

PCGC码由多个被称为子码的LDPC码级联构成，文献［8］提出的PCGC码编码结构如图1所示。其余已知文献中的PCGC编码结构都是图中所示结构或是基于此结构的变体。图中，s0为信息比特X的直接复制，s1和s2是信息比特X通过编码器1和编码器2分别编码后产生的校验比特。s=［s0，s1，s2］即为PCGC编码后生成的码字。

图1　PCGC编码器结构

令编码器生成的码字s经过调制和信道后在接收端接收到的对应数据为y=［y0，y1，y2］，即y0对应的是信息位s0在接收端的信号，y1、y2分别对应的是校验位s1、s2在接收端的信号，则PCGC码典型译码器结构如图2所示。

图2　PCGC译码器结构

图2中，译码器1和译码器2先后进行迭代译码，译码方式采用LDPC码译码算法。译码器1迭代后生成传递给译码器2的外部信息p1e，译码器2迭代后生成传递给译码器1的外部信息p2e，译码器1第一次迭代时，p2e值初始化为0。

可以看出，传统PCGC码译码算法中译码器1和译码器2为串行关系，译码器2需要译码器1计算出外部信息p1e后才能开始消息迭代，在一定程度上相较于单个LDPC码增加了译码延迟。

2本文提出的译码算法

定义PCGC码的两个LDPC子码的校验矩阵分别为H1和H2。不失一般性，随机设置H1和H2如式（1）和式（2）所示，H1和H2的前部分表示系统信息位，后部分表示校验位。

由文献［8］中PCGC码定义可知，校验矩阵H1和H2的前3个符号对应相同的系统信息位，两个校验矩阵可联合表示如式（3）所示。由基于置信传播的LDPC码译码算法可知，新构成的矩阵H的前3个符号可联合更新变量信息。

以H中第一行第一列元素对应的变量消息更新为例，除式（3）所示外，也可用Tanner图表示如下：

图3　PCGC码h11处对应的变量消息更新

信息位在矩阵H中对应的h11处的变量节点与矩阵H1和H2中共4个校验节点连接，变量消息可由这4个校验节点联合更新。

基于上述思想，本文提出的PCGC码译码器架构如下页图4所示。

令两个校验矩阵的维数分别为M1×N1和M2× N2，对应于其的接收端信息分别为y和y'，子译码器采用最小和译码算法，本文提出的PCGC译码算法具体步骤如下：

图4　本文提出的PCGC译码器结构

①初始化。分别计算由信道获得的两个子译码器变量节点的初始概率似然比消息L1（Pi），L2（Pi''），，并对其相邻的校验节点赋值，变量消息分别表示为L1（qij）和L2（q'i'j'），表达式如下：

②分别对每个子译码器进行校验消息更新，校验消息分别表示为，计算表达式如下：

式中，Vj和Vj''分别表示H1中与校验节点j相连的变量节点的集合和H2中与校验节点j'相连的变量节点的集合，Vji和Vj''i'分别表示Vj中除i外的变量节点的集合和Vj''中除i'外的变量节点的集合。

③分别对每个子译码器进行变量消息更新，表达式如下：

式中，Ci和Ci''分别表示H1中与变量节点i相连的校验节点的集合和H2中与校验节点i'相连的校验节点的集合，Ci j和Ci'' j'分别表示Ci中除j外的校验节点的集合和Ci''中除j'外的校验节点的集合。

④判决消息更新。

⑤两个子码均校验成功或达到设定的最大迭代次数则输出译码结果，否则重复前述步骤。

可以看出，本文提出的PCGC码译码算法每个步骤均可实现两个子LDPC码的并行译码，即实现了PCGC码的并行译码机制，相较于传统译码算法的串行译码机制提高了译码迭代速率。

3仿真结果与分析

采用与文献［8］中相同构造的码长为1 920，码率为1/3的PCGC码，子译码器均采用最小和译码算法，传统译码算法最大迭代次数设置为50次，本文提出的译码算法最大迭代次数设置为25次，分别仿真在传统PCGC译码算法和本文提出的译码算法下的性能。仿真结果如图5所示。

图5　码长1 920，码率1/3 的PCGC码译码性能

图6　码长600，码率1/3的PCGC码译码性能

采用与文献［13］中相同构造的码长为600，码率为1/3的PCGC码，子译码器均采用最小和译码算法，其余设置同上，分别仿真在传统PCGC译码算法和本文提出的译码算法下的性能。仿真结果如图6所示。

由图5和图6可以看出，对于短PCGC码和中长PCGC码，本文提出的译码算法在信噪比较高时误码率性能均好于PCGC码传统译码算法。本文提出的PCGC码译码算法采用并行译码机制，相较于传统译码算法串行机制，加快了译码迭代速率，提高了收敛速度，正因如此，在低信噪比时，本文提出的译码算法要差于传统译码算法，原因是低信噪比下，本文提出的算法加速了错误信息的扩散。

4　结论

提出了一种新的并行级联LDPC码译码算法，相较于传统的译码算法，本文算法实现了各子码的并行译码，提高了译码速率，降低了译码延迟，且信噪比较高时误码率性能更优。本文提出的算法更便于PCGC码在实际工程应用中实现。但是，本文对于PCGC码各子码结构对新算法的影响未作分析，有待下一步继续研究。

参考文献：

［1］GALLAGER R G.Low-density parity-check codes［J］.IRE Transactions on Information Theory，1962，8（1）:21-28.

［2］MACKAY D J C，NEAL R M.Near shannon limit performance of low-density parity-check codes［J］.Electronics

Letters，1996，33（6）:457-458.

［3］TAGHAVI M H，SHOKROLLAHI A，SIEGEL P H.Efficient implementation of linear programming decoding［J］.IEEE Transactions on Information Theory，2011，57（9）:5960-5982.

［4］张立军，刘明华，卢萌.低密度奇偶校验码加权大数逻辑译码研究［J］.西安交通大学学报，2013，47（4）:35-38.

［5］TIWARI H D，HUYNH N B，YONG B C.Flexible LDPC decoder using stream data processing for 802.11n and 802.16e ［J］.IEEE Transactions on Consumer Electronics，2011，57 （4）:1505-1512.

［6］YONGMIN J，YUNHO J.Low-complexity multi-way and reconfigurable cyclic shift network of QC-LDPC decoder for Wi-Fi/WIMAX applications［J］.IEEE Transactions on Consumer Electronics，2013，59（3）:467-475.

［7］JENFA H，CHUN M H，CHAO C Y.Construction of one-coincidence sequence quasi-cyclic LDPC codes of large girth［J］.IEEE Transactions on Information Theory，2012，58（3）:1825-1836.

［8］BEHAIRY H，CHANG S.Parallel concatenated gallager codes［J］.Electron Letters，2000，36（24）:2025-2026.

［9］LI J，YOU X H，YUN H K.Low complexity decoding algorithm of parallel concatenated LDPC code［J］.Proceedings of the IEEE 6th Circuits and Systems Symposium on Emerging Technologies，2004（1）:289-291.

［10］李晋，滑翰，华惊宇，等.并行级联LDPC码译码迭代终止准则研究［J］.通信学报，2006，27（4）:95-100.

［11］SERRATO J C，O’FARRELL T.Structured parallel concatenated LDPC codes［C］//In the Annual London Conference on Communications（LCS 2006），2006.

［12］CATHERINE P C.Parallel concatenation of LDPC codes with two sets of source Bits［C］//2011 4th International Conference on Emerging Trends in Engineering and Technology，2011，112-115.

［13］KUMAR，PRAVIN R.An efficient methodology for parallel concatenation of LDPC codes with reduced complexity and decoding delay［C］//2013 National Conference on Rakhesh Singh Communications（NCC），2013.

A Novel Decoding Algorithm for Parallel Concatenation of LDPC Codes

FAN Wen-tong1，MA Lin-hua1，LIN Zhi-guo2
（1.School of Aeronautics and Astronautics Engineering，Air Force Engineering University，Xi’an 710038，China；2.School of Equipment Management and Safety Engineering，Air Force Engineering University，Xi’an 710051，China）

Abstract：A novel decoding algorithm for parallel concatenation of LDPC codes is proposed for solving the problem of the high decoding latency in traditional PCGC decoders which are not suitable for real-time communication applications.Through parallel message passing operations for component LDPC codes in a PCGC code and combination updates for the same systematic message bit，the proposed algorithm realizes a fully parallel decoding manner，replacing the serial manner used in traditional ones.Theory analysis and simulation results show that the proposed algorithm can achieve lower decoding latency and better BER with high SNR but worse BER with low SNR，compared with the traditional PCGC decoding algorithm.

Key words：decoding，latency，bit error rate，combination，Parallel concatenated Gallager codes

作者简介：范文同（1983-），男，江苏盐城人，博士。研究方向：信息编码。

*基金项目：国家自然科学基金资助项目（61201209）

收稿日期：2015-03-01修回日期：2015-05-16

文章编号：1002-0640（2016）03-0012-03

中图分类号：TN911.22

文献标识码：A