深空通信中基于噴泉碼的前向糾刪方法

杜 超， 郭 慶

(哈爾濱工業大學 通信技術研究所, 黑龍江 哈爾濱 150001)

0 引言

深空通信的基本特征是傳輸距離異常遙遠；并由此導致鏈路衰耗嚴重、誤碼率高，傳輸時延巨大，鏈路易中斷等衛星通信和地面無線通信所不具備的特殊問題。信道編碼技術作為保證通信系統可靠性的關鍵技術，對于解決上述問題具有重要意義。深空信道(自由空間段)通常被認為是一種理想的無記憶加性高斯白噪聲信道，這種信道正是構成Shannon信道編碼理論的基礎信道，因此使得在該信道模型下進行的信道編碼理論與仿真分析具有實際意義[1]。

傳統深空通信信道編碼技術主要針對物理層信息比特進行錯誤保護，當面對由于未糾正的比特錯誤引起的應用層錯誤幀接收情況時，只能采用自動重傳請求(ARQ)機制來保證分組數據的可靠接收。但是，在深空通信中應用ARQ機制受到鏈路傳輸長時延的顯著約束。文獻[2]指出的聯合物理層信道編碼與上層面向分組糾刪編碼的方法為解決此問題提供了良好思路。

噴泉碼作為新近興起的一種糾刪編碼，可以在無需反饋信道的情況下提供一種高效可靠的前向恢復(糾刪)方法，避免ARQ機制在深空通信應用中的瓶頸，非常適合于深空通信的特殊環境；同時在衛星廣播通信等領域也具有良好的應用性[3]。本文將帶有檢錯機制的Turbo碼分組傳輸信道等效為刪除信道，并應用系統 Raptor碼作為具體的噴泉碼實現方案，通過實際仿真分析了該方法的性能并與傳統信道編碼方法進行了比較。

1 噴泉碼基本原理

噴泉碼作為一種基于刪除信道、面向數據分組的前向糾刪編碼方法，具有傳統糾刪編碼所不具備的“無率”和“一致”特性：即對于任意刪除信道模型，不論其統計特性如何，只要接收端能夠從編碼器生成的半無限長序列中準確接收到一定數量的編碼符號，即可準確譯碼。

1.1 噴泉碼構造方法

目前主要有兩種噴泉碼構造方法：LT(Luby Transform)碼和Raptor碼。

LT碼是第一種噴泉碼實現方案，其編碼過程體現出噴泉編碼的核心思想，具體步驟如下：

① 將原始信息分組成為k個輸入符號(X1,X2,X3,…,Xk)；

② 根據給定的編碼度分布序列ρ(d) (d=1,2,3,…,k)，隨機選擇di(i =1,2,3,…)個輸入符號作為第i個編碼符號的鄰接節點；

2017年11月，華東理工大學學生社團趁早讀書會組織了“21天閱讀習慣養成”活動。在活動中，學生可以選擇任意一本喜歡的書，每天完成一定的閱讀，通過在微信活動群打卡，和大家分享喜歡的段落或讀書感想，此外還會設置每日話題供讀者討論。活動結束后，讀者收獲很大，但是由于趁早讀書會剛剛起步，人數比較少，活動影響力較小。

③ 對 di個輸入符號進行逐次異或運算得到編碼符號表示上的k維列向量，di個“1”元素的位置在vi中隨機分布。

LT碼編碼過程可用分組碼生成矩陣方法表述：令X表示輸入符號集，vi表示第 i個編碼符號的編碼系數向量，定義LT碼生成矩陣：

則LT編碼即為由輸入符號集根據編碼生成矩陣GLT進行線性運算的過程：

其中E[1:n]即為生成的編碼符號集。

Raptor碼與LT碼的主要不同之處是在LT編碼之前，首先對k個輸入符號進行C(n, k)線性變換，生成n個中間符號，再對其進行LT編碼生成輸出符號。Raptor碼預編碼冗余符號P由輸入符號通過預編碼生成矩陣Gpre(s × k)得到：

其中預編碼常用方法包括Hamming碼、LDPC碼等[4]；然后經過LT編碼由中間符號M(MT=[XTPT])生成編碼符號：

聯立式(3)和式(4)，得到：

1.2 噴泉碼譯碼算法及復雜度

對于刪除信道模型上的噴泉碼，傳輸過程中編碼符號以一定比例被刪除(丟失)，假設接收端能夠接收到其中 r(r＞k)個編碼符號(Ei1,Ei2, Ei3,…,Eir)，i∈(1,2,3,…,n)，那么譯碼即為由此r個編碼符號恢復全部輸入符號(X1,X2,X3,…,Xk)的過程。噴泉碼譯碼算法有兩種(以LT碼為例)：

(1) 高斯消去法

