喷泉码

在编码理论中，喷泉码（也称为无码率抹除码）是一类抹除码，其有能力从一组给定的源符号中产生一串无限的编码符号序列，而在理想情况下，只需获得大小和源符号相同或稍大的任意编码符号子集，便可恢复源符号。术语“喷泉”或“无码率”是指这样的事实：这些码不显示出固定的编码率。 如果原始k个源符号可以从任意k个编码符号中恢复，则该喷泉码是最佳的。喷泉码是高效的编解码算法，因有很大概率能从任意k’个编码符号恢复原始的k个源符号（k’仅稍大于k）而知名。 LT码是第一种实际实现的喷泉码。随后提出的Raptor码和在线码加入了输入符号的预编码阶段，实现线性时间的编解码复杂度。 中文名喷泉码外文名Fountain codes时 间1998年 目录 1 抹除码介绍 2 概念介绍 ▪ 原因 ▪ 发展历史 ▪ 基本思想 ▪ 特点 ▪ 应用方向 ▪ 两种喷泉码 ▪ 技术发展 抹除码介绍编辑 抹除码是相对于复制而言的。使用复制的情况，我们对一个文件做几个副本，放在不同的地方，再去管理它们。 抹除码的思路，简单来说，是将文件转换成一个碎片集合，每一个碎片很小，碎片被打散分布到一组服务器资源池里。只要存留的碎片数量足够，就可以合成为原本的文件。这可以在保持原本的数据健壮性的基础上大大减少需要的存储空间。 概念介绍编辑 原因 在传统“抹除通道”上的传输，通常得仰赖发送端以及接收端持续性的双向沟通：首先发送端的文件是以多个小数据包的形式进行传输的，一个文件被简单粗暴地切割成k个数据包大小的片段，发送端对它们编码后将这些带有信息的封包发送到接收端。这些小的数据包如果在传输过程中产生错误，就会导致接收失败，否则就能被成功接收。成功与否取决于接收端在收到每个封包时对其进行的评估，如果该封包可以被解码，则传送一个确认（ACK信息）给发送端；反之，丢弃毁坏的封包，并传送请求让发送端再次发送该封包。显然，在这种通道上还会需要一个用于确定哪些数据包需要被重新传送的反向通道（back channel）。该双向沟通会持续进行直到所有信息的封包都被成功传送且解码为止。 [1] 随着因特网的迅猛发展，人们在享受信息传递的方便与快捷的同时也对通信系统的服务能力和范围提出了更高的要求，有限的网络带宽与迅速增长的网络数据量和下载规模之间形成了一对亟需解决的矛盾。因特网中可靠的数据传输一直是许多研究的热点。很多时候，可靠性是靠使用合适的协议来保证的。例如，普遍使用的TCP/IP用重传机制来保证传输的可靠性。但是在很多情况下，TCP/IP协议并不适用，如点到多点传输，或在严重损坏的信道上进行传输（质量很差的无线或卫星链路）。基于反馈重传的TCP在传输距离太长的时候性能很差，因为长距离导致发送方等待反馈确认信息时的空闲时间太长。同时，单一删余信道的模型不适用于数据从一个发送者同时发送到多个接收者的情况。在这种情况下，从发送者到多个接收者的删余信道的删余概率可能不同。当接收者数量很多时，不太可能估计每个信道的删余率和丢包情况，因此，需要构造可靠的传输方案。 发展历史 针对这一问题， John Byers及Michael Luby等人于1998年首次提出了数字喷泉（Digital Fountain）的概念，它是针对大规模数据分发和可靠广播的应用特点而提出的一种理想的解决方案，但当时并未给出实用数字喷泉码设计方案。2002年，Luby提出了第一种实用数字喷泉码——LT码。之后，Shokrollahi又提出了性能更佳的Raptor码，实现了近乎理想的编译码性能。在学术理论日渐完善的同时，数字喷泉码也日益受到产业界的关注，获得了越来越多的应用[5]。1998年，M. Luby、A. Shokrollahi等人联合创立了Digital Fountain公司（简称DF公司），以推广数字喷泉概念的实际应用，很快便引起了包括MIT、UC Berkeley、纽约大学、多伦多大学、日本住友电工等机构和单位的关注。目前，已有越来越多的学者和机构开始致力于喷泉编码的研究，数字喷泉在数据分发与广播应用上也获得了越来越多的支持与采纳。 基本思想 所谓喷泉码，是指这种编码的发送端随机编码，由k个原始分组生成任意数量的编码分组，源节点在不知道这些数据包是否被成功接收的情况下，持续发送数据包。而接收端只要收到k(1+ε)个编码分组的任意子集，即收到一个稍微大于原来k值得N，就可通过译码以高概率（(和ε有关)）成功地恢复全部原始分组。 下面这个比喻形象地解释了这个过程。 单个源节点S如同源源不断产生水滴(编码分组)的喷泉，不停地向周围的多个桶K(表示多个接收端的缓存)发送"水滴"(表示数据包)，当一个桶里的水满了以后(缓存满)，它才向源节点发送一个反馈。每次发送的水滴是一帧里面随机选择的一些包组合起来的包，这种组合可以是线性的，也可以是非线性的，随机选择保证了每次发送的信息对接收节点是有用的。桶在装满水之后（接收足够数量的水滴），即可达到饮用（成功译码）的目的，而不必关心具体是哪一滴水(编码分组)流入桶中。当源节点收到所有桶的ACK以后，再发送新的一帧，否则继续发送组合包。 这也是这种编码方式被称为喷泉码( Fountain Codes)的原因。 特点 精心设计的数字喷泉码不仅拥有很小的译码开销ε，而且具有简单的编译码方法和很小的编译码复杂度。同时喷泉码还可以有效提高信道容量，使得网络更加健壮。 应用方向 喷泉码最初是为抹除信道设计的，其最大的特点就是码率无关性，即编码器可以生成的编码符号的个数是无限且灵活的，译码器只需接收到任意足够数目的编码符号就能还原数据。因此不管抹除信道的抹除概率多大，编码器能源源不断地产生编码符号直到译码器还原出源文件。正是由于涌泉码的这个特性，使得涌泉码在删除信道中获得了逼近香农限的性能。 后来，研究发现涌泉码在二进制对称信道(BSC)和加性高斯白噪声(AWGN)等信道中同样能获得很好的性能。在此之后，LT码的研究范围不断扩大，LT码独特的码率无关性，特别适合无线通信中的广播、多播业务，因此LT码在无线广播系统和协作中继网络中的应用成为近几年的一个研究热点。 喷泉码的应用范主要可以概括为如下几个方面： ①在广域网、国际互联网、卫星网上进行高速大文件传输。以RS为代表的前向纠错编码通过硬件实现，按照保护小块数据的要求设计，主要是对受到破坏的多个比特或单个比特进行检测和校正。而LT码意在保护大型文件，而且这种技术以软件方式实现，速度非常快。由于没有了TCP的网络时延影响吞吐量，喷泉码可以在互联网，无线网，移动网及卫星网上提供接近网络带宽速度的大文件传输。 ②在无线网、移动网提供质量完善的流媒体点播或广播。利用喷泉码技术来处理Internet最为头疼的流式视频、音频、视频游戏、MP3文件等，可以提供质量完善的流媒体点播或广播。 ③在3G移动网、数字电视广播网、电信组播网及卫星广播系统提供无需反馈信道的可靠性数据广播。由于不需反馈，用户数量的增长对于发送方来说没有任何影响，发送方可以服务任意数量的用户。 两种喷泉码 喷泉码有两类：LT码和Raptor码。LT码是喷泉码的第一次具体实现，是由Michael Luby 提出的，后来Amin Shokrollahi对LT码做出了改进，提出了第二类喷泉码，即Raptor码。 1、LT码（卢比变换码） LT码是第一类码率不受限码的实用实现，即其码率不需要事先确定，同时它具有简单的编译码方法以及较小的译码开销和编译码复杂度，为数字喷泉码的发展奠定了基础。LT码是通用的数字喷泉码，也就是说对于具有不同删除概率的各种删除信道均是逼近最优的。 在数据传输时，将长为N的文件分割成k=N/ l个输入符号(即每个输入符号的长为l)，并称每个数据包为输入符号，称每个编码包为输出符号。 定义：LT码的度分布ρ( d)(d≥1)定义为一个输出符号结点的度为d的概率。 LT码生成每个编码分组的过程如图1所示： （1）将原始数据等分为k个数据分组，在1～k范围内按某一分布Ω（称为编码度分布）随机选取一个整数d，其中k称为该码的码长，d称为编码分组的度； （2）在数据分组中均匀地随机选取d个不同包； LT码的译码采用一种迭代算法[3]。在译码的每一步，译码器都在编码包集合中寻找度为1的包，这些包组成的集合称为输出可译集。它们连接的数据包组成的集合称为输入可译集。显然，输出可译集中的元素与对应的相连的数据包取值相同，因此输入可译集中的所有数据包都能被直接译出。在此之后，译码器将每一个译出的数据包与跟它相连的所有编码包分别进行异或，计算结果取代对应编码包原来的值，完成之后删去与它们之间的连接关系。重复上述过程直至不存在度为1的包为止。如果所有数据包都被恢复则译码成功，否则译码失败。该算法即称为喷泉码的BP译码算法。图2给出了一个译码实例。其算法过程具体为： （1）接收一定数量的编码分组，根据编码分组间的对应关系（可以通过分组头部等方式显式传递，也可以通过事先约定伪随机序列等方式隐式传递）建立双向图。顶层节点代表原始分组，底层节点代表编码分组，连接它们的边代表该原始分组是该编码分组的模二和分量。简单实例如图2(a)所示。 （2）任意选取一个度数为1的编码分组。如果不存在，则译码停止；如果存在，则通过简单的复制运算，即可恢复与之相连的唯一原始分组。简单实例如图2(b)所示。 （3）将已经恢复的原始分组模二和到与其相连的所有其他编码分组中，消除其在这些编码分组中的模二和分量。相应地，将双向图中对应的边删除，使得这些编码分组的度数减1。简单实例如图2(c)所示。如果某个编码分组的度数减小为1，则称该编码分组被“释放”，如图2(c)最右侧的编码分组。 （4）重复步骤（2）和（3），直至译码停止。如果所有原始分组都已经恢复，则译码成功；否则，译码失败，必须接收更多的编码分组才能继续译码。如图2(d)，2(e)，2(f)所示。 图2 LT码解码示意 显然，合理的度数分布是LT码性能的关键。从LT码编码过程考虑，一方面应该使平均度数较小，这样才可以减小生成每个编码分组需要的运算量；另一方面又应该给予较大度数一定的选取概率，这样才可以通过m≈k个编码分组覆盖所有的原始分组。从LT译码过程考虑，一方面应该使编码分组保持一定的释放速度，这样才可以保证译码过程不会终止；另一方面又不能使编码分组释放过快，否则大量已经释放的编码分组将增加重复覆盖的可能性，引入不必要的冗余[7]。正是基于以上考虑，Luby首先给出了理想Soliton分布，使得译码过程在期望意义下每步迭代恰好释放一个编码分组。之后Luby通过修正理想Soliton分布，给出了更加实用的鲁棒Soliton分布。理论分析证明：在鲁棒Soliton分布下，当受到k+O(k)个编码分组后，译码器即可以高概率成功译码；以模二和运算的次数来衡量，生成每个编码分组需要的运算量是O(logk)，而成功译码需要的运算量是O(klogk)。根据文献报告的数据，在Digital Fountain公司设计的商用LT码中，译码开销ε不超过5%，而译码失败概率可以低于10-8。可见，LT码不仅编译码方法简单直观，而且性能相当优良。 2、Raptor码 Raptor码是LT码的基础上发展出来的改进版。它是基于这样一个认识：LT码生成的编码包中有少量连接度很高的包，这些包的作用主要是保证对所有数据包的良好覆盖，从而保证译码的完整性，然而这些高连接度包的存在消耗了很多编译码异或操作，同时也降低了低连接度包的比例，从而减小了译码过程中可译集的大小，降低了译码成功率。如果能采用别的方法来代替高连接度包完成对数据包的良好覆盖则可以有效地提高译码成功率并降低编译码复杂度。 基于这个思想，Raptor码提出采用两步编码的方式。首先对原始信息用一个分组码进行预编码，然后采用一个弱化的LT码对数据进行编码并发送。所谓弱化的LT码是指它生成的编码包没有高连接度包，无法完全译出原始数据。Raptor码译码时，首先用BP算法对数据进行正常译码。由于弱化LT码能以很高的概率恢复出绝大多数的数据包，因此剩下未被译码的数据包所占的比例就被控制在一个很小的范围以内，这些未被译码的数据不再通过高连接度的编码包来保证覆盖和恢复，而是利用预编码的纠错能力进行恢复。通过联合优化弱化LT码和预编码的码率和参数，Raptor可以获得更低的编译码复杂度，而在相同译码开销下能实现更高的译码成功率。 Raptor码的编码和译码均需O (kln(1/ε))次包异或操作，其中ε是译码开销。可见，Raptor码的编译码复杂度与码长成线性关系，优于LT码的对数关系。 [2] 技术发展 当喷泉码被用于大规模的多媒体传输时，传统的LT或者Raptor码无法满足实时组播应用中的非等重误码保护（unequal error protection ，UEP ）。Expanding Window Fountain(EWF) codes成为了一种实现这种需求的新方式。显然，它是一种能够在抹除信道中的无率（rateless）码。 EWF码使用了窗口技术，而不是通过不平等选择输入的符号来实现UEP。这种技术通过在UEP无率码设计中添加附加参数以满足不同标准的接收者接收，使得它比传统加权的方式更为一般化并且更具灵活性。无论是理论研究还是实验表明，这种窗口技术都使得UEP设计具有了更好的性能。音乐喷泉公司【热线电话:13172194676】主要从事音乐喷泉工程、喷泉安装调试工程，根据客户的要求设计、施工音乐喷泉、程控喷泉、变频喷泉、跑动喷泉、旱式喷泉、摇摆喷泉、漂浮喷泉、雕塑喷泉、超高喷泉、波光喷泉、水池喷泉、叠水喷泉、室内喷泉、奇特喷泉、瀑布水帘、冷雾喷泉、微型喷泉及各类控制系统等一体化服务。音乐喷泉公司_广场喷泉_喷泉水景_程控喷泉_旱地喷泉施工设计公司城市导航：