一种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— )，硕士，工程师，主研自组织网络通信与信息系统。