一种RaptorQ码的模式选择解码算法

李 越，张立军，李明齐，朱秋煜

(1.上海大学,上海 200444；2.中国科学院 上海高等研究院，上海 201210)



一种RaptorQ码的模式选择解码算法

李 越1,2，张立军2，李明齐2，朱秋煜1

(1.上海大学,上海 200444；2.中国科学院 上海高等研究院，上海 201210)

针对 RaptorQ 码解码复杂度高的问题，提出了一种模式选择解码(MSD)算法。该方法结合优化失活解码高斯消元(OIDGE)算法与快速降维解码(DRFD)算法的优点，综合考虑了信道的实际丢包情况与不同解码算法的效率，根据计算所得丢包率，选择合适的解码算法。在嵌入式系统上进行了实验，结果表明，该算法在不同丢包率情况下可以自适应地选择合适的解码算法，提高了RaptorQ码的解码效率。

应用层FEC；喷泉码；RaptorQ码；高斯消元解码

近几年互联网数据流量大幅度增长，为了有效地支持流媒体传输和文件分发，3GPP-MBMS和DVB-H IPDC都将喷泉码作为应用层的前向纠错(AL-FEC)方案[1-2]。LT码[3]是第一个实用的喷泉码编码方案。Raptor码[4]通过将LDPC码与LT码级联，降低了解码开销。RaptorQ码是一种定义在伽罗华域 GF(256)上的Raptor码，它继承了所有Raptor码的基本属性和编解码处理流程，同时能降低解码失败概率，但在编解码的过程中需要对预编码矩阵进行复杂的求逆运算，导致其解码复杂度较高。IETF RFC 6330[5]根据码约束矩阵具有稀疏性的特点，提出了失活解码高斯消元算法(Inactivation Decoding Gaussian Elimination, IDGE)，文献[6]在此基础上提出了优化失活解码高斯消元(Optimized Inactivation Decoding Gaussian Elimination, OIDGE)算法，该算法通过简化解码步骤和对行选择方法进行优化，提高了解码计算的效率。文献[7]首次提出增量解码(Incremental Decoding)的概念，另外，文献[8]和[9]提出了两种增量高斯消元解码算法，结果均表明增量解码技术优于重新解码的方法。文献[10]提出一种降维快速解码(Dimensionality Reduced Fast Decoding, DRFD)算法，该算法通过降低矩阵维数，降低了解码复杂度，但算法的性能受信道符号删除率的影响较大。在信道符号删除概率较高(>0.1)时，该算法的解码速度明显下降。

虽然OIDGE算法在很大程度上降低了解码的计算复杂度，但是在嵌入式系统上仍然难以满足接收系统的实时性要求。而DRFD算法的性能受信道符号删除率的影响较大，在高丢包率信道条件下的性能反而下降。因此本文对RaptorQ码的解码机制进行改进，在OIDGE算法与DRFD算法的基础上，提出了一种RaptorQ码的模式选择解码(Mode Selection Decoding, MSD)算法，该方法综合考虑了信道的实际丢包情况与两种解码算法的效率，根据当前接收到的编码数据块中丢失的数据包数目占总数据包数目的百分比，选择对应的解码模式。实验结果表明，该算法可以在不同丢包率情况下自适应地选择合适的解码算法，在低丢包率时选择DRFD解码，在高丢包率时选择OIDGE解码，提高了RaptorQ码的解码速度。

1 RaptorQ码的解码

RaptorQ码由预编码和LT编码级联构成的线性码。编码分为预编码和LT编码两个过程。预编码过程通过一个预编码矩阵A生成中间符号，首先将K个源符号增补得到K′，对应K′个源符号向量，接着进行预编码产生L(L=K′+S+H)个中间符号，其中K′表示源符号，S表示LDPC符号，H表示HDPC符号。最后由中间符号进行LT编码产生最终的编码符号[5]。

RaptorQ 的解码过程相当于，通过对预编码矩阵A进行高斯消元求逆矩阵，还原出中间符号向量。其过程可表示为

C=A-1·D

(1)

式中：D表示接收到的编码符号向量；C表示恢复出的中间编码符号向量。然后对中间符号向量C进行LT编码来恢复出源数据符号向量[7]。

1.1 OIDGE解码算法

文献[4]的增强高斯消元解码算法(EGE)认为，如果标准的高斯消元过程进行成功，可以直接进行回代，解码成功；如果高斯消元过程失败，则重新执行高斯消元步骤，直至成功解码。

