一種RaptorQ碼的模式選擇解碼算法

李 越，張立軍，李明齊，朱秋煜

(1.上海大學(xué),上海 200444；2.中國科學(xué)院 上海高等研究院，上海 201210)

?

一種RaptorQ碼的模式選擇解碼算法

李 越1,2，張立軍2，李明齊2，朱秋煜1

(1.上海大學(xué),上海 200444；2.中國科學(xué)院 上海高等研究院，上海 201210)

針對 RaptorQ 碼解碼復(fù)雜度高的問題，提出了一種模式選擇解碼(MSD)算法。該方法結(jié)合優(yōu)化失活解碼高斯消元(OIDGE)算法與快速降維解碼(DRFD)算法的優(yōu)點(diǎn)，綜合考慮了信道的實(shí)際丟包情況與不同解碼算法的效率，根據(jù)計算所得丟包率，選擇合適的解碼算法。在嵌入式系統(tǒng)上進(jìn)行了實(shí)驗(yàn)，結(jié)果表明，該算法在不同丟包率情況下可以自適應(yīng)地選擇合適的解碼算法，提高了RaptorQ碼的解碼效率。

應(yīng)用層FEC；噴泉碼；RaptorQ碼；高斯消元解碼

近幾年互聯(lián)網(wǎng)數(shù)據(jù)流量大幅度增長，為了有效地支持流媒體傳輸和文件分發(fā)，3GPP-MBMS和DVB-H IPDC都將噴泉碼作為應(yīng)用層的前向糾錯(AL-FEC)方案[1-2]。LT碼[3]是第一個實(shí)用的噴泉碼編碼方案。Raptor碼[4]通過將LDPC碼與LT碼級聯(lián)，降低了解碼開銷。RaptorQ碼是一種定義在伽羅華域 GF(256)上的Raptor碼，它繼承了所有Raptor碼的基本屬性和編解碼處理流程，同時能降低解碼失敗概率，但在編解碼的過程中需要對預(yù)編碼矩陣進(jìn)行復(fù)雜的求逆運(yùn)算，導(dǎo)致其解碼復(fù)雜度較高。IETF RFC 6330[5]根據(jù)碼約束矩陣具有稀疏性的特點(diǎn)，提出了失活解碼高斯消元算法(Inactivation Decoding Gaussian Elimination, IDGE)，文獻(xiàn)[6]在此基礎(chǔ)上提出了優(yōu)化失活解碼高斯消元(Optimized Inactivation Decoding Gaussian Elimination, OIDGE)算法，該算法通過簡化解碼步驟和對行選擇方法進(jìn)行優(yōu)化，提高了解碼計算的效率。文獻(xiàn)[7]首次提出增量解碼(Incremental Decoding)的概念，另外，文獻(xiàn)[8]和[9]提出了兩種增量高斯消元解碼算法，結(jié)果均表明增量解碼技術(shù)優(yōu)于重新解碼的方法。文獻(xiàn)[10]提出一種降維快速解碼(Dimensionality Reduced Fast Decoding, DRFD)算法，該算法通過降低矩陣維數(shù)，降低了解碼復(fù)雜度，但算法的性能受信道符號刪除率的影響較大。在信道符號刪除概率較高(>0.1)時，該算法的解碼速度明顯下降。

雖然OIDGE算法在很大程度上降低了解碼的計算復(fù)雜度，但是在嵌入式系統(tǒng)上仍然難以滿足接收系統(tǒng)的實(shí)時性要求。而DRFD算法的性能受信道符號刪除率的影響較大，在高丟包率信道條件下的性能反而下降。因此本文對RaptorQ碼的解碼機(jī)制進(jìn)行改進(jìn)，在OIDGE算法與DRFD算法的基礎(chǔ)上，提出了一種RaptorQ碼的模式選擇解碼(Mode Selection Decoding, MSD)算法，該方法綜合考慮了信道的實(shí)際丟包情況與兩種解碼算法的效率，根據(jù)當(dāng)前接收到的編碼數(shù)據(jù)塊中丟失的數(shù)據(jù)包數(shù)目占總數(shù)據(jù)包數(shù)目的百分比，選擇對應(yīng)的解碼模式。實(shí)驗(yàn)結(jié)果表明，該算法可以在不同丟包率情況下自適應(yīng)地選擇合適的解碼算法，在低丟包率時選擇DRFD解碼，在高丟包率時選擇OIDGE解碼，提高了RaptorQ碼的解碼速度。

