基于贪婪搜索的RC-LDPC编码序列打孔算法研究*

马 慧，吴彦鸿，王宏艳

（1.航天工程大学 电子与光学工程系，北京 101416；2.航天工程大学 航天信息学院，北京 101416）

0 引 言

随着航空航天活动的陆续开展，信息的传输方式已经从传统地基传输向新型天基传输方向转变，空间数据转发的需求量也在逐步增加。跟踪与数据中继卫星系统（Tracking and Data Relay Satellite System，TDRSS）是负责在轨航天器与地面站之间进行高覆盖率测控和数据转发的天基通信系统，具备跟踪测轨、数据中继等重要功能[1-2]。但是，现有中继卫星系统在中高轨道进行数据传输时，会面临信号衰减和电磁干扰的各种影响，无法保证通信链路的可靠性和通信质量[3]。

在目前保障通信系统稳定传输的方案中，信道编码技术是一项关键技术。随着航天任务中回传至地球站的数据转发量日益增加，传统的编码方案已难以满足TDRSS对于链路通信的全天时、高速率的传输需求。而LDPC编码作为目前发展前景最好的信道编码之一，是无线通信信道编码领域的研究热点[4-5]。

由于TDRSS通信信道具有时变性，链路存在损耗或者干扰，因此为保证通信可靠性，信道编译码器应具备码率自适应变换的能力[6-7]。而高性能码率兼容技术的采用，不仅可降低TDRSS系统实现复杂度，也可使整个通信过程更加灵活高效。码率兼容算法的相关研究呈现出繁荣发展的趋势，尤其是打孔算法构造的RC-LDPC编码只需要使用一对编译码器结构，且硬件实现复杂度低，是当前卫星时变信道中优先使用的差错控制编码[8]。现有打孔算法大多基于密度进化或者EXIT分析对打孔算法进行研究，尽管译码门限的性能得到了改善，但由于未考虑到繁冗的计算量和余留Tanner图的内在特性，无法保证打孔码字的最终性能[9-11]。文献[12]提出的基于序列准则的打孔方案，首次对打孔后余留的Tanner图内在连通性方面进行考虑，具有实现简单、灵活性强的优点，但由于忽视了到变量节点错误恢复概率的因素，打孔节点性能仍存在优化空间。因此，本文提出一种基于贪婪搜索的序列准则打孔算法，以实现码率提升后误码性能的改善。

1 变量节点恢复树

在LDPC码字进行译码时，若某校验节点的邻居节点集合中只存在一个删余节点，那么删余节点的纠错能力可通过校验节点的消息传递而恢复，这类校验节点称为幸存校验节点（Survived Check Node，SCN）。若校验节点的邻居节点集中存在多个删余节点，该删余节点无法获得校验节点的消息传递而无法恢复校验能力，这类节点称为死亡校验节点（Dead Check Node，SCN）。随着删余节点的恢复过程，部分死亡校验节点可逐渐转化为幸存校验节点。同时，满足一次迭代后恢复的删余节点称为一步恢复（1-Step Recoverable，1-SR）节点，满足k次迭代恢复的为k-SR节点，而未被打孔节点为0-SR节点，且删余节点可进一步转化为恢复树的结构进行分析[13]。

首先假设n-SR节点vj为根节点，根据最大迭代次数n对节点进行分组，0-SR节点对应集合0G，k-SR节点对应集合kG，n-SR对应集合nG。其次，寻找其SCN子节点连接，然后进一步寻找删余节点和未删余节点进行连接。最后，重复上述操作，直至所有叶子节点均满足0-SR，最终得到的恢复树结构如图1所示，其中实心圆表示未打孔节点，空心圆表示打孔节点。可知，经过首次迭代后，所有的1-SR节点可恢复校验能力；经过第二次迭代，可恢复出2-SR节点的校验能力；重复上述操作，直至恢复出根节点。

图1 节点恢复树结构

2 基于贪婪搜索的序列打孔算法

基于贪婪搜索的序列打孔算法的本质是通过贪婪搜索保证从低到高恢复级别的k-SR节点最大化，再针对同一级别的k-SR节点，根据打孔图样的环连接性度量打孔节点的优先级别，以改善码率兼容码字的性能。

近似环外信息度（Approximate Cycle Extrinsic message degree，ACE）作为校验矩阵中环连通性的有效度量，同样是打孔过程中值得考虑的重要因素[14]。低ACE值的连接环一旦由于噪声影响引起停止集的状态恶化，环中变量节点的连通性和译码性能将难以保证。出于对环结构中停止集的考虑，给出所有环通用的近似环外消息度公式[15]：

它为有效度量余留Tanner图的内在特性，定义变量节点vj对应的总近似环外消息度为：

式中，L表示变量节点参与的最短环。

