基于新型随机度分布的压缩喷泉码

陈月云 刘 伟

(北京科技大学计算机与通信工程学院 北京 100083)

1 引言

喷泉码[1]是一类新颖的基于图的信道编码技术，无码率特性使其在发送编码之间无需等待反馈，因其性能优越被逐步推广到无线广播多播服务中[2]。

Luby等人于1998年首次提出喷泉码概念，并在2002年提出了第1种现实可行的喷泉码——LT码[3]。之后，文献[4]在LT码的基础上进行改进，使其译码时间有所提高，这种新型的喷泉码后又被命名为Raptor码。

在文献[3]中给出两种度分布，分别是理想孤子度分布和稳健孤子度分布。理想孤子度分布理论上使每一个编码符号在任何一次译码迭代中释放概率相同[3]，保证在译码迭代过程中总存在仅有一个输入符号在预处理集中，使每完成一次迭代都能译出一个输入符号。但在实际中，由于度分布映射的随机性使得极微小的波动误差都能造成预处理集消失并致使译码失败。稳健孤子度分布是在理想孤子度分布的基础上做了改进，由两部分组成，第1部分为上述的理想孤子度分布，另一部分加入了两个调节参数c和δ，在结合了理想孤子度分布的优点基础上，扩展了译码过程中的预处理集，使其消失概率充分小，提高译码成功概率，但同时由于编码覆盖的冗余度增加，造成译码效率降低。

文献[5]提出多目标进化算法，以译码开销和计算复杂度作为目标参数，采用不同度分布可获得不同指标的高译码性能。文献[6]提出喷泉码优先级的概念，将高优先级的重要数据采用度1或2进行编码，使重要数据能够被快速译码。文献[7]提出一种简单的度分布，称为二进制指数分布(Binary Exponential Distribution,BED)。但是该方法可能会过分增加度1的产生概率，降低了信源符号参与编码的概率，增加度1断层的出现概率[8]。

文献[8,9]在文献[7]的基础上对简单 BED 度分布加以改进，进一步优化了喷泉码的性能。文献[9]提出基于二项分布函数的度分布函数，增加原始符号参与编码的概率；文献[10]提出的转换度分布是将BED度分布与稳健孤子度分布相结合，有效提高成功译码概率。但以上两种改进度分布的编码性能没能在最大程度上逼近理想孤子度分布，在译码效率方面仍有可提升空间。在文献[2]中对于喷泉码译码给出两种通用译码算法，即高斯消元译码算法及置信传播(BP)译码算法。文献[10]给出一种最大似然(ML)译码算法。高斯译码及ML译码算法较BP算法能够提高效率但译码复杂度较高，且随着信源符号数增加而迅速增加，但是由于BP算法受度1断层的制约，一旦出现度1断层则译码中断[11]。

本文通过分析低的度值对编译码产生的影响，提出二进制指数随机度分布(BERDD)，具有理想孤子度分布及BED分布的性能折中，不仅降低译码过程中出现度1断层的概率而且译码复杂度低，译码开销小，迭代效率高。喷泉码的译码需要传输编码生成矩阵，且一列生成矩阵中元素个数等于信息包的符号个数，在发送过程中占用大量带宽，由此提出基于绝大多数生成矩阵的稀疏特性，采用码本方式对生成矩阵进行压缩的策略，有效压缩发送数据帧长，提高系统吞吐量。

2 系统模型

蜂窝小区内用户向基站发出多媒体业务请求，实现数据的实时传输，用户随机分布在小区内的不同位置，系统模型如图1所示。基站将请求相同多媒体数据的M个用户划分为一个多播组 G roup(U1,U2,…,UM)，基站采用喷泉码对所要发送数据包进行编码。基站以信息包为单位发送多媒体数据，当多播组中的所有用户都成功接收并完成一个信息包译码后，基站发送下一个信息包。由于多播组用户在实际地理位置上是随机分布的，因此每个用户与基站间的信道状况各不相同，所以信息的传输效率取决于多播组中信道条件最差的用户。

系统原理如图2所示。在信源端，将长为Kall个符号的信息分隔为n=Kall/K个信息包(即每个信息包大小为K个符号)。

图1 系统模型

喷泉码的编码算法：

(1)根据给定的度分布函数ρ(d)随机产生度d；