1 RaptorQ碼的解碼

RaptorQ碼由預(yù)編碼和LT編碼級聯(lián)構(gòu)成的線性碼。編碼分為預(yù)編碼和LT編碼兩個過程。預(yù)編碼過程通過一個預(yù)編碼矩陣A生成中間符號，首先將K個源符號增補(bǔ)得到K′，對應(yīng)K′個源符號向量，接著進(jìn)行預(yù)編碼產(chǎn)生L(L=K′+S+H)個中間符號，其中K′表示源符號，S表示LDPC符號，H表示HDPC符號。最后由中間符號進(jìn)行LT編碼產(chǎn)生最終的編碼符號[5]。

RaptorQ 的解碼過程相當(dāng)于，通過對預(yù)編碼矩陣A進(jìn)行高斯消元求逆矩陣，還原出中間符號向量。其過程可表示為

C=A-1·D

(1)

式中：D表示接收到的編碼符號向量；C表示恢復(fù)出的中間編碼符號向量。然后對中間符號向量C進(jìn)行LT編碼來恢復(fù)出源數(shù)據(jù)符號向量[7]。

1.1 OIDGE解碼算法

文獻(xiàn)[4]的增強(qiáng)高斯消元解碼算法(EGE)認(rèn)為，如果標(biāo)準(zhǔn)的高斯消元過程進(jìn)行成功，可以直接進(jìn)行回代，解碼成功；如果高斯消元過程失敗，則重新執(zhí)行高斯消元步驟，直至成功解碼。

文獻(xiàn)[5]中失活高斯消元算法常被叫做IDGE算法。它利用置信度傳播的方法尋找出可以解碼的符號，同時生成一個與A同維度的矩陣X，用來記錄在A矩陣上進(jìn)行的行/列變換操作。該算法在求解預(yù)編碼矩陣的逆的過程中，分別進(jìn)行置信度傳播、高斯消元和前向消元的步驟。由于該算法需要對矩陣X進(jìn)行矩陣乘法運(yùn)算尋找失活符號，反而增加了計算量。

針對這一問題，在文獻(xiàn)[6]中提出一種優(yōu)化算法——OIDGE算法。該算法避免了對矩陣X的乘法運(yùn)算，直接對UM×u(upper)進(jìn)行消元。雖然此時UM×u(upper)是稠密的，只需要消去在解碼輸出時用到的部分行即可，其他行不需要進(jìn)行消元。由于省略了與X的乘法，A矩陣左上角仍為單位陣，故 OIDGE 算法只需3步即可完成矩陣A的逆運(yùn)算。

文獻(xiàn)[5]提出增量解碼(Incremental Decoding)的概念，當(dāng)高斯消元過程失敗時，將增加接收編碼符號的個數(shù)，以獲得行數(shù)足夠多的預(yù)編碼矩陣，保證預(yù)編碼矩陣的滿秩性。當(dāng)解碼失敗時只需在解碼失敗矩陣的基礎(chǔ)上進(jìn)行修補(bǔ)解碼，避免了需要從頭開始解碼而造成的解碼時延。

在運(yùn)行頻率為1 GHz的Freescale ARM架構(gòu)的嵌入式主板上測試了RaptorQ碼的解碼過程，對IDGE與OIDGE解碼算法中每個數(shù)據(jù)塊解碼的時間消耗進(jìn)行比較。每個數(shù)據(jù)塊包含K個源符號，經(jīng)過 RaptorQ 編碼后生成長度為N個編碼符號塊。結(jié)果如表1所示，其中K表示每個數(shù)據(jù)塊包含源符號的個數(shù)，T表示每個符號的字節(jié)長度。

表1 每個數(shù)據(jù)塊解碼時間消耗μs

1.2 DRFD算法

