喷泉码中半随机生成法去短小环

刘立军，谢红，解武

哈尔滨工程大学信息与通信工程学院，黑龙江哈尔滨 150001

喷泉码中半随机生成法去短小环

刘立军，谢红，解武

哈尔滨工程大学信息与通信工程学院，黑龙江哈尔滨 150001

分析了喷泉码中LT码的生成原理及影响译码性能的因素，生成矩阵中的短小环是影响编译码性能的主要因素，其中，长度为4的短小环对编译码的性能影响最大。提出了一种半随机生成法去除长度为4的短小环的方法。仿真结果表明：去除长度为4的短小环之后，明显改善了喷泉码的性能，降低了译码复杂度，提高了系统性能。

喷泉码；LT码；串行置信传播算法；短小环；半随机生成法

1998年，M.Luby等人首次提出喷泉码的概念，其主要是针对二进制删除信道而提出来的一种线性纠错码［1］。喷泉码名字的由来是因为喷泉码的编码器能够像喷泉向外面喷射出水滴一样，能够根据源信息产生无数个喷泉码的编码包。假设源文件的大小是K bits，喷泉码的编码器每次产生的编码码字大小是l bit，接收端就不断地接收信源端发送过来的码字，当接收端接收的码字数目稍微大于K bits时，接收端就能够准确的译码［2］。

喷泉码最大的特性就是与它的码率无关性。由于喷泉码的特性能够让任何一个删除信道的性能都接近最佳，所以喷泉码的用途十分广泛。在删除信道中，不论有多少编码码字被信道删除，发送端都能够发送足够多的码字，来让接收端译码。接收端一旦能够接收到N个码字（N比K稍大），就可以准确地恢复源文件［3-4］。

影响喷泉码性能之一的因素就是生成矩阵的结构，生成矩阵中的短小环的影响最大。所以，本文提出一种半随机生成法去除短小环的方法。

1 LT码与串行BP译码

1.1 LT码编码

LT码是喷泉码的一种，而且是第一种可以通过编码设计能够实现的喷泉码。LT码的编码原理是通过构造喷泉码生成矩阵，根据这个生成矩阵来实现喷泉码的编码。

假定想要发送的源文件信息为s1，s2，…，sk，k是信息的长度，并假定度分布为Ω1，Ω2，…，Ωk那么可以按照下式生成编码码字：

式中Ωd表示校验节点是由d个源信息节点通过运算而得到的概率。

下面分步讨论LT码编码原理具体的实现步骤：

1）根据上面介绍的度分布Ω1，Ω2，…，Ωk，随机的选取一个度值d（d∈［1，k］）。

2）根据步骤1）得到的度值d，等概率的方式随机生成一个列向量v，v＝（v1，v2，…，vk），这个向量中“1”的个数为d，其中vi∈｛0，1｝，i＝1，2，…，k。

3）然后再根据式（1）的方式生成一个相应的编码符号cj，式（1）中的求和是二进制的加法。

4）不断重复步骤1）～3），N次之后，就能够得到生成矩阵的一个编码之后的序列（c1，c2，…，cN），而生成矩阵G就是把对应的列向量v1，v2，…，vN按照固定的顺序排列就可以得到。

LT码同样是基于对稀疏矩阵构造的一种线性的纠错码，满足二分图论的表示方法要求，所以LT码同样能够用二分图论的方式来表示。图1是一个喷泉码编码过程的具体表示方式，其中信息的长度是4，编码的长度是5，图1（a）是生成矩阵的表示形式，图1（b）是与图1（a）对应的Tanner图的表示方式。Tanner图中的符号节点s1，s2，…，sk是相应的源信息节点，c1，c2，…，cn是根据源信息节点生成的校验节点。

图1 生成矩阵与Tanner图

度分布在一定程度上决定了喷泉码的性能，所以本文中采用Shokrollahi在文献［10］中所提出的度分布，这个度分布的表示如下所示：

1.2 串行BP译码算法

信道状态为高斯白噪声时，喷泉码的译码通常采用的是标准BP译码算法。这个算法在每一轮的迭代过程中，都是并行对所有符号节点和校验节点进行相应的更新，具体的迭代过程如图2（a）所示。2001年，E.Yeo等人提出了串行BP译码算法（SBP）被用作LDPC码的译码算法。这个算法是在每一轮的迭代过程中，对不同类型的节点信息分步骤进行更新。具体的更新过程如图2（b）所示。根据选择的节点类型的差异，SBP算法同时又可以分为2种不同的算法。

