郭 曉張更新 徐任暉 牛大偉

(解放軍理工大學(xué)通信工程學(xué)院 南京 210007)

一種用于RaptorQ碼的降維快速譯碼算法

郭 曉*張更新 徐任暉 牛大偉

(解放軍理工大學(xué)通信工程學(xué)院 南京 210007)

針對(duì)新型高效數(shù)字噴泉碼——RaptorQ碼譯碼復(fù)雜度高的問(wèn)題，利用它是系統(tǒng)碼的特性，該文提出一種降維快速譯碼算法。該算法利用預(yù)先計(jì)算的逆矩陣，將譯碼過(guò)程中對(duì)接收編碼約束矩陣的求逆轉(zhuǎn)化為對(duì)更小維數(shù)矩陣的求逆，以降低譯碼復(fù)雜度。算法譯碼效果與現(xiàn)有譯碼算法等價(jià)。仿真結(jié)果表明，在信道符號(hào)刪除概率較低(小于0.2)時(shí)，該算法的譯碼速度顯著高于現(xiàn)有算法。

譯碼算法；數(shù)字噴泉；RaptorQ碼；降維譯碼

1 引言

RaptorQ碼[1]是數(shù)字噴泉技術(shù)的最新研究成果，目前被廣泛應(yīng)用于無(wú)線(xiàn)實(shí)時(shí)多媒體傳輸、文件分發(fā)、衛(wèi)星通信等諸多領(lǐng)域[2?6]。文獻(xiàn)[7]的研究結(jié)果表明，在分組長(zhǎng)度小于104量級(jí)時(shí)，僅僅通過(guò)引入兩個(gè)冗余符號(hào)，RaptorQ碼即可將譯碼失敗概率降至10?6量級(jí)；與LT(Luby-Transform)碼和Raptor碼相比，RaptorQ碼為實(shí)現(xiàn)成功譯碼所需的冗余分組數(shù)大為降低。

然而，RaptorQ碼的性能提升是以編譯碼復(fù)雜度的提高為代價(jià)的。理論上，使用置信傳播(Belief Propagation, BP)譯碼算法可在線(xiàn)性時(shí)間復(fù)雜度內(nèi)對(duì)Raptor類(lèi)碼(包括RaptorQ碼)進(jìn)行譯碼[8]。但在實(shí)踐中，受碼長(zhǎng)度的限制，單純使用BP譯碼算法會(huì)使成功譯碼概率大大降低。為了實(shí)現(xiàn)在較少編碼冗余的情況下提高成功譯碼的概率，當(dāng)前實(shí)用的譯碼算法主要依賴(lài)于對(duì)接收編碼約束矩陣A'的求逆運(yùn)算[9]。文獻(xiàn)[10]的研究表明，在符號(hào)長(zhǎng)度T=4的情況下，求逆運(yùn)算所耗費(fèi)的時(shí)間約占整個(gè)編譯碼時(shí)間的99%; T=1024時(shí)，這一時(shí)間約占整個(gè)編譯碼時(shí)間的95%。可見(jiàn)，RaptorQ碼的譯碼復(fù)雜度由矩陣求逆運(yùn)算的復(fù)雜度決定。

目前，針對(duì)RaptorQ碼編譯碼過(guò)程中求逆運(yùn)算復(fù)雜度較高的問(wèn)題，IETF RFC 6330[1]利用碼約束矩陣具有稀疏性的特點(diǎn)，采用失活譯碼(Inactivation Decoding, ID)技術(shù)和高斯消元(Gaussian Elimination, GE)法，給出了一種有效的RaptorQ碼譯碼算法，稱(chēng)為失活譯碼高斯消元(Inactivation Decoding Gaussian Elimination, IDGE)算法。文獻(xiàn)[10]在此基礎(chǔ)上提出了優(yōu)化失活譯碼高斯消元(Optimized Inactivation Decoding Gaussian Elimination, OIDGE)算法，該算法通過(guò)簡(jiǎn)化譯碼步驟和對(duì)行選擇方法進(jìn)行優(yōu)化，提高了譯碼計(jì)算的效率。文獻(xiàn)[11]等利用GPU的并行結(jié)構(gòu)，給出了RaptorQ碼的并行譯碼算法。文獻(xiàn)[12]利用Sherman-Morrison公式和預(yù)先計(jì)算的逆矩陣，給出了一種遞歸譯碼算法，該算法在信道符號(hào)刪除概率較低時(shí)，相對(duì)于前述算法性能有較大提升。本文稱(chēng)該算法為遞歸逆矩陣譯碼(Recursive Matrix Inversion Decoding, RMID)算法。但該算法需要獲得信道的先驗(yàn)符號(hào)刪除概率，計(jì)算效率的提升依賴(lài)于對(duì)信道符號(hào)刪除概率估計(jì)的準(zhǔn)確性，有一定的應(yīng)用局限性。