(2)在信息包中的K个符号中随机选取d个不同的输入符号；

(3)编码后的输出符号为(2)中d个不同输入符号的异或和。

为避免因衰落信道产生传输差错导致译码失败，在发送端采用循环冗余校验(Cyclic Redundancy Check,CRC)，在接收端删除产生差错数据帧。由于喷泉码的无码率特性，因此删除错误帧不会对译码造成影响。在码本压缩模块中，数据帧以码本方式经过压缩处理，即用不同位数的标志位表示生成矩阵中1的位置，以达到缩短发送帧长的目的。在接收端，多播组内用户不断接收编码信息直至完成一个信息包的译码，当基站收到该多播组所有用户译码成功的确认信息后对下一信息包进行编码并发送。

图2 系统原理框图

3 二进制指数随机度分布(BERDD)

度分布的设计影响喷泉码的译码开销与计算复杂度。由于在译码过程中译码器首先寻找度为1的编码符号，即编码符号只和唯一的信源符号相连，并将其还原为信源符号，则度为1的编码可以最直接且最快速地还原信源符号。此后通过异或相加，删除他们在生成图中相连的边[12]，降低未恢复编码的度值，从而使某些度为 2的编码的度值降为 1，通过迭代实现译码。但是，如果在译码过程中生成矩阵不能收敛到度1时，译码过程中断，称之为度1断层。因此，度值较低的编码符号特别是度为 1的编码符号个数多时，降低产生编码时输出符号间的关联性，则译码容易出现度1断层，需要接收更多的编码才能完成译码，导致译码开销增加。相反，若度值较低的编码符号特别是度为1的编码符号个数太少，译码所需模二加次数增加，导致译码复杂度增加，译码速度降低。

因此，度为1的编码个数应有合理取值，本文提出基于递缩等比数列的改进型随机度分布函数，叫做二进制指数随机度分布(Binary Exponential Random Degree Distribution,BERDD)，为

ρ(d)为二进制指数分布(BED)[13]。BED分布是基于无穷递缩等比数列，d=t(t=1,…,K- 2)的产生概率是d=t+ 1 产生概率的2倍。τ(d)为理想孤子度分布。在模型式(1)中，将BED分布与理想孤子度分布进行归一化。BERDD分布既能弥补BED分布度1产生概率过高的缺陷，又能最大程度上保留理想孤子度分布的优良特性且有效避免度1断层的出现。

图3给出度1对译码过程产生的影响。图中以4个输出符号及5个编码符号为例，根据稳健孤子度分布、BED及BERDD的度分布函数得到度1的产生概率分别为μ(1)=0 .1237[4],ρ(1)=0 .5,f(1)=0 .35，四舍五入分别取度1编码符号个数为1,3,2，如图3(a),3(b),3(c)所示。图3(a)中，完成译码需6步迭代，8次异或运算。图3(b)中，当译码进入状态2时，出现度1断层，导致译码中断。图3(c)所示译码过程，完成译码只需3步迭代，4次异或运算，相比度1编码符号个数为3的情况，译码迭代次数减少。由此可见，BERDD度分布能够在降低度1断层出现概率的同时，提高译码速度，降低译码复杂度。

图3 译码状态转移图

4 基于码本的压缩喷泉码设计

4.1 码本压缩编码原理

根据BERDD度分布函数可知，低度值的产生概率远高于高度值的产生概率，因此每进行一次编码生成矩阵大多数为K×1的稀疏矩阵列，其中K为信息包大小。采用码本方式进行压缩，即用M个二进制比特来表示矩阵中1所在的位置，称此M个二进制比特为标志位。当矩阵中1的个数L<

成功译码所需接收的编码个数N=(1 +ε)K，其中ε为译码开销，ε＜1。由于接收端需要编码产生的生成矩阵进行二部图重构以完成译码，因此，整个译码过程所需发送的符号总数为A=(1+K)N。采用码本压缩编码，当生成矩阵度值满足d＜D时，该生成矩阵可被压缩，且压缩后的符号数为M×d。有BERDD度分布函数f(d)可知N个编码符号中度为d的个数是N×f(d)， 则整个译码过程所需发送符号总数为

得到压缩率为

4.2 编码效率及占用带宽分析

