張亞航 程博文

(北京空間飛行器總體設計部,北京100094)

一種適用于衛(wèi)星數據傳輸的高效編解碼算法

張亞航 程博文

(北京空間飛行器總體設計部,北京100094)

提出了一種噴泉編解碼方法,又稱為快速速龍碼(RRC),該編碼方法能實現(xiàn)與傳統(tǒng)速龍碼相同的差錯控制效率的同時,時間復雜度相對更低。相對傳統(tǒng)速龍碼,在編碼過程中無需計算中間節(jié)點,直接通過生成矩陣計算校驗節(jié)點;其解碼方法是先通過置信傳播(BP)算法對校驗節(jié)點進行降度之后,再對校驗節(jié)點降度之后組成的矩陣進行高斯消元法解碼,從而降低矩陣規(guī)模。改進后的算法更加高效和簡單,適用于航天器空間通信中的應用層數據傳輸、存儲保護和深空探測信號傳輸。

速龍碼;噴泉編解碼;空間通信;衛(wèi)星

1 引言

衛(wèi)星廣播通信覆蓋區(qū)域廣闊,傳播距離遠,和其他通信方式相比有其獨特的優(yōu)勢;特別是在發(fā)生重大自然災害的時候更能表現(xiàn)出其不可替代的通信能力。但是無線通信中由于通信環(huán)境的影響(如太陽耀斑干擾),會出現(xiàn)數據在傳輸中丟失或錯誤的情況。這個時候需要信道糾錯編碼進行數據恢復保證數據傳輸的可靠性[1-2]。

噴泉碼[3-4]最大的特點是碼率無關性,接收端只要收到比原信息長度略多的碼字,就能將所有信息還原。噴泉碼的理念由Luby于1998年提出,并在2002年提出了一種具體的噴泉碼算法——LT碼[4]。其后,Shokrollahi等進一步研究,提出了譯碼性能更好的速龍碼(Raptor Codes)[5],2005年后Luby將其改進為系統(tǒng)速龍碼(Systematic Raptor Codes),并在2007年成為RFC(Request for Comments)標準[6]。相對于傳統(tǒng)編解碼算法,速龍碼的優(yōu)勢主要包括:碼率無關性;能夠以小的冗余、以極高的概率恢復出源節(jié)點;只有異或操作,具有較高的效率;源節(jié)點大小可以是任意長度;編碼冗余動態(tài)可調。由于以上特點,該算法能夠滿足一些航天任務需求,適合航天領域應用。

國內航天器星載計算機運算速度一般在10～50 MHz,軟件運行空間較為受限[7]。相對于航天器嵌入式軟件運行環(huán)境,該算法仍然顯得過于復雜,且由于編解碼矩陣較大,內存占用較多。文獻[8]認為傳統(tǒng)速龍碼解碼過程中從L×L尋找具備r個1的行的過程效率太低,并提出了改進的算法從而提高了解碼速率。文獻[9]通過增加預處理過程改進生成矩陣,進而減少解碼時矩陣行列交互次數,從而提高解碼速度。文獻[10]通過改進預編碼,從而提高譯碼效率。盡管這些文獻在一定程度提高了編碼復雜度,但是解碼矩陣規(guī)模并無變化,只是將解碼時矩陣運算簡化。

本文通過對傳統(tǒng)速龍碼的編解碼方式進行修改,在編碼過程將中間節(jié)點和修復節(jié)點計算合并成一次矩陣運算,直接通過生成矩陣計算校驗節(jié)點;其解碼方法先進行置信傳播(BP)算法對校驗節(jié)點進行降度之后,再對校驗節(jié)點降度之后組成的矩陣進行高斯消元法解碼,從而降低矩陣規(guī)模,使得編解碼速率提高,稱為快速速龍碼(Rapid Raptor Codes,RRC)。試驗表明,該算法的編碼速率和解碼速率相對傳統(tǒng)速龍碼有了明顯改進,同時該算法的解碼矩陣規(guī)模明顯減小。