為了進(jìn)一步降低譯碼復(fù)雜度，本文利用RaptorQ是系統(tǒng)碼的特性，提出一種降維快速譯碼(Dimensionality Reduced Fast Decoding, DRFD)算法。該算法利用預(yù)先計(jì)算的逆矩陣，將譯碼過(guò)程中對(duì)接收編碼約束矩陣A'的求逆轉(zhuǎn)化為對(duì)更小維數(shù)矩陣A''的求逆，以降低譯碼復(fù)雜度。算法使用的降維變換方法未改變接收端編碼約束矩陣的符號(hào)間約束關(guān)系，譯碼效果與現(xiàn)有譯碼算法等價(jià)。

2 RaptorQ碼編譯碼原理與譯碼復(fù)雜性分析

RaptorQ可以看作一種無(wú)限碼長(zhǎng)的線(xiàn)性分組碼，其編譯碼過(guò)程可由生成矩陣來(lái)表示，如圖1所示。

圖1 RaptorQ碼編譯碼原理框圖

編碼過(guò)程分為預(yù)編碼和LT(Luby-Transform )編碼[13]兩個(gè)步驟，預(yù)編碼器首先將K個(gè)源符號(hào)編碼成L個(gè)中間符號(hào)，LT編碼器再將L個(gè)中間符號(hào)編碼成無(wú)限長(zhǎng)碼序列。RaptorQ碼的編譯碼運(yùn)算是在GF(256)上實(shí)現(xiàn)的，基本的運(yùn)算單位為Byte(8 bit)，為了提高編譯碼效率，通常將同時(shí)參與運(yùn)算的若干個(gè)Byte視為一個(gè)符號(hào)。符號(hào)大小(即每個(gè)符號(hào)包含的字節(jié)個(gè)數(shù))為T(mén), IETF RFC6330推薦的取值范圍為4至1024。具體編碼過(guò)程如下。在預(yù)編碼階段，K個(gè)源符號(hào)構(gòu)成的向量經(jīng)過(guò)尾部補(bǔ)零操作后形成長(zhǎng)度為K'的向量t',K'為RaptorQ碼預(yù)置的源符號(hào)向量長(zhǎng)度，K'≥K。t'再經(jīng)過(guò)首部補(bǔ)足S+H個(gè)零后形成輸入向量d=(d0,d1,…, dL?1)T, S為預(yù)編碼矩陣A中LDPC(Low Density Check Codes)約束的個(gè)數(shù)，H為HDPC(High Density Check Codes)約束的個(gè)數(shù)，L=K'+S +H 。經(jīng)過(guò)預(yù)編碼器后生成中間符號(hào)向量c=(c0,c1,…,cL?1)T，輸入向量和中間符號(hào)向量的關(guān)系為

預(yù)編碼矩陣A由一系列子矩陣構(gòu)成。

其中，IS為S×S維單位陣，IH為H×H維單位陣，GLDPC1和GLDPC2為行數(shù)S的LDPC矩陣，GHDPC為H×(L?H)維HDPC矩陣，GLT(i),1≤i＜K′為K'×L維的LT約束矩陣，i為內(nèi)部符號(hào)標(biāo)識(shí)(Internal Symbol Identifier, ISI), RaptorQ碼可通過(guò)ISI唯一確定編碼符號(hào)的LT約束關(guān)系，詳見(jiàn)文獻(xiàn)[1]。

在LT編碼階段，中間符號(hào)向量c經(jīng)過(guò)LT編碼器生成無(wú)限長(zhǎng)編碼符號(hào)向量e=(e,e,…,e,…)T。

01K?1其中由K'?K個(gè)補(bǔ)零符號(hào)所生成的編碼符號(hào)恒為零，接收端譯碼器可根據(jù)編碼器參數(shù)進(jìn)行重現(xiàn)，不需要進(jìn)行傳輸。其余的符號(hào)用非負(fù)整數(shù)編號(hào)，即

?+為非負(fù)整數(shù)集，i'為編碼符號(hào)標(biāo)識(shí)(Encoding Symbol Identifier, ESI)。

在編碼過(guò)程中，為了保證RaptorQ的系統(tǒng)碼特性，預(yù)編碼和LT編碼使用了K個(gè)相同的LT約束關(guān)系，由

