一種用于深空通信的系統(tǒng)LT碼

王麗娜，魏 鵬，胡廣大，唐 偉

(1．北京科技大學計算機與通信工程學院，北京100083;2．北京科技大學自動化學院，北京100083)

0 引言

深空通信具有傳播距離遙遠、傳播延時長、誤碼率高、傳輸鏈路易中斷等特點，而且航天器的存儲容量和處理能力又很有限，因此采用傳統(tǒng)的前向糾錯技術不能有效地保證信息傳輸?shù)目煽啃裕?］。噴泉碼是一種無碼率、無需反饋鏈路的前向糾錯碼，可以在不需要反饋信道的情況下高效地恢復數(shù)據(jù)，避免了反饋重傳機制應用于深空通信時的瓶頸問題。噴泉碼的編譯碼復雜度較低，將其應用于深空通信時可以降低航天器的編譯碼時間，緩解深空通信長延時帶來的不利影響，而且不存在反饋擁塞問題［2－5］。噴泉碼還具有恢復閃斷數(shù)據(jù)的能力，可以有效改善接收信號起伏大、甚至閃斷等問題［6］。

LT(Luby Transform)碼［7－8］是第一類實用的噴泉碼，是針對刪除信道提出來的一種糾錯碼。LT碼的編碼思想是根據(jù)編碼器的有限輸入與無限輸出的映射特性生成數(shù)據(jù)包，當接收端收到一定數(shù)量的數(shù)據(jù)包時就可以恢復出原始信息，以此來保證信息傳輸?shù)目煽啃浴Ｉ羁胀ㄐ判诺琅c無記憶的加性高斯白噪聲(AWGN)信道非常相似，可以建模為理想的AWGN信道。由于LT碼是一種以刪除信道為背景的稀疏圖編碼，當其應用于深空通信時存在一定的譯碼失敗概率，而且LT碼需要接收足夠多的數(shù)據(jù)分組后才能開始譯碼，且會產(chǎn)生譯碼開銷，這些對于功率和存儲空間受限的深空通信系統(tǒng)來說是非常不利的。目前，已有文獻對AWGN信道上LT碼的性能進行研究，并提出了相應的改善措施［9－11］。本文通過對AWGN深空通信環(huán)境中LT碼的研究發(fā)現(xiàn)，當LT碼用于深空通信時，其譯碼性能并不理想，而且輸入符號不能保證被全選。針對存在的問題，本文通過修改LT碼的二分圖構造系統(tǒng)LT碼，提出一種去環(huán)的左正則LT碼編碼方案，這樣LT碼譯碼器可以采用置信傳播(BP)譯碼算法［12］，且能保證譯碼算法的有效性。本文通過采用外信息轉(zhuǎn)移圖(EXIT圖)［13］和MATLAB仿真工具對系統(tǒng)LT碼的性能進行分析，結果表明，提出的編碼方案能夠明顯降低LT碼的錯誤平層，提高BP譯碼算法的性能。

1 系統(tǒng)LT碼

當傳統(tǒng)LT碼的編碼符號通過AWGN深空通信信道被接收以后，譯碼器采用對數(shù)域BP譯碼算法進行譯碼時，傳統(tǒng)LT碼具有較高的誤碼率和錯誤平層。造成這種結果的原因有兩個:一是缺少一個合適的校驗矩陣;二是輸入符號沒有通過信道，從而缺少輸入符號的初始先驗概率。因此，需要依據(jù)深空通信的特性來改善LT碼的性能。

1．1二分圖

為了讓k個輸入符號s=［s1，s2，…，si，…，sk］擁有它們的先驗概率p(si)，需要讓它們通過信道，這樣就自然形成一種系統(tǒng)的LT碼。同時，通過傳統(tǒng)LT碼的異或運算操作繼續(xù)構建出二分圖中校驗節(jié)點和變量節(jié)點的關系。