定义E(K)为信源符号数为K时的编码效率，即信源符号数与发送符号数之比。则编码效率可表示为K/ (1 +K)N=1 /(1 +K)(1 +ε)。因此，编码效率与信息包大小K近似成反比，即信息包越大，编码效率越低。

应用码本压缩喷泉码传输，设发送端信源符号数为Kall个，标志位的个数为M，则生成矩阵维数最大为2M，即参与一次LT编码的信息包符号数最多为K=2M。发送所有信源符号所需的信息包个数为Kall/2M，则正确译出一个信息包所需的编码个数为N=K× (1 +ε)=2M× (1 +ε)。由式(4)得，正确译出一个信息包所需接收的比特数为

由式(6)可以看出随着M的增大，编码效率有所下降。

由于码本压缩的原理是用标志位比特来表示稀疏生成矩阵中1的位置，因此产生编码的度值越小其产生的生成矩阵的可压缩度就越高。以K=32为例，其标志位个数M=l og232=5 ，其可被压缩的度的最大值D=[2M/M]=[32/5]=6 ，则当d＞D时，发送一个编码所附带的生成矩阵列为 32 bit，当d=1时，压缩后的生成矩阵列仅为5 bit，其压缩率为15.6%。因此，度1产生的个数对压缩效果起着至关重要的作用。

对编码产生的生成矩阵采用码本压缩后，发送数据帧长缩短。设压缩前发送数据帧长为Lbit，压缩后发送数据帧长为Li(i=1,…,N)，且＜L，经喷泉码编码后码率RB不变。需要注意的是，由于每次编码产生的生成矩阵的稀疏度不同，因此压缩后大小不定。由式(8)得＜R(i=1,…,N)，即经B数据压缩后码元速率降低，则发送每帧所占用的信道带宽降低，其中为压缩后的码元速率。

综上所述，对发送数据帧进行码本压缩后，平均占用带宽降低，节省了带宽资源，提高了带宽利用率。

5 性能仿真及分析

在仿真中，采用 LT码作为喷泉码编码，完成编码后为每个分组加上校验和，不考虑校验和的漏检概率，则近似将分组交换的逻辑信道等效为删除信道，以BPSK作为调制方式，接收端采用置信传播译码算法。图4，图5是单一用户条件下对性能参数的仿真结果。图6，图7仿真多播环境下考察译码开销，为简化分析，取多播组用户数为 5，数据分组经瑞利衰落信道且信道条件相互独立。

表1给出不同度分布度值产生概率统计，仿真中原始数据包为100个符号，根据稳健孤子，BED和BERDD 3种度分布分别产生100×1000个编码，对不同度值进行统计，表1给出度值分别为1,2,3,4,5,10,50,100的产生概率。可以看出，BERDD分布度值的产生概率介于稳健孤子度分布与 BED分布之间，与前文分析一致，且随着度值的增大，其产生概率逐渐降低。另外，由表中数据知，对于3种度分布度值在 5以下的产生概率总和均接近或超过50%，说明编码产生的生成矩阵绝大多数为稀疏矩阵，这为码本压缩提供了有利依据。

图4 度分布覆盖情况

图5 译码复杂度

图6 不同度分布完成译码所需编码个数

图4，图5分别给出根据3种度分布函数产生编码是对输出符号的覆盖情况曲线及译码复杂度曲线。如图4所示，数据包大小K分别取30,50,80,100,120，计算在不同度分布函数下确保所有信息符号都参与编码的最少编码次数。BED度分布在编码时要覆盖到所有信息符号所需编码次数较多，因为其小度值的产生概率过大，尤其是度 1的产生概率，Robust度分布的覆盖性最好。由图5可以看出，随着信息包大小K值增加，成功译码所需模二加运算次数增加，且在相同条件下，BED度分布最优，BERDD度分布次优。因此，编码时度分布对输出符号覆盖性越好，则译码复杂度越高。虽然Robust度分布的覆盖性最好，但在译码过程中译码复杂度高，译码速度较慢。BERDD度分布取前两者的折中，在提高低度值产生概率的同时，兼顾对输出编码的覆盖。

表1 度值产生概率统计

图7 采用码本压缩传输前后平均占用带