可知，LT編碼器生成的前K個(gè)編碼符號(hào)即為K個(gè)源符號(hào)。在生成的無(wú)限長(zhǎng)碼編碼序列中，除去K個(gè)源符號(hào)的編碼符號(hào)稱(chēng)為修復(fù)符號(hào)。

得到。若A'不可逆，方程組不具有唯一解，譯碼失敗，需要接收更多的編碼符號(hào)e'，直至A'可逆。第2步，由式(3)可得向量t'，去掉補(bǔ)足的零后即可得源符號(hào)向量t，從而完成譯碼過(guò)程。需要指出的是，本文所指的矩陣可逆是指矩陣的列滿(mǎn)秩，即可以通過(guò)初等矩陣行變換將其上三角化。

從上述編譯碼過(guò)程可以看出，RaptorQ碼的編譯碼算法都依賴(lài)于對(duì)約束矩陣的求逆運(yùn)算。在發(fā)送端，對(duì)于給定的編碼長(zhǎng)度K，預(yù)編碼約束矩陣A是固定的，其逆矩陣?1A可以通過(guò)預(yù)先計(jì)算的方式得到。在接收端，由于傳輸過(guò)程中符號(hào)丟失具有隨機(jī)性，每一次參與譯碼運(yùn)算的A'是不同的，譯碼過(guò)程不可避免地需要對(duì)A'進(jìn)行求逆運(yùn)算。一般的矩陣求逆算法，如GE算法，具有O(N3)的計(jì)算復(fù)雜度。為了提高譯碼的效率，現(xiàn)有的譯碼算法[1,10,12]利用A'具有稀疏性的特征，主要采用失活譯碼技術(shù)加快譯碼速度。在失活譯碼的過(guò)程中，每個(gè)迭代譯碼步驟都需要優(yōu)先選擇矩陣中非零元最少的行優(yōu)先進(jìn)行譯碼。該操作需要對(duì)矩陣元素進(jìn)行掃描，占用大量的譯碼時(shí)間，在矩陣維數(shù)較高時(shí)，算法相當(dāng)?shù)托?。綜上所述，對(duì)高維矩陣的操作是現(xiàn)有譯碼算法效率不高的主要原因。

3 降維快速譯碼(DRFD)算法設(shè)計(jì)

3.1 DRFD算法設(shè)計(jì)的出發(fā)點(diǎn)

在第2節(jié)介紹的兩步譯碼過(guò)程中，首先需要求解式(5)恢復(fù)出L個(gè)中間符號(hào)，也就是求解一個(gè)包含M個(gè)線(xiàn)性約束關(guān)系和L個(gè)未知變量的線(xiàn)性方程組，該計(jì)算過(guò)程等價(jià)于對(duì)一個(gè)M×L維矩陣進(jìn)行求逆操作。觀(guān)察進(jìn)入RaptorQ碼譯碼器輸入端的接收符號(hào)向量, K個(gè)源符號(hào)經(jīng)過(guò)刪除信道后，接收端收到其中的s個(gè)，其余為r個(gè)修復(fù)符號(hào)，s+r=N，譯碼器僅需要譯出另外K?s個(gè)源符號(hào)即可得到源符號(hào)向量t。RaptorQ碼的編譯碼過(guò)程都是線(xiàn)性運(yùn)算，理論上，對(duì)一個(gè)包含r(r≥K?s)個(gè)線(xiàn)性約束關(guān)系和K?s個(gè)未知變量的線(xiàn)性方程組求解，即有可能得到K?s個(gè)未知變量，等價(jià)于對(duì)r×(K?s)維矩陣進(jìn)行求逆操作。

RaptorQ碼具有極高的碼率特性，其譯碼失敗的概率為[14]

由此可以看出，成功譯碼所需的編碼符號(hào)數(shù)N以很高的概率等于參與編碼符號(hào)個(gè)數(shù)K，即當(dāng)修復(fù)符號(hào)的個(gè)數(shù)r約等于丟失符號(hào)的個(gè)數(shù)K?s時(shí)，譯碼即可以很高的概率成功譯碼。編碼符號(hào)經(jīng)過(guò)符號(hào)刪除概率為p的刪除信道后，丟失的源符號(hào)數(shù)量K?s≈K?p。當(dāng)信道符號(hào)刪除率p?1時(shí)，K?p?K ，可得r≈K?s≈K?p?K＜L≤M。從這個(gè)數(shù)量關(guān)系看，在信道的符號(hào)刪除概率較低時(shí)，第2節(jié)所述的兩步譯碼方法是低效的。如果存在一種有效的方法將譯碼矩陣從M×L維降為r× (K?s)維，RaptorQ碼譯碼即可轉(zhuǎn)化為對(duì)較小維數(shù)矩陣求逆的過(guò)程，從而提高譯碼速度。

