John Byers及Michael Luby等人于1998年首次提出了数字喷泉（Digital Fountian）的概念，它是针对大规模数据分发和可靠广播的应用特点而提出的一种理想的解决方案，但当时并未给出实用数字喷泉码设计方案。2002年，Luby提出了第一种实用数字喷泉码——LT码1。之后，Shokrollahi又提出了性能更佳的Raptor码2，实现了近乎理想的编译码性能。在学术理论日渐完善的同时，数字喷泉码也日益受到产业界的关注，获得了越来越多的应用

发展历史

应用方向

概念

LT码

Raptor码

发展历史

随着因特网的迅猛发展，人们在享受信息传递的方便与快捷的同时也对通信系统的服务能力和范围提出了更高的要求，有限的网络带宽与迅速增长的网络数据量和下载规模之间形成了一对亟需解决的矛盾。因特网中可靠的数据传输一直是许多研究的热点。很多时候，可靠性是靠使用合适的协议来保证的。例如，普遍使用的TCP/IP用重传机制来保证传输的可靠性。但是在很多情况下，TCP/IP协议并不适用，如点到多点传输，或在严重损坏的信道上进行传输（质量很差的无线或卫星链路）。基于反馈重传的TCP在传输距离太长的时候性能很差，因为长距离导致发送方等待反馈确认信息时的空闲时间太长。同时，单一删余信道的模型不适用于数据从一个发送者同时发送到多个接收者的情况。在这种情况下，从发送者到多个接收者的删余信道的删余概率可能不同。当接收者数量很多时，不太可能估计每个信道的删余率和丢包情况，因此，需要构造可靠的传输方案。

针对这一问题， John Byers及Michael Luby等人于1998年首次提出了数字喷泉（Digital Fountain）的概念，它是针对大规模数据分发和可靠广播的应用特点而提出的一种理想的解决方案，但当时并未给出实用数字喷泉码设计方案。2002年，Luby提出了第一种实用数字喷泉码——LT码[1]。之后，Shokrollahi又提出了性能更佳的Raptor码[2]，实现了近乎理想的编译码性能。在学术理论日渐完善的同时，数字喷泉码也日益受到产业界的关注，获得了越来越多的应用[5]。1998年，M. Luby、A. Shokrollahi等人联合创立了Digital Fountain公司（简称DF公司），以推广数字喷泉概念的实际应用，很快便引起了包括MIT、UC Berkeley、纽约大学、多伦多大学、日本住友电工等机构和单位的关注。目前，已有越来越多的学者和机构开始致力于喷泉编码的研究，数字喷泉在数据分发与广播应用上也获得了越来越多的支持与采纳。

应用方向

喷泉码的应用范围很广，主要可以概括为如下几个方面：

①在广域网、国际互联网、卫星网上进行高速大文件传输。以RS为代表的前向纠错编码通过硬件实现，按照保护小块数据的要求设计，主要是对受到破坏的多个比特或单个比特进行检测和校正。而LT码意在保护大型文件，而且这种技术以软件方式实现，速度非常快。由于没有了TCP的网络时延影响吞吐量，喷泉码可以在互联网，无线网，移动网及卫星网上提供接近网络带宽速度的大文件传输。

②在无线网、移动网提供质量完善的流媒体点播或广播。利用喷泉码技术来处理Internet最为头疼的流式视频、音频、视频游戏、MP3文件等，可以提供质量完善的流媒体点播或广播。

③在3G移动网、数字电视广播网、电信组播网及卫星广播系统提供无需反馈信道的可靠性数据广播。由于不需反馈，用户数量的增长对于发送方来说没有任何影响，发送方可以服务任意数量的用户。

2005年，DF公司先后与美国第二大卫星广播公司Sirius公司以及全球第一大手机厂商诺基亚公司签署协议，向他们的后续产品提供数字喷泉技术的支持。特别值得一提的是，Digital Fountain公司设计的系统Raptor码已经被DVB-H标准和3GPP组织的多媒体广播和多播业务(MBMS)标准采用[4]，该公司的Digital Fountain RaptoFEC技术将成为3GPP流式文件下载服务的MBMS标准的一部分。

概念

在传统的ARQ方法中，当用户数很大时，可能出现一种情况：用户发送的ARQ信息占据了绝大多数的网络资源，使得正常的通信不能顺利进行，这种情况称为“反馈风暴”。在这种情况下，重传方式完全不起作用，前向纠错方法的效率也不高。数字喷泉码可以有效地解决反馈风暴问题，并且采用随机编码，保证每次发送的信息对接收节点是有用信息。数字喷泉码的基本思想是单个源节点S不停的向周围的多个桶K（表示多个接收端的缓存）发送“水滴”(表示数据包)，当一个桶里的水满了以后（缓存满），它才向源节点发送一个反馈。每次发送的水滴是一帧里面随机选择的一些包组合起来的包，这种组合可以是线性的，也可以是非线性的，在桶里的水满了以后进行相应的解码，当源节点收到所有桶的ARQ以后，再发送新的一帧，否则继续发送组合包。数字喷泉码还可以有效提高信道容量及网络的鲁棒性。

