47数字喷泉码

ResearchInstituteofCommunicationTechniques,BeijingInstituteofTechnology2011-10-231数字喷泉码吴彬斌2011.10.23BeijingInstituteofTechnology2011-10-232ResearchInstituteofCommunicationTechniquesoutline喷泉码的产生随机线性喷泉码LT码：–LT码的编码–LT码的解码–度分布函数的设计Raptor码BeijingInstituteofTechnology2011-10-233ResearchInstituteofCommunicationTechniques喷泉码的产生在互联网中，信息的是以数据包传送的。通常每个数据包要么无差错的被接收端接收，要么根本就没有被接收端接收到。TCP协议中，针对网络丢包的做法是检错重传机制。这种简单的检错重传传送协议的优点是可以保证接收机总能无差错的完成数据接收，但反馈对信道资源浪费比较严重而且当接收方和发送方距离较远时还会产生较大的时延。1998年M.Luby首次提出了喷泉码的概念。2002年Luby给出了一种现实可实现的喷泉码——LT码。在LT码的基础上Shokrollahi和Luby在2004年提出了比LT码复杂度更低的数字喷泉码——Raptor码。BeijingInstituteofTechnology2011-10-234ResearchInstituteofCommunicationTechniques所谓喷泉码，是指该编码可以由k个原始信源信息生成任意数量的编码分组，再通过译码可以高概率的恢复原始分组。编码过程就如同源源不断产生水滴的喷泉，而我们只要接到足够的水滴，即可达到饮用的目的，所以被称为喷泉编码。同时因为喷泉码不存在码长,码率的定义也被称为无码率码。数字喷泉码的无码率特性使得发送端可以无止尽的产生编码符号信息，每个编码符号都是由信源信息独立随机异或生成。由于各码字的独立随机性，每块码字均包含信源信息。所以进过删除信道时，删除编码信息的任意部分，不会影响其他符号信息参与译码。BeijingInstituteofTechnology2011-10-235ResearchInstituteofCommunicationTechniques随机线性喷泉码假设编码器需要编码的文件为,它们只能被正确地传输或被删除。在每一个时钟周期,编码器产生一个K阶随机二进制矩阵,编码器的输出由异或而成，即：由不同的异或而来，可以对每K个随机在一个半无限的二进制矩阵中定义一个新的列，如右图所示。Ksss,,21KnGntksKkknknGst1ntksntBeijingInstituteofTechnology2011-10-236ResearchInstituteofCommunicationTechniques接着，以编码的数据包经过信道传输，发生数据包删除,接收端一直接收数据包，直到接收到N个。在此假定认为接受端已知随机矩阵，且随机矩阵与和相联系,则可以称上图中矩阵可利用的部分为G，并通过G将源文件恢复。随着源文件大小（K）的增加，随机线性喷泉码能够接近香农理论的极限，但随机线性喷泉码的编码和解码的代价都是K的二次方。在K很大时，编解码的复杂度很高。因此希望找到复杂度更小的喷泉码，由此出现了LT（LubyTransform）码。ntksBeijingInstituteofTechnology2011-10-237ResearchInstituteofCommunicationTechniquesLT码的编码原理LT码是第一个真正意义上实用的喷泉码,其编码算法如下：–将原始信源数据等分为k个数据包,在1~k范围内按编码的度分布中随机选取一个整数d，其中d称为该编码包的度；–在数据包中均匀地随机选取d个不同的数据包；–对这d个数据包求异或，即可得到一个编码包。注：编码的度分布表示随机选到整数d的概率为,其中D为能取到的最大度数。编码度分布也可以用下式表示：Ksss,,21D21,,D21,,d12321DDxxxxBeijingInstituteofTechnology2011-10-238ResearchInstituteofCommunicationTechniquesLT的译码方法——高斯消元高斯消元算法是一类对喷泉码通用的译码方法。假设接收端收到n个符号，每个接受符号代表一个由k个未知输入的线性方程，则整个译码过程可以看做一个n个方程联合求解k个未知数的方程组。其步骤如下：–假设H是经过删除信道后的生成矩阵，将H矩阵扩展为含接收信息向量N的增广矩阵，；–利用矩阵初等变换将此增广矩阵进行转换成为–若此单位矩阵I满秩，则译码成功，译码输出X即为；若此单位矩阵不满秩，说明接受信息不足，译码失败，接收端继续接受信息，进入下一轮译码。注：高斯消元算法的缺点是译码复杂度高，不适合于长码的运算。'HNHH’''NIH'NBeijingInstituteofTechnology2011-10-239ResearchInstituteofCommunicationTechniquesLT译码算法——BP算法BP算法适用于只经过删除信道，接收到的一组编码符号集合只发生丢失,而不引入误差的情况。我们称接收到的已经编码的数据包为检验码。解码过程如下：–译码器寻找校验节点中d=1的节点，即校验节点只和唯一的符号节点相连。如果存在，则将和此节点相连的节点的值还原为校验节点的值；–寻找上一步中还原符号节点相连的校验节点集合，并与进行异或，然后删除它们与的联系；–循环迭代这个过程，直到所有的符号被正确地译出。–若在循环迭代起始不存在d=1的节点，则译码无法启动，在循环迭代中d=1的节点消耗殆尽，循环也将被终止，译码器译码失败，接收端继续接受信息，进入下一轮译码。qsqsqsBeijingInstituteofTechnology2011-10-2310ResearchInstituteofCommunicationTechniquesBeijingInstituteofTechnology2011-10-2311ResearchInstituteofCommunicationTechniques度分布函数的设计喷泉码的度分布信息，是喷泉码编码和性能的关键。因为喷泉码译码依赖于接受信息中d=1节点的分布，而译码的持续则有赖于在迭代过程中d=1节点的持续产生。一个好的度分布应满足的条件：–大部分的节点的度值应该较小，以减少编码和译码整体的异或计算次数和保证译码过程的持续进行；–少量参与编码的节点应该度值较大，以防出现漏编码的信息点。BeijingInstituteofTechnology2011-10-2312ResearchInstituteofCommunicationTechniquesIdealSoliton分布：IdealSoliton分布是最理想的译码状态，即在每一次解码循环中，至少有一个检验码的度为1。同时当一个检验码处理过后，又有一个新的度为1的检验码出现,因此可以实现译码次数的最优化。为简便起见,不妨取K=100，则可知：;,3,2)1(1;11)(KddddKd;9900/1)1(100;6/1)1(3;2/1)1(2;100/1)1(1时，时，时，时，ddddBeijingInstituteofTechnology2011-10-2313ResearchInstituteofCommunicationTechniques可见，度为1的概率为1/100；度为2的概率为1/2；度为3的概率为1/6；…；度为100的概率为1/9900。为了简便和精确，将把概率区间[0,1]扩大10000倍为（0,10000]，再将（0，10000]按各个度的概率划分为100个区间，调用RAND函数，在0到10000之间产生随机数，看这个随机数落在划分的哪个区间，就确定了一个随机度。度取该度的概率取该度的区间11/100（0，100]21/2（100，5100]31/6（5100，6766]………1001/9900（9999，10000]BeijingInstituteofTechnology2011-10-2314ResearchInstituteofCommunicationTechniques度只是决定了编码由几个异或而成，但并没有确定是哪几个异或。实际上对于某一个度，其对应的编码可由源文件中的任意个异或得来。同确定随机度的方法一样，也可以随机的选取。但选择每个的概率是一样的，都是1/K。同样为了精确，把概率区间[0,1]扩大10000倍为[0，10000]，再将[0，10000]均分为个区间.Ks取该区间的概率取的区间1/100（0，100]1/100（100，200]………1/100（9900，10000]BeijingInstituteofTechnology2011-10-2315ResearchInstituteofCommunicationTechniques对于某一个度，再调用MATLAB中的RAND函数，在0到10000之间随机产生个数，看这个随机数落在划分的哪些的选取区间，就确定由哪些参与编码。但是在实际应用中，编码度分布的抽样无法精确符合Ideal分布，存在一定的波动误差,从而致使迭代中度为1的节点断层，导致译码失败，因此实际性能并不理想。ndndndKsKsBeijingInstituteofTechnology2011-10-2316ResearchInstituteofCommunicationTechniquesRobustSoliton分布：改进型RobustSoliton分布有效地结合了Ideal分布的的优点,并加入另外两个调节参数c和;它们的引进将保证在每一次解码循环中度为1的检验码的数目,而不是1个。参量是接收到个确知的数据包后无法解码的概率的极限。c在实际应用中可以作为一个小于1的可调整的常数，以达到优化性能的目的。RobustSoliton分布分为两部分，一部分如下：ln(/)scKk时；时；时sKdsKdsKssKddKsde/0/)/(log;1)/(,,3,2,11)(BeijingInstituteofTechnology2011-10-2317ResearchInstituteofCommunicationTechniques另一部分即为上面提到的IdealSoliton分布:对两者取归一化可得Robust分布：其中,解码能够成功的概率至少为时，需要接收到已经编码的数据包的数目。;,3,2)1(1;11)(KddddKdZddd)()()(dddZ)()(1KZK'BeijingInstituteofTechnology2011-10-2318ResearchInstituteofCommunicationTechniques)01.1,1010/,10(5.0,01.0ZsKsc)03.1,337/,30(5.0,03.0ZsKsc)1.1,101/,99(5.0,1.0ZsKscBeijingInstituteofTechnology2011-10-2319ResearchInstituteofCommunicationTechniques解码需要的接收数据包数目柱状图BeijingInstituteofTechnology2011-10-2320ResearchInstituteofCommunicationTechniqu