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

摘要：針對TDRSS通信系統對碼率兼容LDPC編碼的應用需求，對RC-LDPC編碼的打孔演算法進行了研究。通過分析打孔後LDPC子碼的余留Tanner圖特性和錯誤恢復概率，提出了一種基於貪婪搜索的序列打孔演算法。通過對變數節點恢復樹結構中的低恢復級別節點進行最大化搜索，再根據總近似環外消息度準則對節點進行排序，以實現碼率提升和誤碼性能的改善。模擬結果表明，相比隨機打孔演算法和序列打孔演算法，貪婪搜索打孔演算法誤碼性能較好，且構造子碼的性能表現更加突出。

正文內容：

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）節點，滿足 次迭代恢復的為 -SR節點，而未被打孔節點為0-SR節點，且刪余節點可進一步轉化為恢復樹的結構進行分析[13]。

首先假設 -SR節點vj 為根節點，根據最大迭代次數n 對節點進行分組，0-SR節點對應集合G0 ， k-SR節點對應集合Gk ，n -SR對應集合Gn 。其次，尋找其SCN子節點連接，然後進一步尋找刪余節點和未刪余節點進行連接。最後，重複上述操作，直至所有葉子節點均滿足0-SR，最終得到的恢復樹結構如圖1所示，其中實心圓表示未打孔節點，空心圓表示打孔節點。可知，經過首次迭代後，所有的1-SR節點可恢復校驗能力；經過第二次迭代，可恢復出2-SR節點的校驗能力；重複上述操作，直至恢復出根節點。

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

基於貪婪搜索的序列打孔演算法的本質是通過貪婪搜索保證從低到高恢復級別的 -SR節點最大化，再針對同一級別的 -SR節點，根據打孔圖樣的環連接性度量打孔節點的優先順序別，以改善碼率兼容碼字的性能。

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

它為有效度量余留Tanner圖的內在特性，定義變數節點vj 對應的總近似環外消息度為：

對於特定的MxN 維校驗矩陣H ，將矩陣中的變數節點根據所需恢復迭代次數分成G0,G1,L,Gn 組，其中G0 對應為0-SR節點集，Gn 對應為 -SR節點集。設I 和J 分別表示校驗矩陣的行索引集和列索引集，和表示矩陣中未分配的行、列索引集。H 中各行對應的列索引子集表示為，。同理，各列對應的行索引集合為 ，其中

。Pk 表示打孔後碼率為rk 的刪余節點的列索引集，n 表示打孔節點所需恢復的最大迭代次數。基於序列準則的貪婪搜索打孔演算法流程圖，如圖2所示。

貪婪搜索演算法是一種次優化演算法且計算複雜度低，在LDPC編碼的構造中具有重要意義。貪婪演算法的實質是在當前面臨的條件下做出最佳抉擇，以得到局部最優解。首先計算中行索引集合Rw 的最小值min Rw ，並在min Rw 中尋找列索引集合的最小值minCw ，同時找出對應節點組成序列對。當中存在多對節點時，選擇的刪余序列應滿足錯誤恢復概率最低。高斯信道中的變數節點的錯誤概率表達式為：

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

式中mu0 表示信道中接收的LLR信息均值，表示vj 對應的節點恢復樹中0-SR節點的數量，rj 表示倖存校驗節點的鄰居點集。函數的表達式為：

可知，函數在定義域內單調遞減。根據式（4）可知，vj 對應的S(v) 越大，mu(v) 越小，對應的節點錯誤概率Pe(v) 越大。因此，為保證錯誤概率最低，需選取具備最小的S(v) 的打孔序列，使其連接的0-SR點最少。

對於每一級的 k-SR節點，進行和S(v) 的貪婪搜索，直至得到不同恢復級別的節點集。依次從G1,G2,L,Gn 節點集中進行打孔節點的選擇，碼率rk 對應的打孔節點數目為：

式中，打孔節點數應滿足npk＜npmax 。初始化打孔時，p0 滿足為，判斷，需從當前集合G1 中取值。若G1 中存在多個候選方案，選擇G1 中具有最大SCN的變數節點集作為候選。若中存在多個候選方案，選擇具有最大 TotalACE的變數節點作為打孔節點輸出。打孔節點vj 選擇結束後，再對pk 、Gn 和進行更新，便於下一次打孔節點的選擇。由此可見，當迭代次數k 值較小、對應的 -SR越多時，子碼的恢復性能越好。

3　模擬實驗與性能分析

為驗證打孔演算法的性能，本節採用經PEG-ACE兩步擴展得到的（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所示，其中實線表示子碼碼字的誤比特率，虛線表示子碼碼字的誤幀率，「貪婪搜索」表示本文設計的基於貪婪搜索的序列打孔演算法，「序列打孔」表示基於序列準則的打孔演算法，「隨機打孔」表示隨機打孔演算法。

根據上述模擬對比結果可知以下結論：

（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.

[3] 馬慧,吳彥鴻.跟蹤與數據中繼衛星系統抗干擾技術[J].兵器裝備工程學報,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.

[6] 王家勝.我國數據中繼衛星系統發展建議[J].航天器工程,2011(02):1-8.

[7] 翟政安.下一代數據中繼衛星系統發展思考[J].飛行器測控學報,2016,35(02):89-97.

[8] 章謙驊.深空通信中RC-LDPC碼構造及誤碼平底分析[D].杭州:電子科技大學,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.

[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.

[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.

[16]楊明川,呂谷,陳佳音等.深空通信中基於原模圖的AR4JA碼性能分析[C].中國宇航學會深空探測技術專業委員會學術年會,2012.

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

作者：蔡　璟1，丁宗銀2

單位：1.江蘇電力信息技術有限公司，江蘇 南京 210024；

2.江蘇電力信息技術有限公司，江蘇 南京 210024

作者簡介：蔡　璟，男，碩士，工程師，主要研究方向為電網信息系統研發；

丁宗銀，男，學士，軟體工程師，主要研究方向為軟體工程。

本文刊登在《通信技術》2018年第5期（轉載請註明出處，否則禁止轉載）

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！