馬 慧，吳彥鴻，王宏艷

（1.航天工程大學 電子與光學工程系，北京 101416；2.航天工程大學 航天信息學院，北京 101416）

0 引 言

隨著航空航天活動的陸續(xù)開展，信息的傳輸方式已經(jīng)從傳統(tǒng)地基傳輸向新型天基傳輸方向轉(zhuǎn)變，空間數(shù)據(jù)轉(zhuǎn)發(fā)的需求量也在逐步增加。跟蹤與數(shù)據(jù)中繼衛(wèi)星系統(tǒng)（Tracking and Data Relay Satellite System，TDRSS）是負責在軌航天器與地面站之間進行高覆蓋率測控和數(shù)據(jù)轉(zhuǎn)發(fā)的天基通信系統(tǒng)，具備跟蹤測軌、數(shù)據(jù)中繼等重要功能[1-2]。但是，現(xiàn)有中繼衛(wèi)星系統(tǒng)在中高軌道進行數(shù)據(jù)傳輸時，會面臨信號衰減和電磁干擾的各種影響，無法保證通信鏈路的可靠性和通信質(zhì)量[3]。

在目前保障通信系統(tǒng)穩(wěn)定傳輸?shù)姆桨钢?，信道編碼技術(shù)是一項關(guān)鍵技術(shù)。隨著航天任務(wù)中回傳至地球站的數(shù)據(jù)轉(zhuǎn)發(fā)量日益增加，傳統(tǒng)的編碼方案已難以滿足TDRSS對于鏈路通信的全天時、高速率的傳輸需求。而LDPC編碼作為目前發(fā)展前景最好的信道編碼之一，是無線通信信道編碼領(lǐng)域的研究熱點[4-5]。

由于TDRSS通信信道具有時變性，鏈路存在損耗或者干擾，因此為保證通信可靠性，信道編譯碼器應(yīng)具備碼率自適應(yīng)變換的能力[6-7]。而高性能碼率兼容技術(shù)的采用，不僅可降低TDRSS系統(tǒng)實現(xiàn)復(fù)雜度，也可使整個通信過程更加靈活高效。碼率兼容算法的相關(guān)研究呈現(xiàn)出繁榮發(fā)展的趨勢，尤其是打孔算法構(gòu)造的RC-LDPC編碼只需要使用一對編譯碼器結(jié)構(gòu)，且硬件實現(xiàn)復(fù)雜度低，是當前衛(wèi)星時變信道中優(yōu)先使用的差錯控制編碼[8]?，F(xiàn)有打孔算法大多基于密度進化或者EXIT分析對打孔算法進行研究，盡管譯碼門限的性能得到了改善，但由于未考慮到繁冗的計算量和余留Tanner圖的內(nèi)在特性，無法保證打孔碼字的最終性能[9-11]。文獻[12]提出的基于序列準則的打孔方案，首次對打孔后余留的Tanner圖內(nèi)在連通性方面進行考慮，具有實現(xiàn)簡單、靈活性強的優(yōu)點，但由于忽視了到變量節(jié)點錯誤恢復(fù)概率的因素，打孔節(jié)點性能仍存在優(yōu)化空間。因此，本文提出一種基于貪婪搜索的序列準則打孔算法，以實現(xiàn)碼率提升后誤碼性能的改善。

1 變量節(jié)點恢復(fù)樹

在LDPC碼字進行譯碼時，若某校驗節(jié)點的鄰居節(jié)點集合中只存在一個刪余節(jié)點，那么刪余節(jié)點的糾錯能力可通過校驗節(jié)點的消息傳遞而恢復(fù)，這類校驗節(jié)點稱為幸存校驗節(jié)點（Survived Check Node，SCN）。若校驗節(jié)點的鄰居節(jié)點集中存在多個刪余節(jié)點，該刪余節(jié)點無法獲得校驗節(jié)點的消息傳遞而無法恢復(fù)校驗?zāi)芰?，這類節(jié)點稱為死亡校驗節(jié)點（Dead Check Node，SCN）。隨著刪余節(jié)點的恢復(fù)過程，部分死亡校驗節(jié)點可逐漸轉(zhuǎn)化為幸存校驗節(jié)點。同時，滿足一次迭代后恢復(fù)的刪余節(jié)點稱為一步恢復(fù)（1-Step Recoverable，1-SR）節(jié)點，滿足k次迭代恢復(fù)的為k-SR節(jié)點，而未被打孔節(jié)點為0-SR節(jié)點，且刪余節(jié)點可進一步轉(zhuǎn)化為恢復(fù)樹的結(jié)構(gòu)進行分析[13]。

