高家利

(重慶理工大學(xué) 工程訓(xùn)練中心，重慶 400054)

一種Raptor碼編碼技術(shù)的改進(jìn)算法

高家利

(重慶理工大學(xué) 工程訓(xùn)練中心，重慶 400054)

為了減少流媒體服務(wù)器的運(yùn)算負(fù)荷，提供更長(zhǎng)的應(yīng)用層前向糾錯(cuò)保護(hù)周期，避免出現(xiàn)丟包重傳工作，對(duì)傳統(tǒng)Raptor編碼算法進(jìn)行了改進(jìn)。針對(duì)已知區(qū)塊長(zhǎng)度的源碼，預(yù)先計(jì)算出相應(yīng)的運(yùn)算序列，再來(lái)產(chǎn)生編碼符號(hào)。實(shí)驗(yàn)結(jié)果顯示，改進(jìn)算法與傳統(tǒng)算法相比，編碼速度至少提高2倍左右。

Raptor碼；流媒體；應(yīng)用層前向糾錯(cuò)；運(yùn)算序列

近年來(lái)隨著國(guó)家對(duì)網(wǎng)絡(luò)建設(shè)的不斷投入，網(wǎng)絡(luò)覆蓋率和網(wǎng)速不斷提升，基于IP網(wǎng)絡(luò)的多媒體應(yīng)用范圍也在不斷擴(kuò)大，例如交互式網(wǎng)絡(luò)電視(IPTV)、WiFi多播、視頻點(diǎn)播、多源下載和數(shù)據(jù)存儲(chǔ)等[1]。但在利用IP網(wǎng)絡(luò)進(jìn)行流媒體傳播的過(guò)程中，會(huì)出現(xiàn)丟包現(xiàn)象，影響視頻播放質(zhì)量。為了解決這一問(wèn)題，在DVB-H標(biāo)準(zhǔn)和3GPP的MBMS標(biāo)準(zhǔn)中，都采用Raptor碼作為前向糾刪碼，為視頻傳輸系統(tǒng)提供一種有效的差錯(cuò)控制策略。

Raptor碼是一種實(shí)用的噴泉碼，由Shokrollahi于2006年在LT碼基礎(chǔ)上改進(jìn)而來(lái)。對(duì)流媒體服務(wù)器來(lái)說(shuō)，Raptor碼的編碼雖然很有效率，但如果同時(shí)支持多個(gè)頻道的即時(shí)信號(hào)時(shí)，服務(wù)器的編碼工作量將非常大。特別是在源碼碼長(zhǎng)較大時(shí)，比如支持更高清晰度的視頻信號(hào)或信號(hào)在強(qiáng)干擾的情況下傳播，服務(wù)器的負(fù)荷將會(huì)加大，成為制約流媒體服務(wù)可擴(kuò)展性的一個(gè)重要因素。因此，改進(jìn)現(xiàn)有Raptor碼的編碼效率仍然是十分必要的。韓國(guó)高麗大學(xué)的Jun Heo等人提出以增量式高斯消元法為基礎(chǔ)加快Raptor碼的編碼速度[2]。中國(guó)傳媒大學(xué)的張銓等人提出通過(guò)修改Raptor碼生成矩陣來(lái)降低高斯消元法的運(yùn)算復(fù)雜度[3]。上海交通大學(xué)的余國(guó)華等人在Raptor碼譯碼方式上提供了自己的優(yōu)化思路[4]。本文通過(guò)先計(jì)算出運(yùn)算序列的方式來(lái)提高編碼效率。

1 Raptor碼編碼技術(shù)

傳統(tǒng)的Raptor編碼主要包含兩個(gè)部分，預(yù)編碼和LT編碼，如圖1所示。預(yù)編碼過(guò)程是將源符號(hào)通過(guò)傳統(tǒng)糾刪碼轉(zhuǎn)換為中間編碼符號(hào)。然后對(duì)中間編碼符號(hào)采用弱化LT碼再次進(jìn)行編碼，最終生成編碼符號(hào)。在解碼過(guò)程中，先利用LT譯碼恢復(fù)固定比例的中間編碼校驗(yàn)單元，再利用傳統(tǒng)糾刪碼的譯碼方式恢復(fù)出源碼[5-7]。通過(guò)模擬實(shí)驗(yàn)發(fā)現(xiàn)，在Raptor編碼過(guò)程中，大部分時(shí)間都花在預(yù)編碼階段：用源符號(hào)產(chǎn)生中間校驗(yàn)碼符號(hào)，即用高斯消元法解出X=M-1Y，其中M是中間編碼符號(hào)集的生成矩陣，Y是源碼符號(hào)集衍生的擴(kuò)充集的列向量。