2 傳統(tǒng)速龍碼

2.1 編碼算法

傳統(tǒng)速龍碼的編碼過程分為兩步[6]:

第1步:通過K個源節(jié)點生成L(L＞K)個中間節(jié)點。假設消息由K個給定的源節(jié)點組成,設向量C,有C=[C1,C2,…,CL-K,CL-K+1,…,CL-1,CL],預編碼生成矩陣G1L×L。令

式中 M為中間節(jié)點向量;L×L的矩陣G 1L×L代表著預編碼過程中LDPC、Half碼與LT碼在伽羅華域GF(2)上的生成矩陣,且保證矩陣G1L×L滿秩,即該矩陣可逆。G1L×L的結構如圖1所示, S為矩陣G_LDPC的列數;H為矩陣G_Half的列;K標識源節(jié)點個數,也是矩陣G_LT的列; L=S+H+K。

第2步:由L個中間節(jié)點根據LT編碼算法,計算出編碼矩陣G2N×L生成N個最終的修復節(jié)點向量R=[R1,R2,…,RN],其中,G2N×L每個行代表一個修復節(jié)點生成向量,每個列代表一個中間節(jié)點。

圖1 G1L×L結構Fig.1 Composition of G1L×L

2.2 解碼算法

傳統(tǒng)速龍碼解碼算法基于高斯消元法。假設接收到P個節(jié)點(K≤P≤K+N),接收到的節(jié)點集合記為向量D。

第1步:令Q=S+H+P,根據接收到的節(jié)點,可以獲得Q×L的矩陣G 3Q×L,其中G3Q×L的生成方法見參考文獻[6],且有

第2步:對G3Q×L進行高斯消元,若最終G3Q×L轉化成L×L的單位矩陣,即G3Q×L的秩大于L,則可以解出M,否則解碼失敗。

第3步:根據M和方程式(1),可以算出向量C,即源節(jié)點。

3 快速速龍碼

3.1 編碼算法

本設計方案中,在編碼過程中不再采用中間節(jié)點得到校驗節(jié)點的方法,而是按照下式直接生成校驗節(jié)點向量R=[R1,R2,…,RN],從而生成N個校驗節(jié)點。具體方式如下。

令LT編碼算法LTEnc()產生一個N×L的LT編碼矩陣G2N×L。矩陣G2N×L的結構如圖2所示。

矩陣G2N×L中第i行為1的列代表著相應位置上的中間節(jié)點參與了生成第i個校驗節(jié)點的異或操作,則校驗節(jié)點R的產生所示為

式中 G2N×L×G1L×L表現(xiàn)了源節(jié)點與校驗節(jié)點應滿足的關系。在此記

矩陣AN×L中同源結點向量C進行異或的列為后K列,因此取AN×L的后K列構成矩陣ZN×K,可得

圖2 G2N×L結構Fig.2 Composition of G2N×L

式中 向量C′=[C′1,C′2,…,C′k]代表K個輸入節(jié)點的集合。如圖3所示,Pre_A標識矩陣AN×L的前S+H列,End_A標識矩陣AN×L的后K列。

由上述過程可以看出,相對于傳統(tǒng)的速龍碼編碼方法,本設計方案的編碼方法中省去了中間節(jié)點的復雜計算,從而大幅度減小編碼時間消耗,降低編碼器對硬件的要求。

圖3 矩陣A與矩陣ZN×K的關系Fig.3 Relationship between matrix ZN×Kand matrix A

3.2 解碼算法

如3.1節(jié)所示,本算法在編碼過程中除去了中間節(jié)點的計算,解碼算法同樣不計算中間節(jié)點,而是結合高斯消元算法和置信傳播譯碼算法進行解碼。

