LT码编译码分析及改进

贾惠宁

（北京新立机械有限责任公司，北京100039）

摘要：数字喷泉码是一类不受限的纠错码，即从原始数据分组编码产生的编码分组序列是无限的。通过研究数字喷泉码中译码终止的原因，得出在数字喷泉码中，译码终止是由于缺少度数为1的编码包，导致译码提前终止以至译码失败。注意到度数为2的编码包在整个编码包中占有很高的比例；因此，将数据包分成两组，在度数为2时，分别从两组中取出数据，这样可以有效地提高数据的覆盖率，降低译码提前终止的概率。通过对编码算法的改进，提高整个数字喷泉码的译码成功率。

教育期刊网 http://www.jyqkw.com
关键词 ：数字喷泉码；译码终止；度数；改进算法

中图分类号：TN911?34 文献标识码：A 文章编号：1004?373X（2015）14?0020?04

收稿日期：2014?12?25数字喷泉码与传统的信道编码相比，具有“无固定速率”这一特性。这使得数字喷泉码可以应用到许多复杂的信道当中，这一特性是由数字喷泉码的编码和译码方式直接决定的，因此有必要得到性能更加优良的数字喷泉码的编译码方案，使得它在实际应用中可以更加方便，运算复杂度更低。LT码和Raptor码是数字喷泉码中最典型的两种方案，而Raptor码是在LT码编码之前进行了一个预编码，因此LT码成为了现在最基础也是研究最为广泛的编码方案。本文将对LT码的编译码方案进行系统的分析，并在此基础上对其编码算法进行改进，使其性能更加的优良，最后通过仿真验证结论。

1 LT 码编译码方案分析

1.1 LT码编码方案分析

LT 码的生成矩阵与其编码的二分图是一一对应的，节点的度对应到二分图中表示与对应节点相关联的边的个数。因此，LT 码的度分布函数决定了其编码的结构，合理的度数分布函数是LT 码编码方案的关键。当使用固定的BP译码算法时，LT码编码的性能几乎完全由度数分布函数决定；因此希望LT码的度数分布函数尽量满足以下条件：

（1）尽可能用最少的接收到的编码包译出原始的数据包，即译码开销尽量小。

（2）在编码时使所选取的平均度数尽量小，这样可以减少模运算，使得编译码代价尽可能的小。

LT码的度数分布函数应该保证所有的数据包都至少被选取1次，形成所需要的编码包，即编码过程应该覆盖到所有的数据包，使得在译码的过程中不会丢掉某一个数据包导致译码失败。从编码的角度考虑，要使平均度数尽可能小，这样可以保证运算量小，但是同样为了保证编码包可以覆盖到每一个数据包，就必须有少量的大数值度数存在。如当数据包的长度k = 100 时，除了要选取大量的小数值的度数，如1 或2，同时也要选取极少量的大数值的度数如99或100。从译码的角度考虑，一方面要保持编码包的释放速率以得到对应的数据包，但是同时，释放的速率不可以太快，如果太快就将导致有大量的数据包被重复的释放，这样带来不必要的冗余。

1.2 LT码译码方案分析

对于具有良好的度数分布函数的LT 码编码算法，BP译码算法往往可以达到较为理想的译码复杂度。

LT码的BP译码算法，首先译出与所有度数为1的编码包相连的数据包，然后再处理与这些数据包相关联的其他编码包，称这些编码包为预处理集；然后再处理预处理集，将预处理集中的元素与相连的编码包中的元素进行模运算，并且去除度数为1的编码包与数据包的相关联性，经过这个处理，原来度数为1的编码包将不存在，而原来度数不为1 的编码包现在度数将变为1；最后再对上述过程进行反复，即可以得出译码结果；如果最终有1个数据包未被译码出来，称之为译码失败，反之译码成功。

由上述分析可知，BP 译码算法的关键是在查找度数为1的编码包，只有不断地有度数为1的编码包存在，译码过程才可以不断地进行下去，而如果在未完成译码时，一旦度数为1的编码包为0，译码将提前终止，这是不希望看到的。而度数为1的编码包的数量直接由LT码的度数分布函数决定，因此就要对LT码的度数分布函数进行专门的分析，以了解度数为1的编码包的具体分布和变化情况。

1.3 LT码度数分布函数分析

由于度数分布函数是LT 码当中最重要的函数，其性能的优劣直接影响到编码译码算法的进行，因此应该先对度数分布函数进行分析。

首先假设一种最理想的度数分布函数，即所有的编码包的度数均为1，这是在译码过程中非常乐意见到的，需要所有的编码包可以覆盖到所有的数据包，这样在译码的过程中将不会有数据包被遗漏。假设数据包的个数为k ，编码包的个数为n ，则任意一个符号被覆盖的概率P ，可等效为所有的符号都不被覆盖概率，即为：