文獻(xiàn)[10]利用 RaptorQ 碼是系統(tǒng)碼的特性，提出一種降維快速解碼算法。該算法的原理是利用預(yù)先計算的逆矩陣，將解碼過程中對接收編碼約束矩陣的求逆轉(zhuǎn)化為對更小維數(shù)矩陣的求逆，以降低解碼復(fù)雜度。該算法的解碼效果與現(xiàn)有解碼算法等價。實(shí)驗(yàn)結(jié)果表明，該算法降低了矩陣求逆的維度，在信道符號刪除概率較低(<0.1)時，該算法的解碼速度明顯高于現(xiàn)有算法，且算法復(fù)雜度遠(yuǎn)低于IDGE算法。

DRFD算法的具體步驟是通過矩陣變換將求逆的對象由L×L維的預(yù)編碼矩陣A變換為r×r維矩陣Gx，其中r=K-s，s是一個數(shù)據(jù)塊中接收到的信息符號的個數(shù)，r是該數(shù)據(jù)塊中丟失的信息符號個數(shù)。在低丟包率的情況下，有r?L，因而復(fù)雜度降低。

在一個數(shù)據(jù)塊中，可以把接收到的L×T維符號矩陣D分解為D=D0+Dx，其中D0包含接收到的s個信息符號，Dx包含丟失的r個信息符號，其余部分為0。記S為接收到的信息符號組成的集合，R為丟失的信息符號組成的集合。注意到D=A·C，則接收到的r個修復(fù)符號可以表示為

E=GLT·C=GLT·A-1·(D0+Dx)=

G0·d0+Gx·dx

(2)

式中：r×s維矩陣G0=GLT·{A-1}i∈S；r×r維矩陣Gx=GLT·{A-1}i∈R；矩陣{A-1}i∈S和{A-1}i∈R分別代表從A-1中抽取對應(yīng)于S和R的列組成的集合；s×T維矩陣d0={D0}j∈S和r×T維矩陣dx={Dx}j∈R分別代表從D0和DX中抽取對應(yīng)于S和R的行組成的集合。從式(2)可得

(3)

其中A-1可預(yù)先求得，實(shí)際解碼過程中只需用高斯消元法對Gx求逆。

雖然總是有r≤K

2 模式選擇算法

2.1 解碼器的結(jié)構(gòu)

為了提高RaptorQ碼的解碼效率，本節(jié)提出一種用于RaptorQ碼的模式選擇解碼(MSD)算法,該算法結(jié)合了OIDGE算法和DRFD算法的優(yōu)點(diǎn)。如圖1所示，分配器Allocator為接收到的每一個數(shù)據(jù)塊分配一個選擇器Selector，并將接收到的符號按數(shù)據(jù)塊分別緩存在相應(yīng)的選擇器中。選擇器根據(jù)接收到信息符號的數(shù)量來選擇解碼算法。

圖1 模式選擇解碼器

2.2 模式選擇解碼過程

模式選擇解碼算法流程圖如圖2所示。

圖2 模式選擇解碼流程圖

首先進(jìn)行初始化。

第一步：生成選擇器。

接收一個編碼符號Symbol(i,j)，它屬于第i個文件的第j個數(shù)據(jù)塊。分配器在已有的子解碼器列表中檢索(i,j)，檢查是否有選擇器Selector(i,j)與之對應(yīng)。若存在對應(yīng)的Symbol(i,j)，則將(i,j)輸入給它；若沒有對應(yīng)的選擇器，則由分配器創(chuàng)建一個新的選擇器Selector(i,j)，重置編碼符號個數(shù)NUM(i,j)=0，將Symbol(i,j)輸入給它，跳轉(zhuǎn)至第二步。

第二步：選擇器Selector(i,j)接收到符號Symbol(i,j)。

若該選擇器已創(chuàng)建子解碼器Sub-Decoder(i,j)，則將符號輸入到該子解碼器，跳轉(zhuǎn)至第三步。若尚未創(chuàng)建子解碼器Sub-Decoder(i,j)，則將符號存入緩存，記錄當(dāng)前編碼符號個數(shù)NUM(i,j)，若當(dāng)前編碼符號個數(shù)NUM(i,j)

第三步：子解碼器解碼。

若解碼成功，則對序列號ESI=1:K輸出源符號，該數(shù)據(jù)塊解碼完畢，刪除選擇器Selector(i,j)和子解碼器Sub-Decoder(i,j) ；若解碼失敗，則跳轉(zhuǎn)至第一步進(jìn)行增量解碼。

2.3 性能分析