图2 2种译码算法的更新过程

下面讨论串行BP译码算法的具体实现步骤：

1）首先，分别对下面2个数据进行初始化处理：

a）根据式（2）计算，可以得到接收到的信息初始化值。

式中：yj为接收端接收到的编码符号序列的一个编码符号，σ2为高斯信道中噪声的方差。

b）把所有的符号节点传递给与每个符号节点相连的校验节点的信息初始化为

2）在每一轮的迭代过程中，按照编码的顺序对每一个符号节点si迭代更新相应的接收信息，按照下面的过程来更新每一个节点：

a）首先，计算与这个符号节点连接的每个校验节点cj传递给符号节点si的信息L（l）（rji），按照式（3）进行更新。

式中：P（j）为所有跟校验节点cj连接的符号节点的集合，而i′∈P（j）＼i表示P（j）中除si之外所有的符号节点。

b）计算节点si传递给节点cj的信息L（l）（qji），按照式（4）所示的方式进行计算。

式中：M（i）代表的是所有与符号节点si相连接的校验节点的集合，而j′∈M（i）＼j表示M（i）中除cj之外的所有校验节点。

3）当译码迭代过程都结束时，根据式（5）计算所有的符号节点迭代译码后的信息大小，然后再根据式（6）对所有的符号节点进行判定，并得到最终的译码结果，译码结束。

2 喷泉码中短小环的影响与去小环算法

2.1 短小环的危害

生成矩阵的结构对喷泉码的性能影响非常大，特别是生成矩阵中的短小环，是主要的影响因素之一。例如，在图2（b）中，符号c3-s3-c4-s2-c3相互连接之后就构成了一个长度为4的短小环。短小环对喷泉码的性能影响主要体现在2个方面。编码时，总是希望编码后的码字能够包含尽可能多的原始信息，从而使编码后的码字能够包含所有的原始信息，而小环的存在，使编码后的码字里面包含了更多的重复信息，影响编码后的码字信息量。译码时，由于短小环的存在，节点之间传递信息时相互独立的性质遭到破坏。一个节点传递出去的信息，通过组成小环节点之间的相互传递，又把这个信息传递到自己本身，导致信息的迭代更新速度降低，译码的复杂度提高。由于这2方面的影响，找到一种去除喷泉码的短小环的方法就显得尤为重要。

2.2 半随机生成法去小环

由于低密度奇偶校验码LDPC的研究比较早，LDPC码的去小环方法的研究也相当成熟，在规则的LDPC码的检验矩阵去小环的研究中，已经研究出了很多方法，例如列分裂方法、根据校验矩阵检测环的方法等，但这些方法都不适用于LT码。这些方法都是通过调整生成矩阵的方式来实现的，都在一定程度上影响了生成矩阵度的分布，而且这些方法实现起来也比较困难。本文提出一种可以方便去除长度为4的短小环的方法，即半随机生成法。该方法的步骤为：

1）生成一个K－1行K－1列的全零矩阵（K为符号节点个数），按照图3的方式给矩阵赋值；

2）编码第i个校验节点，按照度分布随机选取一个d的值作为这个校验节点的度；

3）如果d＝2，随机生成一个数N（N＜K－1）；

4）在图3矩阵中对应的列c，随机生成一个数r（c＜r＜K－1）；

5）如果矩阵的第c列中的第r个数是零，则重复步骤4），否则把这个数变成零；

6）把第c个符号节点和第r个符号节点作为第i个校验节点的编码符号；

7）重复步骤2）～6），完成编码。

图3 去环矩阵

3 仿真分析

图4、5分别是标准BP译码去小环和串行BP译码去小环前后的性能仿真对比图。假定信道为高斯白噪声信道，设置相应的仿真条件如下：噪声的平均能量设定为1，噪声的方差设定为2；源信息的长度是1 000，调制方式采用BPSK调制，译码时设定迭代次数为10，图中的每个点是100帧数据仿真计算出来的平均值。

图4 标准BP译码算法去小环前后的性能对比

图5 串行BP译码算法去小环前后的性能对比

