卢比变换码

编辑:引退网互动百科 时间:2019-12-10 11:08:38
编辑 锁定
本词条缺少信息栏名片图,补充相关内容使词条更完整,还能快速升级,赶紧来编辑吧!
卢比变换码(LT码,英文:Luby transform codes, LT codes)是第一个最接近完善的抹除码(erasure correcting codes,详细见后)的实用涌泉码(fountain codes,详细见后),由Michael Luby在1998年发明并于2002年发表。
LT码一个显著的特征是采用简单且基础的异或编码以及解码
LT码的另一个特征是rateless,即它的码率不存在。由于它可以产生无限量的讯息封包,因此必须将接收到的封包进行解码的百分比极小。而LT码之所以属于抹除码之一的原因是它可以用在二进制抹去通道(Binary erasure channel, BEC)上进行传输。

卢比变换码抹除码(erasure correcting codes)

编辑
抹除码是相对于复制而言的。使用复制的情况,我们对一个文件做几个副本,放在不同的地方,再去管理它们。
抹除码的思路,简单来说,是将文件转换成一个碎片集合,每一个碎片很小,碎片被打散分布到一组服务器资源池里。只要存留的碎片数量足够,就可以合成为原本的文件。这可以在保持原本的数据健壮性的基础上大大减少需要的存储空间。

卢比变换码涌泉码(又称喷泉码,fountain codes)

编辑

卢比变换码为何要使用涌泉码

在传统“抹去通道”上的传输,通常得仰赖发送端以及接收端持续性的双向沟通:首先发送端进行编码以及传送带有讯息的封包,然后接收端这边在收到每个封包时会对其进行评估,如果该封包可以被解码,则传送一个确认(ACK信息)给发送端;反之,丢弃毁坏的封包,并传送请求让发送端再次发送该封包。该双向沟通会持讯进行值到所有讯息的封包都被成功传送且解码为止。
然而当用户数很大时,可能出现一种情况:用户发送的ACK信息占据了绝大多数的网络资源,使得正常的通信不能顺利进行,这种情况称为"反馈风暴"。
在这种情况下,重传方式完全不起作用,前向纠错方法的效率也不高。而涌泉码就可以有效地解决反馈风暴问题,并且采用随机编码,保证每次发送的信息对接收节点是有用信息。

卢比变换码涌泉码的基本思想

涌泉码的基本思想是单个源节点S不停的向周围的多个桶K(表示多个接收端的缓存)发送"水滴"(表示数据包),当一个桶里的水满了以后(缓存满),它才向源节点发送一个反馈。每次发送的水滴是一帧里面随机选择的一些包组合起来的包,这种组合可以是线性的,也可以是非线性的,在桶里的水满了以后进行相应的解码,当源节点收到所有桶的ACK以后,再发送新的一帧,否则继续发送组合包。涌泉码还可以有效提高信道容量及网络的鲁棒性。
所谓涌泉码,是指这种编码的发送端可以由k个原始分组生成任意数量的编码分组,接收端只要收到k(1+ε)个编码分组的任意子集,即可通过译码以高概率成功(和ε有关)恢复全部原始分组,精心设计的数字喷泉码不仅拥有很小的译码开销ε,而且具有简单的编译码方法和很小的编译码复杂度。可以看到,上述编码过程就如同源源不断产生水滴(编码分组)的喷泉(编码器),而我们只要用杯子(译码器)接收足够数量的水滴,即可达到饮用(成功译码)的目的,而不必关心是那一点水(编码分组)流入你的杯中。正因为如此,这种编码被称为涌泉码(FountainCodes)。需要特别指出的,涌泉码与LDPC码的最大区别在于其中不存在码长n的定义,或者说码长趋于无穷;相应地,码率R=k/n的定义也不存在,因此涌泉码也被称为无率码(RatelessCodes)。

卢比变换码使用涌泉码之后的讯息传输过程

