牛芳琳，李宝明，陈付亮，王洪玉，祝开艳

(1．辽宁工业大学电子与信息学院，辽宁锦州121001; 2．大连理工大学信息与通信工程学院，辽宁大连116024; 3．航天恒星科技有限公司，北京100086; 4．大连海洋大学信息工程学院，辽宁大连116023)



一种改进的基于部分信息喷泉码度分布设计

牛芳琳1，2，李宝明3，陈付亮3，王洪玉2，祝开艳4

(1．辽宁工业大学电子与信息学院，辽宁锦州121001; 2．大连理工大学信息与通信工程学院，辽宁大连116024; 3．航天恒星科技有限公司，北京100086; 4．大连海洋大学信息工程学院，辽宁大连116023)

摘要:与传统的喷泉码相比，基于反馈信息的喷泉码可以有效降低译码开销，其编码所采用度分布则是喷泉码设计的关键，本文提出一种适用于反馈喷泉码的基于部分信息度分布构造方法．该方法首先提出具有较小译码开销的最佳单项式度分布函数，并将其与传统的SRSD度分布相结合，然后通过参数调整可以获得修正后的ISRSD度分布函数．仿真结果表明在已知部分信息的喷泉码中，与传统的SRSD度分布函数相比，采用ISRSD度分布函数进行编码使其性能得到明显的提高．

关键词:喷泉码; LT码; BP译码; SRSD

1　引言

喷泉码［1］最早由Michael Luby等人在1998年首先提出来，直到2002年，文献［2］中提出了鲁棒孤立子度分布(Robust Soliton Distribution，RSD)函数，使喷泉码的实现成为现实．与传统的固定矩阵编码方法不同，喷泉码编码方法是指信源按照一定的概率规则随机选择信源符号进行异或求和得到编码符号，其编码所采用的概率规则被称为度分布函数．度分布函数的设计在很大程度上决定了喷泉码的性能的好坏，一个好的喷泉码可以使译码开销趋于与1.为了降低译码开销，近年来，很多学者均致力于对喷泉码度分布的研究，如文献［3］中提出通过对度分布的修正增加低度校验节点，使得规则变量节点度LT(Luby Transform，LT)码解码瀑布区域(雪崩区域)提前，降低了成功解码所需的译码开销．文献［4］对二进制度分布进行调整，然后将其与RSD进行有机结合，并进一步优化得到适用于短码长的修正二进制-鲁棒孤子度分布．但是现有的喷泉码与理想喷泉码相比，译码开销依旧较大．由信息论理论可知，有效利用接收端的反馈信息可以降低源信息的不确定度，一些学者提出基于反馈信息的喷泉码，即在喷泉码中合理有效利用少量反馈信息降低译码开销．如文献［5］中提出基于反馈的RT(Real time)纠错方法，文中指出利用反馈信息的喷泉码可以有效降低喷泉码的译码开销．文献［6］提出基于反馈的DALT (Doped Accumulate LT，DALT)传输协议，指出这种基于反馈传输的喷泉码性能接近于Raptor码［7］．文献［8］中，通过反馈信息对RSD度分布函数进行修正得到基于部分信息的转移RSD(Shifted RSD，SRSD)度分布函数．文献［9］提出了多次反馈喷泉码，接收端依据编码符号度平均概率的变化给信源发送反馈信息，用以修正SRSD度分布函数进行LT编码，而文献［10～15］则提出对ripple等的变化进一步改进，调整反馈信息来修正度分布函数，减少反馈喷泉码译码开销．针对反馈的喷泉码，设计合适的度分布函数可以有效的降低译码开销．本文对传统的基于部分信息的SRSD度分布函数进行改进，首先提出具有较小译码开销的最佳单项式度分布，将其作为修正项对传统的SRSD进行修正，并进行优化得到了基于部分信息喷泉码的修正转移鲁棒孤立子度分布(Improved SRSD，ISRSD)函数．采用这种度分布函数进行基于部分信息的喷泉码编码，与传统的SRSD度分布相比，可以有效的降低译码开销．

2　基于部分信息的度分布函数

2.1RSD度分布函数

度分布函数是设计喷泉码的关键，一个好的度分布函数可以有效减少喷泉码的译码开销．M．Luby在文献［2］首先提出理想孤子分布ISD度分布

