LT码的增强型BP译码算法

杨晓非，季瑞军，黄　胜，张春明

(重庆邮电大学 光通信与网络重点实验室，重庆 400065)

LT码的增强型BP译码算法

杨晓非，季瑞军，黄胜，张春明

(重庆邮电大学 光通信与网络重点实验室，重庆 400065)

摘要:传统的LT码采用的BP译码算法，当不存在度1编码分组时会导致BP译码算法失败，不能继续译码。为了提高译码的成功率，分析了剩余编码分组的结构，提出LT码的再次译码算法(Again Belief Propagation decoding algorithm，ABP)。算法主要思想是BP译码失败后，查找满足条件的可译结构，继续译码，直到译码成功或再次失败，如果失败重复上面步骤直到译码成功或可译结构不存在，从理论上分析了可译结构存在的概率。仿真结果显示译码成功率得到提高。

关键词:LT码；BP译码；译码效率；增强型译码算法

数字喷泉码在1998年被提出[1]。LT码是由M.Luby等人针对删除信道设计出的第一个实用的数字喷泉码[2]，之后数学家Shokrollahi针对LT码的缺点改进后提出了性能更好的Raptar码[3]，数字喷泉码在广播通信[4]，针对数据拥有不同优先等级的视频传输[5]，复杂信道环境的深空通信[6]，当前热门的数据安全存储[7]等领域具有广泛的应用前景。LT码译码算法采用BP(置信传播)译码算法，然而，译码很可能因为查找不到度1的编码分组而导致失败，影响了数据传输质量。由于传输质量的要求，通常需要接收多于原始信息分组数量的编码分组才能成功恢复原始信息分组，把多接收的编码分组与信息分组的长度之比称为译码开销。

文献[8]就如何提高LT码等无码率编码算法的译码效率问题进行了讨论，从减少开销得到的复杂度出发，文章中提出了一种提前结束译码的算法。文献[9]对BEC上的Raptor码译码方案进行了讨论，提出一种可以在不损失性能的情况下有效地减小译码时间的方案即增量高斯消去的译码方案，相对于高斯消除算法，该算法在译码矩阵中增加一些行，这可以保证矩阵的三角化成功。文献[10]对无码率码的生成方式进行了改进，讨论了无码率码在迭代译码时的一些独有特性。笔者分别在相等、不等差错保护和有限长码字情况下，分析了LT码和Raptor码在进行最大似然译码算法译码时的错误码元概率的上下界，进行LT解码时，接收端可以根据接收到的编码分组的个数来译出原始信息的不同部分。

深入分析译码的整个过程可以知道，译码过程可以转换为解一次多元方程组的过程，译码即是求解变量元素，这里的变量元素就是信息分组，只要方程组系数矩阵(译码矩阵)满秩，方程组有解，理论上译码是可以完成的。由于BP译码算法只是查找度数为1的编码分组，BP译码算法失败时并不意味着系数矩阵不满秩，即剩余的编码分组仍然具有可译性。对于这种方程组可解但BP译码由于检测不到度1编码分组而失败的情况，本文提出一种更加完善的BP译码算法，经过仿真验证可以看出确实改善了译码的效果，译码成功率得到了提高。

1LT码编译码原理

LT码：其编码是由K个符号分组生成任意数量的编码分组，接收端只需要接收到任意个编码分组，即可以以一定概率成功解码全部信息分组。这里，N略大于K，这样会带来一定的译码开销。

1.1编码过程

LT码的编码过程如下[2]：

1)根据度分布函数ρ(d)随机选取整数d作为编码分组的度数。这里1

2)从K个信息分组等概随机选取d个并异或得到编码分组。

重复上面的步骤，直到接收端接收到N个编码分组为止。编码过程如图1所示。

图1　编码分组的生成示例

1.2译码过程

根据LT码的定义，接收端接收到个编码分组即可以开始译码，具体过程如下[2]：

1)根据接收到的编码分组和信息分组的对应关系建立二分图。

2)遍历所有的编码分组，如果存在度1的编码分组，则可以译出与之相连的信息分组，若不存在，则译码结束。

3)将已经译出的信息分组的值异或到与之相连的编码分组中，去掉二分图中与这个信息分组相连的边。

4)重复步骤2)和3)直到译码停止。若所有的信息分组全部译出则成功译码，否则译码失败。

1.3LT码的度分布

M.Luby等人提出来两种编码分组的度分布，首先是ISD(IdealSolitonDistribution)函数[2]表示为

(1)

在理想情况下，该度分布每次译码迭代后恰好有一个度1的编码包留下，但是实际情况却是度1的编码包太少，很有可能在某次迭代后消失，尤其是短码长的数据很容易在译码前期就迭代失败。

RSD[2]如式(2)～(3)所示

(2)

(3)

在传统LT码译码迭代会因为没有度1的编码分组导致译码失败。实际上剩下的编码分组是存在可译性的。本文针对BP译码算法的这种漏洞，提出了增强型的BP译码算法，在BP译码失败之后查找二分图中的特殊结构，根据特殊结构译出其中的一个信息分组，这使BP译码算法可以继续执行。