刪除信道上的最大似然譯碼等價于利用高斯消去法求解編碼線性方程組。由式(2)可知，求解線性方程組 GLT(i1,i2,i3,…,ir) · X =[Ei1TEi2TEi3T… EirT]T的過程即為噴泉碼的最大似然譯碼，只要編碼生成矩陣GLT的秩大于k，即可成功譯碼。對于均勻分布的編碼生成矩陣GLT，采用高斯消去法在譯碼失敗概率為1/kc時的譯碼開銷為O(ln(k)/k)，隨輸入符號數目k增加而趨近于0；但是當碼長逐漸增大時，高斯消去法譯碼代價(O(rk))成平方增大，因此適用于碼長較短的情況。

(2) 消息傳遞MP (Message Passing)算法

MP算法廣泛應用于基于稀疏圖形的編碼方法。對以刪除信道為基礎的噴泉碼，MP算法尤為簡單。均勻分布的度分布序列不能保證MP算法可靠譯碼，因此必須設計合理的度分布序列。根據文獻[5]提出的魯棒孤波分布可以得出，為保證可靠譯碼(譯碼失敗概率為1/kc)所需的譯碼開銷以及譯碼代價分別為O(ln2(k) /)和O(ln(k))，此時，譯碼開銷隨k增加同樣趨近于0，而相比于高斯消去法具有更低的譯碼代價。

2 深空通信中基于噴泉碼的前向糾刪方法

深空通信信道模型近似為理想AWGN信道，而噴泉碼研究的基礎信道模型為刪除信道。為了分析本文中基于噴泉碼的前向糾刪方法在AWGN信道下的性能，需要將應用層系統Raptor碼與物理層Turbo碼相結合，建立起對應關系。圖1所示為仿真系統結構圖，將帶有CRC檢錯機制的Turbo碼分組傳輸信道等效為刪除信道，簡化了仿真系統復雜度。

圖1 仿真系統結構

2.1 系統Raptor碼

LT碼和Raptor碼都是非系統碼，而大多數實際系統期望得到系統碼字輸出，通過對Raptor碼編碼過程進行適當改進，可以得到系統Raptor碼。本文采用系統Raptor碼作為應用層前向糾刪編碼的具體實現方案，下面對其進行分析。

設Si表示輸入符號，對于系統Raptor碼，要求編碼碼字的前k位等于k個輸入符號，即對任意Ei(i=1,2,3,…,k)，有Ei≡Si成立。通過對Raptor編碼輸入符號集X進行一定的處理，可以保證上述要求。假設該關系表示為S[1:k]=E[1:k]=Gk· X，那么代入式(3)、式(4)得到：

直觀來看，系統Raptor編碼首先需要計算編碼預處理矩陣Gk-1并由之得到輸入符號集X=Gk-1·S，再根據Raptor碼編碼過程式(3)、式(4)得到編碼符號。實際上，可以構造類似于式(5)的Raptor碼編碼約束矩陣A，使得

據此推出系統 Raptor碼編碼步驟：①根據編碼約束矩陣由式(7)得到中間符號集M；②對中間符號集M進行LT編碼得到系統Raptor碼。

雖然噴泉碼具有理論上的優良性能，但是目前實用噴泉碼方案僅限于MBMS標準建議的系統Raptor碼，參考3GPP標準系統Raptor碼設計原則[6]，對短碼長(k=256, 512, 1024)的系統Rapotr碼性能進行分析。圖2所示仿真結果表明在信道刪除概率f=0.1的情況下，只要接收到一定冗余數量(等價于譯碼開銷)的編碼符號，即可以在不同輸入符號數目的情況下得到相同的譯碼性能。

圖2 不同輸入符號數目條件下系統Raptor碼譯碼失敗概率

圖3所示為固定輸入符號長度k=256時，在不同的信道刪除概率下，系統 Raptor碼的譯碼失敗概率與編碼/輸入符號數目比之間的關系。可見，在不同刪除信道條件下，當達到一定碼率(即發送足夠多的編碼符號)時，系統Raptor碼的具有一致的譯碼性能。

圖3 不同刪除概率條件下系統Raptor碼譯碼失敗概率

2.2 Turbo碼

深空通信中采用系統Raptor碼作為應用層糾刪編碼對數據分組提供前向恢復機制建立在物理層信道編碼的基礎上。Turbo碼綜合卷積碼、偽隨機交織、最大后驗概率譯碼以及迭代譯碼思想，達到了接近 Shannon極限的性能，并已被選為CCSDS標準建議的深空通信信道編碼方案之一，采用 Turbo碼可以為系統提供盡可能大的編碼增益。限于篇幅，有關Turbo碼的原理介紹此處不作詳述，相關內容參考文獻[7]。