由于随机过程产生的实际行为在期望值上下波动，采用ISD度分布的喷泉码在译码过程中可能会导致可译集符号消失，从而使译码开销变大．M．Luby在研究了ISD度的特性后，对式进一步修改，加入τ(d )用以增强ρ(1 )、ρ(s/k )等概率，τ(d )的数学表达式为

将理想分布ρ(d )与τ(d )进行合并得到归一化RSD度分布

2.2基于部分信息的SRSD度分布函数

文献［8］提出基于部分信息的喷泉码概念，当接收端已知n个信源符号，信源利用已知符号个数n对RSD度分布进行修正，以降低信源编码符号的不确定度，可以减少喷泉码的译码开销．经过n修正的RSD度分布函数称为SRSD度分布函数，依据这一度分布函数进行LT编码则称为SLT码．其中SRSD数学表达式为

其中，1≤j≤k; k表示信源需要发送的信源符号个数; n表示接收端接已知的信源符号的个数;μRSD(k－n)表示度1≤d≤k－n的RSD度分布; round(·)表示四舍五入取整．

根据喷泉码编码方法可知，j的取值范围必须满足1≤j≤k，由式可知，当k－n＜d≤k，则j＞k，超出编码长度范围．式(4)中1≤d≤k－n时，存在∑jμRSD(k－n)(d) ＜1，则r(j)不服从概率分布．本文提出对式进行归一化处理，得到

3　修正的转移度分布函数

3.1单项式度分布函数

传统的喷泉码编码度分布函数可以用多项式表示，即

其中: k表示信源符号数量; ad表示度为d的概率，并且满足

针对基于部分信息的喷泉码，接收端已经存在部分度为1的信源符号，在其度分布设计时候，即使不考虑度1的概率，接收端也可以采用BP方法成功译码，因此，本文提出一种单项式度分布函数

其中: d表示编码的度; n表示接收端已经恢复信源符号个数;由∑dad= 1可知，ad=1.

式(7)即为基于部分信息的单项式度分布函数．

BP译码方法中指出，只有与编码符号相邻未知符号个数等于1才能恢复1个未知符号．采用单项式度作为度分布函数，受到n的限制，度为d的编码符号与相邻未知符号个数大于1的情况，导致不能译码，因此需要对d的取值范围进行讨论．

以图1为例，接收端已知部分信源原始符号，采用喷泉码编码符号对未知符号进行恢复，设k = 6，n = 4，接收到编码符号度d分别为5、3和6.图中黑色圆点表示已知信源符号，白色圆点表示未知信源原始符号，方框表示接收到度为d的编码符号．

图1(a)中，d =5的编码符号与4个已知信源符号相邻，与1个未知信源符号相邻，由BP译码可以解出S4;图1(b)中d =3，度小于n +1，可以从已知n个符号中可以选取到d－1个已知符号，解出1个未知符号;图1(c)中，d =6大于n +1，编码符号无论采用什么组合方法，不存在与1个未知符号相邻的情况．

由分析可知，当d－1＞n时，度为d的编码符号无法进行BP译码，因此我们可以得出满足单项式xd作为度分布函数取值范围

3.2最佳修正项

在2.2.1节中提出了基于部分信息的单项式度分布函数，由式可知，当d不同的时候，度分布函数则不同，恢复未知符号(k－n )所需要的译码符号个数m也不同．下面我们通过实验观察选取不同的d对译码符号个数m的影响．

设信源需要发送符号个数k = 500，n分别选取495 和450．采用Matlab进行仿真，运行次数1000，d与译码符号个数m的关系曲线如图2所示．

采用式(7)作为基于n个信源符号的度分布函数进行喷泉码编码，由图2(a)和图2(b)中的实验结果可以知，当d不同时候，译码符号个数m也不同，并且均为下凹曲线，存在一个d使译码符号m达到最小．图2(a)为n =495时d与m的关系曲线．由k =500可知，当n =495时候，未知信源符号的个数等于5.而当d等于185时m为最少值，即m =7.7，采用式(7)作为编码度分布函数的时候，仅需要接收到7.7个编码符号即可恢复所有信源符号;图2(b)中n =450，当d =32，仅需要接收到76.9个编码符号即可恢复未知的50个信源符号．

3.3修正转移度分布函数

3.3.1修正转移度分布函数表达式