首先假設(shè)n-SR節(jié)點vj為根節(jié)點，根據(jù)最大迭代次數(shù)n對節(jié)點進行分組，0-SR節(jié)點對應(yīng)集合0G，k-SR節(jié)點對應(yīng)集合kG，n-SR對應(yīng)集合nG。其次，尋找其SCN子節(jié)點連接，然后進一步尋找刪余節(jié)點和未刪余節(jié)點進行連接。最后，重復(fù)上述操作，直至所有葉子節(jié)點均滿足0-SR，最終得到的恢復(fù)樹結(jié)構(gòu)如圖1所示，其中實心圓表示未打孔節(jié)點，空心圓表示打孔節(jié)點。可知，經(jīng)過首次迭代后，所有的1-SR節(jié)點可恢復(fù)校驗?zāi)芰?；?jīng)過第二次迭代，可恢復(fù)出2-SR節(jié)點的校驗?zāi)芰?；重?fù)上述操作，直至恢復(fù)出根節(jié)點。

圖1 節(jié)點恢復(fù)樹結(jié)構(gòu)

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

基于貪婪搜索的序列打孔算法的本質(zhì)是通過貪婪搜索保證從低到高恢復(fù)級別的k-SR節(jié)點最大化，再針對同一級別的k-SR節(jié)點，根據(jù)打孔圖樣的環(huán)連接性度量打孔節(jié)點的優(yōu)先級別，以改善碼率兼容碼字的性能。

近似環(huán)外信息度（Approximate Cycle Extrinsic message degree，ACE）作為校驗矩陣中環(huán)連通性的有效度量，同樣是打孔過程中值得考慮的重要因素[14]。低ACE值的連接環(huán)一旦由于噪聲影響引起停止集的狀態(tài)惡化，環(huán)中變量節(jié)點的連通性和譯碼性能將難以保證。出于對環(huán)結(jié)構(gòu)中停止集的考慮，給出所有環(huán)通用的近似環(huán)外消息度公式[15]：

它為有效度量余留Tanner圖的內(nèi)在特性，定義變量節(jié)點vj對應(yīng)的總近似環(huán)外消息度為：

式中，L表示變量節(jié)點參與的最短環(huán)。

對于特定的MN×維校驗矩陣H，將矩陣中的變量節(jié)點根據(jù)所需恢復(fù)迭代次數(shù)分成G0,G1,…,Gn、J∞組，其中0G對應(yīng)為0-SR節(jié)點集，nG對應(yīng)為n-SR節(jié)點集。設(shè)I和J分別表示校驗矩陣的行索引集和列索引集，I∞和J∞表示矩陣中未分配的行、列索引集。H中各行對應(yīng)的列索引子集表示為理，各列對應(yīng)的行索引集合為Rw= Γ(j) ∩ J ，其中Γ( i ) = { i: Hi,j= 1 ,1 ≤ j≤ m }。 Pk表示打孔后碼率為 rk的刪余節(jié)點的列索引集，n表示打孔節(jié)點所需恢復(fù)的最大迭代次數(shù)?；谛蛄袦蕜t的貪婪搜索打孔算法流程圖，如圖2所示。

圖2 基于序列準則的貪婪搜索算法流程

貪婪搜索算法是一種次優(yōu)化算法且計算復(fù)雜度低，在LDPC編碼的構(gòu)造中具有重要意義。貪婪算法的實質(zhì)是在當前面臨的條件下做出最佳抉擇，以得到局部最優(yōu)解。首先計算I∞中行索引集合Rw的最小值minRw，并在minRw中尋找列索引集合的最小值min Cw，同時找出對應(yīng)節(jié)點組成序列對D = {}。當中存在多對節(jié)點時，選擇的刪余序列應(yīng)滿足錯誤恢復(fù)概率最低。高斯信道中的變量節(jié)點的錯誤概率表達式為：

式中，Q函數(shù)滿足單調(diào)遞減。 mu( v)表示變量節(jié)點接收的消息期望，其函數(shù)表達式為：

式中表示信道v中 接收的LLR信息均值，S( v ) = 表γ示 j對應(yīng)的節(jié)點恢復(fù)樹中0-SR節(jié)點的數(shù)量，j表示幸存校驗節(jié)點的鄰居點集。函數(shù)φ(x)的表達式為：

可知，φ(x)函數(shù)在定義域內(nèi)單調(diào)遞減。根據(jù)式（4）可知， v j對應(yīng)的 S ( v)越大， mu( v)越小，對應(yīng)的節(jié)點錯誤概率 Pe( v)越大。因此，為保證錯誤概率最低，需選取具備最小的 S ( v)的打孔序列，使其連接的0-SR點最少。

對于每一級的k-SR節(jié)點，進行I∞、J∞和S( v)的貪婪搜索，直至得到不同恢復(fù)級別的節(jié)點集。依次從G1,G2,…,Gn節(jié)點集中進行打孔節(jié)點的選擇，碼率 rk對應(yīng)的打孔節(jié)點數(shù)目為：

式中，打孔節(jié)點數(shù)應(yīng)滿足 n pk＜npmax。初始化打孔時， P0滿足為φ，判斷 ? n pk≠ 0 ，需從當前集合 G1中取值。若 G1中存在多個候選方案，選擇 G1中具有最大SCN的變量節(jié)點集 G1'作為候選。若 G1'中存在多個候選方案，選擇具有最大TotalACE的變量節(jié)點作為打孔節(jié)點輸出。打孔節(jié)點 v j選擇結(jié)束后，再對pk、Gn和?npk進行更新，便于下一次打孔節(jié)點的選擇。由此可見，當?shù)螖?shù)k值較小、對應(yīng)的k-SR越多時，子碼的恢復(fù)性能越好。