假設在實際應用場景中,接收端收到K′個源節(jié)點和N′個修復節(jié)點,且有K′≤K,N′≤N,則丟失的源節(jié)點數為k=K-K′,k與信道丟包率β相關,一般來說k=K×β。

本文方案中,將通過置信傳播算法和兩步完成解碼算法及最大似然解碼算法相結合的方法進行解碼。

第1步:先采用置信傳播譯碼算法進行解碼矩陣降度。

如第3.1節(jié)所示,修復節(jié)點實際上是由一個或多個源節(jié)點通過生成矩陣生成。設其中第i個修復節(jié)點由di個源節(jié)點生成,則稱該修復節(jié)點的度為di,顯然,源節(jié)點本身可以看作度為1的修復節(jié)點。對所有N′個修復節(jié)點的度向量集合為d=[d1,d2,…,dN′]。此時,采用置信度傳播算法,對修復節(jié)點進行“降度”操作(表示將修復節(jié)點同組成它本身的源結點進行異或運算),若d中第i個元素di中包含有已接收到K′個源節(jié)點中的元素j,即第j個源結點參與異或運算生成修復節(jié)點di,則將di對應的修復節(jié)點與第j號源節(jié)點進行異或,直到d中不含有K′個源節(jié)點中的任意元素。

此處引入節(jié)點之間相關的概念,判斷第i個修復節(jié)點同丟失的源節(jié)點j是否相關的方法是:查詢矩陣ZN×K,若ZN×K中第i行、第j列為1,則說明第i個修復節(jié)點同第j個源節(jié)點相關。

第2步:通過最大似然解碼(高斯消元)算法完成最終解碼。

假設降度之后剩余n個校驗節(jié)點,n≤N′,則剩余修復節(jié)點集合記為R′=[R′1,R′2,…,R′n]。由于降度之后的校驗節(jié)點只同丟失的源結點相關,取d′中所有度向量構成一個n×k的小矩陣Z′,矩陣Z′的形式如圖4所示。其中Z′的第i行為1的列代表著相應位置上丟失的源節(jié)點參與了生成校驗節(jié)點的異或操作。記所有丟失的源節(jié)點集合為向量C′=[C′1,C′2,…,C′k]。

圖4 降度之后的Z′矩陣Fig.4 De-degreed matrix Z′

顯然,Z′矩陣滿足等式

通過最大似然解碼算法(高斯消元解碼算法),根據式(4),可以解出丟失的源節(jié)點向量C′=[C′1,C′2,…,C′k]。從而計算出丟失的k=K-K′個源節(jié)點,將計算出來的丟失源結點補充到源數據中,完成數據的修復。

4 性能分析

本節(jié)主要針對LT編碼、速龍碼和快速速龍碼進行分析和比較,并對速龍碼和快速速龍碼進行軟件仿真編解碼速度比對。

4.1 計算性能理論分析

(1)傳統(tǒng)速龍碼計算性能分析

速龍碼的編碼算法中,先通過預編碼算法生成中間節(jié)點,然后再用LT編碼算法進行編碼。設K為源節(jié)點個數,其編碼時間復雜度為O(K ln(1/e)),其中e為編碼冗余度。在解碼過程中,系統(tǒng)速龍碼采用高斯消元法,其時間復雜度為O(K3)。

(2)快速速龍碼計算性能分析

速龍碼取消了中間節(jié)點的生成,其編碼時間復雜度為O(δ×K×e),其中δ為編碼平均關聯(lián)度,一般來說δ為2左右。解碼算法中,由于結合了高斯消元算法和置信傳播譯碼算法,因此時間復雜度跟丟包率β相關,其時間復雜度為O((βK)3),可見,當β＜1時,快速速龍碼無論是編碼算法還是解碼算法,時間復雜度都大大優(yōu)于速龍碼。

4.2 譯碼性能理論分析

本系統(tǒng)編碼算法的結果同傳統(tǒng)速龍碼的結果一樣可以最大限度地利用修復節(jié)點解碼,而且解碼糾錯性能完全一樣,證明如下:

根據2.1節(jié)編碼方案可知,傳統(tǒng)速龍碼編碼方程R=G2N×L×G1L×L×C,等價于本設計中編碼時的關系式R=ZN×K×C,對于傳送的源節(jié)點,將傳送的源節(jié)點看作在ZN×K之上加入K×K的單位矩陣的編碼矩陣為Z 1(N+K)×K,顯然,傳統(tǒng)速龍碼最終能夠正確解碼的前提是接收到的節(jié)點重構的矩陣Z1′(N′+K′)×K滿秩。

使用置信傳遞解碼的過程,實際上等價于對接收到的修復節(jié)點同正確接收到的源節(jié)點取消關聯(lián),因此置信傳遞解碼過程之后的修復節(jié)點方程式R′=Z′N′×k×C′。同正確接收到的源節(jié)點不相關,即置信傳遞解碼過程之后的修復節(jié)點等價于丟失節(jié)點異或而成。文獻[5-6]中已經證明,當Z′N′×k滿秩時,則一定可以通過高斯消元正確解碼,即本設計方案可以正確解碼。而同時,若Z′N′×k非滿秩,則說明修復節(jié)點的度無法正確推導源節(jié)點,則其他所有方法也無法推導源節(jié)點。由此可證,本設計方案從理論上可以最大限度利用修復節(jié)點解碼。

4.3 性能仿真比對

本次仿真的方法主要在應用層實現(xiàn),軟件實現(xiàn)使用C語言實現(xiàn),運行在Linux 2.6操作系統(tǒng)內核,計算機中央處理器為Intel(R)Pentium(R)CPU@2.33 GHz。在實際測試中,本算例選擇了節(jié)點大小為16 KB,節(jié)點個數K=1 024的數據塊。

在編碼過程中,分別選擇了冗余為1%,2%,5%,10%的情況,其同傳統(tǒng)速龍碼編碼時間消耗的測試數據對比結果如圖5所示。結果表明,傳統(tǒng)速龍碼編碼時間受冗余度影響較小,而快速速龍碼編碼時間幾乎同冗余度呈正比;且快速速龍碼在編碼時間上較傳統(tǒng)速龍碼少很多,尤其是當冗余越小,差距越明顯。

在解碼過程,設置數據冗余率為20%,丟包率分別選取了1%,2%,5%,10%的情況。解碼過程主要針對矩陣處理速度和完整解碼速度進行對比。其最終的解碼時間對比結果如圖6所示。

圖5 快速速龍碼和傳統(tǒng)速龍碼編碼耗時比對(K=1031)Fig.5 Encoding times compare in milliseconds between rapid raptor codes and raptor codes(K=1 031)

圖6 快速速龍碼和傳統(tǒng)速龍碼解碼耗時比對(K=1031)Fig.6 Decoding times compare in milliseconds between rapid raptor codes and raptor codes(K=1 031)

針對不同的碼長,設置數據冗余率為10%,丟包率都為5%,每個節(jié)點大小為16 kbit。碼長K分別為250,500,1 000,1 500和2 000,其解碼速度如圖7所示。

從圖6可以看到,由于矩陣本身的縮小,速龍碼的矩陣規(guī)模大幅度下降,隨著鏈路丟包率的降低,解碼速度的提高越明顯;如圖7所示在相同丟包率(誤碼率)下,碼長越長,快速速龍碼解碼速度提高越明顯。與理論分析相符。

圖7 不同碼長下快速速龍碼和傳統(tǒng)速龍碼解碼耗時比對Fig.7 Decoding times compare in milliseconds in different source nodes K between rapid raptor codes and raptor codes

5 結束語

