LT码编译码分析及改进

LT码编译码分析及改进

作者：贾惠宁

来源：《现代电子技术》2015年第14期

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

关键词： 数字喷泉码； 译码终止； 度数； 改进算法

中图分类号： TN911⁃34 文献标识码： A 文章编号： 1004⁃373X（2015）14⁃0020⁃04 Analysis and improvement for coding⁃decoding of LT code JIA Huining

（Beijing Xinli Machinery Co.， Ltd， Beijing 100039， China）

Abstract： Digital fountain code is a class of rateless erasure code. The number of encoded symbols that is generated from the original data is potentially limitless. By the relative study， the reason of decoding termination of digital fountain code was found， which caused by the lack of degree⁃1 encode packages， and may lead to decode terminate ahead of time and decoding failure. Because of this， it is found that the degree⁃2 encode packages occupies a high proportion in the whole encode packages. Therefore， the data package is divided into two groups. When the degree is 2， the data is taken out respectively from the two groups. In this way， the coverage of data can be improved effectively， and the probability of decoding termination in advance can be reduced. With the improvement of coding algorithm， the decoding success rate of digital fountain code was improved.

Keywords： digital fountain code； decoding end； degree； improved algorithm

数字喷泉码与传统的信道编码相比，具有“无固定速率”这一特性。这使得数字喷泉码可以应用到许多复杂的信道当中，这一特性是由数字喷泉码的编码和译码方式直接决定的，因此有必要得到性能更加优良的数字喷泉码的编译码方案，使得它在实际应用中可以更加方便，运算复杂度更低。LT码和Raptor码是数字喷泉码中最典型的两种方案，而Raptor码是在LT码编码之前进行了一个预编码，因此LT码成为了现在最基础也是研究最为广泛的编码方案。本文

龙源期刊网 http://www.qikan.com.cn

将对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码的

龙源期刊网 http://www.qikan.com.cn

度数分布函数决定，因此就要对LT码的度数分布函数进行专门的分析，以了解度数为1的编码包的具体分布和变化情况。 1.3 LT码度数分布函数分析

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

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

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

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

现在，假设某一个编码包的度数为[i]，此时未被处理的输入符号个数为[L]，那么[qi，L]表示度数为[i]的编码包，在还有[L]个数据包未被处理时被释放的概率，则： [q1，k=1] （3）

[q2，L=2Lkk-1， L=1，2，…，k-1] （4）

[qi，L=ii-1j=0i-3k-L+1-jj=0i-1k-j， i=3，4，…，k；L=1，2，…，k-i+1] （5） [qi，L=0， i和L为其他] （6）

由上面式子可得，由于[ri，L]表示还剩下[L]个原始数据包未被处理时度数为[i]的编码包中被选中并被释放的概率，因此[ri，L=piqi，L]，[ rL]表示还有[L]个原始数据包未被处理时一个编码包被释放的概率，因此： [rL=ri，L] （7）

龙源期刊网 http://www.qikan.com.cn

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

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

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

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

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

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

龙源期刊网 http://www.qikan.com.cn

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

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

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

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

（1） 将原始的数据按照等长[l]分成[k]个数据包（不足的通过补0完成）； （2） 将原始数据包分成2组，每组的数据包个数相等；

（3） 根据已经设计好的度数分布函数[ρ]，随机地选取度数[d]，作为数据包的编码度数； （4） 判定[d]是否等于2，如果等于2则从已经分好的两组当中分别选取一个数据包，如果不等于2，则在[k]个数据包中等概率地选[d]个数据包； （5） 将选出的[d]个数据包进行异或运算，生成一个编码包； （6） 重复上述步骤，直至接收端接收到足够多的编码包。

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

龙源期刊网 http://www.qikan.com.cn

3 仿真及其分析

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

图1 使用鲁棒分布改进前后的性能对比

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

图2 度数为2的数据包分组不同的情况下性能对比

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

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

[1] 王新梅，肖国镇.纠错码原理与方法[M].西安：西安电子科技大学出版社，1991. [2] LUBY M. LT codes [C]// Proceedings of the 43rd.Annual IEEE Symposium Foundations of Computer Science （FOCS）. Vancouver， Canada： IEEE， 2002： 271⁃280.

龙源期刊网 http://www.qikan.com.cn

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

[4] LEE K R H. A maximum⁃likelihood decoding algorithm of LT codes with a small fraction of dense rows [C]// IEEE International 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 analysis of LT codes [C]// IEEE International Symposium on Information Theory. [S.l.]： IEEE， 2004： 39⁃48.

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

[9] Anon. On the optimization of degree distributions in LT code with covariance matrix

adaptation evolution strategy [C]// Proceedings of the IEEE Congress on Evolutionary Computation. [S.l.]： IEEE， 2010： 1⁃8.

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

龙源期刊网 http://www.qikan.com.cn