3.2 降維變換

DRFD算法利用預(yù)先計(jì)算的編碼矩陣的逆?1A來(lái)實(shí)現(xiàn)接收端編碼約束矩陣的降維變換。采用DRFD算法的譯碼器結(jié)構(gòu)如圖2所示。

圖2 使用DRFD算法的RaptorQ碼譯碼器結(jié)構(gòu)

降維變換的原理可以用向量分解的方法進(jìn)行說(shuō)明。將含補(bǔ)零符號(hào)的待求的譯碼向量d?分解成兩個(gè)向量之和：

其中GLT(i),i∈RI為修復(fù)符號(hào)對(duì)應(yīng)的LT約束關(guān)系矩陣，RI為修復(fù)符號(hào)對(duì)應(yīng)的ESI集合。對(duì)于給定的編碼長(zhǎng)度K，依據(jù)文獻(xiàn)[1]給出的RaptorQ碼編碼構(gòu)造方法，編碼約束矩陣的逆矩陣?1A可以通過(guò)預(yù)先計(jì)算得到。

式(8)可以化簡(jiǎn)為

給出下面的定理，該定理為降維變換提供理論依據(jù)。

定理1 對(duì)于RaptorQ碼的譯碼，式(9)有唯一解，當(dāng)且僅當(dāng)式(5)有唯一解。

證明 RaptorQ碼的設(shè)計(jì)保證了預(yù)編碼矩陣AL×L是可逆的，即其所有L個(gè)行是線(xiàn)性無(wú)關(guān)的。在接收編碼約束矩陣×L中，s個(gè)源符號(hào)、S個(gè)LDPC約束關(guān)系、H個(gè)HDPC約束關(guān)系、K'?K個(gè)補(bǔ)零約束關(guān)系所對(duì)應(yīng)的行與AL×L相同，因此這些行也構(gòu)成線(xiàn)性無(wú)關(guān)組。

×L中的s+S+H+(K'?K)個(gè)線(xiàn)性無(wú)關(guān)的行，剩余矩陣的秩為L(zhǎng)?(s+S+H+(K'?K))=K?s ，即rank(GLT(i),i∈RI)=K?s 。A?1為滿(mǎn)秩矩陣，由A''=GLT(i),i∈RI?A?1可知rank(A'')= rank(GLT(i),i∈RI)=K?s ，故式(9)有唯一解。

定理1說(shuō)明，降維變換并沒(méi)有改變接收編碼符號(hào)的可譯特性。式(9)使用了與式(5)相同的編碼約束關(guān)系，即降維譯碼方法與傳統(tǒng)的兩步譯碼方法譯碼效果等價(jià)。

3.3 DRFD算法

如第2節(jié)所述，傳統(tǒng)RaptorQ碼的譯碼算法依賴(lài)于對(duì)接收編碼約束矩陣A'進(jìn)行求逆，在能夠進(jìn)行成功譯碼的前提下，A'的維數(shù)僅取決于編碼器的參數(shù)K，不受信道刪除率的影響。而DRFD算法則依賴(lài)于對(duì)降維矩陣A''的求逆，A''的維數(shù)受信道刪除率的影響。當(dāng)信道符號(hào)刪除率p?1時(shí)，A''相對(duì)于式(5)中的A'，維數(shù)大大降低。

以K=10為例，根據(jù)文獻(xiàn)[1]給出的RaptorQ碼編碼構(gòu)造方法，編碼器向信道發(fā)送11個(gè)編碼符號(hào)。假設(shè)信道分組刪除率約為0.1，接收端接收到9個(gè)源符號(hào)和1個(gè)修復(fù)符號(hào)，加入編碼約束關(guān)系后，接收端編碼約束矩陣為?，F(xiàn)有的GE算法、×27IDGE算法和OIDGE算法都需要對(duì)這個(gè)27×27維矩陣執(zhí)行求逆運(yùn)算，以恢復(fù)出27個(gè)中間符號(hào)。RMID算法雖然不直接對(duì)A'進(jìn)行求逆，但在遞歸求逆的過(guò)程中，使用到的中間矩陣維數(shù)仍然是27×27維的。利用本文所提算法，經(jīng)過(guò)降維變換后，A''為1×1維矩陣，直接可以計(jì)算出丟失的源符號(hào)。

經(jīng)過(guò)降維變換后，解式(9)即可得到丟失的源符號(hào)。丟失的源符號(hào)與接收到的源符號(hào)合并，即可得到完整的譯碼向量d?。