在3GPP MBMS和DVB-H標(biāo)準(zhǔn)中，所使用的Raptor編碼算法IETF RFC 5053中有個(gè)重要特征，當(dāng)兩個(gè)源符號(hào)塊的大小K(源符號(hào)塊包含的編碼符號(hào)數(shù))相同時(shí)，就算源碼包含的原始信息不同，二者的中間符號(hào)生成矩陣M也是完全相同的，即使二者所使用的編碼符號(hào)大小不同也沒(méi)有影響。對(duì)一個(gè)流媒體服務(wù)來(lái)說(shuō)，在上述標(biāo)準(zhǔn)的前向糾錯(cuò)框架中，所使用的應(yīng)用層前向糾錯(cuò)(AL-FEC)源符號(hào)塊的區(qū)塊長(zhǎng)度是固定的，也就是說(shuō)很多源符號(hào)塊長(zhǎng)度K是已知的。如果先執(zhí)行一次高斯消元得到M-1，再利用預(yù)先計(jì)算好的M-1來(lái)計(jì)算接下來(lái)的每個(gè)來(lái)源符號(hào)塊的中間編碼符號(hào)塊Y，則編碼的時(shí)間會(huì)縮短很多。

圖1 傳統(tǒng)Raptor碼編碼方案

2 Raptor碼編碼改進(jìn)算法

通過(guò)高斯消元法得到M-1后，求中間編碼符號(hào)塊X時(shí)，只需要進(jìn)行M-1與Y之間的矩陣乘法，但在實(shí)際應(yīng)用時(shí)，K的值通常比較大，例如：4096、6144、8192等。矩陣乘法的計(jì)算成本仍然相當(dāng)高，經(jīng)過(guò)觀察，這其中許多部分的運(yùn)算可以簡(jiǎn)化。如圖2所示，假設(shè)xij為源碼符號(hào)塊i的第j個(gè)中間編碼符號(hào)，yij為源碼符號(hào)塊i的第j個(gè)擴(kuò)充源碼符號(hào)，運(yùn)算+為XOR運(yùn)算，在其中，xi,9需要經(jīng)過(guò)6次XOR運(yùn)算才能得到，然而，若xi,18的值是已知的，則只需要1次XOR運(yùn)算就可以得到xi,9，即xi,9=xi,18+yi,14。K=7時(shí)中間編碼符號(hào)計(jì)算方式(M=20×20)為

(1)

圖2 改進(jìn)Raptor編碼算法框圖

上述情況在其他的中間編碼符號(hào)產(chǎn)生過(guò)程中也存在，因此，如果按照一個(gè)特定的順序來(lái)依次算出每個(gè)中間編碼符號(hào)，而不是直接進(jìn)行矩陣乘法，則會(huì)減少一定程度的運(yùn)算量。本文使用一個(gè)預(yù)編碼運(yùn)算發(fā)生器來(lái)產(chǎn)生上述的特定運(yùn)算序列OL，預(yù)編碼運(yùn)算發(fā)生器由預(yù)編碼矩陣發(fā)生器、預(yù)編碼運(yùn)算序列發(fā)生器和預(yù)編碼運(yùn)算序列存儲(chǔ)這3部分構(gòu)成。因此提出的Raptor碼改進(jìn)算法的框架圖如圖2所示，包含預(yù)編碼運(yùn)算發(fā)生器和基于運(yùn)算序列的Raptor碼編碼器2個(gè)模塊。

2.1 預(yù)編碼矩陣發(fā)生器

如果預(yù)編碼矩陣發(fā)生器輸出一個(gè)生成矩陣M并傳送給預(yù)編碼運(yùn)算序列發(fā)生器，相應(yīng)的新運(yùn)算序列就會(huì)產(chǎn)生，并輸出給快速中間符號(hào)發(fā)生器，新運(yùn)算序列和相對(duì)應(yīng)的K值被存儲(chǔ)在預(yù)編碼運(yùn)算序列存儲(chǔ)器中，預(yù)編碼矩陣發(fā)生器的算法如下：

Require：Block length K

Ask Precode Operation List Storage whether K is changed or not

