基于单反馈SLT码的纠错码与MP联合译码

2015-06-19牛芳琳王洪玉祝开艳

系统工程与电子技术 2015年1期

牛芳琳，王洪玉，祝开艳

（1．大连理工大学信息与通信工程学院，辽宁大连116023；2．辽宁工业大学电子与信息工程学院，辽宁锦州121001；3．大连海洋大学信息工程学院，辽宁大连116023）

牛芳琳1，2，王洪玉1，祝开艳3

转移LT（shifted Luby transform，SLT）码是信源依据接收端的反馈信息进行的LT（Luby transform，LT）编码方法，这种编码方法可以有效地减少解码所需要的数据包个数，由此，本文针对基于单次反馈SLT码的信道纠错码与信息传递（message propagation，MP）联合译码方法，对原有的转移鲁棒孤立子分布（shifted robust soliton distribution，SRSD）函数进行改进得到适合MP联合译码的扩展转移鲁棒孤立子分布（expand shifted robust soliton distribution，ESRSD）函数。将本文提出的ESRSD用于MP联合译码方案分别与LT码、反馈SRSD MP联合译码相比，实验结果显示，采用本文提出的ESRSD进行编码在MP译码所需要数据包的个数最少。

SLT编码；纠错码；鲁棒孤立子分布；信息传递译码

0 引言

在数字信号传输过程中，受到噪声的干扰，数字符号会产生无法恢复的错误，为了保证数据可靠传输，传统方法是采用检错重发（automatic repeat request，ARQ）和前向纠错（forward error correction，FEC）技术。ARQ技术，其重发机制对信道容量会产生较大的资源浪费，尤其是当用户数较多时或信道受到较大干扰的情况下，需要利用反馈信道传送大量不必要的反馈确认信息（acknowledgement， ACK），ACK占用较多的网络资源，导致不能进行正常的数据传输；而采用FEC技术无需利用反馈信道和重传应答机制，不会产生重传等待应答带来的时延，但其纠错能力随着码长的增加相应增加，译码器的复杂性也相应地增加，而且在带宽和功率方面也需要付出更多的代价。

与ARQ和纠错码相比，采用喷泉码［1-2］编码方法，不需要ARQ的重传机制，也不需要通过增加纠错码的长度来提高纠错能力。喷泉码编码方法是对k个具有校验功能的数据包按照一定的度分布函数随机选取d个数据包进行异或得到编码包，这些编码包源源不断地从信源发送出去，接收端将接收到的编码包进行校验，如果编码包是正确的，则将其参与到信息传递（message propagation，MP）译码中去；如果编码包是错误的，则将其丢弃，继续接收新的编码包进行译码，直到接收端译出信源数据包则结束译码过程。度分布函数是喷泉码实现的关键，设计有效的度分布可以降低译码开销，文献［3］中最早给出一种稳健的鲁棒孤立子分布（robust soliton distribution，RSD）实现了LT（Luby transform，LT）编码。度分布的优化问题一直是LT编码研究的热点，如文献［4- 6］等都对度分布进行改进降低译码开销。文献［7- 12］等对LT码传输方法进行改进，提出基于反馈信息的转移LT（shifted Luby transform，SLT）编码，在已经恢复部分数据包的情况下，将恢复数据包的个数按照一定规则反馈给信源，信源根据反馈信息对传统的RSD进行转移，得到基于反馈信息的转移度分布（shifted robust soliton distribution，SRSD）函数进行LT编码，接收端将接收到的编码包与已经恢复的数据包相结合进行MP译码。为了进一步降低译码开销，LT码与信道编码级联的编码方法被提出，如文献［13］中将LT码作为外码与低密度奇偶校验（low density parity check，LDPC）码构成级联码，而文献［14］中在LT码与纠错码构成级联码的基础上对传统的度分布进行优化，有效地提高了译码增益。文献［15］中，对于接收到的多个错误数据包，利用数据包之间所满足的逻辑关系提出删除法进行译码，这种方法需要对接收到的信号先进行硬判决，对得到的数字符号进行校验以判断接收到的数据包是否正确。