2增强型BP译码算法

图2是ABP可译结构示意图，编码分组tm的度为i-1，编码分组tn的度为i，其中3

ABP可译结构查找算法：遍历剩余生成矩阵G的任意两列，异或遍历迭代中被选中的两列(对应位置元素异或)，当结果中只有一个元素为1，其余元素为0时，即查找到图2所示结构。

图2　结构图示

图中编码分组tm的度为i-1，编码分组tn的度为i，3

图3示出了ABP可译结构查找算法示例。图3a为BP译码算法失败后的译码矩阵G，遍历矩阵G中的任意两列，只有图3a椭圆阴影圈住的两列符合ABP可译结构，对矩阵中的这两列进行异或，得到结果如图3b所示，然后用该结果去替换ABP可译结构中度数大的那一列，并且用两个编码分组异或的值去替换度数较大的编码分组，如图3c所示。

图3　ABP可译结构查找算法示例

本算法可以扩展为对3个或3个以上的不同剩余的编码分组进行的操作，异或3个不同剩余的编码分组，观察是否可以产生度为1的编码分组。但因为有3个编码分组组成的这种结构的概率低译码查找复杂度大，这里不做理论分析和实验验证。

2.1ABP译码算法具体操作步骤

步骤1：在信息分组未完全恢复的情况下，编码分组tn中没有度1的分组则译码迭代停止，转到步骤4。

步骤2：令信息分组sK=tn，更新与tn相连的编码分组，更新的结果为当前编码包与tn异或的结果，最后删掉tn。

步骤3：若信息分组全部恢复则译码成功，否则重复步骤1。

步骤4：查找满足ABP的可译结构。即遍历剩余生成矩阵G的任意两列，异或遍历迭代中被选中的两列(对应位置元素异或)，当结果中只有一个元素为1，其余元素为0时，即找到ABP可译结构，则根据sj=tm⊕tn恢复出结构中的信息分组sj，更新二分图，重复步骤1；查找不到则译码失败。

图4是算法流程图。

图4　算法流程图

当检测到BP译码算法失败时，会进入可译结构的检测，更新二分图也就是生成矩阵，继续跳回BP译码。本算法不但提高译码的成功率，而且也减译码开销。

2.2ABP结构存在的概率

这种结构存在的概率可以看作成从箱子中取小球的问题，每个小球取出的概率是相等的。这里装有N-L小球的箱子，tn可以看成从中取i个小球，取出后放回，tm可以看成从中取出i-1个小球。

对于任意两个编码分组符合这种结构的概率为

(4)

对于未处理的编码分组共有c(N-L,2)个两两组合，于是，未处理编码分组中存在度为i和度为i-1的比编码符号符合这种结构的总数

(5)

对于不同的度M的取值为

…

(6)

符合度3的编码分组包含度2的编码分组的这种ABP可译结构的个数最多，不受未处理编码分组数的影响。其他度数的这种结构的个数随着未处理编码分组数的减少而增加。由此可知，未处理的编码分组会以一定的概率符合这种条件。

3仿真分析

仿真与传统的BP译码算法作为对比。选择理想孤子分布作为编码的度分布，这里主要考察两个性能指标，一个是译码成功率，当所有的信息符号全部正确译出时代表译码成功；另一个性能指标是成功译出分组比例，及每次译码结束时，成功译出信息分组占总的信息分组的比例。对信息分组数为1 000和2 000进行1 000次实验。

图5是译码成功率的仿真图，横坐标为译码开销。仿真用的BEC信道，其删除概率为0.02。由图可以看出，使用改进算法的译码成功率大幅度增加，并且随着译码开销的增加，改进算法提升的幅度增大。由传统的LT的编码特性可知，随着信息分组数的增加，编码的度分布函数更加接近于理想孤波分布，所以信息分组数越大，译码性能越好。如图中虚线所示，信息分组数为2 000的LT码译码成功率要大于信息分组数为1 000的LT码。由图中实线可以看出，改进算法译码额有这样的趋势，即信息分组数为2 000的LT码译码成功率要大于信息分组数为1 000的LT码。

图5　译码成功率仿真图

图6是成功译出分组比例随译码开销变化的仿真图。信道模型为二进制删除信道，删除概率为0.02。可以看出，成功译出分组比例与译码成功率有相同的趋势，改进算法成功译出分组比例要高于传统的BP译码算法。信息分组数为2 000的LT码成功率译出分组比例同样大于信息分组数为1 000的LT码。

图6　成功译出分组比例仿真图

图7是译码成功率随译码负载变化的仿真图。信道模型为二进制删除信道，删除概率为0.05。由图可以看出，在相同的译码开销下LT码的再次译码算法的性能优于BP译码算法的性能。

图7　译码成功率仿真图

