特定条件下的LT码关键参数性能研究

摘 要：针对LT码的编译码过程、度数分布以及应用环境特性，提出了LT码度数分布中的关键参数分析模型，其核心思想是在对LT码的编译码参数进行极限值研究，在数学分析的基础上得出了最优化参数条件下的LT码性能，并且对各个参数的重要性进行分析，提出了数字喷泉码译码失败概率的具体值。在极限值条件下研究了接收的数据量对LT码的影响以及得出了最佳接收数据量。理论研究和仿真结果表明：提出的关键参数分析模型，能够较好的拟合实际LT码性能条件。

关键词：数字喷泉码 LT码 度数分布 应用模型

中国分类号：TN911.22 文献标识码：A 文章编号：1672-3791（2013）07（c）-0001-02

数字喷泉码是近年来兴起的一种新型信道编码技术。在1998年，M.Luby等国外专家提出数字喷泉码原理后[1]，其理论与应用也越来越受到关注。它具有一些特殊的优点，数字喷泉码不需要数据重传信道，可以大大节省信道资源。在通信中，有效性和可靠性是一对矛盾，信道编码技术是保证信息传输可靠性的必要方法。信道编码实质上是通过增加信息的冗余来提高信息传输的可靠性。在信号衰减很严重，传输信号淹没在噪声中时，可靠性问题就尤为严重的凸现出来了。为了使信号具有较强的抗噪声干扰的能力，需要对信号加以改造，使信号内部结构具有更强的规律性或相关性，以保证在噪声干扰下仍能发现错误，甚至纠正错误，恢复原来的信息。

数字喷泉码作为一种信道编码可以改进无反馈信道的通信方式，它是一种前向纠错编码技术。信息在发送端经过纠错编码后送入信道，接收端通过纠错译码自动纠正传输中的差错，这样的方式叫做前向纠错（FEC）[2]，前向则是指过程是单向的，没有反馈。这种方法具有较低的开销和较精确的差错恢复能力。而传统的FEC存在一些缺陷[3]：（1）在传输过程当中，数据组与组之间有时延。（2）当接收端在没有接收到系统所要求数据包个数的情况下，需要发送端重传整个数据块，不符合实时传输。而对于数字喷泉码，不需要发送端与接收端之间的交互，可以大大减少传输时延。而且，当没有接收到应有的数据包个数时，不需要重传整个数据块。

数字喷泉码的应用环境主要是删除信道，删除信道主要是指的一种类似于纠错概率很高的噪声信道，在其中传输的数据要么彻底丢失，要么完全正确无误的被接收。

1 数字喷泉码

数字喷泉码可以从K个原始数据分组生成得到无穷多个编码分组，是一种无码率的码。当接收端收到足以译码的编码分组的个数时，便能成功译码，该种码便被形象的称为喷泉码。数字喷泉码不需要数据重传信道，可以提高信息传输的可靠性。在数字喷泉码的研究当中，将其分为三类[4，5]：（1）随机线性喷泉码。（2）LT码（Luby Transtion Code）（3）Raptor码。严格意义上说，随机线性喷泉码不算是喷泉码，其编译码复杂度太大且成功译码概率较低；LT码是第一种可以实现的喷泉码算法，它也是一种稀疏码，其编译码过程是做二分图的过程；Raptor码是在LT码基础上进行的编码，其编码时平均度数较低。本文主要研究LT码，将会详细讨论LT码的编译码过程[5，6]，其余两类具体编码可参见参考文献[7，8，9]。

1.1 LT编码

（1）从合适的度数分布当中，随机地选择一个值，该值即为该编码分组由几个原始数据生成，叫做该次编码分组的度数。

（2）从原始数据分组（比特）当中随机的选择个数据，将该个数据进行模2和。

（3）重复以上步骤，生成编码分组。

1.2 LT译码

喷泉码的译码，目前普遍采用MP（message passing）算法，过程如下。

（1）在得到的编码分组数据当中，找到度数为1的编码分组，若没有，则译码失败。

（2）在二分图当中，将该度数为1的编码分组直接复制为原始数据分组。

（3）将上一步生成的原始数据分别模2和到与之相连的其余编码分组当中，并且去除该原始数据和这些编码分组的连接关系。

（4）将上一步当中的编码分组数据的度数减少1。

（5）重复以上四个步骤，直至恢复原始数据，译码完成。

1.3 LT码的度数分布

在上述LT码的编码过程当中，需要一个合适的度数分布，这是该种算法最关键的问题，它必须满足以下两个条件。

（1）在一定意义上度数分布较高，使得生成的编码分组能够尽可能包含所有原始数据。

（2）要求编码分组的度数不能太高，使LT译码能够成功开始以及进行下去。

2 LT码编译码过程的研究与仿真

2.1 有关参数的研究

在数字喷泉码编译码过程当中，一个重要的指标就是译码失败的概率。根据提出的理论，它不需要反馈信道，通过发送端可以给出无穷多个编码分组，是无码率的，只要接收端收到足够的编码分组，便能以高概率译码。而进行整个过程时，度数分布是一个重要的概念，直接关系到译码能否开始进行以及译码成功的概率。