对于特定的MN×维校验矩阵H，将矩阵中的变量节点根据所需恢复迭代次数分成G0,G1,…,Gn、J∞组，其中0G对应为0-SR节点集，nG对应为n-SR节点集。设I和J分别表示校验矩阵的行索引集和列索引集，I∞和J∞表示矩阵中未分配的行、列索引集。H中各行对应的列索引子集表示为理，各列对应的行索引集合为Rw= Γ(j) ∩ J ，其中Γ( i ) = { i: Hi,j= 1 ,1 ≤ j≤ m }。 Pk表示打孔后码率为 rk的删余节点的列索引集，n表示打孔节点所需恢复的最大迭代次数。基于序列准则的贪婪搜索打孔算法流程图，如图2所示。

图2 基于序列准则的贪婪搜索算法流程

贪婪搜索算法是一种次优化算法且计算复杂度低，在LDPC编码的构造中具有重要意义。贪婪算法的实质是在当前面临的条件下做出最佳抉择，以得到局部最优解。首先计算I∞中行索引集合Rw的最小值minRw，并在minRw中寻找列索引集合的最小值min Cw，同时找出对应节点组成序列对D = {}。当中存在多对节点时，选择的删余序列应满足错误恢复概率最低。高斯信道中的变量节点的错误概率表达式为：

式中，Q函数满足单调递减。 mu( v)表示变量节点接收的消息期望，其函数表达式为：

式中表示信道v中 接收的LLR信息均值，S( v ) = 表γ示 j对应的节点恢复树中0-SR节点的数量，j表示幸存校验节点的邻居点集。函数φ(x)的表达式为：

可知，φ(x)函数在定义域内单调递减。根据式（4）可知， v j对应的 S ( v)越大， mu( v)越小，对应的节点错误概率 Pe( v)越大。因此，为保证错误概率最低，需选取具备最小的 S ( v)的打孔序列，使其连接的0-SR点最少。

对于每一级的k-SR节点，进行I∞、J∞和S( v)的贪婪搜索，直至得到不同恢复级别的节点集。依次从G1,G2,…,Gn节点集中进行打孔节点的选择，码率 rk对应的打孔节点数目为：

式中，打孔节点数应满足 n pk＜npmax。初始化打孔时， P0满足为φ，判断 ∆ n pk≠ 0 ，需从当前集合 G1中取值。若 G1中存在多个候选方案，选择 G1中具有最大SCN的变量节点集 G1'作为候选。若 G1'中存在多个候选方案，选择具有最大TotalACE的变量节点作为打孔节点输出。打孔节点 v j选择结束后，再对pk、Gn和∆npk进行更新，便于下一次打孔节点的选择。由此可见，当迭代次数k值较小、对应的k-SR越多时，子码的恢复性能越好。

3 仿真实验与性能分析

为验证打孔算法的性能，本节采用经PEGACE两步扩展得到的（1 024，2 048）原模图AR4JA编码[16]作为母码进行打孔分析，译码过程中将删余节点对应的初始信息置零。调制方式采用BPSK，信道为AWGN信道。译码采用BP译码，最大迭代次数同样设置为80次，在每个信噪比条件下将实验次数设置为107量级。对RC-AR4JA编码母码采用基于贪婪搜索的序列打孔算法进行打孔仿真，同时将随机删余算法[17]和基于序列准则的打孔算法[12]作为对比，构造分别为0.6、0.7和0.8的不同码率RC-AR4JA编码子码。误码性能仿真对比结果，如图3、图4和图5所示。

图3 不同打孔算法构造的LDPC编码（R=0.6）性能对比

图4 不同打孔算法构造的LDPC编码（R=0.7）性能对比

图5 不同打孔算法构造的LDPC编码（R=0.8）性能对比

其中实线表示子码码字的误比特率，虚线表示子码码字的误帧率，“贪婪搜索”表示本文设计的基于贪婪搜索的序列打孔算法，“序列打孔”表示基于序列准则的打孔算法，“随机打孔”表示随机打孔算法。

根据上述仿真对比结果可知以下结论：

（1）子码码率为0.6时，在10-6误码率水平上，贪婪搜索打孔相比随机打孔算法存在0.5 dB的信噪比优势，相比序列打孔算法存在0.08 dB的微弱优势。此时，删余节点数目相对较少，因此节点恢复级别对删余码字的性能影响相对较小。

（2）随着打孔目标码率增加为0.7时，在10-6误码率水平上，贪婪搜索打孔与随机打孔相比有1 dB的性能优势，相比序列打孔算法存在0.2 dB的性能优势。伴随着码字中冗余变量节点的进一步删余，译码过程中会涉及到高级别删余节点的恢复。贪婪搜索打孔中最大化低恢复级别节点的打孔准则，能够在一定程度上提升节点的恢复可靠度。

（3）当打孔目标码率进一步增加至0.8时，在误码率10-6水平上，贪婪搜索打孔与随机打孔算法之间的优势明显，相比序列打孔算法相比存在0.5 dB的性能优势。由于码字中冗余变量节点大部分被删除，译码过程中删余变量节点的可靠性降低，译码性能逐渐出现损失。贪婪搜索打孔中最大化幸存校验节点和TotalACE的打孔准则，可在一定程度上提升节点的错误恢复概率，同时优化删余码字的环分布特性。