文献[5]中失活高斯消元算法常被叫做IDGE算法。它利用置信度传播的方法寻找出可以解码的符号，同时生成一个与A同维度的矩阵X，用来记录在A矩阵上进行的行/列变换操作。该算法在求解预编码矩阵的逆的过程中，分别进行置信度传播、高斯消元和前向消元的步骤。由于该算法需要对矩阵X进行矩阵乘法运算寻找失活符号，反而增加了计算量。

针对这一问题，在文献[6]中提出一种优化算法——OIDGE算法。该算法避免了对矩阵X的乘法运算，直接对UM×u(upper)进行消元。虽然此时UM×u(upper)是稠密的，只需要消去在解码输出时用到的部分行即可，其他行不需要进行消元。由于省略了与X的乘法，A矩阵左上角仍为单位阵，故 OIDGE 算法只需3步即可完成矩阵A的逆运算。

文献[5]提出增量解码(Incremental Decoding)的概念，当高斯消元过程失败时，将增加接收编码符号的个数，以获得行数足够多的预编码矩阵，保证预编码矩阵的满秩性。当解码失败时只需在解码失败矩阵的基础上进行修补解码，避免了需要从头开始解码而造成的解码时延。

在运行频率为1 GHz的Freescale ARM架构的嵌入式主板上测试了RaptorQ码的解码过程，对IDGE与OIDGE解码算法中每个数据块解码的时间消耗进行比较。每个数据块包含K个源符号，经过 RaptorQ 编码后生成长度为N个编码符号块。结果如表1所示，其中K表示每个数据块包含源符号的个数，T表示每个符号的字节长度。

表1 每个数据块解码时间消耗μs

1.2 DRFD算法

文献[10]利用 RaptorQ 码是系统码的特性，提出一种降维快速解码算法。该算法的原理是利用预先计算的逆矩阵，将解码过程中对接收编码约束矩阵的求逆转化为对更小维数矩阵的求逆，以降低解码复杂度。该算法的解码效果与现有解码算法等价。实验结果表明，该算法降低了矩阵求逆的维度，在信道符号删除概率较低(<0.1)时，该算法的解码速度明显高于现有算法，且算法复杂度远低于IDGE算法。

DRFD算法的具体步骤是通过矩阵变换将求逆的对象由L×L维的预编码矩阵A变换为r×r维矩阵Gx，其中r=K-s，s是一个数据块中接收到的信息符号的个数，r是该数据块中丢失的信息符号个数。在低丢包率的情况下，有r≪L，因而复杂度降低。

在一个数据块中，可以把接收到的L×T维符号矩阵D分解为D=D0+Dx，其中D0包含接收到的s个信息符号，Dx包含丢失的r个信息符号，其余部分为0。记S为接收到的信息符号组成的集合，R为丢失的信息符号组成的集合。注意到D=A·C，则接收到的r个修复符号可以表示为

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中抽取对应于S和R的列组成的集合；s×T维矩阵d0={D0}j∈S和r×T维矩阵dx={Dx}j∈R分别代表从D0和DX中抽取对应于S和R的行组成的集合。从式(2)可得

(3)

其中A-1可预先求得，实际解码过程中只需用高斯消元法对Gx求逆。

虽然总是有r≤K

2 模式选择算法

2.1 解码器的结构

为了提高RaptorQ码的解码效率，本节提出一种用于RaptorQ码的模式选择解码(MSD)算法,该算法结合了OIDGE算法和DRFD算法的优点。如图1所示，分配器Allocator为接收到的每一个数据块分配一个选择器Selector，并将接收到的符号按数据块分别缓存在相应的选择器中。选择器根据接收到信息符号的数量来选择解码算法。

图1 模式选择解码器

2.2 模式选择解码过程

模式选择解码算法流程图如图2所示。

图2 模式选择解码流程图

首先进行初始化。

第一步：生成选择器。

接收一个编码符号Symbol(i,j)，它属于第i个文件的第j个数据块。分配器在已有的子解码器列表中检索(i,j)，检查是否有选择器Selector(i,j)与之对应。若存在对应的Symbol(i,j)，则将(i,j)输入给它；若没有对应的选择器，则由分配器创建一个新的选择器Selector(i,j)，重置编码符号个数NUM(i,j)=0，将Symbol(i,j)输入给它，跳转至第二步。

第二步：选择器Selector(i,j)接收到符号Symbol(i,j)。

若该选择器已创建子解码器Sub-Decoder(i,j)，则将符号输入到该子解码器，跳转至第三步。若尚未创建子解码器Sub-Decoder(i,j)，则将符号存入缓存，记录当前编码符号个数NUM(i,j)，若当前编码符号个数NUM(i,j)

