单次反馈的Raptor 码的内码度分布设计

雷维嘉，张伟，谢显中

(重庆邮电大学移动通信技术重庆市重点实验室，重庆 400065)

0 引言

Luby在1998年提出了数字喷泉码的概念［1］。喷泉码是一种码率不固定的信道编码，在发送端由k个源数据包可以生成任意数量的编码包，接收端只要收到任意k(1+ε)个编码包后能以很大的概率成功译出全部源数据包，其中ε是译码开销。Luby在2002年给出第一类实用的喷泉码—LT码［2］。之后，Shokrollahi提出了另外一类性能更佳的喷泉码，即Raptor码［3］。目前，Raptor码已经被3GPP中多媒体广播和多播业务(multimedia broadcastmulticast service，MBMS)标准［4］以及掌上数字视频广播(digital video broadcastinghandheld ，DVB－H)标准［5］所采用。

当系统存在反馈时，除用反馈控制信息传输外，还可利用反馈来调整喷泉码的编码过程，提高编译码性能。文献［6］提出在应用喷泉码的中继传输中，目的端向中继反馈具体译出哪些源包，接着中继调整编码对象，来减少译码开销。类似地，文献［7］所提方案不仅调整编码对象，同时，根据反馈信息改进度分布，可进一步减少译码开销，提高译码效率。文献［8］针对短码给出一种基于反馈的Raptor码编码方案，通过反馈具体译出哪些源包来改变度分布，减少译码开销。文献［9］给出一种混合喷泉编码，通过反馈具体哪些源包未译出，发送端再直接发送相应的源包，加速了译码进程等。除此之外，还可以从调整度分布和反馈时间的选择方面进行综合研究，提高译码效率。

本文给出一种单次反馈的Raptor码的内码度分布方案:接收端在最佳反馈时间点反馈译出中间包的比例系数α，发送端根据α来调整度分布，可减小冗余包的传输。通过理论分析和仿真得到最佳的反馈时间点，并通过仿真表明，采用该度分布方案，不仅编译码复杂度较小且是线性的，而且，可明显减小译码开销。

1 Raptor码

Raptor码是在LT码的基础上发展而来，LT码译码过程中，恢复全部源数据包至少需要k log k次异或运算，不具有线性的译码复杂度，其中，k表示源数据包的个数。Raptor码通过预编码和弱化的LT编码，使译码的运算量降低为k log(1/ε)，实现了线性的译码复杂度。

1.1 Raptor码的编码

Raptor码的编码包括预编码和LT编码2个部分。其中，预编码作为外码;LT编码作为内码。预编码:编码器对k个源数据包使用传统纠删编码(比如Tornado码［10］、LDPC 码［11］或者重复累积码)产生 K个中间数据包，其中，K=k/R，R为预编码的码率。LT编码:将K个中间包作为LT码的输入包进行编码，得到Raptor码的编码包。整个编码如图1所示。

图1 Raptor码的编码Fig.1 Encoding of Raptor codes

1.2 Raptor码的译码

Raptor码的译码包括2个阶段，第1阶段为LT码的译码，由编码包译出K(R+σ)个中间数据包，其中，σ≥ 0;第2阶段为纠删码译码，由译出的中间数据包恢复k个源数据包。LT码的译码可采用高斯消元法或者置信传播(belief propagation，BP)算法［2］，前者译码开销小，但译码速度慢且复杂度相对高;后者虽然译码开销大点，但译码速度快且复杂度较低。实际应用中多采用BP算法，本文针对采用BP译码时的译码复杂度和译码开销等进行分析。

1.3 内码度分布

度分布的设计对喷泉码的性能至关重要，它的好坏直接决定了编译码性能。一方面，度为1和其他低度的编码包的数量决定了译码能否开始并持续进行，但这些编码包覆盖的原始信息较少，为了成功译码需要接收更多的编码包;另一方面，度较大的编码包能覆盖更多的原始信息，减小译码开销，但容易出现译码中断，同时编译码复杂度也高。

Raptor码的内码度分布为弱化的LT码度分布，为了实现线性的译码复杂度，其度分布中最大度不再是K，而是一个较小的值。下面介绍3种常用的内码度分布。度分布的表达式常用函数表达式和多项式2种方式来描述，前者是度分布的概率分布律，而后者用多项式中的幂次表示度的值，系数为取相应值的概率。

1 )平均度为3的度分布 ωK(d)。度分布ωK(d)［12］是由鲁棒孤子分布 μ(d)改进得到，μ(d)是基于理想孤子分布ρ(d)和正数函数τ(d)而来，其中，ρ(d)的表达式为

