数字喷泉码

数字喷泉码信息与通信工程学院：钱晋希指导教师：赵旦峰教授喷泉码是什么喷泉码是指可以由k个原始数据分组生成任意数量的编码分组，而接收方只要收到其中任意m个编码分组，即可通过译码以高概率成功恢复全部原始数据分组。一般情况下，这里m的略大于k，从而引入一定的译码开销ε，定义1/km可以看到，上述编码过程就如同源源不断产生水滴（编码分组）的喷泉（编码器），而我们只要用杯子（译码器）接收足够数量的水滴，即可达到饮用（成功译码）的目的。正因如此，该种编码被称为喷泉码。喷泉码的发展历程•1998年，M．Luby等人首次提出喷泉码的概念，它是一种BEC(BinaryEraseChannel)码，但当时并没有给出现实可行的喷泉码设计方案。同年，M．Luby、A．Shokrollahi等人联合创立了DigitalFountain公司，以推广数字喷泉概念的实际应用。•2002年，M．Luby提出了第一种现实可行的喷泉码——LT码。在学术理论日渐完善的同时，喷泉码也日益受到产业界的关注，获得了越来越多的实际应用。•目前，一种由DigitalFountain公司设计的系统Raptor码也已经被DVB-H标准和3GPP组织的MBMS标准采用，并且正在参与其他多项国际标准的制定。人们对喷泉码的研究现状对于喷泉码的设计需要考虑两方面的问题：应该尽量减小译码开销ε，使其趋于零。应该尽量减小编译码复杂度，理想情况下，应该使生成每个编码分组需要的运算量是一个与k无关的常数，而成功译码m个编码分组获得k个原始数据分组需要的运算量是一个关于k的线性函数。针对以上两个方面，人们提出以下三种方案：a随机线性喷泉码。b改进型的LT码。cRaptor码。随机线性喷泉码(最简单的喷泉码)其大概原理如下：设K个原始数据包为P1，P2，⋯，Pk,进行如下编码：(F即原始数据文件)其中：为K×N矩阵，其元素按照某种特定的规律取0或1，加法运算为模2和；而为=(,,……,)其中，……,为编码数据且K.''FGRG/R/R/r/1r/2rN/r/1r/2rN/N/将编码数据,,……,进行存储,在读取时由于不可靠性,部分数据没有接收到,即下式成立:R=FG其中:R=(r1,r2,rN)G=(G1,G2,GN)如果G(在模2和的意义下)广义可逆，即存在，则F=则F可求出，即数据可得到恢复．r/1r/2rN/'NNKGRG特别地，考虑N=K的情况，那么G为K×K二元矩阵(即只含0和1两个元素的矩阵)，广义逆即一般逆．如果G为模2可逆,则可得F。GG-1G可逆则可如下考虑:G可逆的充要条件为：G的每一列矩阵与它前面所有的列矩阵皆线性无关.•G1线性独立即为非零向量，其概率为();•G1与G2线性无关的概率为();21k2)1(1k这个过程一直进行下去,则可得G可逆的概率为()×()×……×（）×（）×（）当K相当大(如大于10)时，其值约为0．289．对于高度可靠的数据存储来说，0．289这个值太小了。为了提高数据恢复的可靠性，可以取G的一部分GK×K，使得它可逆．要使GK×K以概率1－δ可逆，必须使其中：δ≤21k2)1(1k8114112112k)1log(KN数据恢复的复杂性即求与求R的复杂性之和．求逆矩阵的计算量O()，R与之模2乘法计算量为O()，因此当K相当大时，计算复杂性为O()数量级，即具有三次方复杂性。G-1G-1k3G-122kk3改进型的LT码改进型的LT码大大降低了编码与解码的复杂性。LT编码的过程就是做二分图的过程。编码：1)选择合适的度数分布p(d)，根据设计的度数分布选取编码分组度数d.2)从k个原始数据分组中，等概率地随机选取d个.3)将这个d原始数据分组模二和，生成一个编码分组。其中合适的度数分布为RobustSolitondistribution,它来源于IdealSolitondistribution.IdealSolitondistribution.如下：p(1)＝1/kp(d)=1/(d(d-1)),ford=2,3,4,……,k因为IdealSolitondistribution只能让每一次都只有一个度数为一的编码分组存在，不实用。RobustSolitondistribution,除了p(d)之外，还定义了一个t(d)t(d)=其中s=cln(k/δ)是每次度数为1的编码分组个数的期望值，并非是一。c:比1小的一个常数δ:译码失败的概率。那么RobustSolitondistribution分布u(d)为：u(d)=,其中z=1)/(0)/()/1log(.1)/(11.skdskdksskddkszdtdp)()(ddtdp)()(kLT码编码过程译码：(1)接收一定数量的编码分组，根据对应关系建立双向图。(2)任意选取一个度数为1的编码分组。(3)对于已经恢复的原始数据分组，将其模二和到与其相连的所有其他编码分组中，生成新的修正的编码分组。将双向图中对应的边删除，使这些编码分组的度数减1。(4)重复步骤2和3，直至译码停止。LT码译码过程对于改进型的LT码：选择合适的常数c,则当接收到＝k+2ln(s/δ)s个编码分组时，至少能以1-δ概率成功恢复原始数据分组。其平均度数为lnk，编译码复杂度为kln(k/δ)。k、Raptor码Raptor码先通过原始数据分组k个生成一个预编码分组＝k/(1-)个（＝，为LT码编码分组的平均度分布，在raptor码中大部分为2或3，平均＝3，则＝5％）。若预编码分组的误码率恰为时，这个预编码分组能纠正误码。k~f~f~edddf~k~f~f~f~然后用weakenLT编码分组传送这个预编码分组，当译码接收到略大于k个编码分组时，便可恢复(1-)个预编码分组，即k个（k=(1-)）最后用(1-)个预编码分组来恢复原始数据分组。WeakenLT码中度数分布大部分都是2或3，平均度数是3.k~k~f~k~f~k~f~而且，数字喷泉码是用在删除信道或者纠错能力很好的（如同删除信道）的噪声信道当中的一种码。因为从原始数据分组产生的编码分组可以是无限的，从这个角度来说，数字喷泉码是无码率的；并且所产生的编码分组数可以实时的确定。不管信道上的产出事件的统计特性如何，可以根据需要发送足够多的编码分组，以便译码器能恢复信源数据。数字喷泉码的前景•在网络数字存储当中应用数字喷泉码。•数字喷泉码也可以用在自组式网络和无线传感网络（WSN）中。•在无线通信以及其他许多领域当中可以应用数字喷泉码。谢谢！