3 仿真實驗與性能分析

為驗證打孔算法的性能，本節(jié)采用經(jīng)PEGACE兩步擴展得到的（1 024，2 048）原模圖AR4JA編碼[16]作為母碼進行打孔分析，譯碼過程中將刪余節(jié)點對應(yīng)的初始信息置零。調(diào)制方式采用BPSK，信道為AWGN信道。譯碼采用BP譯碼，最大迭代次數(shù)同樣設(shè)置為80次，在每個信噪比條件下將實驗次數(shù)設(shè)置為107量級。對RC-AR4JA編碼母碼采用基于貪婪搜索的序列打孔算法進行打孔仿真，同時將隨機刪余算法[17]和基于序列準則的打孔算法[12]作為對比，構(gòu)造分別為0.6、0.7和0.8的不同碼率RC-AR4JA編碼子碼。誤碼性能仿真對比結(jié)果，如圖3、圖4和圖5所示。

圖3 不同打孔算法構(gòu)造的LDPC編碼（R=0.6）性能對比

圖4 不同打孔算法構(gòu)造的LDPC編碼（R=0.7）性能對比

圖5 不同打孔算法構(gòu)造的LDPC編碼（R=0.8）性能對比

其中實線表示子碼碼字的誤比特率，虛線表示子碼碼字的誤幀率，“貪婪搜索”表示本文設(shè)計的基于貪婪搜索的序列打孔算法，“序列打孔”表示基于序列準則的打孔算法，“隨機打孔”表示隨機打孔算法。

根據(jù)上述仿真對比結(jié)果可知以下結(jié)論：

（1）子碼碼率為0.6時，在10-6誤碼率水平上，貪婪搜索打孔相比隨機打孔算法存在0.5 dB的信噪比優(yōu)勢，相比序列打孔算法存在0.08 dB的微弱優(yōu)勢。此時，刪余節(jié)點數(shù)目相對較少，因此節(jié)點恢復(fù)級別對刪余碼字的性能影響相對較小。

（2）隨著打孔目標碼率增加為0.7時，在10-6誤碼率水平上，貪婪搜索打孔與隨機打孔相比有1 dB的性能優(yōu)勢，相比序列打孔算法存在0.2 dB的性能優(yōu)勢。伴隨著碼字中冗余變量節(jié)點的進一步刪余，譯碼過程中會涉及到高級別刪余節(jié)點的恢復(fù)。貪婪搜索打孔中最大化低恢復(fù)級別節(jié)點的打孔準則，能夠在一定程度上提升節(jié)點的恢復(fù)可靠度。

（3）當打孔目標碼率進一步增加至0.8時，在誤碼率10-6水平上，貪婪搜索打孔與隨機打孔算法之間的優(yōu)勢明顯，相比序列打孔算法相比存在0.5 dB的性能優(yōu)勢。由于碼字中冗余變量節(jié)點大部分被刪除，譯碼過程中刪余變量節(jié)點的可靠性降低，譯碼性能逐漸出現(xiàn)損失。貪婪搜索打孔中最大化幸存校驗節(jié)點和TotalACE的打孔準則，可在一定程度上提升節(jié)點的錯誤恢復(fù)概率，同時優(yōu)化刪余碼字的環(huán)分布特性。

4 結(jié) 語

針對TDRSS通信系統(tǒng)碼率自適應(yīng)變換技術(shù)的應(yīng)用需求，提出一種基于貪婪搜索的RC-LDPC編碼序列打孔算法，兼顧了編碼的錯誤恢復(fù)特性和內(nèi)在環(huán)連接特性。相比傳統(tǒng)的打孔算法，該算法可實現(xiàn)更好的譯碼性能和更低的譯碼復(fù)雜度。尤其是在高碼率時，子碼的性能優(yōu)勢更加突出。因此，該算法適用于采用高碼率LDPC編碼的TDRSS高速數(shù)傳鏈路。

參考文獻：

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

[2] 王家勝,齊鑫.為載人航天服務(wù)的中國數(shù)據(jù)中繼衛(wèi)星系統(tǒng)[J].中國科學(技術(shù)科學),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] 馬慧,吳彥鴻.跟蹤與數(shù)據(jù)中繼衛(wèi)星系統(tǒng)抗干擾技術(shù)[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碼的研究進展和應(yīng)用展望[J].通信技術(shù) ,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] 王家勝.我國數(shù)據(jù)中繼衛(wèi)星系統(tǒng)發(fā)展建議[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] 翟政安.下一代數(shù)據(jù)中繼衛(wèi)星系統(tǒng)發(fā)展思考[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碼構(gòu)造及誤碼平底分析[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] 王志娜,肖旻,王琳.碼率自適應(yīng)原模圖LDPC碼的設(shè)計[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短碼的優(yōu)化構(gòu)造[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].中國宇航學會深空探測技術(shù)

專業(yè)委員會學術(shù)年會,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.