LT码的性能分析及仿真

杨 玲，宋时立，刘国超，陈 霄，文 红

（①电子科技大学 通信抗干扰国家级重点实验室，四川 成都610054；②东南大学 移动通信国家重点实验室，江苏 南京 210096）

0 引言

喷泉码是一类基于图的线性纠删码，在广播方式的通信系统中，发送端对原始信息进行编码，得到源源不断的编码信息并且发送，只要接收端能正确接收到足够的编码信息就可以译出原始数据信源，反馈重传的差错控制方式相比，其更为有效，尤其适用于深空通信环境。

Michael Luby[1]于1998年提出了喷泉码[2-3]的概念，喷泉码的设计需要主要考虑2方面的问题：①译码开销ε尽量小，使其趋近于0；②编译码复杂度尽量低：理想情况下，希望做到每个编码分组需要的运算量是一个与K无关的常量，获得K个原始数据分组的成功译需要的运算量是K的线性函数。

本文首先介绍LT码随机度分布，进而剖析LT的编码、译码算法[4-5]，对各种长度的LT进行了仿真。本论文的结果对LT码的选用有参考意义。

1 LT码的编码译码算法

LT码指：其编码由K个信源包生成任意数量的编码包，译码器接收到编码包中任意N个，即可以高概率通过译码成功恢复出全部信源包，这里，每个信源包代表一个数据包，可以是1比特，也可以是多个比特[4-7]。通常情况下，N略大于K，由此会有一定的译码开销 β=N/ K-1。

LT码的关键就是设计随机度。也就是LT码的随机行为完全由度ρ（d）来决定。

度：与该编码包相连的原始数据分组数目。

度分布：对于所有的d，ρ（d）表示编码分组中出现度为d的概率。

目前研究得较为成熟的度分布主要有4种：全“1”分布、理想孤波分布、均匀分布和鲁棒孤波分布。其中鲁棒孤波分布是最为广泛使用的一种度分布。

1.1 LT码的编码算法具体实现

1)从度分布概率函数 ρ（d）中随机选取编码数据包的度d。本文我们选用的鲁棒孤波分布。

2)从K个原始数据包中，等概率地随机选取d个源始数据包 sk。其中这里的d就是刚从度分布函数中选的度数。

3)将这d个源始数据包进行模二和，生成一个编码数据包。

图1 一个编码数据包的生成过程

以图1为例，我们先从鲁棒孤波度分布函数中选取得度d=4，然后从K个源数据包中等概的选出4个数据包，图中我们选的是s1、s3、s4和sk。最后将这4个数据包进行模二和。这样就得到了一个编码数据包。

1.2 LT码译码算法

目前 LT码的译码算法主要有消息传递算法(MP，Message Passing)和高斯消元法(GE，Gaussian Elimination Decoding)2种。

1.2.1 消息传递算法（MP）

LT码在删除信道条件下的MP译码过程如下：

1）首先寻找度为1的编码符号nt，即该编码包只与一个ks相连。如果找不到这样的编码包，译码过程就此终止，信源包无法恢复。

①令ks=nt；②将ks与所有和ks有联系的nt异或；③删除所有与ks的联系。

2）重复过程步骤1，当所有的ks都确定后，译码停止。

1.2.2 高斯消元算法（GE）

高斯消元法的译码步骤如下：

1）对生成矩阵进行列变换，对应列接收的数据包进行相同的变换，将生成矩阵G变换为[Ek*k|P]形式，对应的t1,t2,…,tn变换为

以图2为例说明LT码的译码过程。

在图2（a）中 t1是度为1，与t1相连的是 s1。所以令 t1=s1。在图2（b）中，令 t1=s1后，恢复出了 s1，然后释放掉t1。图 2（c）中，恢复出 s1后，删除了与 s1相连的 t2和 t4的连线。此时，t4的度此时为1，令 t4=s2，然后 s2数据得到恢复，删除 t4。图2（d）中，s2已经恢复出来了，然后让 s2与和它相连的 t2和t3相异或，并且删除与其的连线。图 2（e）中，此时 t2和 t3的度都为1，与他们相连的是 s3，所以 s3也就恢复出来了；图2（f）是恢复出来的原始数据包。

