基于貪婪搜索的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.