表1给出了k=1 000，R=0.95时，分别采用上述3种度分布编码时的译码开销。不难看出，随着平均度的增大，译码开销逐渐减小，但平均度的增大意味着需要进行更多的编译码异或操作。因此，为了减小译码开销而显著增大平均度的设计思想并不可取。

表1 k=1 000，采用3种度分布编码时的平均度和译码开销Tab.1 Average degree and overhead of three degree distributions with k=1 000

本文重点研究当系统存在单次反馈时，如何利用反馈来提高Raptor码的译码性能，而度分布对喷泉码的性能至关重要，于是在度分布ωK(d)的基础上，本文提出一种单次反馈的内码度分布，不仅可实现线性且较小的译码复杂度，而且使译码开销明显降低。

2 单次反馈的内码度分布

当系统存在反馈时，除用反馈控制信息传输外，如何有效利用反馈来减小译码开销，可以从3个方面重点考虑:反馈内容、反馈时间和发送端如何调整。反馈内容方面，主要有反馈成功译出中间包个数(或者一个比例系数)和反馈具体哪些中间包已译出(或者没有译出的中间包)等2种;反馈时间方面，研究最佳的反馈时间点使译码开销最小;发送端调整方面，调整度分布或者编码对象等。

2.1 反馈内容

当反馈具体哪些中间包已译出时，需要一个K比特的向量表示，即 g=(g1，…，gi，…，gK)T，其中，gi=0表示第i个中间包未译出，gi=1表示第i个中间包已译出。对于短码来说，K值较小反馈量不大，文献［8］研究了短码采用这种反馈方式，并取得了较好的效果。当K的数量级为103或者104以上的中长码，反馈量非常大将导致占用过多的信道资源，也会降低整体的效率。因此，中长码一般采用反馈成功译出中间包个数的方式。

当接收端译出n个中间包后，如果接收的编码包仅覆盖译出的中间包，则该编码包成为冗余包。例如，中间包 x和 y已译出，编码包 m=x⊕ y，“⊕”表示异或运算，由于m中没有包含对译码有

由(7)式不难得出，当n趋近于K时，p趋近1，说明接收端译出的中间包越多，则接收的冗余编码包也越多。

2.2 调整度分布

这里定义，反馈时间点α为接收端译出中间包的个数n占源包个数k的比例。为了最大程度地消除冗余编码包，期望的编码对象是K－αk个未译出的中间包，只需调整编码对象，于是度分布应为ωK－αk(d)，d=1，2，…，D。但反馈内容是一个数 α，发送端无法只对K－αk个未译出的中间包进行编码，编码对象仍是K个中间包。

设反馈之后发送端编码采用的度分布为ψK(d)，那么ψK(d)应满足(8)式，其中，R是预编码的码率。

当R与α一定时，d是一个常数，说明采用用的信息，该包为冗余包，接收端会将其丢弃。一个度为d的编码包是冗余包的概率为ψK(d)编码具有线性的译码复杂度。

2.3 最佳的反馈时间点

在单次反馈的情况下(假设反馈信号能被正确接收)，找出使译码开销最小的最佳反馈时间点α非常重要。下面从译码进程中编码包被释放概率的角度分析，这里参照Luby给出的几个定理［2］，然后推出Raptor码每次译码迭代后恢复中间包个数的表达式。

定义1 编码包被释放是指在译码进程中，一个中间包译码迭代后使某个编码包的度变为1，该编码包恢复其相关联的中间包后，度变为0被释放。

定理1 当还有L个中间包未译码迭代时，一个度为d的编码包被释放的概率q(d，L)为

由于每个编码包被释放时能恢复一个中间包，那么每次译码迭代后恢复中间包个数的期望值是K×r(L)，这里假定有K个编码包。目前，理论进一步推导译码效率的变化比较困难，我们仿真了不同k值采用ωK(d)编码时的K×r(L)与译码进程(KL)的函数曲线，其中L表示未译码迭代的中间包个数，它们表现非常相似，这里仅以 k=1 000，R=0.95为例，仿真曲线如图2所示。

从图2可看出，当K－L＞600后，曲线开始下滑，说明恢复中间包的速率开始变慢;在K－L＞800后，K×r(L)＜1，表明每次译码迭代后恢复中间包的个数不足1个，译码效率明显降低。因此，可以考虑当译出大约0.8×k个中间包时反馈具体α的值，发送端接收反馈信息来调整编码度分布，减小冗余包的传输，从而提高译码效率。

最后，我们给出单次反馈的内码度分布θα(d)方案:发送端先采用ωK(d)编码，当接收端译出大约α×k个中间包后反馈α，发送端接收α后采用ψK(d)编码，直到接收端成功译码为止。θα(d)的表达式为

3 仿真结果