图6为3种度分布函数译码开销性能曲线，通过统计成功译码所需编码符号个数来衡量度分布性能。由前文分析知，K值越大译码复杂度越高，此处设定K为150以内数值。由图6可知，在信息包大小一定情况下，采用BERDD分布函数完成译码所需编码个数小于Robust度分布和BED度分布，且随着信息包大小的增加，其性能优势体现得更为明显。

图7为在不同信息包大小条件下采用码本压缩喷泉码传输前后平均占用信道带宽仿真曲线。其中，喷泉码的度分布采用本文提出的BERDD度分布，且由前文分析可知，在码本压缩过程中当标志位分布取3,4,5,6,7 bit时，信息包大小为8,16,32,64,128 bit的压缩率最高。因此，在仿真中取信息包大小分布为8,16,32,64,128 bit。由图6可以看出，采用码本压缩喷泉码传输后，在一定信息包大小条件下平均占用信道带宽降低，节省了带宽资源。若喷泉码编码后码速率不变，随信息包大小的增加，采用码本压缩喷泉码传输，其带宽利用率性能优势更为明显。

6 结论

本文通过分析度分布对喷泉码编译码的影响，提出了 BERDD分布，将理想孤子度分布和 BED分布进行归一化，折中两者度值产生概率。仿真表明，对于符号数为100的信息包，采用BERDD度分布编码度1的产生概率较稳健孤子度分布提高了23%，且译码复杂度较稳健孤子度分布大大降低。在多播传输环境下译码开销低于稳健孤子度分布及BED分布，随着信息包符号数的增多，其译码开销性能优势体现更为明显。采用码本压缩喷泉码传输方式，对编码产生的生成稀疏矩阵压缩，用标志位信息表示稀疏矩阵中1的位置，缩短发送数据帧长，节省了带宽资源，提高了带宽利用率，具有一定的实用价值。

[1]MacKay D.Fountain codes[J].IEEProceedings Communications,2005,150(6): 1062-1068.

[2]3GPP TS 26.346 V6.12.0.Multimedia Broadcast/Multicast Service (MBMS)[S].2008.

[3]Luby M.LT codes[C].Proceedings of the 43rd Annual IEEE Symposium on the Foundations of Computer Science,USA,Nov.19,2002,43,271-280.

[4]Shokrollahi A,et al..Raptor codes[J].IEEE Transactions on Information Theory,2007,58(4): 2551-2567.

[5]Chen Chi-ming and Chen Ying-ping.Optimizing degree distributions in LT codes by using the multiobjective evolutionary algorithm based on decomposition[C].Proceedings of Evolutionary Computation (CEC),Barcelona,Spain,July 18-23,2010: 1-8.

[6]Woo S and Cheng M.Prioritized LT codes[C].Proceedings of Information Sciences and Systems,Princeton,USA,Mar.19-21,2008: 568-573.

[7]Al Agha K and Kadi N.Fountain codes with XOR of encoded packets for broadcasting and source independent backbone in multi-hop networks using network coding[C].Proceedings of Vehicular Technology Conference,Barcelona,Spain,Apr.26-29,2009: 1-5.

[8]Zaman M S and RamaMurthy G.A new degree distribution for LT codes for broadcasting in Ad hoc network using network coding[C].First UK-India International Workshop on Cognitive Wireless Systems (UKIWCWS),Delhi,India,Dec.10-12,2009: 1-5.

[9]Kadi N and Al Agha K.New degree distribution to improve LT-code in network coding for broadcasting in Ad hoc wireless networks[C].Proceedings of IEEE International Symposium on Personal,Indoor and Mobile Radio Communications (PIMRC),Istanbul,Turkey,Sept.26-30,2010: 1820-1825.

[10]Schotsch B and Schepker H.The performance of short random linear fountain codes under maximum likelihood decoding[C].Proceedings of IEEE International Conference on Computer Communications(ICC),Kyoto,Japan,June 5-9,2011: 1-5.

[11]Huang Wei-zheng and Li Huan-lin.Fountain codes with message passing and maximum likelihood decoding over erasure channels[C].Proceedings of Wireless Telecommunications Symposium (WTS),New York,USA,Apr.13-15,2011: 1-5.

[12]Lin Guang-rong.Finite length analysis of fountain codes based on stopping set[J].Journal of Electronics＆Information Technology,2008,30(11): 2634-2637.