張亞航 程博文

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

一種適用于衛(wèi)星數(shù)據(jù)傳輸?shù)母咝Ь幗獯a算法

張亞航 程博文

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

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

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

1 引言

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

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

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

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

2 傳統(tǒng)速龍碼

2.1 編碼算法

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

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

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

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

圖1 G1L×L結(jié)構(gòu)Fig.1 Composition of G1L×L

2.2 解碼算法

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

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

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

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

3 快速速龍碼

3.1 編碼算法

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

令LT編碼算法LTEnc()產(chǎn)生一個(gè)N×L的LT編碼矩陣G2N×L。矩陣G2N×L的結(jié)構(gòu)如圖2所示。

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

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

矩陣AN×L中同源結(jié)點(diǎn)向量C進(jìn)行異或的列為后K列,因此取AN×L的后K列構(gòu)成矩陣ZN×K,可得

圖2 G2N×L結(jié)構(gòu)Fig.2 Composition of G2N×L

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

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

圖3 矩陣A與矩陣ZN×K的關(guān)系Fig.3 Relationship between matrix ZN×Kand matrix A

3.2 解碼算法

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

假設(shè)在實(shí)際應(yīng)用場景中,接收端收到K′個(gè)源節(jié)點(diǎn)和N′個(gè)修復(fù)節(jié)點(diǎn),且有K′≤K,N′≤N,則丟失的源節(jié)點(diǎn)數(shù)為k=K-K′,k與信道丟包率β相關(guān),一般來說k=K×β。

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

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

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

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

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

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

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

顯然,Z′矩陣滿足等式

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

4 性能分析

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

4.1 計(jì)算性能理論分析

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

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

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

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

4.2 譯碼性能理論分析

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

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

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

4.3 性能仿真比對(duì)

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

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

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

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

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

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

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

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

5 結(jié)束語

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

[1] 張乃通,李暉,張欽宇.深空探測通信技術(shù)發(fā)展趨勢(shì)及思考[J].宇航學(xué)報(bào),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] 顧術(shù)實(shí),張欽宇,焦健.一種適用于深空通信的有限隨機(jī)性噴泉碼算法[J].宇航學(xué)報(bào),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] 孫兆偉,劉源,邢雷,等.面向多任務(wù)的可重構(gòu)星載計(jì)算機(jī)設(shè)計(jì)[J].系統(tǒng)工程與電子技術(shù),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預(yù)編碼技術(shù)研究[J].計(jì)算機(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年獲北京大學(xué)軟件工程專業(yè)碩士學(xué)位,工程師。研究方向?yàn)樾禽d軟件設(shè)計(jì)、綜合電子、空間信息安全。