4 结 语

针对TDRSS通信系统码率自适应变换技术的应用需求，提出一种基于贪婪搜索的RC-LDPC编码序列打孔算法，兼顾了编码的错误恢复特性和内在环连接特性。相比传统的打孔算法，该算法可实现更好的译码性能和更低的译码复杂度。尤其是在高码率时，子码的性能优势更加突出。因此，该算法适用于采用高码率LDPC编码的TDRSS高速数传链路。

参考文献：

[1] Teles J,Samii M V,Doll C E.Overview of TDRSS[J].Advances in Space Research,1995,16(12)：67-76.

[2] 王家胜,齐鑫.为载人航天服务的中国数据中继卫星系统[J].中国科学(技术科学),2014(03)：235-242.WANG Jia-sheng,QI Xin.The Chinese Data Relay Satellite System for Manned Space Flight[J].Science of China(Technology),2014(03)：235-242.

[3] 马慧,吴彦鸿.跟踪与数据中继卫星系统抗干扰技术[J].兵器装备工程学报,2017(07)：123-128.MA Hui,WU Yan-hong.Research on TDRSS System Anti-jamming Technology[J].Journal of Ordnance Equipment Engineering,2017(07)：123-128.

[4] Thorpe J.Low-Density Parity-Check(LDPC) Codes Constructed from Protographs[R].Interplanetary Network Progress Report,2003：154.

[5] 易旭,杜昊阳.LDPC码的研究进展和应用展望[J].通信技术 ,2016,49(01)：1-6.YI Xu,DU Hao-yang.Progress and Application Prospect of Generalized LDPC Codes[J].Communications Technology,2016,49(01)：1-6.

[6] 王家胜.我国数据中继卫星系统发展建议[J].航天器工程 ,2011(02)：1-8.WANG Jia-sheng.Proposal for Developing China's Data Relay Satellite System[J].Spacecraft Engineering,2011(02)：1-8.

[7] 翟政安.下一代数据中继卫星系统发展思考[J].飞行器测控学报 ,2016,35(02)：89-97.ZHAI Zheng-an.Development of Next Generation Data Relay Satellite Systems[J].Journal of Spacecraft TT&C Technology,2016,35(02)：89-97.

[8] 章谦骅.深空通信中RC-LDPC码构造及误码平底分析[D].杭州：电子科技大学,2015.ZHANG Qian-ye.RC-LDPC Codes Construction and Error Flat Analysis in Deep Space Communication[D].Hangzhou：Dianzi University,2015.

[9] Vellambi B N,Fekri F.Finite-length Rate-compatible LDPC Codes：a Novel Puncturing Scheme[M].IEEE Press,2009.

[10] 王志娜,肖旻,王琳.码率自适应原模图LDPC码的设计[J].重庆邮电大学学报(自然科学版 ),2012,24(01)：55-59.WANG Zhi-na,XIAO Wen,WANG Lin.Design of Ratecompatible Protogragh LDPC Codes[J].Journal of Chongqing university of Posts and Telecommunications(Natural Science Edition),2012,24(01)：55-59.

[11] Wei Y,Yang Y,Jiang M,et al.Joint Shortening and Puncturing Optimization for Structured LDPC Codes[J].IEEE Communications Letters,2012,16(12)：2060-2063.

[12] 陈州辉.IEEE 802.1lac码率兼容LDPC码研究[D].成都：西南交通大学,2015.CHEN Zhou-hui.Research on Rate-Compatible LDPC Codes for IEEE 802.11ac Standard[D].Chengdu：Southwest Jiaotong University,2015.

[13] Ha J,Kim J,Klinc D,et al.Rate-compatible Punctured Low-density Parity-check Codes with Short Block Lengths[J].IEEE Transactions on Information Theory It,2006,52(02)：728-738.

[14] Tian T,Jones C R,Villasenor J D,et al.Selective Avoidance of Cycles in Irregular LDPC Code Construction[J].Communications IEEE Transactions on,2004,52(08)：1242-1247.

[15] 包建荣,高西奇,刘超等.扩展原模图LDPC短码的优化构造[J].华中科技大学学报(自然科学版 ),2016,44(05)：35-40.BAO Jian-rong,GAO Xi-qi,LIU Chao.Optimal Construction of Extended Protograph LDPC Short Code[J].Journal of Huazhong University of Science and Technology(Natural Science Edition),2016,44(05)：35-40.

[16] 杨明川,吕谷,陈佳音等.深空通信中基于原模图的AR4JA码性能分析[C].中国宇航学会深空探测技术

专业委员会学术年会,2012.

YANG Ming-chuan,LV Gu,CHEN Jia-yin,et al.Performance Analysis of AR4JA Code Based on Original Model in Deep Space Communication[C].China Aerospace Association Deep Space Exploration Technology Professional Committee Academic Annual Meeting,2012.

[17] Varnica N,Soljanin E,Whiting P.LDPC Code Ensembles for Incremental Redundancy Hybrid ARQ[C].Information Theory,2005：995-999.