傳統(tǒng)LT碼在刪除信道下的二分圖如圖1(a)所示，它由輸入符號和編碼符號構成。為了使LT碼適用于AWGN深空通信信道，本文對傳統(tǒng)LT碼的二分圖進行修改，如圖1(b)所示，此LT碼為系統(tǒng)碼，由變量節(jié)點和校驗節(jié)點構成。

圖1 LT碼二分圖Fig．1 The bipartite graph of LT codes

在圖1(b)給出的系統(tǒng)LT碼二分圖中，輸入符號s=［s1，s2，…，si，…，sk］和編碼符號t=［t1，t2，…，ti，…］可以當作變量節(jié)點，c=［c1，c2，…，ci，…］與LDPC碼中的校驗節(jié)點類似。圖1所示的系統(tǒng)LT碼二分圖與LDGM(Low-density Generator Matrix)碼二分圖的區(qū)別是修改后的LT碼的譯碼開銷仍然在一定的范圍內(nèi)，能夠動態(tài)地增加編碼符號的數(shù)量，保留了噴泉碼無碼率的特性，如同在刪除信道下一樣，而LDGM碼的碼率則是依據(jù)預估的信道模型進行固定的。二者更明顯的區(qū)別是，LDGM碼在編譯碼過程中首先要確定的是校驗矩陣，該矩陣對編碼器和譯碼器都是確定和已知的，編碼時需要把校驗矩陣變換成合適的分塊矩陣，然后再進行編碼。而系統(tǒng)LT碼無需提前確定一個校驗矩陣，它是在編碼過程由無碼率特性自然形成生成矩陣Gp，然后再把這個矩陣變換成合適的校驗矩陣，使其構成了校驗關系，最后依據(jù)這個校驗關系執(zhí)行BP譯碼算法。

LT碼在二進制刪除信道下遇到的一個問題是在譯碼開銷較低時，不是所有的輸入符號都被選擇進入編碼過程，這樣就會使后續(xù)的譯碼一定會失敗，通常需要N=k ln(k/δ)個編碼符號才能保證能以1－δ的概率成功譯碼，其中，k為數(shù)據(jù)包的長度，δ為譯碼失敗概率門限。同樣地，在深空通信信道下，這個問題也會導致BP譯碼算法的性能下降。因此，可以假設所有的輸入符號不是按照隨機方式被選擇參與編碼的，而是依據(jù)它們的度數(shù)進行排序，然后優(yōu)先選擇度數(shù)低的符號參與編碼，以期達到所有的輸入符號都被選擇參與編碼過程，這樣就提高了BP譯碼算法的譯碼性能。另一方面，刪除信道下LT碼的成功譯碼過度依賴度為1的編碼符號，它們是譯碼過程進行下去的關鍵。然而，在AWGN深空通信信道環(huán)境下，度為1的編碼符號并沒有在BP譯碼算法中提供任何有益的作用。相反地，它們使得信噪比(SNR)和誤碼率(BER)曲線中具有較高的錯誤平層，因此需要修改校驗節(jié)點的度分布，降低度為1的編碼符號出現(xiàn)的概率或者不出現(xiàn)。

1．2編碼算法

隨著系統(tǒng)LT碼編碼的進行，生成矩陣Gp被逐步生成出來。如果所有的輸入符號都按照相同的概率被選擇，那么在生成矩陣中四環(huán)和六環(huán)的形成就難以避免，這些環(huán)會降低BP譯碼算法的性能［14］。為了解決這一問題，本文在文獻［10］的基礎上提出一種去四環(huán)和六環(huán)的編碼算法。

令Ωc(x)表示校驗節(jié)點的度分布，且

式中:ωi是度為i的校驗節(jié)點的概率。

盡管LT碼在理論上是無碼率的，但在實際應用時仍需設置輸入符號的最大編碼符號數(shù)量n。本文提出的系統(tǒng)LT碼編碼算法步驟如下:

步驟1．接收編碼符號，依據(jù)度分布Ωc(x)為第i個編碼符號生成度數(shù)di，若存在沒有選中過的輸入符號，則進入步驟2;否則進入步驟3;

步驟2．依據(jù)每個輸入符號被選擇的次數(shù)對其進行排序，隨機選擇di個從未被選中過的輸入符號，進入步驟7;

步驟3．重新把所有的輸入符號加入到待選集合V中，對于第j個選擇的輸入符號，若j≤di，則進入步驟4;否則返回步驟1;

步驟4．從V中那些選擇次數(shù)最小的輸入符號里隨機選擇一個作為第j個輸入符號，并將其從V中去除，進入步驟5;

步驟5．消除潛在的四環(huán)。把那些已存在的校驗節(jié)點(即第1個到第j－1個選擇的輸入符號的鄰居節(jié)點)作為集合P，把P中校驗節(jié)點的鄰居節(jié)點作為集合Q，從V中去除Q的元素，進入步驟6;

步驟6．消除潛在的六環(huán)。把P—中校驗節(jié)點作為集合U，并從V中去除那些與U中校驗節(jié)點相鄰的節(jié)點的輸入符號，返回步驟3;

步驟7．計算di個輸入符號的模二加之和，并將其作為第i個編碼符號，返回步驟1。

根據(jù)上述系統(tǒng)LT碼的編碼算法可以得到一個維度是k×n的稀疏矩陣Gp，則生成矩陣為G=［I Gp］，其中I是一個維度為k×k單位矩陣。

編碼過程可以表示為u=sG=［s t］，編碼符號為u=［u1，u2，…，ui，…，uk+n］=［s t］，則碼率為R=k/(k+n)，系統(tǒng)LT碼的譯碼開銷為γ=n/k。

式中 為變量節(jié)點的平均度 為校驗節(jié)點的平均度。

變量節(jié)點的平均度可表示為

為了保證所有的輸入符號都被選擇，γ需要滿足如下條件，即

2 系統(tǒng)LT碼分析

2．1右正則系統(tǒng)LT碼

考慮校驗節(jié)點的度dc為常數(shù)的系統(tǒng)LT碼，與LDPC碼類似，定義這類碼為右正則系統(tǒng)LT碼。

首先采用EXIT圖來分析系統(tǒng)LT碼的收斂閾值，以說明上節(jié)提出的系統(tǒng)LT碼編碼算法既不會對校驗節(jié)點的度產(chǎn)生影響，也不會降低LT碼的性能。

變量節(jié)點被當作變量節(jié)點譯碼器(VND)，校驗節(jié)點被當作校驗節(jié)點譯碼器(CND)［15］。對于變量節(jié)點譯碼器而言，輸出的外信息為

相應地，對于校驗節(jié)點譯碼器，輸出的外信息為

式中:

對于右正則系統(tǒng)LT碼，考慮校驗節(jié)點的度dc分別為7、10和13的情況，譯碼開銷γ為1．1，碼率R為0．476，通過EXIT圖來推斷右正則系統(tǒng)LT碼的收斂閾值，其結果如圖2所示。

圖2 VND和CND的EXIT圖Fig．2 The EXIT charts of VND and CND

由圖2可知，校驗節(jié)點的度dc分別取7、10和13時，VND和CND相交的點對應的SNR分別為－0．1 dB、1．1 dB和1．9 dB。

接下來，依據(jù)第1節(jié)提出的系統(tǒng)LT碼編碼算法，通過MATLAB仿真對右正則系統(tǒng)LT碼的譯碼性能進行分析。這里輸入符號的數(shù)量k取1000，對數(shù)域BP譯碼算法的最大迭代次數(shù)設置為50。譯碼開銷γ為1．1，碼率R為0．476，當校驗節(jié)點的度dc分別取5、7、9、11和13時系統(tǒng)LT碼與傳統(tǒng)LT碼的仿真結果如圖3所示。

圖3 不同度分布下右正則系統(tǒng)LT碼與傳統(tǒng)LT碼的比較Fig．3 Comparisons between right-regular systematic LT codes and conventional LT codes for different degree distribution