在本文的研究过程中，信源（原始数据）选择的均是相关性不大的随机数据比特。通过对鲁棒孤子分布的参数进行改进，得到最优化参数情况下的译码失败概率，本文在对参数的研究过程当中，得出参数c较参数的影响大，c会直接影响译码失败概率，而的变化基本对译码失败概率没有影响。据图1和图2可得出最优化的参数c在0.2处转折，可选择c大于或等于0.2，这里我们选择c=0.2，因影响较小，对可以根据实际应用情况而定，研究当中我们选择=0.01。

用最优化的参数可以使译码失败的概率降到相对很低的范围。

2.2 接收数据量对译码性能影响的研究

如上所述，数字喷泉码是一种无码率的码，而在数字喷泉码的研究过程当中，得出数字喷泉码能成功译码所需接收的最少数据量有三种[5，6]：、以及。其中N是接收数据量。本文针对固定的原始数据比特K=512比特，当接收到的编码分组个数不同时得到的译码效果如图3所示。

图3中显示了接收数据分别为以上三种情况时的译码性能。由图可以看出，随着接收端收到的数据比特数的增加，译码失败概率在减少，当收到的数据比特数在接近K值时，该概率减少非常迅速，之后速度下降，基本维持稳定。在收到 个编码分组时效果最好，可以得到最佳接收数据至少为。而且，对于一定的原始数据信息，并不是收到的编码分组越多，译码概率就越高，是取决于其中度数1的编码分组S的个数。

2.3 译码失败概率具体值的研究

喷泉码的译码概率和以下几个因素有关：（1）收到编码分组的个数。（2）度数为1的编码分组个数。因为喷泉码是一种无码率的码，可以生成无穷多个编码分组，能够保证接收端有足够的编码分组成功译码。Luby指出，选择一个合适的参数c后（本文得出最优参数c=0.2），当接收端收到个编码分组时便能以高概率成功译码，该译码成功的概率在Luby的理论上的理想值为1-，但实际过程中做不到。经过本文的研究仿真，得出在Luby理论下的译码失败概率平均值为10-2数量级左右，而使用喷泉码最初的理论值以及使用（该值是仅仅保证接收端可以开始进行译码到完成所需的编码分组个数，并不能保证高概率）时，译码失败概率平均值则比Luby理论下的值大，如图4所示。

由图4可得，接收数据量为 和时其译码失败概率在～数量级之间，波动相对较大，而且当收到时较效果好。在具体数值上，平均值基本为10-2数量级左右，如表1所示。而接收数据量为时，其译码失败概率比较大，但较平稳，为10-1左右。

3 数字喷泉码的进一步研究

数字喷泉码的应用环境只能是删除信道，而理想的删除信道是不存在的。在实际应用过程当中，纠错能力较强的噪声信道近似于删除信道，那么可以设想，在实际应用时，可以将数字喷泉码与纠错能力较强的纠错码进行级联，从而体现出数字喷泉码的性能。如图5所示

该图是数字喷泉码在实际当中应用的一种可能模型。其中由纠错码编码到纠错码译码部分相对数字喷泉码来说相当于删除信道，因为纠错码对信道进行了“改造”。只要纠错码的纠错性能达到一定要求，就能体现出数字喷泉码在通信当中的优越性能。其中纠错码可以采取Turbo码，LDPC码等纠错性能较好的码。

4 结论

数字喷泉码是在前向纠错码的基础上发展而来的，它应用于删除信道，且不需要顾及信道中删除事件的统计特性。它在发送端发送无穷多个编码分组，只要接收端收到一定数量的编码分组数据，就能够以高概率成功译码。数字喷泉码在提出的时候只是一个概念，并没有可行的算法，而LT是第一种实现的数字喷泉码，它充分继承了数字喷泉码的优点，但是LT码的编译码复杂度比较大，实时性较差。同时，删除信道也是数字喷泉码理论的一个重要组成部分，本文首先对LT码的各个方面性能及参数做了较深入的研究，给出了LT码的一些结论，并且提出了一种可能的删除信道应用模型，当应用纠错能力较强的码时，可以实现数字喷泉码的实际应用。在后续的研究当中，需要对数字喷泉码的算法进行改进，使其编译码复杂度下降，提高在应用时的可靠性和有效性。

参考文献

[1]卢守信.喷泉码技术研究[J].信息科技，2007，6：101-102.

[2]张宗橙.纠错编码原理和应用[M].北京：电子工业出版社，2003，4：25-27.

[3]熊鹰，金心宇.前向纠错编码传输机制的优化[J].江南大学学报，2006，4：127-131.

[4]MacKay D J C.Fountain codes[J].IEE mun，2005，152（6）：1062-1068.

[5]AminShokrollahi.FountainCodes[J].EPFL.2003.

[6]Michael Luby.LT Codes[C].Proceedings of the 43r Annual IEEE Symposium on Foundations of Computer Science，2002：1-10.

[7]王仕奎，张爱清.基于喷泉码的分布式鲁棒存储[J].武汉大学学报：工学版，2007，6.

[8]孟庆春，王晓京.Raptor Code预编码技术的研究[J].计算机工程，2007，1.

[9]Amin Shokrollahi.Raptor Codes[C].IEEE Transactionson Information Theory，2006，52（6）：2551-2567.