在高斯消元法可以恢復(fù)源數(shù)據(jù)塊的情況下，失活解碼算法也能保證對其恢復(fù)，并且效率更高。失活解碼算法在第一步和第三步使用置信度傳播解碼，解碼時間是線性的。因此，在源數(shù)據(jù)塊范圍內(nèi)，整個失活解碼過程解碼時間是線性的，采用IDGE/OIDGE算法[5-6]，其復(fù)雜度是O(L2)。

DRFD算法使用降維變換降低了GE算法的矩陣的維數(shù)。該算法改變了傳統(tǒng)的兩步譯碼結(jié)構(gòu)，無需先譯出中間符號，直接通過接收的編碼符號譯出丟失的源符號。雖然計算Gx=GLT·{A-1}i∈R的過程需要引入矩陣乘法和加法，在一定程度上增加了計算量。但矩陣GLT(i), i∈R為二進(jìn)制稀疏矩陣，對A-1中的行進(jìn)行異或操作即可計算出Gx，省去了GF(256)上的矩陣乘法。假設(shè)信道的丟包率為p，則矩陣GLT(i), i∈R的行數(shù)r約為pK,矩陣Gx的譯碼計算復(fù)雜度為O(pKL)，L為中間符號的個數(shù)，略大于K。而對Gx的消元只能采用標(biāo)準(zhǔn)高斯消元算法，其復(fù)雜度是O(r3)[8]，DRFD 算法整體的計算復(fù)雜度為O(p3k3)[8]。因此，在丟包率比較高的情況下，r值較大，后者的復(fù)雜度反而高于前者；在低丟包率的情況下，有r≤L，因而復(fù)雜度降低。

本算法在信道丟包率較低時的計算復(fù)雜度為O(r3)，在信道丟包率大于10%左右時的計算復(fù)雜度為O(L2)。

3 實(shí)驗(yàn)結(jié)果

算法驗(yàn)證分別在PC機(jī)(64位處理器，Interl?CoreTM2 E7200 2.53 GHz)和Freescale ARM架構(gòu)的嵌入式主板上進(jìn)行。嵌入式主板采用飛思卡爾酷睿A9系列處理器，運(yùn)行頻率為1 GHz。用C語言程序?qū)崿F(xiàn)了RaptorQ碼的解碼過程，分別對OIDGE算法，DRFD算法與本文提出的MSD算法進(jìn)行了測試。每個數(shù)據(jù)塊包含K=64個源符號，每個符號長度為T=1 024 byte，經(jīng)過 RaptorQ 編碼后生成長度為N=80的編碼符號塊，然后在刪除信道上進(jìn)行傳輸。接收端對接收到的編碼符號進(jìn)行緩存和解碼。對每個數(shù)據(jù)塊重復(fù)多次進(jìn)行上述過程，直到接收端成功解碼為止。這里開發(fā)了RaptorQ編譯碼算法庫，并把它集成到了開源項(xiàng)目上，用來實(shí)現(xiàn)符合FLUTE(File Delivery over Unidirectional Transport)協(xié)議的文件傳輸。其中發(fā)送端調(diào)用RaptorQ編碼，運(yùn)行在一臺PC機(jī)上；接收端(嵌入式主板)調(diào)用RaptorQ解碼。通過測試，得出3種解碼算法的耗時圖如圖3所示。

圖3 OIDGE，DRFD，MSD算法的解碼時間

3條曲線分別代表了3種算法的解碼時間隨著丟包率變化的趨勢。結(jié)果顯示DRFD算法在丟包率低于10%的范圍內(nèi)解碼時間比OIDGE短，但在其他范圍內(nèi)耗時明顯增加，而OIDGE 解碼時間較平穩(wěn)。MSD算法則結(jié)合了兩者的優(yōu)點(diǎn)，在任何丟包率的情況下，都能在較短的時間內(nèi)進(jìn)行解碼。在5%丟包率時，MSD算法相對OIDGE算法的解碼時間減少了一半，在高丟包率時，兩者基本相等。實(shí)際解碼時間證明，編碼符號經(jīng)過選擇器的時間可以忽略不計，不對解碼造成影響。

4 結(jié)論