为了更有效地恢复错误数据包，提高通信传输效率，本文针对单反馈的SLT码与信道纠错码相联合的MP译码方法，对SLT编码转移的SRSD度分布的基础上进行改进，得到适合纠错码与MP联合译码的扩展转移鲁棒孤立子分布（expand shifted robust soliton distribution，ESRSD）。

本文首先介绍了SLT码与纠错码联合MP译码算法；然后对SRSD进行改进得到ESRSD；最后通过实验仿真验证采用ESRSD可以有效地降低信源发送编码包个数。

1 单反馈SLT与纠错码联合MP译码

设接信源按时间顺序发送k个具有校验功能的数据包｛s1，s2，…，sk｝，接收端对接收到的k个数据包经过校验统计出正确数据包的个数n，将n反馈给信源，信源依据n得到一个新的度分布函数，并进行LT编码，编码包源源不断地发送给接收端，对错误的数据包进行恢复，直到所有的错误数据包全部被恢复。采用传统的MP译码方法，一个编码包最多只能恢复一个错误数据包，而编码包与纠错码联合的MP译码方法，存在同时恢复多个错误数据包的情况。

设信源发送S1、S2、S3和S4共4个数据包，经过校验，S2正确，其余均为错误数据包。图1为基于单反馈SLT编码的MP解码过程，黑色圆点表示正确数据包，白色圆点表示错误的数据包，l表示一个编码包最多能够恢复错误数据包的个数，设l≤2。

图1 l≤2单反馈的SLT编码的MP译码过程

信源依据反馈信息发送SLT编码包Pi。如图1（a）所示，首先接收到编码包P1，依据携带的编码地址可知，P1＝S1＋S2＋S4，在接收端，S2已知，S1、S4为错误数据包，则P1＝S1＋S4，依据硬判决网络信道联合译码［15］解出S1、S4。继续接收编码包P2，如图1（b），P2＝S1＋S3，S1已知，解出S3。

传统的MP译码，只有当编码包的相邻节点数为1的时候才能解出未知数据包，采用这种联合译码结构，存在1个编码包可以同时解出多个错误数据包的情况。如图1中存在3个错误数据包，采用联合译码方法仅需要2个编码包即可恢复，因此这种与信道编码相结合的MP译码方法所需要的编码包个数减少，提高了纠错能力。

在信道纠错码与MP相结合的译码方案中，经过迭代后，如果编码包与错误数据包之间满足p＝s1＋s2＋…＋slmod（2）逻辑关系，Si表示发生错误的数据包，即1个正确编码包与多个错误数据包相邻，构成网络信道联合译码的结构，则可以解出所有的Si。

单反馈SLT与纠错码联合MP译码方法的流程图如图2所示，具体步骤如下。

图2 单反馈SLT与纠错码联合MP译码方法

步骤1 信源对信源符号进行信道编码，得到k个具有校验功能的数据包，按顺序发送出去。

步骤2 接收端对于接收到的k个数据包分别校验，统计出正确数据包的个数n。如果n＝k，则得到所有信源信息，发送ACK反馈给信源；如果n＜k，则将n反馈给信源。

步骤3 信源依据反馈信息n，修正度分布函数并对k个数据包进行SLT编码，发送给接收端进行纠错。

步骤4 接收端将接收到的编码包与先前接收到正确的数据包进行纠错码与MP联合译码，直到恢复所有错误数据包，发送ACK给信源，停止发送编码包。

2 度分布设计

2.1 扩展的理想度分布

由第1节可知，SLT编码包与纠错码联合MP译码，存在1个编码包同时恢复小于等于l个错误数据包的情况，针对这种联合译码方案，需要设计一种合适的度分布以降低译码开销。

