第二章 喷泉码介绍
减小。
? 算法复杂度：
1 编码复杂度：对一个数据包的编码复杂度是K/2，所以对于总的K个数
据包来说，编码复杂度是K2/2。 2 解码复杂度：
3O(K)。 1) 矩阵求逆的复杂度是
2O(K)（通过反向消2) 将收到的数据包配合矩阵求逆而做的转换，复杂度是
3O(K)。 K元求解上三角矩阵）。所以，解码总的个数据包的复杂度是
2.5 LT喷泉码
2.5.1 定义
假设现有K个符号(symbol)待发送。这里每个符号可以是1比特，也可以是
一个数据包(packet)。由于实验中我们采用的是包级别的LT编码，所以本文的符号特指数据包。 定义1.
度(d):生成一个LT编码包所需的源数据包的个数。 定义2.
度分布函数?(d)：对于所有的d，?(d)表示该LT编码包中出现度为d的概率。
2.5.2 LT码的编码
编码过程非常简单，关键是度分布函数的设计。 1) 从度分布函数?(d)中随机选取LT编码数据包的度d。
2) 等概率地从K个原始数据包中随机选取d个不同的原始数据包。 3) 将这d个原始数据包互相异或产生一个LT编码包。 4) 重复步骤1)、2）、3）N次得到N个编码包。
现以图2-4为例，分析LT喷泉码的编码过程：
从LT度分布函数中按照概率分布，某次恰取得d=3,然后从K个原始数据包中等概率地选取3个，这里是t1、t3、tk，接着将这3个数据包互相异或就得到了一个LT数据包。
11
上海理工大学硕士学位论文
s1?(1)???s2s3。。。sk?1sk?(3)???d?3原始数据包LT编码包
?(k)图2-4 某个LT编码包的生成
2.5.3 LT码的解码
对于LT的译码，通常有两种方法： ? 高斯消元算法[26]（Gaussian Elimination,GE）:
高斯消元法适用于所有喷泉码的解码，这源于它在数学上实际就是解线性方程组。因此，所谓LT码解码端的任务就是从T?GS中通过矩阵求逆恢复出S矩阵，这里S是源数据包矩阵，T表示收到的LT编码包的矩阵。原始数据包和LT编码包的关系可用N?K的生成矩阵G来表示，这里K是原始数据包的个数，N是发送端生成的LT编码包的个数。若矩阵满秩，那么就表明译码成功，否则就不能够恢复源数据包，那么就需要接收更多的LT编码包。 ? 置信传递算法[24]（Belief Propagation,BP）: 1)根据LT编码包和原始数据包的对应关系建立二分图。
2)在译码的每一阶段，都在LT编码包集合中寻找度为1的包，显然，这些LT编码包对应相连的原始数据包可以直接译出。
3)译码器将每一个译出的原始数据包与所有跟它相连的LT编码包相异或，异或后的值覆盖对应LT编码包的以前的值，同时删去这个译出的原始数据和对应的LT编码包的联系(二分图的边)，从而使得这些编码包的度数减1，这样就会产生新的度数为1的编码包。
4）重复上述过程（2）（3），直到译码结束或者没有度数为1的编码包，迭代过程停止。如果所有LT编码包被成功恢复，则译码成功，否则译码失败。
现以图3-5为例，分析置信传递算法的解码过程：
12
第二章 喷泉码介绍
首先，编码过程建立了二分图，如图2-5的（1）中所示，上面的每个圆圈表示输入符号，下面的每个圆圈代表输出符号，可以看出，每个输出符号是由几个输入符号异或而成的。圆圈中的0或1代表该符号的取值。图2-5中的其他图也类似。
然后，寻找度为1的输出符号，在图2-5的（2）中，正好第二个输出符号的度为1，这样，我们就得到了中间的那个输入符号的值也为0。此时，我们可以将连接上述两个符号的边去掉，如图2-5的（3）所示。当得到中间这个输入符号后，我们将它的值同所有和它连接的输出符号相异或，图2-5的（3）中，它只和最后一个输出符号相连，0和1异或后为1，则最后一个输出符号的值就要变为1。
接着，我们再将刚刚进行异或的两个符号相连的边去掉，如图2-5的（4）所示，我们再在这些输出符号中寻找度为1的输出符号，结果发现最后一个输出符号的度为1，这样最右面的输入符号的值也为1。
同样，此时我们可将连接最右边的输入符号和输出符号的边去掉，如图2-5的（5）所示，当得到最右边这个输入符号后，我们将它的值同所有和它连接的输出符号相异或，图2-5的（5）中，它只和第一和第三个输出符号相连，1和1异或后为均为0，则第一和第三个输出符号值均变为0。
最后，将刚刚的最右边的输入符号和第一，三个输出符号的边去掉，如图2-5的（6）所示，再在这些输出符号中寻找度为1的输出符号，结果发现有两个输出符号的度为1，它们同时得到第一个输入符号的值为0。
13
上海理工大学硕士学位论文
010(1)1110(2)11001101111011(3)010(4)0110010(5)10001(6)图2-5 BP译码示意图
对于BP这种迭代译码方式，存在中途失败的可能，如不存在度为1的编码包，为提高译码成功率，文献[27]和[28]从编码端着手，通过优化编码度分布函数提高译码性能。文献[29]研究了喷泉码的软译码算法，文献[30]采用一种基于矩阵重排的译码算法，文献[31]采用了一种增强BP译码算法。 2.5.4 LT码度分布函数的设计
LT喷泉码的发明人Luby在设计LT喷泉码时，希望编解码达到以下两个目的[24]：
14