對(duì)式(9)通常使用高斯消元法求解，若高斯消元成功，即可完成譯碼過(guò)程；若高斯消元法失敗，則需要接收更多的修復(fù)符號(hào)以完成譯碼過(guò)程。在需要多次譯碼情況下，可以采用文獻(xiàn)[15]提出的漸增譯碼算法，以減少重復(fù)執(zhí)行高斯消元法需要的計(jì)算開(kāi)銷(xiāo)。

表1給出DRFD算法的步驟。

表1 DRFD算法

從表1給出的DRFD算法可譯看出，該算法改變了傳統(tǒng)的兩步譯碼結(jié)構(gòu)，不再需要先譯出中間符號(hào)而后譯出源符號(hào)，而是直接通過(guò)接收的編碼符號(hào)譯出丟失的源符號(hào)。

在執(zhí)行DRFD算法之前，譯碼需要等待接收N個(gè)編碼符號(hào)。由于RaptorQ碼的高可譯特性，通常取N=K+2。采用此取值可將譯碼失敗的概率降到10?6量級(jí)，同時(shí)引入的解碼時(shí)延和計(jì)算開(kāi)銷(xiāo)都比較小。譯碼器在收到編碼符號(hào)的同時(shí)，可以通過(guò)某種同步方式獲得每個(gè)符號(hào)的編碼符號(hào)標(biāo)識(shí)ESI(如將ESI同編碼符號(hào)一同發(fā)送至接收端)。譯碼器通過(guò)ESI可識(shí)別接收到的源符號(hào)和修復(fù)符號(hào)，這些作為算法參數(shù)輸入至DRFD算法。

修復(fù)符號(hào)的LT約束關(guān)系由修復(fù)符號(hào)的ESI唯一確定，算法步驟1的實(shí)現(xiàn)方法詳見(jiàn)文獻(xiàn)[1]。矩陣GLT(i)為二進(jìn)制稀疏矩陣，算法步驟2利用的該特征將矩陣乘法運(yùn)算轉(zhuǎn)化成矩陣的行累加運(yùn)算，其中為A''的第i行，為A?1的第k行。算法步驟3中，為L(zhǎng)維向量，但部分元素為零，在計(jì)算矩陣乘法時(shí)，A''中部分列不參與運(yùn)算，可以節(jié)約一些計(jì)算開(kāi)銷(xiāo)。算法步驟4中，為L(zhǎng)維向量，但僅包含K?s個(gè)未知源符號(hào)，其余元素為零，因此A''中僅有未知符號(hào)對(duì)應(yīng)的K?s個(gè)列參與的生成，A''可以看作r×(K?s)維矩陣。

算法中所有的加法和乘法運(yùn)算都是GF(256)上的運(yùn)算。算法步驟2中使用到預(yù)編碼約束矩陣A的逆矩陣A?1，該矩陣預(yù)先計(jì)算后存儲(chǔ)在譯碼器端，在譯碼過(guò)程中，其計(jì)算開(kāi)銷(xiāo)可以忽略不計(jì)，但增加了譯碼器端的存儲(chǔ)開(kāi)銷(xiāo)。

3.4 計(jì)算復(fù)雜度分析

DRFD算法使用降維變換降低執(zhí)行GE算法的矩陣的維數(shù)，以達(dá)到降低譯碼計(jì)算復(fù)雜度的目標(biāo)。作為降維的代價(jià)，計(jì)算A''和e(R)的過(guò)程需要引入額外的矩陣乘法和加法，在一定程度上增加了計(jì)算量。但GLT(i),i∈RI為二進(jìn)制稀疏矩陣，利用算法中步驟2給出計(jì)算方法，對(duì)A?1中的行進(jìn)行異或操作即可計(jì)算出A''，不需要進(jìn)行GF(256)上的矩陣乘法。若信道的符號(hào)刪除率為p，則矩陣GLT(i),i∈RI的行數(shù)r約為pK, DRFD算法中步驟2計(jì)算A''的譯碼計(jì)算復(fù)雜度為O(pKL),L為中間符號(hào)的個(gè)數(shù)，略大于K。中約有(1?p)K個(gè)非零元，矩陣A''的行數(shù)約為pK, DRFD算法中步驟3計(jì)算的譯碼計(jì)算復(fù)雜度為O(p(1?p)K2)。算法步驟4在矩陣A''上執(zhí)行GE算法，計(jì)算復(fù)雜度O(p3K3)。因此DRFD算法整體的計(jì)算復(fù)雜度為O(p3K3)。