文献［3］提出了一种理想孤立子分布（ideal soliton distribution，ISD），它是一种理想情况下可以成功进行的LT译码的度分布，本文在文献［3］和文献［6］的度分布基础上对ISD度分布进行扩展，得到同时恢复出小于等于l的适合MP联合译码的ISD度分布

对ρ（d，l）进行归一化即为扩展理想孤立子分布（expand ISD，EISD）

式中，d为编码的度；k为编码包个数；l为1个编码包最多能够解出数据包的个数；γi为比例系数。

对式（1）进行归一化计算

符合概率分布。式（2）即为纠错码与MP联合译码的EISD度分布。

下面对式（1）进行推导，过程如下。

由文献［3］可知，对于接收到的度为d的编码符号，只有当编码符号相邻节点为1时才能解出未知的1个符号，即d－1个符号已知；其概率ρ（d）表示度为d的编码符号在d－1个符号已知的时候解出剩余1个符号的概率，概率等于1／［d（d－1）］，记为ρ（d，1）。LT码与纠错码MP联合译码方案中，则存在1个度为d的编码包与d－l个数据包相邻，可以同时解出剩余的l个错误数据包。例如度为d的编码包，如果需要同时解出2个错误数据包，即l＝2，只有与d－2个数据包相邻才能恢复剩余2个错误数据包，其解出任意2个错误数据包的概率为1／［d（d－2）］，如果l≤2，MP译码每次都可以恢复小于或等于2个错误数据包，则输入1个度为ρ（d）编码包解出2个错误数据包的概率为记为ρ（d，2）。由此可以解出小于等于l个错误数据包，1个度为ρ（d）编码包解出l个错误数据包的概率为

γi大小影响到同时解出i个数据包所对应修正项在ISD度分布中占有的比例。设可以同时解出i个数据包，对应的度为d的编码包中需要与d－i个已知的数据包相邻，才能解出i个错误数据包，由前面分析已知其度分布为当1≤d≤k，其概率之和等于1，由此可以求出γi，本文给出一种计算γi的方法，计算过程如下：

（1）当l＝1时，经过MP译码可以解出1个错误数据包，其分布度函数即为文献［3］中的ISD度分布

（2）当l＝i时，如果编码包的度为d，需要已知d－i个数据包，才能解出剩余的i个错误数据包，则同时解出i个数据包的概率等于由此得到

将γi带入式（1）得到EISD度分布函数，推导过程结束。

2.2 ESRSD度分布函数分布

与ISD相同，EISD分布存在度为1的波纹比较小，在迭代过程中容易消失，因此引入τ（d）［3］对EISD（见式（2））进一步修正，综合上述的EISD

因此，改进后得到的ERSD度分布为

文献［6］提出反馈的SLT编码方法对应的SRSD度分布为

式中，k为信源需要发送的数据包个数；n为接收到的正确数据包个数；u（d）为RSD；round表示四舍五入取整。

对式（7）进行归一化得

结合信道纠错码与MP联合译码方案，将式（6）代入式（8），对ERSD度分布进行偏移，得到转移后的rESRSD（j，l），并进行归一化，得到ESRSD度分布为

式中，RESRSD（j，l）符合概率分布，即为本文提出的适用MP联合译码的ESRSD度分布函数。

2.3 ESRSD度分布函数性能分析

图3为k＝80，n／k＝0.5，l≤3的SRSD与ESRSD的度分布图。

基于单反馈的SLT编码，在已经接收到大量数据包时，信源编码不再考虑1的概率分布，图3中1的概率为0。将SRSD进行扩展得到ESRSD，存在当l≤3可以解码，对于d较低的度分布波纹要求不高，因此ESRSD度分布中，当d较小时其波纹也较小，增加了其他度的概率分布。

图3 度分布图

3 仿真及分析

假设一个理想状态，接收端采用纠错码与MP联合译码，每个编码包均可以恢复小于等于l个未知数据包，丢包率（packet error rate，PER）即为信道删除概率，LT编码中，c＝0.03，δ＝0．5。采用Matlab对实验进行仿真，仿真次数为1 000。