图2 LT码的译码算法实现过程

2 仿真分析

本节对LT码的性能进行仿真。仿真所用的软件是：VC 6.0、Matlab。所用参数是：LT随机度生成用的是鲁棒孤波分布；源数据包的长度K=255、K=2 000、K=4 000、K=6 000、K=8 000；二进制删除信道的删除概率 p分别等于起始值为 0.05，步长为0.05，终值为0. 5；常数c=0.03；译码允许失败概率δ= 0.5；帧长=200；

2.1 短码长的LT码的性能分析

[6-8]。本小节采用发送数据包长度为K=255，结果如图3所示，发送数据包长度K=255，刻画短码长的性能我们用冗余度和成功译码概率关系图来描述。从图中我们可以看到，在源数据包长度比较短的情况，当我们依次增加信道噪声(即丢包率)时，只有当冗余度不断的增加才能完全的恢复出所有的原始数据包。

图3 不同删除概率下译码概率和冗余度比较

以 K=255，q=0.5为例说明，当接收端接收到520个包时 200次迭代才能正确译码一次，此时图中冗余度是信息源包的2.03倍左右。再继续接收成功译码的概率也随之增大。直到接收到1 080个包即冗余度为信息源包的4.23倍时，译码概率才达到1，之后就达到一个成功译码的稳定状态。

2.2 长码长的LT码的性能分析

图4是数据包长度分别为2 000、4 000、6 000和8 000的性能仿真。

图4 鲁棒孤子分布的LT码成功译码数据包数目

从图4中看到，当源信息包为K=2 000时，当接收端接收到2 800个左右数据包就能成功地译出源数据包，我们还可以看到，随着接收数据包的数目增加，接收端能达到接近100%的成功译码。当信源数据包分别为K=4 000，K=6 000，K=8 000时，在接收端如果接收到接近于5 000、7 500和10 000个数据包就能几乎完全成功译码。同时当接收数据包数目增多，几乎每次都能译码成功。

3 结语

本文主要介绍了4种设计LT码随机度分布的方法并进行了Matlab仿真验证，从图中得到鲁棒孤波分布产生的随机度是一种比较好的方式。同时也仿真得到了短码长的LT，因为码长K比较小，编译码的复杂度比较低，相应译码时间也比较少。短码LT的缺点就是译码[9-11]所用的编码包的数量不再趋于原始包长，冗余度会增加。喷泉码的性能受码长的影响较大，要取得好的性能，通常需要较长的码长，但是，码长太长会增加编译码复杂度。

参考文献

[1] LUBY M.LT Codes[M].USA:ACM,2002:6-7.

[2] SHOKROLLAHI A.Raptor Codes[J].IEEE Transactions on Information Theory,2006,52(06): 2551-2555.

[3] 冀保峰，高宏峰. Fountain码编译码技术的研究[J]. 通信技术, 2008,41(11):66-68.

[4] FINAMORE, WEILER A, RAMOS, et al. Improving the Performance of LT Codes[C].USA:IEEE,2010:566-570.

[5] ZHANG Fan, XU Lixin, PAN Xi. Comparison of BP and Gauss Code base on Fountain Code Measuring[C]. USA:ICMTMA,2011:737-740.

[6] ZHU Hongjie,ZHANG Chao,LU Jianhua.Designing of Fountain Codes with Short Code-Length[C].USA:IWSDA, 2007:65-68.

[7] 黄诚,易本顺,吴雄斌,等.短码长 LT码的蚁群算法度分布优化[J].北京邮电大学学报,2011(06):129-133.

[8] 郭春梅，毕雪尧.LT码的性能分析与研究[J].信息网络安全,2010(10):53-55.

[9] 任祥维，文红，张颂.LDPC码的全并行概率译码[J].通信技术，2011,44(08):42-44.

[10] 张威，徐熙宗，张克，等.RS级联编码在超短波通信与卫星通信信道的仿真分析[J].通信技术，2009,42(02):27-29.

[11] 伊立新，刘云莉，袁成刚，等.基于LDPCA的分布式视频编码实现及应用[J].信息安全与通信保密，2012(02):42-47.