從上述結果可以看出,本設計方法的解碼速度和編碼速度較傳統(tǒng)速龍碼都有了極大的提高。本文基于速龍碼編解碼技術的基礎上對其進行改進,提出快速速龍碼,其主要特點和優(yōu)勢為:1)編碼過程直接通過固定的生成矩陣計算修復節(jié)點,更加高效和簡單;2)解碼過程在進行高斯消元之前,先進行置信傳遞算法降度,大幅降低了解碼矩陣的規(guī)模,從而大大減少了系統(tǒng)資源占用和時間復雜度。由于計算量和資源占用的減小,本文提出的快速速龍碼更適用于航天器嵌入式軟件環(huán)境下資源受限的情況。

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

ZHANG NAITONG,LI HUI,ZHANG QINYU.Thought and developing trend in deep space exploration and communication[J].Journal of Astronautics,2007,28(4):786-793.

[2] 顧術實,張欽宇,焦健.一種適用于深空通信的有限隨機性噴泉碼算法[J].宇航學報,2011,32(12): 2545-2549.

GU SHUSHI,ZHANG QINYU,JIAO JIAN.A novel algorithm of the limited-randomness fountaincodes in deep space communication[J].Journal of Astronautics,2011,32(12):2545-2549.

[3] MACKAY D J.Fountain codes[C]∥Proceedings of IEEE Communications,2005,152(6):1062-1068.

[4] LUBY M.LT codes[C]∥Procession of 43rd Annual IEEE Symptium Foundations of Computer Science, Vancouver,Canada,2002.

[5] SHOKROLLAHI A.Raptor codes[J].IEEE Transactions on Information Theory,2006,52(6):2551-2567.

[6] LUBY M,SHOKROLLAHI A,WATSON M.Raptor forward error correction scheme for object delivery[S]. www.ietf.org/rfc/rfc5053.txt,IETF,2007.

[7] 孫兆偉,劉源,邢雷,等.面向多任務的可重構星載計算機設計[J].系統(tǒng)工程與電子技術,2011,33(6): 1407-1414.

SUN ZHAOWEI,LIU YUAN,XING LEI,et al.Design of reconfigurable on-board computer for multitask[J]. Systems Engineering and Electronics,2011,33(6):1407-1414.

[8] ZHANG QUAN,XU WEIZHANG,SHI DONGXIN,et al.An improved algorithm of 3GPP MBMS raptor codes[C]∥2010 International Conference on Measuring Technology and Mechatronics Automation (ICMTMA 2010),2010.

[9] KIM S,LEE S,CHUNG S Y.An efficient algorithm for ML decoding of raptor codes over the binary erasure channel[J].IEEE Communications Letters,2008,12(8):578-580.

[10] 孟慶春,王曉京.Raptor Code預編碼技術研究[J].計算機工程,2007,33(1):1-3.

MENG QINGCHUN,WANG XIAOJING.Research on precoding method in raptor code[J].Computer Engineering,2007,33(1):1-3.

An Efficient Encoding and Decoding Algorithm Suitable for Satellite Data Translation

ZHANG Yahang CHENG Bowen
(Beijing Institute of Spacecraft System Engineering,Beijing 100094)

A time-efficient fountain error-correcting codes called rapid raptor codes(RRC) was presented,which was better than the traditional raptor codes while maintaining the same symbol recoverable performance.Compared with the original raptor code,intermediate symbol and repair symbol generation were combined into one step in encoding process,and the conception of degrees of symbols from the belief-propagation(BP)decoder was imported in decoding process before Gaussian elimination decoding with a much smaller matrix size.The improved algorithm is much simple and has better time-efficient,therefore suitable for satellite application layer data translation,memory protection and deep space message translation.

Raptor Codes;Fountain Codes;Space translation;Satellite

10.3780/j.issn.1000-758X.2015.05.010

(編輯:王曉宇、范真真)

2014-12-19。收修改稿日期:2015-06-05

張亞航 1985年生,2010年獲北京大學軟件工程專業(yè)碩士學位,工程師。研究方向為星載軟件設計、綜合電子、空間信息安全。