假设编码包中度数为0的编码包出现的概率为δ ，那么所有的数据包都至少被一个编码包覆盖的概率为1 - δ ，则在度数都为1 的分布中，所需要的编码包的个数n 至少需要：

由式（2）可表明，如果度数分布全部为1，则在译码的过程中所需要接收到的编码包的数量n 将是一个极大的值，即译码开销非常大，所以假设的这一理想度数分布函数在实际中是不可能使用的。

现在，假设某一个编码包的度数为i ，此时未被处理的输入符号个数为L ，那么q(i,L) 表示度数为i 的编码包，在还有L 个数据包未被处理时被释放的概率，则：

由以上论述可知，在进行BP译码算法时，为了使得BP译码算法可以顺利的进行，在译码的每一步，至少需要一个度数为1的编码包，同时，当此次译码结束，下一轮译码开始的时候，要保证又有新的度数为1的编码包出现，这样才能保证译码顺利的进行下去。

在理想的度数分布函数的情况下，每轮的BP译码算法都有且仅有一个度数为1的编码包被释放；在这轮译码完成之后，又会有且仅有一个度数为1的编码包出现。这就使得在译码的过程中，输入符号加入到BP译码的速率与其被处理的数据相等。一方面，释放的编码包需要随机的译出一个对应的数据包；另一方面，要形成一个新的度数为1的编码包以使得译码过程可以继续进行下去。当k 个输入符号全部被译出来之前，一旦不存在度数为1的编码包时，译码就将失败，从这个角度来看，要保证度数为1 的编码包的个数适当的大一些，而不要为1。综上分析可知，度数为1的编码包的个数应该适当的大些，这样可以提高译码的效率，同时提高译码的成功率。

联立式（3）~式（7）以及理想的度数分布函数，可以得到r(L) = 1 k ，证实了刚才的结论。理想度数分布函数在译码过程中度数为1的编码包个数始终保持不变，始终维持在有且仅有一个度数为1的编码包。

在实际应用中，并不可以按照理想的度数分布函数来设计数字喷泉码，因为这样会造成在实际译码过程中，第一步不能够快速完成，导致后面的很难找到度数为1的编码包，使得译码终止。所以理想度数分布函数是一种可行性很差的度数分布函数，仅在理论研究上存在，也仅具有理论意义。

因此，在具体实践过程中，又提出了鲁棒度数函数分布（Robust Soliton Distribution），在此对它的性能和实用性进行分析。

在鲁棒度数函数分布中提出了中间变量S ，S 的物理意义是每一步迭代译码中度数为1的编码包的个数，这是它与理想度数分布函数的最大不同之处，这样将使得译码的效率大大提高，同时，在每一轮迭代译码的过程中，也不会因为没有度数为1 的编码包导致译码终止。鲁棒度数分布函数的其余原理与理想度数分布函数基本上一致，但是S 的引入，已经从本质上改变编译码过程的算法复杂度，以及整个编译码的译码开销。鲁棒度数分布函数所需要的编码包的个数为：

同时可知，鲁棒度数分布函数中的c,δ 两个参数的大小也会影响到译码的效率，但它们是个经验值，并没有太多的理论依据来确定它们到底取多大，因此需要在实际应用仿真中总结经验，来确定它的大小。

2 改进的LT 码编码方案

经过上面分析可知，BP 译码算法在译码初期经常频繁地停止译码，是因为缺少度数为1的编码包。因此除了对度数分布函数进行改进，使其在每一轮都有足够多的度数为1 的编码包之外，还可以对LT 码的编码方案本身进行改进，从而使得BP译码算法不会频繁的在初期终止，以提高译码的成功率以及译码效率。在改进方案中使用最经典的，同样也是使用最广泛的鲁棒度数分布函数。

由鲁棒度数分布函数可知，在编码包的度数分布中，度数为2的编码包的个数接近所有编码包的一半，因此，需要合理地处理好编码过程中度数为2 的编码包，以实现效率和成功率的提高。

当随机度数为2 时，编码器会在k 个原始数据包中，随机选取2个数据包，并对他们进行模运算，得到相对应的编码包，然后发送到信道中传输。但是在选取这2 个原始数据包时，如果采用随机的方式选取，则总共有C2k 种可能性，而如果在将原始的数据包分成2份（可以相等也可以不相等），则总共的可能性为C2z(k - z) ，选取的可能性大大降低，意味着覆盖率将大大提高，这样，更加有助于在译码的每一步都有足够多的度数为1的编码包用于译码。