信源需要发送的数据包个数k＝200，采用信道纠错码与MP联合解码，度分布分别选取SRSD（l＝1、l≤2和l≤3）、ESRSD（l＝1、l≤2和l≤3），与LT码相比，在不同PER条件下信源需要发送数据包的个数如图4所示。图中l＝1，表示采用传统的MP译码。

从图4中可以看出，采用LT码译码所需要的数据包个数最多；采用信道纠错码与MP联合译码，当l＝1时，SRSD度分布译码所需要的编码包个数最多，当l≠1时，l相同，采用ESRSD度分布所需要的编码包个数小于SRSD度分布编码，并且随着l的增加，所需要编码包个数下降。当信道丢包概率PER＝0时，采用本文方案不需要任何冗余信息，即仅需要发送200个信源数据包即可传输所有的信源信息，而LT编码方法译码需要存在冗余的编码包才能译码，译码所需要的数据包个数大于信源数据包个数。

图4 比较不同方案在删除信道解码时所需要数据包个数

图4 是一种理想情况下的比较，受到MP联合解码能力的限制，不是所有小于等于l个错误数据包都能被恢复，需要考虑到采用删除法联合译码方法恢复l个错误数据包的概率分布情况。在无线通信环境中，高斯白噪声信道，采用二进制相移键控调制，信源发送数据包个数k＝500，信道编码为（31，21）线性分组码，采用纠正1个错误符号同时校验出2个错误符号检纠错方法，度分布分别选取ESRSD（l≤3）、SRSD（l＝1）与SRSD（l≤3），比较在不同信噪比（signal noise ratio，SNR）信源发送数据包个数。实验结果如图5所示，当SNR较低时，采用ESRSD（l≤3）明显优于SRSD（l＝1）和SRSD（l≤3），随着SNR的增加，信源发送数据包个数逐渐减少，当SNR≥2 dB，编码包中发生错误的符号个数降低，通过（31，21）信道纠错码即可恢复，几乎不需要再接收SLT编码包来恢复错误数据包，因此3种情况译码所需数据包个数几乎相同。

图5 采用（31，21）线性分组码与单反馈无码率编码联合译码信源需要的发送数据包个数

4 结论

本文对于单反馈的SLT码与纠错码MP联合译码方法给出一种新的ESRSD度分布函数，在信道环境较差的时候，由于ESRSD度分布考虑到译码可以同时解出小于等于l个数据包概率分布情况，其编码效果优于SRSD。由此得出采用ESRSD度分布进行单反馈的SLT编码，在噪声信道中可以有效地减少信源发送编码包的个数，提高了编码增益。

［1］Byers J W．A digital fountain approach to asynchronous reliable multicast［J］．Selected Areas in Communications，2002，20（8）：1528- 1540．

［2］Mac Kay D J C．Fountain codes［J］．Communications，2005，152（6）：1062- 1068．

［3］Michael L．LT codes［C］∥Proc.of the Foundations of Computer Science，2002：271- 282．

［4］Nguyen T D，Yang L L，Ng S X，et al．An optimal degree distribution design and a conditional random integer generator for the systematic Luby transform coded wireless internet［C］∥Proc.of the Wireless Communications and Networking Conference，2008：243- 248．

［5］Lei W J，Liu H F，Xie X Z．Switch degree distribution：an improved degree distribution for LT digital fountain code［J］．Journal of Chongqing University of Posts and Telecommunications，2012，24（1）：34- 38．（雷维嘉，刘慧峰，谢显中．开关度分布：一种改进的LT数字喷泉编码度分布［J］．重庆邮电大学学报，2012，24（1）：34- 38．）

［6］Chen Y Y，Liu W．Compressed fountain codes based on new random degree distribution［J］．Journal of Electronics&Information Technology，2012，34（5）：1185- 1190．（陈月云，刘伟．基于新型随机度分布的压缩喷泉码［J］．电子与信息学报，2012，34（5）：1185- 1190．）