if K is unchanged then

Let Procode Operation List Storage output Stored OL directly

else

Generates M and then outputs M and K to Procode Operation List Generator

end if

2.2 預(yù)編碼運(yùn)算序列發(fā)生器

預(yù)編碼運(yùn)算序列發(fā)生器在接收到一個(gè)矩陣M后，會(huì)產(chǎn)生相對(duì)應(yīng)的運(yùn)算序列OL。這里使用RFC 5053標(biāo)準(zhǔn)算法產(chǎn)生的運(yùn)算序列具有2個(gè)優(yōu)點(diǎn)：一是產(chǎn)生運(yùn)算序列的時(shí)間快；二是通過(guò)運(yùn)算序列產(chǎn)生中間編碼符號(hào)的速度快。因?yàn)樵跀U(kuò)展來(lái)源符號(hào)上的符號(hào)運(yùn)算就是高斯消元法的列運(yùn)算，即XOR和排列運(yùn)算，即

XOR:Yi=Yi⊕Yj

(1)

Permutation：IMSi=Yj

(2)

上面的2種運(yùn)算在記錄時(shí)，都使用相同的[ij]格式，兩種運(yùn)算在高斯消元法中不會(huì)交錯(cuò)發(fā)生，所有的XOR運(yùn)算結(jié)束后排列運(yùn)算才會(huì)開始，因此使用2個(gè)不同的子運(yùn)算序列來(lái)記錄比較合適。

2.3 快速中間符號(hào)編碼器

將源符號(hào)塊轉(zhuǎn)換為擴(kuò)展源符號(hào)塊，在這個(gè)過(guò)程中，會(huì)有一些值為0的列向量被放在所有的源符號(hào)之前，然后使用XOR子運(yùn)算序列逐一修改擴(kuò)展源符號(hào)集的列向量，運(yùn)算結(jié)果為暫存符號(hào)塊TS(Temporary Symbol Set)。再使用排列子運(yùn)算序列來(lái)安排TS中元素與中間符號(hào)塊的元素間的關(guān)系，最后得到完整的中間編碼符號(hào)塊IMS。整個(gè)運(yùn)算過(guò)程如圖3所示。

圖3 利用運(yùn)算序列產(chǎn)生中間編碼符號(hào)

2.4 運(yùn)算序列存儲(chǔ)器

通過(guò)模擬計(jì)算，表1列出了源符號(hào)塊的區(qū)塊長(zhǎng)度K的值為1 024～8192，在硬盤和內(nèi)存中記錄一個(gè)運(yùn)算序列所需要的容量大小。RFC 5053標(biāo)準(zhǔn)中的Raptor碼所支持的最大區(qū)塊長(zhǎng)度為8192，相應(yīng)的運(yùn)算序列所需容量大?。河脖P中只需要620kbyte，在內(nèi)存中只需要1 970kbyte。對(duì)目前的計(jì)算機(jī)來(lái)說(shuō)，所需的存儲(chǔ)空間并不大。因此，可以先計(jì)算出不同K值設(shè)定的運(yùn)算序列，預(yù)先載入到Raptor編碼器的內(nèi)存中。

表1 運(yùn)算序列所需的存儲(chǔ)空間

3 效果比較與分析

在高鐵車廂內(nèi)，通過(guò)WiFi傳送具備SD清晰度的多播流媒體數(shù)據(jù)時(shí)，一般采用的編碼參數(shù)只需設(shè)定為：編碼符號(hào)大小固定為1 024byte，區(qū)塊長(zhǎng)度K設(shè)定為3072～6144。實(shí)驗(yàn)選擇的區(qū)塊長(zhǎng)度從1 024～8192，編碼符號(hào)大小分別為512 byte，1 024byte和1 536byte。針對(duì)上述參數(shù)設(shè)定，改進(jìn)Raptor算法與傳統(tǒng)算法進(jìn)行了比較實(shí)驗(yàn)。實(shí)驗(yàn)在同一臺(tái)計(jì)算機(jī)上完成，所使用的計(jì)算機(jī)內(nèi)存為4Gbyte，CPU為AMD雙核(A6-5200)2.0GHz。圖4為編碼100個(gè)K值相同的來(lái)源區(qū)塊的平均編碼時(shí)間。

圖4 傳統(tǒng)算法與改進(jìn)算法效果對(duì)比圖