由2.2节可知，在n时候，选取最佳修正项d'度，可以使采用式(9)作为度分布函数进行喷泉码编码译码符号个数m达到最小，d = d'时候BP算法译码能力较强．为了进一步降低译码符号个数，本文提出一种新的基于部分信息的修正转移RSD(Improved Shifted RSD，ISRSD)度分布函数，将式(9)作为修正项引入SRSD度分布函数中，并对其做归一化处理得到

通过大量的实验结果可以观察到，采用单项式作为度分布函数，每1个n都存在1个d值，使译码符号m个数达到最小数值．本文将此时对应的d称为最佳指数d'，由式(7)得到的单项式度分布函数称为最佳修正度分布函数，其数学表达式为

α表示γ(j )在式(10)中占有的比例，(1－α )表示最佳修正项Ω(d' )在式(10)所占的比例．α的变化将会导致μISRSD(j )度分布函数随之发生变化，采用其进行喷泉码编码，译码符号m也会发生变化．

3.3.2最佳指数与最佳调整系数

式(10)度分布函数与最佳调整系数α与最佳指数d'两个参数有关，由于d'与α的大小均有n和k有关，本文提出通过建立实验模型通过查找的方法得到n/k不同条件下d'与α的数值．

设信源需要发送符号个数为k，编码长度k分别取100、400、500，n/k取值范围0．1到1，步长0．1.其中，参数c =0．01，δ=0．5.实验采用Matlab进行仿真测试，仿真次数1000次．

(1)查找最佳修正项指数

采用式(10)作为信源度分布函数进行喷泉码编码，其中a =1.d的取值从1到n +1，步长为1，当译码符号个数最少时候，所对应的d即为本文提出的最佳指数d';

(2)查找最佳调整系数

将已知的最佳指数d'带入进行编码，a选取值范围为0～1，步长0．01，在n/k为固定比值的时候，调整a，使译码符号个数达到最少，此时所对应的a为最佳调整系数．

通过实验查找出的最佳修正指数d'和最佳调整系数a，如表1所示．

将表1中a和d'带入式(10)，即可以得到不同k和n条件下的基于部分信息的ISRSD度分布函数．

在BP译码过程中，需要合理控制编码符号的释放速度，一方面需要防止编码符号释放过慢使译码结束;另一方面，防止编码符号释放过快重复覆盖已经被恢复的符号而增加冗余．RSD度分布函数在设计过程中考虑到每步迭代恰好释放一个编码符号，使迭代译码速度保持平衡．基于部分信息的SRSD度分布通过对RSD度分布的转移取整，致使这种平衡在一定程度上被破坏，导致恢复未知信源符号的译码开销增加．引入的最佳修正项通过调整系数a对SRSD编码符号的译码速度进行调整，在一定程度上减少译码符号数量．观察表1，大多数a取值为0.8左右．但是当n为某些数值的时候，得到a = 1，将其代入式则有μISRSD(j) =μSRSD(j)，即加入的修正项xd'没有发挥增强译码作用．

表1　n/k不同时候，最佳修正项xd'与最佳调整α

3.3.3不同的度分布直方图比较

设信源编码长度k = 100，接收端已知信源符号个数n =70，由表1可知最佳修正项的指数d' = 10、最佳系数a =0.75，分别带入式(9)和式(10)可以得到最佳修正度分布xd'与ISRSD度分布函数．比较RSD、SRSD、最佳修正项xd'和ISRSD度分布直方图，如图3所示．

图3(a)可知，RSD度分布中低度概率较高，如d等于1、2、3等．除了d = 1和d = k/s的概率以外，随着d的增加，RSD度分布的概率逐渐降低，尤其是d大于20，概率几乎接近于0.图3(b)为SRSD度分布直方图，由对RSD的度进行转移，使部分d对应的概率等于0，如原来较大概率的度为1和2的概率也等于0，由于采用其进行编码，BP译码过程中，接收端已经存在足够数量度为1的信源原始符号，可以恢复度3的编码符号，因此不在需要接收度1、2编码符号进行译码，因此可以减少了编码符号的数量;图3(c)为单项式度分布最佳d'的概率为1;图3(d)为本文提出的ISRSD度分布函数直方图，从图中可以观察到，度d'占用较大的概率．将式(10)与式(5)进行数学期望比较，显然ISRSD度的数学期望增加，增加编码符号覆盖信源符号的概率，在一定程度上减少译码符号的数量．

4　实验

为了更好的衡量基于部分信息喷泉码恢复未知符号译码能力，本文中提出反馈译码开销εf的概念，即恢复未知信源符号的译码开销．

εf:译码符号个数m与未知符号(k－n )个数之比值．其数学表达式为

由式(11)和喷泉码的性质可知，反馈译码开销εf≥1，εf越小表明恢复信源所需要的编码符号个数m越少，喷泉码性能越好，理想的反馈译码开销εf→1.

关于喷泉码译码开销与度分布函数的计算比较复杂，文献［16］中给出了k→∞的计算方法;当k为有限值时候，文献［17，18］给出了k为有限长度的译码开销的计算方法．然而，目前还没有基于部分信息的喷泉码译码开销计算方法，本文通过实验来比较ISRSD度分布与文献［8］中的SRSD分布的εf，实验仿真结果如图4所示．

由图4(a)、图4(b)和图4(c)中的实验结果可知，当k分别为100、400和500的时候，ISRSD度得到的反馈译码开销εf明显优于传统的SRSD，同时εf与k的大小有关，随着k的增加，εf下降．

ISRSD优于SRSD的主要原因为，当n为不同数值的时候，都存在一个最佳单项式度分布函数式(10)可以使反馈译码开销达到一个较低的数值，采用其对SRSD进行优化，得到基于部分信息的ISRSD度分布函数式．采用查找的方法调整a，使εf达到最小得到最佳调整系数a，因此可以得到采用ISRSD度分布编码的反馈译码开销εf小于SRSD．如果最佳单项式度分布函数不能使SRSD的反馈译码开销降低，则a = 1，即μISRSD(d) =μSRSD(j)，即ISRSD的反馈译码开销εf与SRSD相同．因此可以得出由本文提出的ISRSD度分布得到的反馈开销εf始终小于等于SRSD，使基于部分信息的喷泉码性能得到提升．

5　结论

由于采用最佳修正项xd'作为基于部分信息n的喷泉码编码可以提高BP译码性能，本文中将xd'引入SRSD的分布函数中，并选取合适的调整系数a得到ISRSD度分布函数．结合实验结果分析可知，对于在相同条件下的基于部分信息的喷泉码，采用改进的ISRSD度分布函数与SRSD度分布函数进相比，可以有效的降低译码开销，提高反馈喷泉码在无线传输的网络性能．

参考文献

［1］Byers J W，Luby M，Mitzenmacher M，et al．A digital fountain approach to reliable distribution of bulk data［J］．ACM SIGCOMM Computer Communication Review，1998，28 (4) : 56－67.

［2］Michael L．Lt codes［A］．Proceedings of 43rd Annual IEEE Symposium on Foundations of Computer Science［C］．USA: IEEE，2002.271－282.

［3］孙文珠，王洪玉，祝开艳，王洁，唐震洲．一种规则变量节点度LT Codes编码方案［J］．电子学报，2014，42(10) : 1918－1924.Sun Wen-zhu，Wang Hong-yu，Zhu Kai-yan，Wang Jie，Tang Zhen-zhou．A novel encoding scheme for regular variable-node degree LT codes［J］．Acta Electronica Sinica，2014，42(10) : 1918－1924.(in Chinese)

［4］雷维嘉，张梦，谢显中．基于度分布合并和可译集优化的LT码度分布设计方案［J］．电子学报，2015，43(4) : 800 －805.Lei Wei-jia，Zhang Meng，Xie Xian-zhong．A design scheme for LT codes degree distribution by combining degree distributions and optimizing ripple size［J］．Acta Electronica Sinica，2015，43(4) : 800-805.(in Chinese)

［5］Amos B，Shlomi D，Noam S．RT oblivious erasure correcting［J］．IEEE/ACM Transactions on Networking，2007，15 (6) : 1321－1332.

［6］Yuan X，Ping L．Doped accumulate LT codes［A］．Proceedings of IEEE International Symposium on Information Theory［C］．France: IEEE，2007.2001－2005.

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

［8］Agarwal S，Hagedorn A，Trachtenberg A．Adaptive rateless coding under partial information［A］．Proceedings of Information Theory and Applications Workshop［C］．San Diego: IEEE，2008.5－11.

［9］Hagedorn A，Agarwal S，Starobinski D，et al．Rateless coding with feedback［A］．Proceedings of INFOCOM［C］．Rio de Janeiro: IEEE，2009.1791－1799.

［10］Sorensen J H，Popovski P，Ostergaard J．Design and analysis of LT codes with decreasing ripple size［J］．IEEE Transactions on Communications，2012，60 (11) : 3191 －3197.

［11］Sorensen J H，Popovski P，Ostergaard J．Feedback in LT codes for prioritized and non-prioritized data［A］．Proceedings of Vehicular Technology Conference (VTC Fall)［C］．Quebec City: IEEE，2012.1－5.

［12］Dai J，Zesong F，Chenglin S，et al．LT Codes with Limited Feedback［A］．Proceedings of IEEE International Conference on Computer and Information Technology (CIT) ［C］．Xi’an: IEEE，2014.669－673.

［13］Talari A，Rahnavard N．LT-AF codes: LT codes with alternating feedback［A］．Proceedings of IEEE International Symposium on Information Theory Proceedings (ISIT) ［C］．Istanbul: IEEE，2013.2646－2650.

［14］Talari A，Rahnavard N．Robust LT codes with alternating feedback［J］．Computer Communications，2014，49: 60 －68.

［15］Zhang L，Liao J，Wang J，et al．Design of improved Luby transform codes with decreasing ripple size and feedback ［J］．IET Communications，2014，8(8) : 1409－1416.

［16］Sejdinovic D，Piechocki R J，Doufexi A．AND-OR tree analysis of distributed LT codes［A］．Proceedings of Networking and Information Theory［C］．Volos Greece: IEEE，2009.261－256.

［17］Karp R，Luby M，Shokrollahi A．Finite length analysis of LT codes［A］．Proceedings．International Symposium on Information Theory［C］．USA: IEEE，2004.37－37.

［18］Maatouk G，Shokrollahi A．Analysis of the second moment of the LT decoder［J］．IEEE Transactions on Information Theory，2012，58(5) : 2558－2569.

牛芳琳女，1971年出生于辽宁锦州．2015年在大连理工大学获得博士学位，现在辽宁工业大学工作．目前主要从事信息论、信道编码、喷泉码、无线通信技术等方面的工作研究．

E-mail: niufanglin@ sina．com

王洪玉(通信作者)男，1968年9月出生于吉林长春．教授、博士生导师、中国电子学会高级会员、IEEE会员．1990年、1993年和1997年分别在吉林工业大学、中国科学院长春光机所和天津大学获工学学士、工学硕士和工学博士学位．现为大连理工大学工作，主要从事移动通信技术、无线网络技术等方面的研究工作．

E-mail: whyu@ dlut．edu．cn

The Improved Degree Distribution for Rateless Code Under Partial Information

NIU Fang-lin1，2，LI Bao-ming3，CHEN Fu-liang3，WANG Hong-yu2，ZHU Kai-yan4
(1．School of Electronics and Information Engineering，Liaoning University of Technology，Jinzhou，Liaoning 121001，China; 2．School of Information and Communication Engineering，Dalian University of Technology，Dalian，Liaoning 116024，China; 3．Space Star Technology Co．，LTD，Beijing，100086，China; 4．Institute of Information Engineering，Dalian Ocean University，Dalian，Liaoning 116023，China)

Abstract:Compared with traditional fountain codes，fountain codes with feedbacks can decrease the decoding overhead effectively．The degree distribution has a very important influence on the decoding efficiency of fountain codes．This paper proposes a new scheme of degree distribution under partial information and we use it in fountain codes with feedback．In the first place，we present an optimum monomial degree distribution with less decoding overhead，and then we combine it with shifted robust soliton distribution (SRSD)．At last，we get the improved SRSD (ISRSD) through parameter adjustment．Simulations verify the encoding performance of fountain codes under parity information using ISRSD is greatly improved compared with traditional SRSD．

Key words:fountain codes; LT codes; belief propagation decoder; shifted robust soliton distribution

作者简介

基金项目:国家自然科学基金(No．61172058) ;锦州市科学计划项目(No．12BID13)

收稿日期:2013-10-08;修回日期: 2015-06-23;责任编辑:蓝红杰

DOI:电子学报URL: http: / /www．ejournal．org．cn10．3969/j．issn．0372-2112．2016．02．008

中图分类号:TN911.23

文献标识码:A

文章编号:0372-2112 (2016) 02-0295-06