数字喷泉码 PPT课件

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