北方华远：喷泉码技术研究

 请加微信号：13391796993，专属您的喷泉设计专家！

更多资讯关注"北方华远":http://www.www.bfhyspq.com (合作)TEL:010-67691862；也欢迎加入我们"喷泉交流群 "：591771305

北方华远喷泉10月18日号讯：

1喷泉码的历史和现状
喷泉码的概念由M．LubY等人于1998年首次提出，但当时并没有给出现实可行的喷泉码设计方案。2002年，M．Lubv提出了第一种现实可行的喷泉码――U1码。在学术理论日渐完善的同时．喷泉码也日益受到产业界的关注，获得了越来越多的实际应用。1998年．M．Luby、A．ShokmUahi等人联合创立了D珥tal Fountain公司，以推广数字喷泉概念的实际应用。目前，一种由Di西tal Fountain公司设计的系统R8口tor码也已经被DVB―H标准和3GPP组织的MBMS标准采用，并且正在参与其他多项国际标准的制定。
2喷泉码的概念
所谓喷泉码．是指该种编码可以由个原始数据分组生成任意数量的编码分组．而接收方只要收到其中任意m个编码分组，即可通过译码以高概率成功恢复全部原始数据分组。一般情况下．这里的m略大于k，从而引入一定的译码开销8，定义为8=m，k一1，也即m=k(1+8)。可以看到。上述编码过程就如同源源不断产生水滴(编码分组)的喷泉(编码器)，而我们只要用杯子(译码器)接收足够数量的水滴，即可达到饮用(成功译码)的目的。正因如此，该种编码被称为喷泉码。显然。喷泉码的设计需要考虑两方面的问题。一方面，应该尽量减小译码开销8，使其趋近于0；另一方面，应该尽量减小编译码复杂度，理想情况下，应该使生成每个编码分组需要的运算量是一个与k无关的常数，而成功译码m个编码分组获得k个原始数据分组需要的运算量是一个关于k的线性函数。
2．1 LT码及其编译码理论
LT码是第一种实用喷泉码，具有简单的编译码方法以及较小的译码开销和编译码复杂度，为喷泉码的发展奠定了基础。LT码生成每个编码分组的过程如图1所示：
1)根据设计的度数分布Q进行随机实验．选取编码分组度数d。
2)从k个原始数据分组中，等概率地随机选取d个。
3)将这d个原始数据分组模二和，生成一个编码分组。
LT码译码过程如图2所示：
1)接收一定数量的编码分组．根据编码分组与原始数据分组的对应关系建立双向图。顶层节点代表原始数据分组，底层节点代表编码分组，连接顶层节点和底层节点的边代表该原始数据分组是该编码分组的模二和分量(图2a)。
2)任意选取一个度数为1的编码分组。如果不存在，则译码停止；如果存在．则通过简单的复制运算．即可恢复与该编码分组相连的唯一原始数据分组(图2b)。
3)对于已经恢复的原始数据分组，将其模二和到与其相连的所有其他编码分组中。生成新的修正的编码分组。相应地。将双向图中对应的边删除．从而使得这些编码分组的度数减1。简单实例如图2c所示。如果在此过程中某个编码分组的度数减少为1，则称该编码分组被“释放”(图2c)。
4)重复步骤2和3，直至译码停止。如果所有原始数据分组都已经恢复，则译码成功；否则，译码失败．必须接收更多的编码分组才能继续译码(图2d、2e、2f)。在每步迭代译码的开始，所有已经“释放”的编码分组。也即此时度数已经减少为1的编码分组。被称为“输出波纹”；而与这些编码分组相连的原始数据分组。被称为“输入波纹”。显然，存在输入波纹和输出波纹．是迭代译码过程得以继续的充分必要条件。如图2e所示，其中的两个编码分组都属于输出波纹，而余下的一个尚未恢复的原始数据分组属于输入波纹。