從圖中可以看出，使用改進(jìn)算法的編碼器，其編碼吞吐量是傳統(tǒng)編碼器的2倍，當(dāng)K值為8192時(shí)，吞吐量則可以達(dá)到傳統(tǒng)編碼器的10倍左右。此外，采用改進(jìn)算法的編碼器，其編碼時(shí)間會(huì)隨著K值的增加而線性增長(zhǎng)，傳統(tǒng)編碼器則是以二次方的速度增加。這樣就可以采用更大的K值來(lái)獲得更長(zhǎng)的前向糾錯(cuò)的保護(hù)周期，同時(shí)還避免高斯消元法所需的時(shí)間會(huì)隨著K值得增加而快速暴增的問(wèn)題。另外，當(dāng)K值固定時(shí)，改進(jìn)算法的編碼器的編碼時(shí)間也會(huì)隨著編碼符號(hào)的增大而線性遞增，這說(shuō)明編碼器在運(yùn)作時(shí)大部分時(shí)間都是花在符號(hào)運(yùn)算上。

4 結(jié)論

為了保證流媒體的傳播質(zhì)量，3GPP MBMS標(biāo)準(zhǔn)、DVB標(biāo)準(zhǔn)和IETF標(biāo)準(zhǔn)都包含了一個(gè)相同的前向糾錯(cuò)框架。本文所提出的改進(jìn)的Raptor算法可以應(yīng)用在上述標(biāo)準(zhǔn)的前向糾錯(cuò)方案中，用來(lái)減輕流媒體服務(wù)器的編碼計(jì)算工作量，實(shí)驗(yàn)結(jié)果顯示，編碼效率至少提高了2倍。編碼速度提高后，相同的服務(wù)器可以支持更大的編碼區(qū)塊，讓Raptor碼可以保護(hù)更高清晰度的流媒體服務(wù)，或提供更長(zhǎng)的應(yīng)用層前向糾錯(cuò)保護(hù)周期，在傳播過(guò)程中能夠抵抗突發(fā)的丟包現(xiàn)象。

[1]徐茂.流媒體服務(wù)器性能調(diào)優(yōu)關(guān)鍵點(diǎn)分析[J].電視技術(shù),2014,38(12): 114-116.

[2]HEO J, KIM S, KIM J.Low complexity decoding for Raptor codes for hybrid-ARQ systems[J].IEEE Trans.Consumer Electronics, 2008, 54(2):390-395.

[3]ZHANG Quan, XU Weizhang, SHI Dongxin, et al.An improved algorithm of 3GPP MBMS Raptor codes[C]//Proc.2010International Conference on Measuring Technology and Mechatronics Automation.Changsha，China：IEEE Press，2010：492-495.

[4]余國(guó)華，楊宇航，魏岳軍.Raptor碼譯碼算法的改進(jìn)方案[J].通信技術(shù),2010,43(8):87-91.

[5]高飛，曾憲鋒，卜祥元.基于調(diào)頻通信的短碼長(zhǎng)Raptor碼改進(jìn)方案[J].北京理工大學(xué)學(xué)報(bào),2013,33(4):403-407.

[6]孟慶春，王曉京.Raptor Code預(yù)編碼技術(shù)研究[J].計(jì)算機(jī)工程，2007，33(1):1-3.

[7]張偉.基于反饋的Raptor碼的編碼算法研究[J].廣東通信技術(shù),2014(3):67-70.

Improved Algorithm for Coding of Raptor Codes

GAO Jiali

(TheEngineeringTrainingCenter,ChongqingUniversityofTechnology,Chongqing400054,China)

To reduce the operation load of the streaming media servers, support a longer protection period, and avoid the packet retransmission, the coding algorithm of classical Raptor codes is improved.For the known source block lengths, firstly, calculate the operation list of the source codes, then operate the coding symbols.The experimental results show that, compared with the classical algorithm, the speed of the coding is increased by two times at least.

Raptor codes；streaming severs；AL-FEC；operation list

【本文獻(xiàn)信息】高家利.一種Raptor碼編碼技術(shù)的改進(jìn)算法[J].電視技術(shù),2015，39(3).

重慶市教委科學(xué)技術(shù)研究項(xiàng)目(0103121276)

TN911.22

A

10.16280/j.videoe.2015.03.024

責(zé)任編輯：薛 京

2014-07-27

高家利(1981— )，碩士，工程師，主研自組織網(wǎng)絡(luò)通信與信息系統(tǒng)。