第三步：子解码器解码。

若解码成功，则对序列号ESI=1:K输出源符号，该数据块解码完毕，删除选择器Selector(i,j)和子解码器Sub-Decoder(i,j) ；若解码失败，则跳转至第一步进行增量解码。

2.3 性能分析

在高斯消元法可以恢复源数据块的情况下，失活解码算法也能保证对其恢复，并且效率更高。失活解码算法在第一步和第三步使用置信度传播解码，解码时间是线性的。因此，在源数据块范围内，整个失活解码过程解码时间是线性的，采用IDGE/OIDGE算法[5-6]，其复杂度是O(L2)。

DRFD算法使用降维变换降低了GE算法的矩阵的维数。该算法改变了传统的两步译码结构，无需先译出中间符号，直接通过接收的编码符号译出丢失的源符号。虽然计算Gx=GLT·{A-1}i∈R的过程需要引入矩阵乘法和加法，在一定程度上增加了计算量。但矩阵GLT(i), i∈R为二进制稀疏矩阵，对A-1中的行进行异或操作即可计算出Gx，省去了GF(256)上的矩阵乘法。假设信道的丢包率为p，则矩阵GLT(i), i∈R的行数r约为pK,矩阵Gx的译码计算复杂度为O(pKL)，L为中间符号的个数，略大于K。而对Gx的消元只能采用标准高斯消元算法，其复杂度是O(r3)[8]，DRFD 算法整体的计算复杂度为O(p3k3)[8]。因此，在丢包率比较高的情况下，r值较大，后者的复杂度反而高于前者；在低丢包率的情况下，有r≤L，因而复杂度降低。

本算法在信道丢包率较低时的计算复杂度为O(r3)，在信道丢包率大于10%左右时的计算复杂度为O(L2)。

3 实验结果

算法验证分别在PC机(64位处理器，Interl®CoreTM2 E7200 2.53 GHz)和Freescale ARM架构的嵌入式主板上进行。嵌入式主板采用飞思卡尔酷睿A9系列处理器，运行频率为1 GHz。用C语言程序实现了RaptorQ码的解码过程，分别对OIDGE算法，DRFD算法与本文提出的MSD算法进行了测试。每个数据块包含K=64个源符号，每个符号长度为T=1 024 byte，经过 RaptorQ 编码后生成长度为N=80的编码符号块，然后在删除信道上进行传输。接收端对接收到的编码符号进行缓存和解码。对每个数据块重复多次进行上述过程，直到接收端成功解码为止。这里开发了RaptorQ编译码算法库，并把它集成到了开源项目上，用来实现符合FLUTE(File Delivery over Unidirectional Transport)协议的文件传输。其中发送端调用RaptorQ编码，运行在一台PC机上；接收端(嵌入式主板)调用RaptorQ解码。通过测试，得出3种解码算法的耗时图如图3所示。

图3 OIDGE，DRFD，MSD算法的解码时间

3条曲线分别代表了3种算法的解码时间随着丢包率变化的趋势。结果显示DRFD算法在丢包率低于10%的范围内解码时间比OIDGE短，但在其他范围内耗时明显增加，而OIDGE 解码时间较平稳。MSD算法则结合了两者的优点，在任何丢包率的情况下，都能在较短的时间内进行解码。在5%丢包率时，MSD算法相对OIDGE算法的解码时间减少了一半，在高丢包率时，两者基本相等。实际解码时间证明，编码符号经过选择器的时间可以忽略不计，不对解码造成影响。

4 结论

本文针对RaptorQ码解码复杂度高的问题，提出了一种模式选择解码算法，该方法综合考虑了信道的实际丢包情况与不同解码算法的效率，根据计算所得丢包率，选择对应的解码模式。实验结果表明，该算法适用于嵌入式系统中的各种丢包率的场景，在一定程度上提高了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]. 电子与信息学报, 2015, 37(6): 1310-1316.

李 越(1992— )，女，硕士生，主研信道编码；

张立军(1974— )，助理研究员，主研视频通信；

李明齐(1971— )，研究员，主研无线“三网融合”、4G/B4G关键技术、基于3GPP的软件无线电；

朱秋煜(1964— )，教授，主研图像处理、模式识别、计算机视觉、智慧城市、计算机应用。

责任编辑：薛 京

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]. 电视技术，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

中科院战略性先导专项子课题(XDA06010301)；国家基金委青年科学基金项目(61401440)；上海市国际科技合作基金项目(14510722300)

2016-04-27