由圖3可以看出，與傳統(tǒng)LT碼編碼算法相比，本文提出的系統(tǒng)LT碼編碼算法具有更低的BER和更好的譯碼性能。更重要的是，提出的系統(tǒng)LT碼編碼算法能夠把錯誤平層降低1個數(shù)量級左右，而且在陡降區(qū)下降得更快，這說明本文提出的系統(tǒng)LT碼編碼算法明顯增強了BP譯碼算法的譯碼性能。從圖中還可以看到，傳統(tǒng)LT碼編碼算法對應的BER-SNR曲線的錯誤平層隨校驗節(jié)點度數(shù)的增加而下降，提出的系統(tǒng)LT碼編碼算法也遵循了相同的規(guī)律。此外，當SNR大于4 dB，校驗節(jié)點的度dc為11和13時的系統(tǒng)LT碼，仿真中沒有發(fā)現(xiàn)任何的誤碼。當SNR低于3 dB時，校驗節(jié)點度dc為7時的右正則系統(tǒng)LT碼的性能較好。對于SNR大于3 dB，BER小于10－5的情況，校驗節(jié)點度dc為9時的右正則系統(tǒng)LT碼的性能最好。

下面對不同譯碼開銷γ下系統(tǒng)LT碼的BER性能進行分析?？紤]校驗節(jié)點的度dc∈［7，10］(dc取整數(shù))的情況，碼率R為0．435，當譯碼開銷γ分別為1．1和1．3時的仿真結果如圖4和圖5所示。

圖4 γ為1．1時右正則系統(tǒng)LT碼的BER性能Fig．4 BER performance of right-regular systematic LT codes withγ=1．1

從圖4和圖5可以看出，對于相同度數(shù)的右正則系統(tǒng)LT碼，當譯碼開銷γ分別為1．1和1．3時，其BER-SNR曲線的發(fā)展趨勢類似，BER曲線在陡降區(qū)下降得較快。而且對于校驗節(jié)點的度dc為9和10時的LT碼，其錯誤平層下降得更快，同時，錯誤平層的斜率增大。當SNR低于2．6 dB時，校驗節(jié)點度dc為7時的右正則系統(tǒng)LT碼的性能較好。對于SNR大于2．6 dB，BER小于10－5的情況，校驗節(jié)點度dc為9時的右正則系統(tǒng)LT碼的性能最好。

圖5 γ為1．3時右正則系統(tǒng)LT碼的BER性能Fig．5 BER performance of right-regular systematic LT codes withγ=1．3

根據(jù)圖3至圖5顯示的結果和分析可以得到校驗節(jié)點的度dc分別為7、10和13時的收斂閾值，即0 dB、1 dB和2 dB，該結果與用EXIT圖分析得到的收斂閾值基本相符，說明本文提出的編碼算法是合理的。對于采用本文提出的編碼算法的右正則系統(tǒng)LT碼，從整體性能上來說，當SNR低于3 dB時，采用校驗節(jié)點度dc為7時的右正則系統(tǒng)LT碼較好;而當SNR高于3 dB時，采用校驗節(jié)點度dc為9時的右正則系統(tǒng)LT碼較好。

2．2非右正則系統(tǒng)LT碼

本節(jié)對采用提出的編碼算法的非右正則系統(tǒng)LT碼的譯碼性能進行分析。

依據(jù)校驗節(jié)點的度dc為9時的系統(tǒng)LT碼，根據(jù)二次擬合曲線，對i=4，5，…，12，有

根據(jù)文獻［9］和［16］，針對提出的系統(tǒng)LT碼編碼算法，修改度分布來消除環(huán)，提出第二種校驗節(jié)點的度分布，即

第三種度分布為

在譯碼開銷γ為1．1，其他參數(shù)保持不變時，根據(jù)式(9)～(11)給出的三種不同的度分布，對傳統(tǒng)LT碼編碼算法和提出的系統(tǒng)LT碼編碼算法的性能進行比較，其結果如圖6所示。