另外，求解式(9)可直接得到未知符號(hào)，不再需要利用矩陣乘法操作從中間符號(hào)c來(lái)恢復(fù)未知符號(hào)。在信道的符號(hào)刪除率為p較小的情況下，相對(duì)于具有O(N3)計(jì)算復(fù)雜度的GE消元法，DRFD算法可以大大減小計(jì)算開(kāi)銷(xiāo)。

4 仿真結(jié)果及分析

為了驗(yàn)證DRFD算法的性能，本節(jié)利用仿真實(shí)驗(yàn)將其與GE, IDGE, OIDGE和RMID算法進(jìn)行比較。IDGE算法參照文獻(xiàn)[1]實(shí)現(xiàn)，OIDGE算法參照文獻(xiàn)[10]實(shí)現(xiàn)，GF(256)上的乘法運(yùn)算采用查表法實(shí)現(xiàn)。仿真中所采用的信道為符號(hào)刪除信道，且具有穩(wěn)定的符號(hào)刪除概率p。參與RaptorQ編碼的源符號(hào)個(gè)數(shù)K的取值范圍為10到2000，符號(hào)大小T取值分別為4和128，符號(hào)刪除概率p取值為0.01, 0.10和0.20，對(duì)于每個(gè)(K,T,p)三元組進(jìn)行500次實(shí)驗(yàn)，每次實(shí)驗(yàn)使用相同的編碼數(shù)據(jù)，分別使用5種不同的譯碼算法進(jìn)行譯碼。仿真算法采用C語(yǔ)言實(shí)現(xiàn)，仿真程序在同一臺(tái)PC機(jī)(Intel i3 CPU@2.4G, DDR2@400MHz)上運(yùn)行。

由于RaptorQ碼的可譯特性由碼結(jié)構(gòu)本身決定，上述5種譯碼算法具有相同的可譯性能，本文主要對(duì)譯碼算法的計(jì)算復(fù)雜度進(jìn)行比較，不對(duì)譯碼失敗概率進(jìn)行比較。各譯碼算法在實(shí)現(xiàn)過(guò)程中使用微秒精度的時(shí)間計(jì)數(shù)器，譯碼計(jì)算復(fù)雜度取譯碼時(shí)間的平均值作為仿真結(jié)果。

在給定分組個(gè)數(shù)K和符號(hào)大小T的條件下，由于RMID算法需要預(yù)先對(duì)信道符號(hào)刪除概率進(jìn)行估計(jì)，且算法性能受信道符號(hào)刪除率和估計(jì)準(zhǔn)確性?xún)蓚€(gè)因素的影響，本文所提的DRFD算法的性能僅受信道符號(hào)刪除率影響，GE, IDGE, OIDGE算法的性能則跟這兩個(gè)因素?zé)o關(guān)。為了清楚說(shuō)明各算法性能之間的關(guān)系，下文分兩部分進(jìn)行分析。

4.1 與GE, IDGE和OIDGE算法的比較

圖3(a)給出了在符號(hào)長(zhǎng)度T=4時(shí)，譯碼時(shí)間隨源分組個(gè)數(shù)K的變化曲線(xiàn)。GE, IDGE, OIDGE算法的譯碼時(shí)間僅受分組個(gè)數(shù)K和符號(hào)大小T影響，在圖中分別給出一條曲線(xiàn)。

由圖3(a)可以看出，RFC6330給出的IDGE算法譯碼速度較GE算法和OIDGE算法低，原因是IDGE算法采用了較為復(fù)雜的行選擇算法，該算法雖然可以最大可能地利用接收編碼約束矩陣A'的稀疏特性，但需要對(duì)A'的元素進(jìn)行多次掃描，掃描矩陣元素需要消耗大量的計(jì)算時(shí)間；在K較小時(shí)，GE算法的譯碼速度略?xún)?yōu)于OIDGE算法，隨著K的不斷增加，OIDGE算法的譯碼速度顯著優(yōu)于GE算法。上述結(jié)果與文獻(xiàn)[10]的結(jié)論一致。DRFD算法譯碼速度在符號(hào)刪除概率p較低時(shí)，譯碼性能顯著優(yōu)于上述3種算法，例如在p=0.1時(shí)，對(duì)應(yīng)于K為100, 500和1500, DRFD算法的譯碼速度是OIDGE算法的17.4, 12.7和7.3倍。隨著p的增長(zhǎng)，DRFD算法的譯碼速度隨之降低。這是由于隨著p的增長(zhǎng)，參與DRFD算法譯碼的修復(fù)分組個(gè)數(shù)隨之增加，導(dǎo)致譯碼矩陣A''的規(guī)模隨之增長(zhǎng)，在A''上執(zhí)行高斯消元算法的算法復(fù)雜度為O(N3)，從而增加了算法中步驟4的譯碼時(shí)間。

