最准特马网站资料2018
参考论文 下载本文

上海理工大学硕士学位论文

对于接收?#30805;?#35328;,如何才能恢复出源文件?由于删除信道的作用,所以在接收端恢复出的生成矩阵很有可能不是Gnk,这里设为Gnk',那么,si就可以通过式(2-2)恢复:

?1si=?tnGnk' (2-2)

k?1K?1?1G'G'是否存在nknk那么能否恢复出源文件的问题就转化为是否存在的问题,

取决于Gnk'是否满?#21462;?#24403;Gnk'中有k行线性独立时,那么Gnk'满?#21462;?#21487;用式(2-3)

表示Gnk'满秩的概率:

?0??K(N)??K?12i??(1?2N)?i?0N?KN?K (2-3)

第一行不为0的概率是1?2?N,第二行不为0,且和第一行不同的概率为

1?2?(N?1),第三行必须不同于前两行?#21335;?#24615;组合,即?*r1??*r2,其中?,

。 ??{0,1},则概率为1?2?(N?2),?#28304;?#31867;推即可得到式(2-3)2.4.2 解码情况讨论

现针对接收端的解码状况?#31209;?#31181;情况讨论:

(1) 当接收端收到的数据包个数小于K,则Gnk'不满秩,故不可能解码成功。 (2) 当接收端收到的数据包个数等于K,则Gnk'满秩的概率为

111(1-2?K)(1-2?(K?1))*...*(1?)(1?)(1?),对于任意的 大于10的K,概率

842均为0.289。

(3) 当接收端收到的数据包个数大于K,现设N=K+E,E即为发送?#30805;?#21457;送

的数据包,设?为当接收端收到在收到E个多余的数据包后未能成功解码

的概率,则1-?即为接收端成功解码的概率。根据上述分析,接收端成功解码的概率即为Gnk'满秩的概率。故由式(2-3)可得:

?N?K?log12 (2-4)

式(2-4)的直观意思即为:当接收端收到N个数据包时,即可以以

1-?的概率成功解码。

2.4.3 性能评价

一般情况下,对于编码而言,性能评价从开销和算法复杂度两个方面来考虑。 ? 开销:

由以上分析可知,随机线性喷泉码的开销随着K(发送文件的大小)的增大而

10

第二章 喷泉码介绍

减小。

? 算法复杂度:

1 编码复杂度:对一个数据包的编码复杂度是K/2,所以对于总的K个数

据包?#27492;擔?#32534;码复杂度是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,?#24188;?#23558;这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):

高斯消元法适用于所?#20449;?#27849;码的解码,这源于它在数学上实际就是解线性方程组。因此,所谓LT码解码端的任务就是从T?GS中通过矩阵求逆恢复出S矩阵,这里S是源数据包矩阵,T表示收到的LT编码包的矩阵。原始数据包和LT编码包的关系可用N?K的生成矩阵G来表示,这里K是原始数据包的个数,N是发送端生成的LT编码包的个数。若矩阵满秩,那么就表明译码成功,否则就不能够恢复源数据包,那么就需要接收更多的LT编码包。 ? 置信传递算法[24](Belief Propagation,BP): 1)根据LT编码包和原始数据包的对应关?#21040;?#31435;二分图。

2)在译码的每一阶段,都在LT编码包集合中寻找度为1的包,显然,这些LT编码包对应相连的原始数据包可以直接译出。

3)译码器将每一个译出的原始数据包与所有跟它相连的LT编码包相异或,异或后的值覆盖对应LT编码包的以前的值,同时删去这个译出的原始数据和对应的LT编码包的联系(二分图的边),从而使得这些编码包的度数减1,这样就会产生新的度数为1的编码包。

4)重复上述过程(2)(3),直到译码结束或者没有度数为1的编码包,迭代过程停止。如果所有LT编码包被成功恢复,则译码成功,否则译码失败。

现以图3-5为例,分析置信传递算法的解码过程:

12

第二章 喷泉码介绍

首先,编码过程建立?#30805;?#20998;图,如图2-5的(1)中所示,上面的每个圆圈表示输入符号,下面的每个圆圈代表输出符号,可以看出,每个输出符号是由几个输入符号异或而成的。圆圈中的0或1代表该符号的取值。图2-5中的其他图也类似。

然后,寻找度为1的输出符号,在图2-5的(2)中,正好第二个输出符号的度为1,这样,我们就得到了中间的那个输入符号的值?#21442;?。此时,我们可以将连接上述两个符号的边去掉,如图2-5的(3)所示。当得到中间这个输入符号后,我们将它的值同所有和它连接的输出符号相异或,图2-5的(3)中,它只和最后一个输出符号相连,0和1异或后为1,则最后一个输出符号的值就要变为1。

?#24188;牛?#25105;们再将刚刚进行异或的两个符号相连的边去掉,如图2-5的(4)所示,我们再在这些输出符号中寻找度为1的输出符号,结果发现最后一个输出符号的度为1,这样最右面的输入符号的值?#21442;?。

同样,此时我们可将连?#24188;?#21491;边的输入符号和输出符号的边去掉,如图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]采用?#24674;只?#20110;矩阵重排的译码算法,文献[31]采用了?#24674;?#22686;强BP译码算法。 2.5.4 LT码度分布函数的设计

LT喷泉码的发明人Luby在设计LT喷泉码时,希望编解码达到以下两个目的[24]:

14





最准特马网站资料2018