可以将改进的LT码的编码方案描述为：

（1）将原始的数据按照等长l 分成k 个数据包（不足的通过补0完成）；

（2） 将原始数据包分成2 组，每组的数据包个数相等；

（3）根据已经设计好的度数分布函数ρ ，随机地选取度数d ，作为数据包的编码度数；

（4）判定d 是否等于2，如果等于2 则从已经分好的两组当中分别选取一个数据包，如果不等于2，则在k个数据包中等概率地选d 个数据包；

（5）将选出的d 个数据包进行异或运算，生成一个编码包；

（6）重复上述步骤，直至接收端接收到足够多的编码包。

综上所述，其实就是在根据度数选取数据包时进行了一个判定的过程，依据所随机到的度数是否为2，按照不同的方法选取数据包进行模运算。接下来将会通过仿真，对改进后的LT码的性能进行研究。

3 仿真及其分析

为了使得仿真可以正确地反应改进的方案，选取鲁棒分布作为对比算法公用的度分布函数。同时为了保证数据比较准确，选取K = 2 000 ，即初始的数据包个数为2 000。图1为改进前的算法和改进后的算法对应的仿真示意图。其中c = 0.2,δ = 0.01 。

通过上述仿真结果可看出，在接收包为2 400 以下时，两种算法的性能差不多，这是因为在接收包较少的情况下，度数为2的编码包的个数本身就很少，这就直接导致改进后的算法在性能上并不一定能优于改进前的性能，但是随着接收包的增多，度数为2的编码包的个数极具的增多，这就使得改进后的算法的优越性就体现出来了，因此，越往后面走，改进后的算法的性能就越好。同时再次考虑到数据包分成两组的过程中，如果不按照等分的方法进行分配的情况再进行一次仿真，这次选取度数为2的数据包的分组是不等分的情况，结果如图2所示。

从图中可看到未等分的性能差一些，因为当两组数据的个数不相等的情况下，两者数据的数量相差越大，则越近似于原有的编码方案，相当于算法又回到了过去。

4 结语

本文详细的对LT 码的编码，译码和度数分布函数进行了剖析，得知在译码的过程中离不开度数为1的编码包，而它又是动态存在的，因此需要将度数为1的编码包的个数始终保持在很高的程度，这样在译码的过程中，就不会因为缺少度数为1 的编码包而导致译码终止，最终导致译码失败。因此考虑到在编码的过程中，对度数为2的编码包的编码过程进行特殊的处理，将所有的数据包，分成2组（最好等分），从每一组中随机选取1个数据包进行模运算，这样可以大大提高数据包的发概率，也大大降低了在译码过程中缺少度数为1的数据包的可能性，使译码的成功率提高。

教育期刊网 http://www.jyqkw.com
参考文献

[1] 王新梅，肖国镇.纠错码原理与方法[M].西安：西安电子科技大学出版社，1991.

[2] LUBY M. LT codes [C]// Proceedings of the 43rd.Annual IEEESymposium Foundations of Computer science（FOCS）. Vancou?ver，Canada：IEEE，2002：271?280.

[3] 朱宏鹏，张更新，谢智东.喷泉码中LT码的次优度分布[J].应用科学学报，2009，27（1）：6?11.

[4] LEE K R H. A maximum?likelihood decoding algorithm of LTcodes with a small fraction of dense rows [C]// IEEE Interna?tional Symposium on Information Theory. [S.l.]：IEEE，2007：2006?2010.

[5] 刘国超，陈霄，苏伟伟，等.短长度分布式喷泉码的性能分析[J].通信技术，2012，45（8）：5?8.

[6] MACKAY D J C. Fountain codes [J].IEEE Proc ? Commun，2005，152（6）：1062?1068.

[7] KARP R，LUBY M，SHOKROLLAHI A. Finite length analysisof LT codes [C]// IEEE International Symposium on InformationTheory. [S.l.]：IEEE，2004：39?48.

[8] SHOKROLLAHI A. Raptor codes [J]. IEEE Transactions on In?formation Theory，2006，52（6）：2551?2567.

[9] Anon. On the optimization of degree distributions in LT codewith covariance matrix adaptation evolution strategy [C]// Pro?ceedings of the IEEE Congress on Evolutionary Computation. [S.l.]：IEEE，2010：1?8.

[10] BYERS J W，LUBY M，MITZENMACHER M，et al. A digi?tal fountain approach to reliable distribution of bulk data [C]//Proceedings of ACM SIGCOMM’98. Vancouver： ACM，1998：56?67.

作者简介：贾惠宁（1987—），女，山西忻州人，助理工程师。研究方向为无线电工艺。