LT码的性能分析与研究.docx

??

?

??

LT码的性能分析与研究

?

?

?

?

?

??

?

?

?

郭春梅毕学尧

（1．联想网御科技（北京）有限公司博士后分站，北京100086；

2．中国科学院软件研究所，北京100190)

摘要：LT码(LubyTransformCodes)属于数字喷泉码，是一类新型前向纠错编码算法，适用于基于包通信的删除信道环境：本文概述了LT码的编译码原理及实现方法，对LT码的理想孤子度分布算法和鲁棒孤子度分布算法进行了仿真验证，分析了LT码在包删除信道下的性能，讨论了实际应用中的参数优化规则，研究结果对提高实时纠删应用的性能具有重要的实用价值。

关键词：数字喷泉码；LT码；前向纠错编码；度分布

TP393.08：A

0引言

前向纠错(FowardErrorCorrecting，FEC)技术近年来广泛应用于信息处理的各个领域。各种纠错码，诸如汉明码、BCH码、RS(Reed-Solomon)码、卷积码、Turbo码、低密度奇偶校验码(LowDensityParitycheckcodes，LDPC)等，所讨论的错误检测和纠错多用于低层协议（如链路层）以比特串为单位的纠错。随着IP技术的发展与普及，对于高层协议的应用、基于数据包通信的删除信道环境下的抗分组丢失技术的研究成为了该领域的研究热点。

LT码是数字喷泉码的一类实用码，采用了随机编码的思想，是一种码率不受限码，也称为无码率码(RatelessCode)。LT码可以在源端产生无限多的编码数据包，直至接收端能正确恢复源文件，由于其在删除信道下的性能优越，在多播传输、广播通信、卫星通信、数据安全存储等领域具有广泛的应用前景。

本文主要研究和分析了LT码的性能，讨论了其在应用中存在的问题，通过仿真结果给出了相关的解决途径和结论，具体结构如下：第二节概述了LT码的编译码原理及实现方法，在第三节中对LT码的理想孤子度分布算法和鲁棒孤子度分布算法进行了仿真验证，第四节分析了LT码在包删除信道下的性能，并讨论了实际应用中的参数优化规则，研究结果对提高实时纠删应用的性能具有重要的实用价值。第五节为全文总结。

1LT码编译码原理

LT码从K个源数据包在线编码产生的编码数据包序列是无限的，每个编码数据包等于若干随机独立选取的源数据包的异或和。接收方只要收到其中任意m个编码数据包（m-般略大于K），就可通过译码以高概率成功恢复全部K个源数据包，因此引入了一定的译码开销s．定义为￡=m/K-I，其对于具有不同删除概率的各种删除信道均是最优逼近的。

1.1编码原理

首先将待编码的源文件分为等长的K个源数据包，设为s1，S2…SK，每个SK都是一个信源符号，在删除信道传输中它只存在两种状态，即被完整传输到目的端或者被删除。

由K个源数据包s1,s2…SK产生n个编码包f1，f2：…fn的过程需遵从以下规则：

1)从度概率分布函数p(d)中随机选择一个码元的度为dn，其值的选取依赖于源数据包的码元个数，有关度分布算法的选择和分析将在第二节进行讨论。

2)从源数据包中随机的选择dn个码元。

3)将选择出的dn个码元进行异或运算，得到一个编码包t。

4)重复以上各步，直至解码过程结束或达到预先设定的编码包数量。LT码属于不规则的二部稀疏图码，在产生编码包的过程中，编码器生成一个K阶随机二进制矩阵GKn，参加生成tn。运销随编码包传输。

1.2译码原理

删除信道下的稀疏矩阵码的解码就是从tl，t2…tn,恢复出s1，S2…SK的过程，一种简便易行的方法是采用置信传播算法实现译码.

定义已经接收到的编码包tn为检验包，具体解码过程如下：

1)找到一个度为l的检验包tn，即该检验包只与一个SK联系。如果没有这样的检验包，则解码过程终止，无法恢复所有的源数据包，解码失败。

2)令SK=tn.

3)将SK与所有和SK有关联的tn进行异或运算。

4)删除所有与SK相关的边，即GKn=0。

5)重复以上各步，直至确定所有SK。

2度分布算法

度分布函数的设计是LT码构造中的关键，因为度分布直接决定了LT码的译码成功概率，也决定着产生编码包所需要的运算量，既要保证编码器输出的编码包有足够大的度，即dn接近于K，以保证让每一个源数据包s。都[来自WwW.lw5U.com]参与编码，又必须有大量的低度编码包，以便保证解码能够开始并持续下去，同时降低在编码和解码过程中的运算量。

2.1理想孤子度分布

理想情况，为了避免出现过多冗余包，希望接收到的编码包tn有这样的性质，即在每～次解码循环中，至少有一个检验码的度为l。理想孤子度概率分布函数设计如下,上述理想状态会一直出现。

经分析，在此度概率分布下编码包的平均度约为InK，至少需要KlnK条边才可能实现成功解码。理想孤子分