［7］Agarwal S，Labs D T A G B，Hagedorn A，et al．Adaptive rateless coding under partial information［C］∥Proc.of the Information Theory and Applications Workshop，2008：5- 11．

［8］Hagedorn A，Agarwal S，Starobinski D，et al．Rateless coding with feedback［C］∥Proc.of the IEEE INFOCOM，2009：1791- 1799．

［9］Sorensen J H，Koike A T，Orlik P．Rateless feedback codes［C］∥Proc.of the IEEE International Symposium on Information Theory Proceedings，2012：1767- 1771．

［10］Sørensen J H，Popovski P，Ostergaard J．Feedback in LT codes for prioritized and non-prioritized data［C］∥Proc.of the Vehicular Technology Conference，2012：1- 5．

［11］Yue G S，Uppal M，Wang X D．Doped LT decoding with application to wireless broadcast service［C］∥Proc.of the IEEE International Conference on Communications，2011：1- 5．

［12］Zhang L，Liao J X，Wang J Y，et al．Diversified SLT codes based on feedback for communication over wireless networks［C］∥Proc. of the Global Information Infrastructure Symposium，2013：1- 6．

［13］Zhu H J．Research on encoding and decoding of fountain codes and their applications［D］．Beijng：Tsinghua University，2009．（朱宏杰．喷泉码编译码技术与应用研究［D］．北京：清华大学，2009．）

［14］Liu X J，Sun X J．Design of short length system Luby transform code of high rate in concatenated scheme［J］．Systems Engineering and Electronics，2013，35（3）：634- 637．（刘晓健，孙晓钧．级联码中的高码率短码长SLT码设计［J］．系统工程与电子技术，2013，35（3）：634- 637．）

［15］Niu F L，Zhang X，Wang D X．A scheme of joint networkchannel erasure correction decoding with binary for wireless communication［J］．Journal of Wuhan University（Natural Science Edition），2013，59（6）：567- 572．（牛芳琳，张兴，王冬霞．无线通信中二进制网络-信道联合删除译码法［J］．武汉大学学报（理学版），2013，59（6）：567- 572．）

MP decoder with error correction codes based on single feedback SLT codes

NIU Fang-lin1，2，WANG Hong-yu1，ZHU Kai-yan3
（1.School of Information and Communication Engineering，Dalian University of Technology，Dalian 116023，China；2.School of Electron&Information Engineering，Liaoning University of Technology，Jinzhou 121001，China；3.Institute of Information Engineering，Dalian Ocean University，Dalian 116023，China）

Shifted Luby transform（SLT）codes are the kind of digital fountain codes whose data packets are encoded with the LT codes by the feedback information in order to decrease the number of the encoded packets at the receiver end．This paper proposes an expand shifted robust soliton distribution（ESRSD）function through modified shifted robust soliton distribution（SRSD）for the scheme of message propagation（MP）decoder with error correction codes based on the single feedback information in order to get the encoded packets recovered those error packets at the end．To compare ESRSD with SRSD，experimental results show that the number of packets by using ESRSD is the least，compared with the other methods in LT codes or using the SLT codes with the SRSD．

shifted Luby transform（SLT）codes；error correction code；robust soliton distribution（RSD）；message propagation（MP）decoder

TN 911．21

10．3969／j．issn．1001-506X．2015．01．28

牛芳琳（1971-），女，讲师，博士研究生，主要研究方向为信息论、数字喷泉码编码技术。

E-mail：niufanglin＠sina．com

王洪玉（1968-），男，教授，博士研究生导师，博士，主要研究方向为无线协作通信技术、自组织网络及无线传感器网络技术。

E-mail：whyu＠dlut．edu．cn

祝开艳（1980-），女，讲师，博士研究生，主要研究方向为协作通信、网络编码技术、数字喷泉码编码技术。

E-mail：zhukaiyan＠dlou．edu．cn

1001-506X（2015）01-0175-05

网址：www．sys-ele．com

2014- 02- 26；