图3仿真了不同的源数据包个数k时，采用内码度分布θα(d)编码，选择不同反馈时间点α时的译码开销ε。α的变化步长为0.1，每个ε值是通过100次蒙特卡洛仿真取平均值得来。可看出，对于不同k值，反馈时间点α取0.8时，译码开销均最小，验证了0.8是最佳反馈时间点的理论结果。，小于f2(x)的平均度5.87，说明采用θα(d)编码，译码复杂度较小，达到了预期目标。为了进一步验证θα(d)的性能，这里增加文献［6］提出的方案γ(d)，即反馈译出具体哪些中间包进而发送端调整编码对象。表2给出了5种度分布的平均度比较。

图3 采用θα(d)编码，选择不同反馈时间点α时的译码开销Fig.3 Overhead of different feedback time points for θα(d)

表2 5种度分布的平均度Tab.2 Average degree of five degree distributions

图4仿真了k=1 000，2 000和5 000时，分别采用5种度分布编码时的译码开销ε。从图4中可看出，对于相同的源包个数k，采用θα(d)和γ(d)编码时的译码开销大体相同且均最小，同样达到了预期的要求。另外，与度分布γ(d)相比，虽然θα(d)的平均度为4.8，大于前者，但采用γ(d)方案所需的反馈量为K比特，其值非常大导致占用过多的信道资源，降低了整体效率。因此，综合来讲，采用θα(d)方案反馈量非常小，译码复杂度较低，同时译码开销明显减小，表现出更佳的性能。

图4 分别采用5种度分布编码时的译码开销εFig.4 Overhead of five degree distributions

4 总结

本文研究了当系统存在单次反馈时，反馈时间的选择，以及Raptor码的内码度分布的调整方案，目的是为了减少冗余编码包，进而减小译码开销，同时保持较小的译码复杂度。通过理论分析和仿真给出了最佳的反馈时间点α的值，以及度分布的调整方案。仿真结果表明，采用反馈和度分布调整编码，明显减小了译码开销，同时译码复杂度是线性的，达到了预期的设计要求。

［1］BYERS J，LUBY M，MITZENMACHER M，et al.A digital fountain approach distribution of bulk data［J］.ACM SIGCOMM Computer Communication Review，1998，28(4):56－67.

［2］LUBY M.LT codes［C］//Proceedings of 43rd Annual IEEE Symposium on Foundations of Computer Science.USA:IEEE Press，2002:271－280.

［3］SHOKROLLAHI A.Raptor codes［J］.IEEE Transactions on Information Theory，2006，52(6):2551－2567.

［4］3GPP.3GPPTS 26.346 V6.3.0，Technical specification

［5］ETSI.TS 102 472 V1.2.1，DVB BlueBook A101 digital video broadcasting(DVB);IP datacast over DVB－H:content delivery protocols［S］. ［s.l.］:ETSI，2006.

［6］JAMES A，MADHUKUMAR A S，ADACHI F.Adaptive rateless coding with feedback for cooperative relay networks［C］//Wireless Communications and Networking Conference.Shanghai:Conference Publications，2012:587－591.

［7］FAZELIM，JAMSHIDIA.The performance evaluation of fountain codes with feedback in cooperative systems［C］//IEEE Iranian Conference on Electrical Engineering.Mashhad:Conference Publications，2013，21:1－5.

［8］SORENSEN JH，KOIKE－AKINO T，ORLIK P.Rateless feedback codes［C］//IEEE International Symposium on Information Theory Proceedings.Cambrige，MA:IEEE press，2012:1767－1771.

［9］YUE G，UPPALM，WANG X.Doped LTDecodingwith Application to Wireless Broadcast Service［C］//IEEE International Conference on Communications.［s.l.］:Conference Publications，2011:1－5.

［10］LUBY M G，MITZENMACHER M，SHOKROLLAHIM A，et al.Efficienterasure correcting codes［J］.IEEE Transactions on Information Theory，2001，47(2):569－584.

［11］AZIZ T，SALEEM N，LQBALM，etal.Performance evaluation ofmulticast relay network using LDPC and convolutional channel codes along－with XOR network coding［J］.The Journal of China Universities of Posts and Telecommunications，2012，19(4):122－128.

［12］MACKAY D JC.Fountain codes［J］.IEE Communications Proceedings，2005，152(6):1062－1068.

雷维嘉(1969－)，男，云南元谋人，博士，教授，主要研究方向为无线通信技术。E－mail:leiwj@cqupt.edu.cn。

张 伟(1988－)，男，山西临汾人，硕士研究生，主要研究方向为协作通信。E－mail:zhangwcqupt@sina.com。

谢显中(1966－)，男，四川通江人，博士，教授，主要研究方向为移动通信技术。E－mail:xiexzh@cqupt.edu.cn。

(编辑:魏琴芳)