LT码编译码分析及改进.doc

LT码编译码分析及改进 贾惠宁 （北京新立机械有限责任公司，北京100039） 摘要：数字喷泉码是一类不受限的纠错码，即从原始数据分组编码产生的编码分组序列是无限的。通过研究数字喷泉码中译码终止的原因，得出在数字喷泉码中，译码终止是由于缺少度数为1的编码包，导致译码提前终止以至译码失败。注意到度数为2的编码包在整个编码包中占有很高的比例；因此，将数据包分成两组，在度数为2时，分别从两组中取出数据，这样可以有效地提高数据的覆盖率，降低译码提前终止的概率。通过对编码算法的改进，提高整个数字喷泉码的译码成功率。 关键词：数字喷泉码；译码终止；度数；改进算法 ：TN911?34：A：1004?373X（xx）14?0020?04 ：xx?12?25数字喷泉码与传统的信道编码相比，具有“无固定速率”这一特性。这使得数字喷泉码可以应用到许多复杂的信道当中，这一特性是由数字喷泉码的编码和译码方式直接决定的，因此有必要得到性能更加优良的数字喷泉码的编译码方案，使得它在实际应用中可以更加方便，运算复杂度更低。LT码和Raptor码是数字喷泉码中最典型的两种方案，而Raptor码是在LT码编码之前进行了一个预编码，因此LT码成为了现在最基础也是研究最为广泛的编码方案。本文将对LT码的编译码方案进行系统的分析，并在此基础上对其编码算法进行改进，使其性能更加的优良，最后通过仿真验证结论。 1LT码编译码方案分析 1.1LT码编码方案分析 LT码的生成矩阵与其编码的二分图是一一对应的，节点的度对应到二分图中表示与对应节点相关联的边的个数。因此，LT码的度分布函数决定了其编码的结构，合理的度数分布函数是LT码编码方案的关键。当使用固定的BP译码算法时，LT码编码的性能几乎完全由度数分布函数决定；因此希望LT码的度数分布函数尽量满足以下条件： （1）尽可能用最少的接收到的编码包译出原始的数据包，即译码开销尽量小。 （2）在编码时使所选取的平均度数尽量小，这样可以减少模运算，使得编译码代价尽可能的小。 LT码的度数分布函数应该保证所有的数据包都至少被选取1次，形成所需要的编码包，即编码过程应该覆盖到所有的数据包，使得在译码的过程中不会丢掉某一个数据包导致译码失败。从编码的角度考虑，要使平均度数尽可能小，这样可以保证运算量小，但是同样为了保证编码包可以覆盖到每一个数据包，就必须有少量的大数值度数存在。如当数据包的长度k=100时，除了要选取大量的小数值的度数，如1或2，同时也要选取极少量的大数值的度数如99或100。从译码的角度考虑，一方面要保持编码包的释放速率以得到对应的数据包，但是同时，释放的速率不可以太快，如果太快就将导致有大量的数据包被重复的释放，这样带来不必要的冗余。 1.2LT码译码方案分析 对于具有良好的度数分布函数的LT码编码算法，BP译码算法往往可以达到较为理想的译码复杂度。 LT码的BP译码算法，首先译出与所有度数为1的编码包相连的数据包，然后再处理与这些数据包相关联的其他编码包，称这些编码包为预处理集；然后再处理预处理集，将预处理集中的元素与相连的编码包中的元素进行模运算，并且去除度数为1的编码包与数据包的相关联性，经过这个处理，原来度数为1的编码包将不存在，而原来度数不为1的编码包现在度数将变为1；最后再对上述过程进行反复，即可以得出译码结果；如果最终有1个数据包未被译码出来，称之为译码失败，反之译码成功。 由上述分析可知，BP译码算法的关键是在查找度数为1的编码包，只有不断地有度数为1的编码包存在，译码过程才可以不断地进行下去，而如果在未完成译码时，一旦度数为1的编码包为0，译码将提前终止，这是不希望看到的。而度数为1的编码包的数量直接由LT码的度数分布函数决定，因此就要对LT码的度数分布函数进行专门的分析，以了解度数为1的编码包的具体分布和变化情况。 1.3LT码度数分布函数分析 由于度数分布函数是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)=1k，证实了刚才的结论。理想度数分布函数在译码过程中度数为1的编码包个数始终保持不变，始终维持在有且仅有一个度数为1的编码包。 在实际应用中，并不可以按照理想的度数分布函数来设计数字喷泉码，因为这样会造成在实际译码过程中，第一步不能够快速完成，导致后面的很难找到度数为1的编码包，使得译码终止。所以理想度数分布函数是一种可行性很差的度数分布函数，仅在理论研究上存在，也仅具有理论意义。 因此，在具体实践过程中，又提出了鲁棒度数函数分布（RobustSolitonDistribution），在此对它的性能和实用性进行分析。 在鲁棒度数函数分布中提出了中间变量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=2000，即初始的数据包个数为2000。图1为改进前的算法和改进后的算法对应的仿真示意图。其中c=0.2,=0.01。 通过上述仿真结果可看出，在接收包为2400以下时，两种算法的性能差不多，这是因为在接收包较少的情况下，度数为2的编码包的个数本身就很少，这就直接导致改进后的算法在性能上并不一定能优于改进前的性能，但是随着接收包的增多，度数为2的编码包的个数极具的增多，这就使得改进后的算法的优越性就体现出来了，因此，越往后面走，改进后的算法的性能就越好。同时再次考虑到数据包分成两组的过程中，如果不按照等分的方法进行分配的情况再进行一次仿真，这次选取度数为2的数据包的分组是不等分的情况，结果如图2所示。 从图中可看到未等分的性能差一些，因为当两组数据的个数不相等的情况下，两者数据的数量相差越大，则越近似于原有的编码方案，相当于算法又回到了过去。 4结语 本文详细的对LT码的编码，译码和度数分布函数进行了剖析，得知在译码的过程中离不开度数为1的编码包，而它又是动态存在的，因此需要将度数为1的编码包的个数始终保持在很高的程度，这样在译码的过程中，就不会因为缺少度数为1的编码包而导致译码终止，最终导致译码失败。因此考虑到在编码的过程中，对度数为2的编码包的编码过程进行特殊的处理，将所有的数据包，分成2组（最好等分），从每一组中随机选取1个数据包进行模运算，这样可以大大提高数据包的发概率，也大大降低了在译码过程中缺少度数为1的数据包的可能性，使译码的成功率提高。 参考文献 1王新梅，肖国镇.纠错码原理与方法M.西安：西安电子科技大学出版社，1991. 2LUBYM.LTcodesC/Proceedingsofthe43rd.AnnualIEEESymposiumFoundationsofComputerScience（FOCS）.Vancou?ver，Canada：IEEE，xx：271?280. 3朱宏鹏，张更新，谢智东.喷泉码中LT码的次优度分布J.应用科学学报，xx，27（1）：6?11. 4LEEKRH.Amaximum?likelihooddecodingalgorithmofLTcodeswithasmallfractionofdenserowsC/IEEEInterna?tionalSymposiumonInformationTheory.S.l.：IEEE，xx：xx?xx. 5刘国超，陈霄，苏伟伟，等.短长度分布式喷泉码的性能分析J.通信技术，xx，45（8）：5?8. 6MACKAYDJC.FountaincodesJ.IEEEProc?Commun，xx，152（6）：1062?1068. 7KARPR，LUBYM，SHOKROLLAHIA.FinitelengthanalysisofLTcodesC/IEEEInternationalSymposiumonInformationTheory.S.l.：IEEE，xx：39?48. 8SHOKROLLAHIA.RaptorcodesJ.IEEETransactionsonIn?formationTheory，xx，52（6）：2551?2567. 9Anon.OntheoptimizationofdegreedistributionsinLTcodewithcovariancematrixadapta