所谓数字喷泉码，是指这种编码的发送端可以由k个原始分组生成任意数量的编码分组，接收端只要收到其中任意k(1+ε)个编码分组，即可通过译码以高概率成功恢复全部原始分组，精心设计的数字喷泉码不仅拥有很小的译码开销ε，而且具有简单的编译码方法和很小的编译码复杂度[3]。可以看到 ,上述编码过程就如同源源不断产生水滴（编码分组）的喷泉（编码器），而我们只要用杯子（译码器）接收足够数量的水滴，即可达到饮用（成功译码）的目的,而不必关心是那一点水（编码分组）流入你的杯中。正因为如此，这种编码被称为数字喷泉码（Digital Fountain Code）。需要特别指出的，数字喷泉码与LDPC码的最大区别在于其中不存在码长n的定义，或者说码长趋于无穷；相应地，码率R=k/n的定义也不存在，因此数字喷泉码也被称为无率码（Rateless Codes）。

数字喷泉码和分组码的差别为[9]：

(1) 对于传统的分组码，码的结构在信息传输之前确定；而数字喷泉码可“在线(online) ”编码产生。

(2) 当采用传统的分组码传输信息时，发送者与接收者之间都知道所采用的编码方法； 而对于数字喷泉码情况并不是这样。由于编码的输出符号与数据的传输并发产生，因此，为了从输出符号恢复原信息，必须将采用的编码方法与输出符号一并传输。在符号对应于包的网络环境中，可以给每个传输包增加用来表示该输出符号是由那些输入符号产生的头信息，于是，描写输入与输出符号之间关系的信息在接收端就可通过数据包头来获得，或者可通过发送端与接收端之间依赖于应用的同步方法来获得。

显然，喷泉码的设计需要考虑两方面的问题：一方面，应该尽量减小译码开销ε，使其趋近于0；另一方面，应该尽量减小编译码复杂度，理想情况下，应该使生成每个编码分组需要的运算量是一个与k无关的常数，而成功译码m个编码分组获得k个原始分组需要的运算量是一个与k无关的常数，而成功译码m个编码分组获得k个原始分组需要的运算量是一个关于k的线性函数。

喷泉码最初是为删除信道设计的，其最大的特点就是码率无关性，即编码器可以生成的编码符号的个数是无限且灵活的，译码器只需接收到任意足够数目的编码符号就能还原数据。因此不管删除信道的删除概率多大，编码器能源源不断地产生编码符号直到译码器还原出源文件。正是由于喷泉码的这个特性，使得喷泉码在删除信道中获得了逼近香农限的性能。后来，研究发现喷泉码在二进制对称信道（BSC）和加性高斯白噪声（AWGN）等信道中同样能获得很好的性能。在此之后，LT码的研究范围不断扩大，LT码独特的码率无关性，特别适合无线通信中的广播、多播业务，因此LT码在无线广播系统和协作中继网络中的应用成为近几年的一个研究热点[8]。

喷泉码有两类：LT码和Raptor码。LT码是喷泉码的第一次具体实现，是由Michael Luby 提出的，后来Amin Shokrollahi对LT码做出了改进，提出了第二类喷泉码，即Raptor码。

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-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码不仅编译码方法简单直观，而且性能相当优良。

Raptor码

Raptor码是LT码的基础上发展出来的改进版。它是基于这样一个认识：LT码生成的编码包中有少量连接度很高的包，这些包的作用主要是保证对所有数据包的良好覆盖，从而保证译码的完整性，然而这些高连接度包的存在消耗了很编译码异或操作，同时也降低了低连接度包的比例，从而减小了译码过程中可译集的大小，降低了译码成功率。如果能采用别的方法来代替高连接度包完成对数据包的良好覆盖则可以有效地提高译码成功率并降低编译码复杂度[3]。

基于这个思想，Raptor码提出采用两步编码的方式。首先对原始信息用一个分组码进行预编码，然后采用一个弱化的LT码对数据进行编码并发送，如图2.4所示。所谓弱化的LT码是指它生成的编码包没有高连接度包，无法完全译出原始数据。Raptor码译码时，首先用BP算法对数据进行正常译码。由于弱化LT码能以很高的概率恢复出绝大多数的数据包，因此剩下未被译码的数据包所占的比例就被控制在一个很小的范围以内，这些未被译码的数据不再通过高连接度的编码包来保证覆盖和恢复，而是利用预编码的纠错能力进行恢复。通过联合优化弱化LT码和预编码的码率和参数，Raptor可以获得更低的编译码复杂度，而在相同译码开销下能实现更高的译码成功率。

Raptor码的编码和译码均需O (kln(1/ε))次包异或操作，其中ε是译码开销。可见，Raptor码的编译码复杂度与码长成线性关系，优于LT码的对数关系。