圖3(b)給出了在T=128時(shí)的仿真結(jié)果。與圖3(a)的結(jié)果類(lèi)似，在符號(hào)刪除概率p較小時(shí)，DRFD算法的譯碼速度同樣優(yōu)于現(xiàn)有3種譯碼算法，例如在p=0.1時(shí)，對(duì)應(yīng)于K為100, 500和1500, DRFD算法的譯碼速度是OIDGE算法的5.3, 2.7和2.1倍，但相對(duì)于T=4時(shí)效率的提高有所減小。T增大導(dǎo)致DRFD算法譯碼速度降低的主要原因是，在算法的步驟3中，T增大將導(dǎo)致矩陣乘法的計(jì)算量增加，從而使步驟3占用大量的計(jì)算時(shí)間。

從圖3(a)和圖3(b)可以看出，隨著p和K的增加，DRFD算法的譯碼速度的優(yōu)勢(shì)會(huì)逐步降低。在p=0.2, K=2000時(shí)，DRFD算法的性能接近OIDGE算法。表明DRFD算法的應(yīng)用有一定的局限性，即DRFD算法不適用于高誤碼率和分組塊較大的應(yīng)用場(chǎng)景。K=2000, T=128時(shí)，單個(gè)傳輸?shù)臄?shù)據(jù)分段大小為256k Byte。單個(gè)傳輸分段大小小于256k Byte、信道符號(hào)刪除概率p小于0.20，這些限制對(duì)于當(dāng)前大多數(shù)的多媒體應(yīng)用來(lái)說(shuō)是可滿(mǎn)足的[16]。

4.2 與RMID算法的比較

圖4給出了DRFD算法與RMID算法在T=4時(shí)，p=0.01和p=0.20的仿真結(jié)果。由于RMID算法需要預(yù)先估計(jì)信道符號(hào)丟失率，故給出兩條曲線(xiàn)，分別表示能夠準(zhǔn)確預(yù)先估計(jì)信道質(zhì)量和估計(jì)的信道質(zhì)量有誤差時(shí)的情況。p?表示預(yù)先估計(jì)的信道符號(hào)丟失率。從圖上可以看出，在給定的信道符號(hào)丟失率的情況下，對(duì)信道質(zhì)量的估計(jì)值影響RMID算法的性能，估計(jì)值的誤差會(huì)降低RMID算法的譯碼速度，這與文獻(xiàn)[12]的結(jié)論一致。DRFD算法不需要預(yù)先估計(jì)信道符號(hào)丟失率，故給出一條曲線(xiàn)。在兩種信道符號(hào)丟失率的情況下，DRFD算法的譯碼速度均優(yōu)于RMID算法。

在T=128時(shí)，DRFD算法與RMID算法的對(duì)比仿真結(jié)論與上述仿真結(jié)論類(lèi)似，本文不再贅述。

5 結(jié)束語(yǔ)

RaptorQ碼是一種高效的數(shù)字噴泉碼，但由于譯碼運(yùn)算需要對(duì)較高維數(shù)的接收端編碼約束矩陣進(jìn)行求逆運(yùn)算，其譯碼的計(jì)算復(fù)雜度較高。本文利用預(yù)先計(jì)算的逆矩陣，提出了一種降維快速譯碼(DRFD)算法，該算法譯碼結(jié)果和現(xiàn)有譯碼算法等價(jià)，不改變現(xiàn)有算法對(duì)RaptorQ碼的可譯性，在信道的符號(hào)刪除概率p較低(小于0.2)時(shí)，譯碼速度顯著優(yōu)于現(xiàn)有算法。信道的符號(hào)刪除率越低，DRFD算法的性能提升約明顯。該算法的性能雖然受信道符號(hào)刪除率的影響，但不需要預(yù)先得到信道符號(hào)刪除率的先驗(yàn)信息，相對(duì)于RMID算法，在提高譯碼速度的同時(shí)，提升了算法的可用性。

圖3 DRFD算法在不同符號(hào)刪除率下與GE, IDGE和OIDGE算法性能比較

圖4 T=4時(shí)DRFD算法在不同符 號(hào)刪除率下與RMID算法性能比較

[1] IETF RFC 6330. RaptorQ forward error correction scheme for object delivery[S]. IETF Proposed Standard, 2011.

[2] Calabuig J, Monserrat J F, Gozálvez D, et al.. AL-FEC for streaming services in LTE E-MBMS[J]. EURASIP Journal on Wireless Communications and Networking, 2013, 2013(1): 1-12.