由于Turbo碼不能判斷譯碼碼字是否正確，因此需要引入幀錯誤控制域以判斷Turbo碼譯碼正確與否，通常采用循環冗余校驗(CRC)碼進行幀錯誤檢驗。值得注意的是，CRC校驗存在一定的漏檢概率，而應用層系統Raptor碼譯碼時需要準確接收正確的譯碼分組，因此有必要對 CRC校驗能力進行限制。分析可知，采用CRC-16進行檢錯，漏檢概率p ≈3×10-5，此時雖然可以保證幀錯誤控制要求，但使得上層系統Raptor碼接收到概率為p ≈ 3×10-5的錯誤譯碼符號，假設以編碼符號長度1000為分組進行譯碼，相當于每100次譯碼中有3次出現錯誤譯碼符號，從而造成譯碼錯誤擴散。為此，應當采用生成多項式g(x) =x32+ x23+ x21+ x11+ x2+ 1的CRC-32編碼，在漏檢概率p ≈ 2×10-9的情況下，可以保證系統Raptor碼譯碼要求。

2.3 仿真結果及分析

根據前文介紹的前向糾刪方法，對其在AWGN信道下的性能進行仿真研究，其中Turbo碼幀長為1784 bit。圖4所示為1/2碼率Turbo碼在應用系統Raptor碼作為應用層前向糾刪編碼前后的FER性能比較。其中，系統Raptor碼編碼符號數目k =512，采用等保護能力的設計方法，即對不同的信道刪除概率，統一采用譯碼開銷 (n - k) =12進行發送。表1所示為仿真系統參數；可見，當Eb/N0＞0.7 dB時，FER達到10-4以下，滿足深空通信系統對于鏈路丟包率的要求。

圖4 1/2碼率Turbo碼在應用系統Raptor碼前后性能比較

在圖 4所示方案的基礎上，考慮一種不等保護能力的系統 Raptor碼編碼方法，仿真結果如下頁圖 5所示。當系統Raptor碼輸入符號數目k=256時，相比于1/4碼率的Turbo碼，采用1/3碼率Turbo碼加系統Raptor碼的前向糾刪方法在碼率大于前者的情況下即可達到更低的FER，如表1右半部分中Eb/N0＞0.1dB的情況。在實際關注的區域(FER =10-4～10-5)，即Eb/N0＞0.4 dB時，該方法編碼碼率為1/(1.0625×3)≈0.32，相比于前者提高近7%，相當于在同等碼率下獲得了一定的編碼增益，從而提高了系統的分組數據保護能力。

圖5 1/4碼率Turbo碼與1/3碼率Turbo碼+系統Raptor碼性能比較

表1 仿真系統參數

注意到，當Turbo碼等效刪除信道刪除概率f ＞40%時，系統Raptor碼碼率很低，意味著接收端為了準確譯碼需要接收大量的編碼冗余符號；此時，該前向糾刪方法效率較低。但是，在適當的信道刪除概率f＜40%，系統Raptor碼能夠以較小的譯碼開銷高效恢復丟失的編碼分組，相比于單純使用Turbo碼的方法，具有更低的碼率。

3 結語

深空通信的特殊環境決定了 ARQ機制作為數據分組可靠接收方法的瓶頸，聯合物理層信道編碼與上層面向分組的糾刪編碼可以有效解決此問題。基于噴泉碼的前向糾刪方法有效利用了噴泉碼的無率和一致特性，確保在一定的信道刪除概率范圍內，能夠高效恢復丟失數據分組；同時，相比于單純使用Turbo碼的方法，在一定范圍內提高了系統的頻帶利用率。應用該方法對分組數據進行前向保護，避免了采用反饋鏈路重傳所引起的巨大時延代價，保證了深空通信系統的可靠性和高效性。

[1] 張乃通,李暉,張欽宇.深空探測通信技術發展趨勢及思考[J].宇航學報,2007,28(04): 786-793.

[2] Calzolari G P, Chiani M, Chiaraluce F, et al.Channel Coding for Future Space Missions: New Requirements and Trends[J].Proceedings of the IEEE, 2007,95(11):2157-2170.

[3] 葛新,龍紅衛,劉榕,等.Raptor碼在衛星廣播通信中的應用及其分析[J].通信技術, 2009,42(05):5-7.

[4] Shokrollahi A.Raptor Codes[J].IEEE Transactions on Information Theory, 2006,52(06):2551-2567.

[5] Luby M.LT Codes[C]//IEEE. Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science. Canada: FOCS,2002:271-282.

[6] TS 26.346 V7.8.0.Multimedia Broadcast/Multicast Service(MBMS): Protocols and Codecs[S].France: 3GPP TSG-SA, 2008.

[7] Blue Book 131.0-B-1. TM Synchronization and Channel Coding[S].USA: CCSDS, 2003.