基于貪婪搜索的RC-LDPC編碼序列打孔算法研究*

馬 慧，吳彥鴻，王宏艷

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

0 引 言

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

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

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

1 變量節(jié)點(diǎn)恢復(fù)樹(shù)

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

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

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

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

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

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

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

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

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

圖2 基于序列準(zhǔn)則的貪婪搜索算法流程

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

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

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

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

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

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

3 仿真實(shí)驗(yàn)與性能分析

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

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

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

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

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

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

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

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

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

4 結(jié) 語(yǔ)

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

參考文獻(xiàn)：

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

[2] 王家勝,齊鑫.為載人航天服務(wù)的中國(guó)數(shù)據(jù)中繼衛(wèi)星系統(tǒng)[J].中國(guó)科學(xué)(技術(shù)科學(xué)),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].兵器裝備工程學(xué)報(bào),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] 易旭,杜昊陽(yáng).LDPC碼的研究進(jìn)展和應(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] 王家勝.我國(guó)數(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].飛行器測(cè)控學(xué)報(bào) ,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].杭州：電子科技大學(xué),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ì)[J].重慶郵電大學(xué)學(xué)報(bào)(自然科學(xué)版 ),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].成都：西南交通大學(xué),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] 包建榮,高西奇,劉超等.擴(kuò)展原模圖LDPC短碼的優(yōu)化構(gòu)造[J].華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版 ),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].中國(guó)宇航學(xué)會(huì)深空探測(cè)技術(shù)

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