发送端同样进行编码以及传送带有讯息的封包。接收端对每个收到的封包进行评估,如果出现错误,则丢弃该封包;反之则收纳作为讯息的一部分。当接收端逐一收取封包直到拥有足够且可以完整解码的有效讯息时,才发送确认给发送端,停止传送封包。

卢比变换码数字喷泉码和分组码的差别

1、对于传统的分组码,码的结构在信息传输之前确定;而数字喷泉码可"在线(online)"编码产生。
2、 当采用传统的分组码传输信息时,发送者与接收者之间都知道所采用的编码方法;而对于数字喷泉码情况并不是这样。由于编码的输出符号与数据的传输并发产生,因此,为了从输出符号恢复原信息,必须将采用的编码方法与输出符号一并传输。在符号对应于包的网络环境中,可以给每个传输包增加用来表示该输出符号是由那些输入符号产生的头信息,于是,描写输入与输出符号之间关系的信息在接收端就可通过数据包头来获得,或者可通过发送端与接收端之间依赖于应用的同步方法来获得。

卢比变换码涌泉码与卢比变换码

卢比变换码,即LT码,是喷泉码的第一次具体实现,是由MichaelLuby提出的,后来AminShokrollahi对LT码做出了改进,提出了第二类喷泉码,即Raptor码。

卢比变换码应用

喷泉码最初是为删除信道设计的,其最大的特点就是码率无关性,即编码器可以生成的编码符号的个数是无限且灵活的,译码器只需接收到任意足够数目的编码符号就能还原数据。因此不管删除信道的删除概率多大,编码器能源源不断地产生编码符号直到译码器还原出源文件。正是由于喷泉码的这个特性,使得喷泉码在删除信道中获得了逼近香农限的性能。后来,研究发现喷泉码在二进制对称信道(BSC)和加性高斯白噪声(AWGN)等信道中同样能获得很好的性能。在此之后,LT码的研究范围不断扩大,LT码独特的码率无关性,特别适合无线通信中的广播、多播业务,因此LT码在无线广播系统和协作中继网络中的应用成为近几年的一个研究热点。

卢比变换码卢比变换码(LT码)

编辑

卢比变换码编码(coding)

将待传送的讯息分割成等长度的n个封包(packet),透过随机数产生器(randomnumbergenerator)依特定的概率分布(probabilitydistribution)产生一个整数degreed,且1<=d<=n,代表着一组讯息需要包含的封包数量。
接着在n组封包中,以离散型均匀分布(uniformdistribution)的方式,选取d组封包出来。
接下来将d组封包之间做异或(XOR)运算,因此要传送的其中一个封包便是:M1⊕M2⊕…⊕Md,其中M1,M2,…Md是总共n组封包中被挑选出来的d组。
该传送的封包前面还须附加一些额外讯息,包括整份讯息有多少个封包(n个)、是哪d个封包被做了XOR运算。
最后,一些形式的侦错码将被附加在封包的最后(可能是某种循环冗余校(cyclicredundancycheck)),该封包才会被进行传输。
以上这些步骤将不断重复进行,直到接收端判断该讯息已被完整接收且成功地解码出来。

卢比变换码解码(decoding)

解码过程中同样使用"异或"(XOR,⊕)来还原被编码的讯息。
如果当前这个封包格式错误(侦错码发生问题),或者该封包是个已处理过封包的复制品,丢弃该封包。
排除以上情形,便可开始处理解码程序;其工作原理是利用A⊕A=0的特性去逐步消去每个封包里的degree,直到总共有n个degree为1的不同封包为止。
对封包Mk解码的范例如下:
(M1⊕…⊕Md)⊕(M1⊕…⊕Mk-1⊕Mk+1⊕…Md)
=M1⊕M1⊕…⊕Mk-1⊕Mk-1⊕Mk⊕Mk+1⊕Mk+1⊕…⊕Md⊕Md
=0⊕…⊕0⊕Mk⊕0⊕…⊕0
=Mk
重复以上步骤,就可以完成解码过程。
词条标签:
科技