一種Raptor碼編碼技術的改進算法

高家利

(重慶理工大學 工程訓練中心，重慶 400054)

一種Raptor碼編碼技術的改進算法

高家利

(重慶理工大學 工程訓練中心，重慶 400054)

為了減少流媒體服務器的運算負荷，提供更長的應用層前向糾錯保護周期，避免出現丟包重傳工作，對傳統Raptor編碼算法進行了改進。針對已知區塊長度的源碼，預先計算出相應的運算序列，再來產生編碼符號。實驗結果顯示，改進算法與傳統算法相比，編碼速度至少提高2倍左右。

Raptor碼；流媒體；應用層前向糾錯；運算序列

近年來隨著國家對網絡建設的不斷投入，網絡覆蓋率和網速不斷提升，基于IP網絡的多媒體應用范圍也在不斷擴大，例如交互式網絡電視(IPTV)、WiFi多播、視頻點播、多源下載和數據存儲等[1]。但在利用IP網絡進行流媒體傳播的過程中，會出現丟包現象，影響視頻播放質量。為了解決這一問題，在DVB-H標準和3GPP的MBMS標準中，都采用Raptor碼作為前向糾刪碼，為視頻傳輸系統提供一種有效的差錯控制策略。

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

1 Raptor碼編碼技術

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

在3GPP MBMS和DVB-H標準中，所使用的Raptor編碼算法IETF RFC 5053中有個重要特征，當兩個源符號塊的大小K(源符號塊包含的編碼符號數)相同時，就算源碼包含的原始信息不同，二者的中間符號生成矩陣M也是完全相同的，即使二者所使用的編碼符號大小不同也沒有影響。對一個流媒體服務來說，在上述標準的前向糾錯框架中，所使用的應用層前向糾錯(AL-FEC)源符號塊的區塊長度是固定的，也就是說很多源符號塊長度K是已知的。如果先執行一次高斯消元得到M-1，再利用預先計算好的M-1來計算接下來的每個來源符號塊的中間編碼符號塊Y，則編碼的時間會縮短很多。

圖1 傳統Raptor碼編碼方案

2 Raptor碼編碼改進算法

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

(1)

圖2 改進Raptor編碼算法框圖

上述情況在其他的中間編碼符號產生過程中也存在，因此，如果按照一個特定的順序來依次算出每個中間編碼符號，而不是直接進行矩陣乘法，則會減少一定程度的運算量。本文使用一個預編碼運算發生器來產生上述的特定運算序列OL，預編碼運算發生器由預編碼矩陣發生器、預編碼運算序列發生器和預編碼運算序列存儲這3部分構成。因此提出的Raptor碼改進算法的框架圖如圖2所示，包含預編碼運算發生器和基于運算序列的Raptor碼編碼器2個模塊。

2.1 預編碼矩陣發生器

如果預編碼矩陣發生器輸出一個生成矩陣M并傳送給預編碼運算序列發生器，相應的新運算序列就會產生，并輸出給快速中間符號發生器，新運算序列和相對應的K值被存儲在預編碼運算序列存儲器中，預編碼矩陣發生器的算法如下：

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 預編碼運算序列發生器

預編碼運算序列發生器在接收到一個矩陣M后，會產生相對應的運算序列OL。這里使用RFC 5053標準算法產生的運算序列具有2個優點：一是產生運算序列的時間快；二是通過運算序列產生中間編碼符號的速度快。因為在擴展來源符號上的符號運算就是高斯消元法的列運算，即XOR和排列運算，即

XOR:Yi=Yi⊕Yj

(1)

Permutation：IMSi=Yj

(2)

上面的2種運算在記錄時，都使用相同的[ij]格式，兩種運算在高斯消元法中不會交錯發生，所有的XOR運算結束后排列運算才會開始，因此使用2個不同的子運算序列來記錄比較合適。

2.3 快速中間符號編碼器

將源符號塊轉換為擴展源符號塊，在這個過程中，會有一些值為0的列向量被放在所有的源符號之前，然后使用XOR子運算序列逐一修改擴展源符號集的列向量，運算結果為暫存符號塊TS(Temporary Symbol Set)。再使用排列子運算序列來安排TS中元素與中間符號塊的元素間的關系，最后得到完整的中間編碼符號塊IMS。整個運算過程如圖3所示。

圖3 利用運算序列產生中間編碼符號

2.4 運算序列存儲器

通過模擬計算，表1列出了源符號塊的區塊長度K的值為1 024～8192，在硬盤和內存中記錄一個運算序列所需要的容量大小。RFC 5053標準中的Raptor碼所支持的最大區塊長度為8192，相應的運算序列所需容量大小：硬盤中只需要620kbyte，在內存中只需要1 970kbyte。對目前的計算機來說，所需的存儲空間并不大。因此，可以先計算出不同K值設定的運算序列，預先載入到Raptor編碼器的內存中。

表1 運算序列所需的存儲空間

3 效果比較與分析

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

圖4 傳統算法與改進算法效果對比圖

從圖中可以看出，使用改進算法的編碼器，其編碼吞吐量是傳統編碼器的2倍，當K值為8192時，吞吐量則可以達到傳統編碼器的10倍左右。此外，采用改進算法的編碼器，其編碼時間會隨著K值的增加而線性增長，傳統編碼器則是以二次方的速度增加。這樣就可以采用更大的K值來獲得更長的前向糾錯的保護周期，同時還避免高斯消元法所需的時間會隨著K值得增加而快速暴增的問題。另外，當K值固定時，改進算法的編碼器的編碼時間也會隨著編碼符號的增大而線性遞增，這說明編碼器在運作時大部分時間都是花在符號運算上。

4 結論

為了保證流媒體的傳播質量，3GPP MBMS標準、DVB標準和IETF標準都包含了一個相同的前向糾錯框架。本文所提出的改進的Raptor算法可以應用在上述標準的前向糾錯方案中，用來減輕流媒體服務器的編碼計算工作量，實驗結果顯示，編碼效率至少提高了2倍。編碼速度提高后，相同的服務器可以支持更大的編碼區塊，讓Raptor碼可以保護更高清晰度的流媒體服務，或提供更長的應用層前向糾錯保護周期，在傳播過程中能夠抵抗突發的丟包現象。

[1]徐茂.流媒體服務器性能調優關鍵點分析[J].電視技術,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]余國華，楊宇航，魏岳軍.Raptor碼譯碼算法的改進方案[J].通信技術,2010,43(8):87-91.

[5]高飛，曾憲鋒，卜祥元.基于調頻通信的短碼長Raptor碼改進方案[J].北京理工大學學報,2013,33(4):403-407.

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

[7]張偉.基于反饋的Raptor碼的編碼算法研究[J].廣東通信技術,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

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

重慶市教委科學技術研究項目(0103121276)

TN911.22

A

10.16280/j.videoe.2015.03.024

責任編輯：薛 京

2014-07-27

高家利(1981— )，碩士，工程師，主研自組織網絡通信與信息系統。