圖6 不同度分布下非右正則系統(tǒng)LT碼與傳統(tǒng)LT碼的比較Fig．6 Comparisons between right-irregular systematic LT codes and conventional LT codes for different degree distribution

從圖6可以看出，在上述三種不同度分布下，本文提出的編碼算法與傳統(tǒng)LT碼編碼算法相比能夠明顯降低曲線上的錯誤平層，減少錯誤平層的斜率。因此，本文提出的編碼算法能夠增強BP譯碼算法的譯碼性能。

對于式(9)至式(11)給出的三種不同的度分布，非右正則系統(tǒng)LT碼的譯碼性能基本相同，但是在曲線的陡降區(qū)，非右正則系統(tǒng)LT碼的性能卻不同。對于第一種度分布來說，其性能和度為9的右正則系統(tǒng)LT碼的性能基本相同。對于第二種度分布來說，其性能在陡降區(qū)和錯誤平層之間有一個很好的折衷。當SNR小于2．5 dB時，采用第二種度分布的非右正則系統(tǒng)LT碼的性能較好。當SNR為2．5 dB時，對應的BER約為10－5。對于采用第三種度分布的非右正則系統(tǒng)LT碼，當SNR大于2．5 dB時，其性能是最優(yōu)的，BER小于10－5。

選取式(10)給出的第二種度分布，對不同SNR(即r=1 dB，2 dB，3 dB，4 dB)條件下、不同碼率時的非右正則系統(tǒng)LT碼的性能進行評估，仿真結果如圖7所示。

圖7 不同SNR和碼率下非右正則系統(tǒng)LT碼的BER性能Fig．7 BER performance of right-irregular systematic LT codes for different SNR and code rates

由圖7可以看出，非右正則系統(tǒng)LT碼的BER隨著碼率的降低而減小，對于不同SNR情況下的所有非右正則系統(tǒng)LT碼的BER性能均遵循相同的規(guī)則。當碼率相同時，SNR越高，非右正則系統(tǒng)LT碼的BER越低。從整體性能上看，SNR為3 dB時的非右正則系統(tǒng)LT碼具有最好的BER性能，它與SNR為1 dB時的非右正則系統(tǒng)LT碼的BER相比，大約能降低5個數(shù)量級。

從前面的分析可知，本文提出的系統(tǒng)LT碼能較好地適應AWGN深空通信環(huán)境，具有較好的BER性能和譯碼性能。但由于該系統(tǒng)LT碼在編碼時要求所有的輸入符號都被選擇參與編碼過程，故其計算復雜度要稍高于傳統(tǒng)LT碼。圖8給出的是系統(tǒng)LT碼和傳統(tǒng)LT碼分別仿真100次得到的平均編譯碼時間對比結果，與傳統(tǒng)LT碼相比，系統(tǒng)LT碼需要的編碼時間略長，但在可接受的范圍內(nèi)，不影響系統(tǒng)LT碼的整體性能。

3 結論

圖8 系統(tǒng)LT碼和傳統(tǒng)LT碼平均編碼時間對比圖Fig．8 Comparison chart of average encoding time of systematic LT codes and traditional LT codes

噴泉碼以其自身獨有的特點使其應用于深空通信時具有明顯的優(yōu)勢，且發(fā)展空間非常廣闊。本文針對AWGN深空通信環(huán)境中傳統(tǒng)LT碼在運用對數(shù)域BP算法時的不理想且所有輸入符號不能保證被全選的問題，設計適用于此環(huán)境下的系統(tǒng)LT碼，提出一種去環(huán)的左正則編碼方案，對采用該編碼方案的右正則系統(tǒng)LT碼和非右正則系統(tǒng)LT碼的性能進行分析，通過仿真證明了本文提出的系統(tǒng)LT碼編碼算法的有效性，并根據(jù)仿真結果說明了采用不同度分布的系統(tǒng)LT碼的適用場合。