从图4、5仿真结果可以看到：在译码开销较小的时候，2种算法的误码率性能都不是很好。这是因为译码端需要接收到更多的码字才能够正确进行译码。随着译码开销的不断增大，每一种算法在译码开销相同的情况下，去环之后译码算法的误码率明显低于去环之前。去除短小环之后，误码率降低，提高了码的性能。这是由于去除小环之后喷泉码编码包含的原始信息更多，译码时迭代更新速度更快，所以性能比去除小环之前提高了。

4 结束语

本文首先分析了LT码的编码原理和LT码的串行BP译码算法，之后主要分析了影响LT码性能的主要因素，得出短小环是影响LT码的性能的重要因素，基于此，提出一种半随机生成法去除LT码短小环的方法，并且详细阐述了这个方法的实现过程。通过仿真对比得出去除LT码的短小环之后，应用标准BP译码算法和串行BP译码算法时，LT码的性能都能够得到提高。由于本文提出的方法是去除长度为4的小环，进一步的工作可以针对去除长度更大的小环展开相关研究。

［1］LUBY M.LT codes［C］//Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science.To-ronto，Canada，2002：271-282.

［2］MACKAY D JC.Good error correcting codes based on very sparsematrices［J］.IEEE Transactions on Information Theo-ry，1999，45（2）：399-431.

［3］ZHANG Kai，HUANG Xinming，SHEN Chen.Soft decoder architecture of LT codes［J］.IEEE Signal Processing Sys-tems，2008，41（7）：210-215.

［4］ABOUEI J，BROWN J D.On the energy efficiency of LT codes in proactive wireless sensor networks［J］.IEEE Trans-actions on Signal Processing，2011，59（3）：1116-1127.

［5］ABDULHUSSEIN A，OKA A，LAMPE L.Decoding with early termination for raptor codes［J］.IEEE communication letters，2008，12（6）：444-446.

［6］ABDULHUSSEIN A，OKA A，LAMPE L.Decoding with early termination for rateless codes［C］//IEEE WCNC.New Orleans，USA，2008：249-254.

［7］PETERSONW，BROWN D T.Cyclic codes for error detec-tion［J］.Proceedings of the IRE.2008，37（8）：228-235.

［8］BRINK T S.Convergence of iterative decoding［J］.IEEE E-lectron.Letter，1999，35（10）：806-808.

［9］PAKZAD P，SHOKROLLAHIA.Exit function for LT and raptor codes，and asymptotic ranks of random matrices［C］//IEEE International Symposium on Information Theo-ry.Nice，France，2007：411-415.

［10］SHOKROLLAHIA.Raptor codes［J］.IEEE Trans Inf The-ory，2006，52（6）：2551-2567.

［11］BRINK T S.Convergence behavior of iteratively decoded parallel concatenated codes［J］.IEEE Trans Comin，2001，49（10）：1727-1737.

［12］ASHIKHMIN A，KRAMER G，BRINK T S.Extrinsic in-formation transfer functions：a model and two properties［C］//Conf Information Sciences and Systems.Princeton，USA，2002：742-747.

A sem i-random generation method for removing the short ring of a fountain code

LIU Lijun，XIE Hong，XIEWu
College of Information and Communication Engineering，Harbin Engineering University，Harbin 150001，China

The generation principle and factors affecting decoding performance of LT codes in a fountain code were analyzed，and itwas found the short ring of the generatormatrix is a major factor affecting the performance of the encoding and decoding，among which a short ring whose length is 4 has the biggest impact on encoding and deco-ding performance.This article presents a semi-random generation method for removing the short ringwith a length of 4.Simulation results show that the removal of the short ringwith a length of 4 significantly improves the performance of the fountain codes，reduces the decoding complexity and improves the system performance.

fountain code；LT code；serial belief propagation algorithm；short ring；semi-random generationmethod

TM461

：A

：1009-671X（2015）01-041-04

10.3969／j.issn.1009-671X.201404001

http：//www.cnki.net／kcms／detail／23.1191.U.20150112.1530.012.htm l

2014-04-02.

日期：2015-01-12.

黑龙江省自然科学基金资助项目（F201339）.

刘立军（1989-），男，硕士研究生；谢红（1962-），女，教授，博士生导师.

谢红，E-mail：xiehong＠hrbeu.edu.cn.