本文針對RaptorQ碼解碼復(fù)雜度高的問題，提出了一種模式選擇解碼算法，該方法綜合考慮了信道的實(shí)際丟包情況與不同解碼算法的效率，根據(jù)計算所得丟包率，選擇對應(yīng)的解碼模式。實(shí)驗(yàn)結(jié)果表明，該算法適用于嵌入式系統(tǒng)中的各種丟包率的場景，在一定程度上提高了RaptorQ碼的解碼效率。

[1] DVB transport of MPEG-2 TS based DVB services over IP based networks:ETSI T S. 102 034 V1.5.1[S].2014.

[2] BOURAS C, KANAKIS N, KOKKINOS V, et al. Embracing RaptorQ FEC in 3GPP multicast services[J]. Wireless networks,2013,19(5): 1023-1035.

[3] LUBY M. LT codes[C]// Proc. the 43rd Symposium on Foundations of Computer Science. [S.l.]：IEEE, 2002:271.

[4] LUBY M, SHOKROLLAHI A, WATSON M, et al. RFC 5053: Raptor forward error correction scheme: Scheme for object delivery[R]. [S.l.]：IETF, 2007.

[5] LUBY M, SHOKROLLAHI A, WATSON M, et al.RFC 6330, RaptorQ forward error correction scheme for object delivery[S].2011.

[6] 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.

[7] KIM S, KO K, CHUNG S Y. Incremental Gaussian elimination decoding of raptor codes over BEC[J]. IEEE communications letters, 2008,12(4):307-309.

[8] MLADENOV T, NOOSHABADI S, KIM K. Strategies for the design of Raptor decoding in broadcast/multicast delivery systems[J]. IEEE transactions on consumer electronics, 2010, 56(2): 423-428.

[9] MLADENOV T, NOOSHABADI S, KIM K. Efficient incremental raptor decoding over bec for 3GPP MBMS and DVB IP-data cast services[J]. IEEE transactions on broadcasting, 2011, 57(2): 313-318.

[10] 郭曉, 張更新, 徐任暉，等. 一種用于 RaptorQ 碼的降維快速解碼算法[J]. 電子與信息學(xué)報, 2015, 37(6): 1310-1316.

李 越(1992— )，女，碩士生，主研信道編碼；

張立軍(1974— )，助理研究員，主研視頻通信；

李明齊(1971— )，研究員，主研無線“三網(wǎng)融合”、4G/B4G關(guān)鍵技術(shù)、基于3GPP的軟件無線電；

朱秋煜(1964— )，教授，主研圖像處理、模式識別、計算機(jī)視覺、智慧城市、計算機(jī)應(yīng)用。

責(zé)任編輯：薛 京

A mode selection algorithm for RaptorQ code decoding

LI Yue1,2, ZHANG Lijun2, LI Mingqi2, ZHU Qiuyu1

(1.ShanghaiUniversity，Shanghai200444，China；2.ShanghaiAdvancedResearchInstitute,ChineseAcademyofSciences,Shanghai201210,China)

Aiming at the problem of high complexity of decoding RaptorQ codes, a mode selective decoding algorithm for RaptorQ code is proposed in this paper. Combined with the advantages of optimized inactivation decoding Gaussian elimination(OIDGE) algorithm and dimensionality reduced fast decoding (DRFD) algorithm, the actual situation and the efficiency of the channel decoding algorithm are taken into account, and then the corresponding decoding mode is adopted according to current packet loss rate. Experiments are carried out on embedded system, and the results show that the decoder can select the appropriate algorithm adaptive to the packet loss rate. This improves the decoding efficiency of RaptorQ codes in a certain extent.

application layer FEC; fountain code; RaptorQ code; Gaussian elimination decoding

李越，張立軍，李明齊，等.一種RaptorQ碼的模式選擇解碼算法 [J]. 電視技術(shù)，2016,40(12)：120-124. LI Y, ZHANG L J, LI M Q，et al.A mode selection algorithm for RaptorQ code decoding[J]. Video engineering，2016,40(12)：120-124.

TN911.22

A

10.16280/j.videoe.2016.12.023

中科院戰(zhàn)略性先導(dǎo)專項(xiàng)子課題(XDA06010301)；國家基金委青年科學(xué)基金項(xiàng)目(61401440)；上海市國際科技合作基金項(xiàng)目(14510722300)

2016-04-27