［1］ 翟政安，羅倫，時信華．深空通信信道編譯碼技術研究［J］．飛行器測控學報，2005，24(3):1－5．［Zhai Zheng-an，Luo Lun，Shi Xin-hua．Research on channel encoding and decoding technologies for deep space communication［J］．Journal of Spacecraft TT＆C Technology，2005，24(3):1－5．］

［2］Byers J W，Luby M，Mitzenmacher M．A digital fountain approach to asynchronous reliable multicast［J］．IEEE Journal on Selected Areas in Communications，2002，20(8):1528－1540．

［3］ 焦健，張欽宇，李安國．面向深空通信的噴泉編碼設計［J］．宇航學報，2010，31(4):1156－1161．［Jiao Jian，Zhang Qinyu，Li An-guo．A method of concatenated fountain codes in deep space communication［J］．Journal of Astronautics，2010，31(4):1156－1161．］

［4］ 顧術實，張欽宇，焦?。环N適用于深空通信的有限隨機性噴泉碼算法［J］．宇航學報，2011，32(12):2545－2549．［Gu Shu-shi，Zhang Qin-yu，Jiao Jian．A novel algorithm of the limited-randomness fountain codes in deep space communication［J］．Journal of Astronautics，2011，32(12):2545－2549．］

［5］ 李云鶴，顧術實，焦健，等．面向火星臨近空間的分布式中繼糾刪編碼機制研究［J］．宇航學報，2013，34(7):963－970．［Li Yun-he，Gu Shu-shi，Jiao Jian，et al．Research on distributed relay erasure codes in Mars proximity network［J］．Journal of Astronautics，2013，34(7):963－970．］

［6］ 吳偉仁，林一，節(jié)德剛，等．噴泉碼的遙測抗閃斷技術應用研究［J］．宇航學報，2013，34(1):86－91．［Wu Wei-ren，Lin Yi，Jie De-gang，et al．Application of fountain coding in telemetry system［J］．Journal of Astronautics，2013，34(1):86－91．］

［7］Luby M．LT codes［C］．The 43rd Annual IEEE Symposium on Foundations of Computer Science，Vancouver，BC，Canada，November 16－19，2002．

［8］MacKay D J C．Fountain codes［J］．IEE Proceedings Communications Online，2005，152(6):1062－1068．

［9］Hussain I，Xiao M，Rasmussen L K．LTcoded MSK over AWGN channels［C］．The 6th International Symposium on Turbo Codes and Iterative Information Processing(ISTC)，Brest，F(xiàn)rance，September 6－10，2010．

［10］Hussain I，Xiao M，Rasmussen L K．Error floor analysis of LT codes over the additive white Gaussian noise channel［C］．2011 IEEE Global Telecommunications Conference(GLOBECOM 2011)，Houston，Texas，USA，December 5－9，2011．

［11］Jesper H S，Toshiaki K，Philip O．Ripple design of LT codes for AWGN channel［C］．2012 IEEE Symposium on Information Theory(ISIT)，Cambridge，USA，July 1－6，2012．

［12］Yuan X，Li P．On systematic LT codes［J］．IEEE Communications Letters，2008，12(9):681－683．

［13］Brink S T．Convergence behavior of iteratively decoded parallel concatenated codes［J］．IEEE Transactions on Communications，2001，49(10):1727－1737．

［14］Frank R K，Brendan J F，Loeliger H．Factor graphs and the sum-product algorithm［J］．IEEE Transaction on Information Theory，2001，47(2):498－519．

［15］Brink ST，Kramer G，Ashikhmin A．Design of low-density parity-check codes for modulation and detection［J］．IEEE Transactions on Communications，2004，52(4):670－678．

［16］Estasmi O，Shokrollahi A．Raptor codes on binary memoryless symmetric channels［J］．IEEE Transactions on Information Theory，2006，52(5):2033－2051．