图8是成功译出分组比例随译码负载变化的仿真图。信道模型为二进制删除信道，删除概率为0.05。由图可以看出，在相同的译码开销下LT码的再次译码算法的性能优于BP译码算法的性能。

图8　成功译出分组比例仿真图

4小结

本文针对BP译码失败时其余编码分组仍然具有可译性的特点，通过查找编码分组是否满足ABP可译结构，提出LT码的再次译码算法。通过对文中提出的结构进行处理后的到可以满足BP译码算法特点的生成矩阵，重新进入译码迭代。仿真结果表明，该算法确实改善了原来BP译码的缺点，可以看出译码的成功率也得到了提高。本文提出的算法不仅可以用在LT码中，同样也可用于其他采用BP译码算法解码的编码方法。

参考文献：

[1]BYER J W，LUBY M，MITZERMACHER M，et al. A digital fountain approach to reliable distribution of bulk data[C]//Proc.ACM Sigcomm’ 98 Conference.[S.l.]：IEEE Press，1998.

[2]LUBY M. LT codes[C] //Proc.43rd Annual IEEE Symposium on Foundations of Computer Science. USA：IEEE Press，2002：271-280.

[3]SHOKROLLAHI A. Raptor codes[J]. IEEE Transactions on information theory，2006， 52(6)：2551-2567.

[4]邓善征，杜兴民，杨军，等.LT 码在移动多媒体广播系统中的应用[J].电视技术，2007，31(3)：37-39.

[5]YU J， ZHONG J， ZHAO M， et al. Novel LT coding scheme with limited feedback in broadcast systems[C]//Proc.2012 International Conference on.Wireless Communications & Signal Processing (WCSP). [S.l.]：IEEE Press，2012： 1-5.

[6]ZHANG Q， ZHANG S， ZHOU W. Enhanced LT decoding scheme in satellite communication [C]//Proc.2014 Sixth International Conference on Wireless Communications and Signal Processing (WCSP). [S.l.]：IEEE Press，2014：1-6.

[7]BALDI M， MATURO N， MONTALI E， et al. AONT-LT： a data protection scheme for cloud and cooperative storage systems [C]//Proc. International Conference on High Performance Computing & Simulation. [S.l.]：IEEE Press，2014：566-571.

[8]HARRISON C， JAMIESON K. Power-aware rateless codes in mobile wireless communication[C]//Proc.the 11th ACM Workshop on Hot Topics in Networks. [S.l.]：ACM Press，2012：25-30.

[9]KIM S， KO K， CHUNG S Y. Incremental Gaussian elimination decoding of raptor codes over BEC[J]. IEEE communications letters，2008，12(4)：307-309.

[10]RAHNAVARD N， VELLAMBI B N， FEKRI F. Rateless codes with unequal error protection property[J]. IEEE transactions on information theory，2007，53(4)：1521-1532.

[11]KOKAL J，FILIPOVIC S， SPASOJEVIC P， et al. Doped fountain coding for minimum delay data collection in circular networks[J]. IEEE journal on selected areas in communications，2009，27(5)：673-684.

杨晓非，博士，副教授，从事电路、信号与系统专业相关的教学和科研工作；

季瑞军，硕士生，主要研究方向为数字喷泉码在未来网中的应用；

黄胜，博士，教授，主要研究方向为光互联网，未来网；

张春明，硕士生，主要研究方向为纠删码及纠删码在未来网中的应用。

责任编辑：闫雯雯

EnhancedLTcodesBPdecodingalgorithm

YANGXiaofei，JIRuijun，HUANGSheng，ZHANGChunming

(Key Laboratory of Optical Fiber Communication and Network Technology ， Chongqing University of Posts and Telecommunications， Chongqing 400065， China)

Abstract:BP decoding algorithm used by general LT code， when degree-1 encoding packet can not be found， BP decoding algorithm failure， however， the original BP algorithm can’t keep decoding. In order to improve the success rate of decoding， the structure of the remaining coded packet is analyzed， this thesis presents a again belief propagation decoding algorithm. When BP decoding fails， the proposed search algorithm can be used to find ABP translatable structure according to the proposed algorithm， maintaining decoding until the decryption succeeds or fails. If decoding fails ， repeat the above steps until the decryption succeeds or translatable structure can’t be found. Through simulation， the decoding success rate has been greatly improved.

Key words:LT codes；BP decoding；decoding efficiency；enhanced BP decoding algorithm

中图分类号:TN911.22

文献标志码：A

DOI：10.16280/j.videoe.2016.03.020

基金项目：国家自然科学基金项目(61371096；61171158)；重庆市自然科学基金项目(cstc2013jcyjA40052);重庆市教委科学技术研究项目(KJ130515)

作者简介：

收稿日期：2015-07-21

文献引用格式：杨晓非，季瑞军，黄胜，等.LT码的增强型BP译码算法[J]. 电视技术，2016，40(3)：93-97.YANGXF，JIRJ，HUANGS，etal.EnhancedLTcodesBPdecodingalgorithm[J].Videoengineering， 2016，40(3)：93-97.