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

郭 曉張更新 徐任暉 牛大偉

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

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

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

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

針對新型高效數字噴泉碼——RaptorQ碼譯碼復雜度高的問題，利用它是系統碼的特性，該文提出一種降維快速譯碼算法。該算法利用預先計算的逆矩陣，將譯碼過程中對接收編碼約束矩陣的求逆轉化為對更小維數矩陣的求逆，以降低譯碼復雜度。算法譯碼效果與現有譯碼算法等價。仿真結果表明，在信道符號刪除概率較低(小于0.2)時，該算法的譯碼速度顯著高于現有算法。

譯碼算法；數字噴泉；RaptorQ碼；降維譯碼

1 引言

RaptorQ碼[1]是數字噴泉技術的最新研究成果，目前被廣泛應用于無線實時多媒體傳輸、文件分發、衛星通信等諸多領域[2?6]。文獻[7]的研究結果表明，在分組長度小于104量級時，僅僅通過引入兩個冗余符號，RaptorQ碼即可將譯碼失敗概率降至10?6量級；與LT(Luby-Transform)碼和Raptor碼相比，RaptorQ碼為實現成功譯碼所需的冗余分組數大為降低。

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

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

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

2 RaptorQ碼編譯碼原理與譯碼復雜性分析

RaptorQ可以看作一種無限碼長的線性分組碼，其編譯碼過程可由生成矩陣來表示，如圖1所示。

圖1 RaptorQ碼編譯碼原理框圖

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

預編碼矩陣A由一系列子矩陣構成。

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

在LT編碼階段，中間符號向量c經過LT編碼器生成無限長編碼符號向量e=(e,e,…,e,…)T。

01K?1其中由K'?K個補零符號所生成的編碼符號恒為零，接收端譯碼器可根據編碼器參數進行重現，不需要進行傳輸。其余的符號用非負整數編號，即

?+為非負整數集，i'為編碼符號標識(Encoding Symbol Identifier, ESI)。

在編碼過程中，為了保證RaptorQ的系統碼特性，預編碼和LT編碼使用了K個相同的LT約束關系，由

可知，LT編碼器生成的前K個編碼符號即為K個源符號。在生成的無限長碼編碼序列中，除去K個源符號的編碼符號稱為修復符號。

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

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

3 降維快速譯碼(DRFD)算法設計

3.1 DRFD算法設計的出發點

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

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

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

3.2 降維變換

DRFD算法利用預先計算的編碼矩陣的逆?1A來實現接收端編碼約束矩陣的降維變換。采用DRFD算法的譯碼器結構如圖2所示。

圖2 使用DRFD算法的RaptorQ碼譯碼器結構

降維變換的原理可以用向量分解的方法進行說明。將含補零符號的待求的譯碼向量d?分解成兩個向量之和：

其中GLT(i),i∈RI為修復符號對應的LT約束關系矩陣，RI為修復符號對應的ESI集合。對于給定的編碼長度K，依據文獻[1]給出的RaptorQ碼編碼構造方法，編碼約束矩陣的逆矩陣?1A可以通過預先計算得到。

式(8)可以化簡為

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

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

證明 RaptorQ碼的設計保證了預編碼矩陣AL×L是可逆的，即其所有L個行是線性無關的。在接收編碼約束矩陣×L中，s個源符號、S個LDPC約束關系、H個HDPC約束關系、K'?K個補零約束關系所對應的行與AL×L相同，因此這些行也構成線性無關組。

×L中的s+S+H+(K'?K)個線性無關的行，剩余矩陣的秩為L?(s+S+H+(K'?K))=K?s ，即rank(GLT(i),i∈RI)=K?s 。A?1為滿秩矩陣，由A''=GLT(i),i∈RI?A?1可知rank(A'')= rank(GLT(i),i∈RI)=K?s ，故式(9)有唯一解。

定理1說明，降維變換并沒有改變接收編碼符號的可譯特性。式(9)使用了與式(5)相同的編碼約束關系，即降維譯碼方法與傳統的兩步譯碼方法譯碼效果等價。

3.3 DRFD算法

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

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

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

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

表1給出DRFD算法的步驟。

表1 DRFD算法

從表1給出的DRFD算法可譯看出，該算法改變了傳統的兩步譯碼結構，不再需要先譯出中間符號而后譯出源符號，而是直接通過接收的編碼符號譯出丟失的源符號。

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

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

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

3.4 計算復雜度分析

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

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

4 仿真結果及分析

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

由于RaptorQ碼的可譯特性由碼結構本身決定，上述5種譯碼算法具有相同的可譯性能，本文主要對譯碼算法的計算復雜度進行比較，不對譯碼失敗概率進行比較。各譯碼算法在實現過程中使用微秒精度的時間計數器，譯碼計算復雜度取譯碼時間的平均值作為仿真結果。

在給定分組個數K和符號大小T的條件下，由于RMID算法需要預先對信道符號刪除概率進行估計，且算法性能受信道符號刪除率和估計準確性兩個因素的影響，本文所提的DRFD算法的性能僅受信道符號刪除率影響，GE, IDGE, OIDGE算法的性能則跟這兩個因素無關。為了清楚說明各算法性能之間的關系，下文分兩部分進行分析。

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

圖3(a)給出了在符號長度T=4時，譯碼時間隨源分組個數K的變化曲線。GE, IDGE, OIDGE算法的譯碼時間僅受分組個數K和符號大小T影響，在圖中分別給出一條曲線。

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

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

從圖3(a)和圖3(b)可以看出，隨著p和K的增加，DRFD算法的譯碼速度的優勢會逐步降低。在p=0.2, K=2000時，DRFD算法的性能接近OIDGE算法。表明DRFD算法的應用有一定的局限性，即DRFD算法不適用于高誤碼率和分組塊較大的應用場景。K=2000, T=128時，單個傳輸的數據分段大小為256k Byte。單個傳輸分段大小小于256k Byte、信道符號刪除概率p小于0.20，這些限制對于當前大多數的多媒體應用來說是可滿足的[16]。

4.2 與RMID算法的比較

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

在T=128時，DRFD算法與RMID算法的對比仿真結論與上述仿真結論類似，本文不再贅述。

5 結束語

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

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

圖4 T=4時DRFD算法在不同符 號刪除率下與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]. 信息工程大學學報, 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年生，講師，博士生，研究方向為信道編碼、深空通信、無線網絡.

張更新： 男，1967年生，教授，博士，博士生導師，研究方向為衛星通信、深空通信.

徐任暉： 男，1978年生，講師，博士，研究方向為認知無線電.

牛大偉： 男，1978年生，講師，博士，研究方向為無線網絡、光交換網絡.

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改回

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

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