[3] Bouras C, Kanakis N, Kokkinos V, et al.. Embracing RaptorQ FEC in 3GPP multicast services[J]. Wireless Networks, 2013, 19(5): 1023-1035.

[4] Bouras C, Kanakis N, Kokkinos V, et al.. Application layer forward error correction for multicast streaming over LTE networks[J]. International Journal of Communication Systems, 2013, 26(11): 1459-1474.

[5] Pandya M A U, Trapasiya S D, and Chinnam S S. Implementation of AL-FEC RaptorQ code over 3GPP E-MBMS network[J]. International Journal of EngineeringResearch and Technology, 2013, 2(5): 170-177.

[6] 黃曉可, 劉洛琨, 張劍, 等. RaptorQ 碼級(jí)聯(lián)方案在衛(wèi)星通信中的應(yīng)用[J]. 信息工程大學(xué)學(xué)報(bào), 2013, 14(3): 306-311.

Huang Xiao-ke, Liu Luo-kun, Zhang Jian, et al.. Application of the RaptorQ codes concatenation in satellite communications[J]. Journal of Information Engineering University, 2013, 14(3): 306-311.

[7] Shokrollahi A and Luby M. Raptor codes[J]. Foundations and Trends in Communications and Information Theory, 2011, 6(3/4): 213-322.

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

[9] Kim S, Lee S, and 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] Mladenov T, Nooshabadi S, Kim K. Efficient GF (256) raptor code decoding for multimedia broadcast/multicast services and consumer terminals[J]. IEEE Transactions on Consumer Electronics, 2012, 58(2): 356-363.

[11] Hu L, Nooshabadi S, and Mladenov T. Forward error correction with Raptor GF(2) and GF(256) codes on GPU[J]. IEEE Transactions on Consumer Electronics, 2013, 59(1): 273-280.

[12] Lu Y, Lai I, Lee C, et al.. Low-complexity decoding for RaptorQ codes using a recursive matrix inversion formula[J]. IEEE Wireless Communications Letters, 2014, 3(2): 217-220.

[13] Luby M. LT codes[C]. Proceeding of the 43rd Annual IEEE Symposium on the Foundations of Computer Science, Vancouver, Canada, 2002: 271-280.

[14] 3GPP Tdoc S4-110449. Rationale for MBMS AL-FEC Enhancements[R]. 3rd Generation Partnership Project (3GPP), 2011.

[15] Kim S, Ko K, and Chung S Y. Incremental Gaussian elimination decoding of raptor codes over BEC[J]. IEEE Communications Letters, 2008, 12(4): 307-309.

[16] Mladenov T, Nooshabadi S, and Kim K. MBMS raptor codes design trade-offs for IPTV[J]. IEEE Transactions on Consumer Electronics, 2010, 56(3): 1264-1269.

郭 曉： 男，1981年生，講師，博士生，研究方向?yàn)樾诺谰幋a、深空通信、無(wú)線(xiàn)網(wǎng)絡(luò).

張更新： 男，1967年生，教授，博士，博士生導(dǎo)師，研究方向?yàn)樾l(wèi)星通信、深空通信.

徐任暉： 男，1978年生，講師，博士，研究方向?yàn)檎J(rèn)知無(wú)線(xiàn)電.

牛大偉： 男，1978年生，講師，博士，研究方向?yàn)闊o(wú)線(xiàn)網(wǎng)絡(luò)、光交換網(wǎng)絡(luò).

Fast Decoding Algorithm for RaptorQ Code Using Matrix Dimensionality Reduction

Guo Xiao Zhang Geng-xin Xu Ren-hui Niu Da-wei
(Institute of Communications Engineering, PLA University of Science and Technology, Nanjing 210007, China)

RaptorQ code is a novel and efficient digital fountain code and its decoder is known to be too complicated. Considering the characteristic of the systematic code, a very fast decoding algorithm can be performed using matrix dimensionality reduction. The algorithm exploits a pre-calculated inverse matrix to achieve dimensionality reduction for the

code constraint matrix. As a result, the decoding complexity is reduced significantly while the failure-overhead curve is still identical to that of the conventional approaches. The simulations show that the decoding speed of the proposed algorithm outperforms the state-of-the-art algorithms, when the erasure probability of the channel is relatively low (less than 0.2).

Decoding algorithm; Digital fountain; RaptorQ code; Dimensionality reduction decoding

TN911.22

： A

：1009-5896(2015)06-1310-07

10.11999/JEIT141037

2014-08-04收到，2014-10-31改回

國(guó)家自然科學(xué)基金(91338201, 61032004)資助課題

*通信作者：郭曉 gosiuua@163.com