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

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

?

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

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

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

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

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

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

雖然OIDGE算法在很大程度上降低了解碼的計(jì)算復(fù)雜度，但是在嵌入式系統(tǒng)上仍然難以滿足接收系統(tǒng)的實(shí)時(shí)性要求。而DRFD算法的性能受信道符號(hào)刪除率的影響較大，在高丟包率信道條件下的性能反而下降。因此本文對(duì)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ù)目的百分比，選擇對(duì)應(yīng)的解碼模式。實(shí)驗(yàn)結(jié)果表明，該算法可以在不同丟包率情況下自適應(yīng)地選擇合適的解碼算法，在低丟包率時(shí)選擇DRFD解碼，在高丟包率時(shí)選擇OIDGE解碼，提高了RaptorQ碼的解碼速度。

1 RaptorQ碼的解碼

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

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

C=A-1·D

(1)

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

1.1 OIDGE解碼算法

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

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

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

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

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

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

1.2 DRFD算法

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

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

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

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中抽取對(duì)應(yīng)于S和R的列組成的集合；s×T維矩陣d0={D0}j∈S和r×T維矩陣dx={Dx}j∈R分別代表從D0和DX中抽取對(duì)應(yīng)于S和R的行組成的集合。從式(2)可得

(3)

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

雖然總是有r≤K

2 模式選擇算法

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

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

圖1 模式選擇解碼器

2.2 模式選擇解碼過(guò)程

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

圖2 模式選擇解碼流程圖

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

第一步：生成選擇器。

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

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

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

第三步：子解碼器解碼。

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

2.3 性能分析

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

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

本算法在信道丟包率較低時(shí)的計(jì)算復(fù)雜度為O(r3)，在信道丟包率大于10%左右時(shí)的計(jì)算復(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語(yǔ)言程序?qū)崿F(xiàn)了RaptorQ碼的解碼過(guò)程，分別對(duì)OIDGE算法，DRFD算法與本文提出的MSD算法進(jìn)行了測(cè)試。每個(gè)數(shù)據(jù)塊包含K=64個(gè)源符號(hào)，每個(gè)符號(hào)長(zhǎng)度為T=1 024 byte，經(jīng)過(guò) RaptorQ 編碼后生成長(zhǎng)度為N=80的編碼符號(hào)塊，然后在刪除信道上進(jìn)行傳輸。接收端對(duì)接收到的編碼符號(hào)進(jìn)行緩存和解碼。對(duì)每個(gè)數(shù)據(jù)塊重復(fù)多次進(jìn)行上述過(guò)程，直到接收端成功解碼為止。這里開(kāi)發(fā)了RaptorQ編譯碼算法庫(kù)，并把它集成到了開(kāi)源項(xiàng)目上，用來(lái)實(shí)現(xiàn)符合FLUTE(File Delivery over Unidirectional Transport)協(xié)議的文件傳輸。其中發(fā)送端調(diào)用RaptorQ編碼，運(yùn)行在一臺(tái)PC機(jī)上；接收端(嵌入式主板)調(diào)用RaptorQ解碼。通過(guò)測(cè)試，得出3種解碼算法的耗時(shí)圖如圖3所示。

圖3 OIDGE，DRFD，MSD算法的解碼時(shí)間

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

4 結(jié)論

本文針對(duì)RaptorQ碼解碼復(fù)雜度高的問(wèn)題，提出了一種模式選擇解碼算法，該方法綜合考慮了信道的實(shí)際丟包情況與不同解碼算法的效率，根據(jù)計(jì)算所得丟包率，選擇對(duì)應(yīng)的解碼模式。實(shí)驗(yàn)結(jié)果表明，該算法適用于嵌入式系統(tǒng)中的各種丟包率的場(chǎ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é)報(bào), 2015, 37(6): 1310-1316.

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

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

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

朱秋煜(1964— )，教授，主研圖像處理、模式識(shí)別、計(jì)算機(jī)視覺(jué)、智慧城市、計(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)；國(guó)家基金委青年科學(xué)基金項(xiàng)目(61401440)；上海市國(guó)際科技合作基金項(xiàng)目(14510722300)

2016-04-27