LT码(翻译)

LT码

Michael Luby

Digital Fountain, Inc.

************************摘要：我们介绍LT码,第一种随着数据长度增长也非常有效的无比率纠删码。

关键词：纠删码，无比率编码，通用码，可靠传输，balls and bins，随机算法。

1.引言

LT码是我们称之为通用纠删码的纠删码第一次实现。编码的符号长度可以任意,从一位二进制符号到常规 位的符号。我们从符号操作方面,分析了编码器和译码器运行时间，这里的符号操作要么是符号之间的异或要么是一个符号的一个副本复制到另一个符号。如果原始数据由k个输入符号组成，那么每个编码符号可以独立于所有其他的编码符号,以平均O(ln(k/δ))次符号操作生成,并且可以从任何 个编码符号，以概率1−δ，通过平均O(k·ln

(k/δ))次符号操作，恢复出k个原始输入符号。

LT码是无比率的,即从数据产生的编码符号的数量可以是无限的。此外,编码符号可以在线生成，和需要的一样多或者一样少。同时,译码器可以从任何生成的编码符号组,只要这个集合的长度是比数据长度略长，精确的恢复复制数据。因为译码器可以从尽可能接近最小数量的编码符号恢复数据,这意味着就任何删除通道而言，LT码接近最优状态。此外,作为数据长度的函数，编码和译码时间非常渐近高效。因此,在某种意义上讲，LT码是通用的,对于每一个删除通道，它们都是同时接近最优状态的,而且，随着数据长度的增长，它们依然是非常有效的。

LT码的分析和Tornado码的分析完全不同[16][17][15]。特别是, Tornado代码分析只适用于最大度为恒定的图表，LT码使用对数密度的图表,进而Tornado代码分析并不适用。此外,Tornado码分析依赖会导致接收开销的技术,本质上是至少是数据长度的恒定比例。而LT码的分析表明，接收开销是数据长度的渐近消失的部分,尽管以渐近稍高的编码和解码时间为代价。

LT码设计和分析的关键是引入和分析LT程序。这个程序及其分析是将经典过程和随机将球扔进桶的分析新颖的概括，而且它具有独立的性质。我们通过使用概率论第一定理，它能准确的捕捉数据恢复过程的行为，提供完整的LT程序的行为过程分析。

在[7][6]中“数字喷泉方法”概念的引入类似于通用纠删码,LT码是第一个全面实现这个概念。本文描述了 [12][13]所做的部分工作的理论基础。

1.1 一些编码细节

从概念上讲，编码符号的产生是非常容易描述的。

• 从一个度分布中随机的抽取编码符号的度 d。好的度分布的设计和分析是本文其余部分的要点。

• 均匀随机选择d个不同的输入符号作为编码符号的邻包。

• 编码符号的值是这d个邻包异或的值。

当使用编码符号恢复成原始数据的输入符号,译码器需要知道每个编码符号的度和邻包组。有很多种不同的方法将这个信息传送给译码器,取决于用途。例如，对于各个编码符号，度和邻包索引的列表明确的发给译码器。作为另外一个例子，每个编码符号的度和邻包索引可能由译码器含蓄的计算出，例如基于编码符号的定时相应或者基于编码符号相对于其他编码符号的位置。作为另外一个例子，密钥与每个编码符号有关,在于编码器和译码器都应用相同的函数产生度和编码符号的邻包组。既然这样，编码器可能随机的选取各个密钥用于产生编码符号，而且密钥可以连同编码符号一起传送到译码器。然而密钥由确定性的程序产生，例如，后面的各个密钥会比前面的密钥大。编码器和译码器利用相同的随机位组，密钥用于伪随机数产生器，使用这些随机数产生编码符号的度和邻包。将度和邻包与编码符号相关联的方法是不同的，取决于应用，这些实施细节超出了本文的范围。

1.2与传统纠删码的比较

传统的纠删码是典型的有固定码率的分组码，即对于n个编码符号的整体，k个输入信号被用于产生n – k个冗余编码，码率为k/n。例如，对于可靠数据分发应用，互联网网络研究建议使用Reed-Solomon和Tornado码，在这些情况中，在编码程序开始之前，k和n都取决于实际条件被限定为相当小的值，或者被固定，参见参考文献 [21][26][2][7][6]。理想情况，和Reed-Solomon码一样，任意n中的k个编码符号对于恢复k个原始输入符号是足够的(例如参见文献[18])。也有时候，和Tornado码一样，对于恢复k个原始的输入信号，需要稍微大于k < n个编码符号。

实践中的Reed-Solomon码只对相当小的k和n的组有效。原因是对于Reed-Solomon码[26][2]的标准应用，需要k(n − k)A/2次符号操作产生编码符号，这里A是使用到的有限域的尺寸。译码次数与此类似。虽然对于实施Reed-Solomon码具有对编码器和译码器都渐进更快的理论算法，即n中k次综合对数，在实际应用中，对于k和n的值，执行次数的平方是比较快的。

Tornado码是块擦除纠删码，与n次编译码次数线性相关[16][17][7][6]。LT码多少与Tornado码有些相像。例如，他们使用近似的规则恢复数据，表面上LT码使用的度分布也与Tornado码使用的度分布类似。但是，实际上用于Tornado码的度分布是不适用于LT码的。输入符号上的度分布类似于稍后描述的孤子分布，并且冗余符号第一层上的度分布接近于泊松分布。输入符号上的孤子分布不能应用于LT码，因为这个分布不能保证无论编码符号邻包上的分布选择什么，当编码符号独立的产生时，分布不能使度分布作用在输入符号上。可以想象转换这个Tornado码上的分布，这样，像LT码，泊松分布用于输入符号，孤子分布用于冗余符号。在Tornado码图表中冗余符号上的由丢失的输入符号诱导的分布，远非孤子分布，而且将恢复规则清晰的应用于诱导分布不会导致合理的接收开销。

越过前面提到的LT码和Tornado码的不同点，较Tornado码LT码具有巨大的应用优势。令c = n/k为Tornado码设计的恒定拉伸参数。一旦k和n被固定下来，那么Tornado码编码器产生n个编码符号，并且如果编码符号的需求增加，也不能在线动态的产生更多编码符号。与此相反，LT码编码器可以根据需要产生同样多或者同样少的编码符号。Tornado码在几层符号之间使用级联顺序的二位图，这里输入符号作为第一层，冗余符号在各个随后的层。实际应用中，这需

要或者编码器和译码器都知道相同的准确的图标结构的先验关系，或者编码器知道准确的图标结构的先验关系，然后发送给译码器。在任何一种情况，这样的预处理都是相当笨拙的，尤其是图标结构尺寸正比于n = ck。尽管如果相同长度的数据被重复的编码译码，折算开销是减小的，但是如果各个数据的长度不同，对于不同的数据长度需要不同的图表结构，那么这样预处理关系就是相当大的缺陷。相反的，LT码使用的度分布基于数据长度是很容易计算的，并且这是唯一的需要调用解码器或者译码器的预处理关系。

对于Tornado码，译码依赖于从n个编码符号中获取足量的不同的编码符号。在一些传输应用中，由传播端发送的编码符号的总数量是有编码器合理产生的编码符号数量的几倍。对于这些应用,在某些情况下，每次从一个符号中选取一个编码符号用来发送是一个好策略。在这种情况下,不难看到,在n = ck个编码符号之中，为了获得k截然不同的编码符号一个接收器需要接收的编码符号的平均数量，为ck ln(c/(c − 1))。（回忆至少需要k个不同编码符号恢复数据）。例如这样，如果c = 2，那么用户端为了接收到k个不同的编码符号，平均需要接收1 .386 k的编码符号。让这个数字更好接受，举例来说，接收1.05k个编码符号，需要c > 10。这个值使Tornado码变得毫无吸引力，因为编码器和译码器存储器的用法，解码时间都与c倍的数据长度成正比。相反，LT码编译码器的寄存器用法与数据长度成正比，起码时间只取决于数据长度，与多少个编码符号被编码器产生和发送无关。

Reed-Solomon码和Tornado码都是系统编码，即所有组成数据的输入符号都直接包含在编码符号之中，然而，LT码不是系统码。

1.3 应用

当数据以互联网协议在网络上传输时，一般的，将其分成相同长度的块，放入包中。任何应用这种协议类型的传输协议都必须保证所有的数据包被接收机接收。这就是为什么例如TCP接收机确认各个接收到的包，并且TCP发送机会重发未被确认的包的原因。由于这些性能，所以TCP/IP不能对于在高延迟网络上传输，以高丢失率传输，或者将相同的内容以高效并发传输方式传输给多个客户端方面进行很好的检测。

纠删码还被推荐对各种各样的数据分发应用提供可靠性。对于点到点传送，在独立于流量与堵塞控制机制，设计纠删码可靠性机制方面中具有优势，如[1]中概述。在点对点数据传送中使用纠删码的优势在于使独立于可靠性之外设计堵塞控制机制变得容易。

对于一对多数据传送的难题，这里网络和发送机的可测量性是最重要的，反馈给发送机需要被限制，并且对于一些发送机，作为冗余的发送包是浪费的，使用[21],[28],[26],[27],[22],[23],[9][7][6]中描述的纠删码，可靠性能够被提供。这种方法的吸引力在于，如果纠删码足够有力，那么一个单独的发送机就能潜在的被用于高效可靠地传送数据给很大数量的并行接收机，而不需要反馈。

当不同的接收机连接发送机的带宽不同时，并且每个接收机都渴望独立于其他接收机，以尽可能最快的速度得到数据时，点到多点的难题甚至更加困难。接收机驱动堵塞控制协议被独立于可靠性协议设计，这个协议可在当前网络条件和接收机与发送机之间的带宽条件，分级的传送产生的包的不同部分给各个接收机

[19][30][4][14]。连同这些堵塞控制协议，纠删码能被用于帮助提供复杂可靠传输系统。

对于多对一传送，对于接收机能从不同位置的多个潜在的发送机发送的相同

的数据，它是有用的。既然如此，接收冗余包是值得注意的，纠删码能使冗余包的传送竟可能减少。在文献[5]中考虑了这个应用，并且基于Tornado码给出了局部的解决方案[16][17]。

对所有这些不同类型的数据传送应用，LT码提供了引人注目的前面提到的纠删码难以企及的优势。使用LT码，在包中接近最小数量的编码符号能被产生发送到接收机，在每个接收机它能恢复原始数据之前需要的包的数量渐近的接近最小可能。当传统的纠删码用于这些解决方案中，在产生任何包之前，要产生的包的数量就已经基于网络条件的最好推测固定了，而且这个推测无可避免的或者过高或者过低。

LT码有各种各样的应用，包括鲁棒分布存储，流媒体内容传送，无线网络中对移动用户的内容传送，对等网络应用，在内容多径传输中网络裂缝确保恢复能力，还有大量的应用以至于本文中不能面面俱到。

2. LT码设计

长度为l的编码符号被选择作为所需的。在实际应用中由于记账操作的开销，使用长为l的编码符号总体的编译码比选择较大的l值更有效率，但是这在理论上是承受不了的。在传输应用中，有时l被选择接近数据包有效负载的长度。

编码工作如下。长度为N的数据被分成 个输入符号，即每个输入符号的长度为l。各个编码符号的长生如1.1小节中描述。给定一组编码符号，与它们关联的度的一些表示方法，以及邻包组，只要译码器工作，就能反复的应用下面的规则恢复输入符号。

定义 1（译码器恢复规则）：如果至少有一个编码符号恰好有一个的邻包，那么邻包能够被立即恢复，因为它是编码符号的一个拷贝。恢复的输入符号的值与任一余下的编码符号异或，使输入符号成为一个邻包，恢复的输入符号作为邻包，从各个编码符号的关系中被清除，并且这些中编码符号中的每个的度减1，也反应了这个清除。

2.1 LT程序

我们介绍LT程序用来帮助描述对于LT码的一个好的度分布的设计和分析。令K为编码符号的总数在这个分析中去被考虑（一般的K略大于k）。LT程序是将球随机的扔进桶的理论新颖的一种概括。关于这个过程一个众所周知分析显示，为了确保每个桶以至少1 - 的概率至少被一个球覆盖，平均需要 。在这个LT程序的分析中，编码符号被比拟成球，输入符号被比拟成桶，如果最终所有的输入符号都被覆盖，那么程序成功了。

定义 2（LT程序）：所有的输入符号初始时都被不被覆盖的。在初始的第一步，所有带有一个邻包的编码符号被释放去覆盖他们唯一的邻包。那些被覆盖到的但是没有被处理输入符号的集合叫做“涟波”，并且这样从这一角度说所有的被覆盖的输入符号都在涟波中。在随后的的每一步，涟波中的一个编码符号被这样处理：从所有那些以它作为邻包的编码符号中，作为邻包的关系被清除，并且所有这样后来恰好有一个余下的邻包的编码符号被释放去覆盖他们余下的邻包。这些邻包中的一些有可能之前没有被覆盖，这将引起涟波增长，当这些邻包中其他可

能已经在涟波中的时候，涟波将不会增长。当在一些步骤的结尾涟波为空时，程序结束。如果最终有至少一个没被覆盖的输入符号，程序失败。如果最终所有的输入符号都被覆盖了，程序成功。在古典的球与桶的程序中，所有的球被一次性扔出。由于碰撞的高可能性，也就是多个球覆盖同一个桶，比在桶中更多的球必被扔出去覆盖所有的桶。相反的，适当的度分布设计能够确保LT程序递增的释放编码符号去覆盖输入信号。初始时只有一小部分编码符号的度为1，并且这样它们覆盖一小部分输入符号。被覆盖的输入符号每次一个被处理，并且每个被处理的输入符号都可能释放其他的编码符号去随机的覆盖没有被处理的输入符号。度分度设计的目标是随着程序进展，缓慢的释放编码符号去保持涟波小，以便于防止输入符号被多个编码符号多余的覆盖，但是同时释放的编码符号足够快以便在程序结束之前涟波不会消失。因为一个编码符号的邻包被独立于所有其他的编码符号随机的选择，所以可以容易的证明一个特殊的编码符号被释放是独立于其他所有的编码符号的这一步。而且，一旦一个编码符号被释放，它将一致的覆盖在未被处理的输入符号中选中的输入符号，独立于其他所有编码符号。这些性能使LT码尤其是服从于一个好的度分布设计和遵从于这些分布的程序分析。不难证明，在LT程序和译码器之间是一一对应的，也就是当且仅当这个编码符号能覆盖那个输入符号，一个编码符号覆盖一个输入符号。这样，当且仅当译码器成功的恢复出所有的数据符号时，LT程序成功。需要去覆盖所有的输入符号的编码符号的总数恰好为需要去恢复数据的编码符号的总数。这些编码符号的度的总数恰好对应需要去恢复数据的符号操作的总数。

3. LT度分布

回忆，根据一个度分布，每个编码符号独立的选择度。

定义3 （度分布）：对于所有的d， 是一个编码符号具有度d的概率。

根据我们最新的发展，LT程序的随机行为的复杂性决定于度分布 ，编码符号数量K，以及输入符号的数量k。我们的目的是设计度分布满足下面2个设计目标：

·以平均尽可能少的编码符号确保LT码程序的成功。回忆确保LT程序成功的编码符号的数量对应确保数据完全恢复的编码符号的数量。

·编码符号的平均度尽可能低。平均度是为产生一个编码符号进行的符号操作的平均数量。平均度乘以K是为恢复所有数据进行的符号操作的平均数量。

一个将球扔进桶的典型程序能被看做一个LT程序的特殊例子，这里所有的编码符号具有度1，并且这样初始时所有的被释放和投掷，也就是下面这样的分布。

定义4 （均匀分布）： 。

依照LT码，这对应于通过随机选择一个输入符号和将它的值拷贝到编码符号，产生各个编码符号。典型的球与桶程序的分析暗示，至少需要 个编码来以至少 的概恢复所有的k个输入符号，遵从均匀分布。这样的结果能被简单的改进用来说明对于任一分布，编码符号的度的总和一定至少为 ，以便至少一次恢复所有的输入符号。这样，虽然服从均匀分布

的符号操作的总数最小，但是需要恢复k个输入符号的编码符号的数量为

乘以较最小可能值大的一个数，这是不能接受的。下面我们发展了孤子分布用来确保刚超过k个编码符号，以便它们的度的总和为 ，足够恢复所有k个输入符号。这样，编码符号的数量和符号操作的总数量都趋近于遵从孤子分布的最小值。

3.1 一些初步概率分析

我们首先分析当L个剩余的输入符号未被处理时，一个特殊的度为i的编码符号被释放的概率。因为一个编码符号的输入符号的邻包独立于其他所有编码符号被选择，所以它服从于当余下的L个没有被处理的输入符号独立于其他所有编码符号时，这个编码符号被释放的概率。

定义 5（编码符号释放）: 当L个剩余的输入符号未被处理时,无论从哪一点这个编码符号随机的覆盖到L个未被处理的输入符号中的一个时，如果它在第k -

L个输入符号的处理下被释放，我们称之为一个编码符号被释放了。

定义 6（度释放概率）: 令q(i, L)为当L个剩余的输入符号未被处理时，度i的一个编码符号被释放的概率。

命题 7（度释放概率公式）

·q(1 ,k)=1。

·对于i =2 ,..., k, 所有的 i = 2, ..., k,

·对于所有其他的i和L，q(i, L) = 0。

证明：这是编码符号的i – 2个邻包是在第一批k−(L+1)符号中被处理，一个邻包在k − L步被处理的，并且余下的邻包在L个未被处理输入符号中的概率。

定义 8（整体释放概率）：当L个剩余的输入符号未被处理时，令 为一个编码符号被选择具有度i并且被释放的概率，也就是

令 为当L个剩余的输入符号未被处理时一个编码符号被释放的整体概率，也就是 。

3.2 理想的孤子分布

一个好的度分布需要的基本性能为在输入符号被处理的同时以相同的比率被加入到涟波中。这个性能是孤子分布这个名称的灵感，因为孤光波子能够将色散平衡完美的反射。

预期效果为尽可能少的释放编码数据包去覆盖一个已经在涟波中输入符号。这是因为释放的用于覆盖已经在涟波中的输入符号编码符号是多余的。因为释放的编码符号随机的覆盖未被处理的输入符号中的一个，这意味着涟波尺寸始终保持小。在另一方面，如果在所有k个输入符号被覆盖之前涟波消失了，那么整体程序以失败告终。涟波尺寸应该保持足够大以确保涟波不会过早的消失。期望的

行为为涟波尺寸既不太大也不太小。从恢复数据所需要的编码符号预期的数量这个角度说，理想孤子分布展示了理想行为。不幸的是，类似于大多数理想的东西，这个分布是相当脆弱的，事实上，在实际应用中它是无用的。但是，它的说明和分析捕获了很多在稍后描述的鲁棒分布中至关重要的因素。

定义 9（理想孤子分布）：理想孤子分布为 ，这里，

·

·对于i =2 ,...,k, 。

注意 作为所需的概率分布。从分布中选择样本的一个方法为第一次选择一个随机的实值 ，然后对于i =2 ,...,k，如果1/i < v

≤ 1/i−1，令样本值为i，如果 ，令样本值为1。则编码符号期望的度分布为 ，这里总计为k。

命题 10（均匀释放概率）：对于理想孤子分布，对于L = k,..., 1，

证明：对于L=k，度为1的所有的编码符号被释放，并且一个编码符号度为1的概率为1/k，这样对于L=k的叙述就是真的了。对于所有其他的命题7中的L的值，

为谐波，

被解释为概率，这是能证实的，当向k-1个桶中一致的随机的扔球时，随着一个桶被一个球覆盖了，各个桶消失了，第i-1个球被扔进L个未被标记的桶中的一个。对于不同的i值，这些事件是互相排斥的，并且因为i =2 ,...,k

− L + 1覆盖所有可能的输出，

设想LT程序的期望行为就是它的实际行为。那么，理想孤子分布将完美的工作，也就是恰好k个编码符号足够恰好一次覆盖k个输入符号。这是因为如果有k个编码符号，那么根据命题10，每当一个输入符号被处理，恰好一个编码符号被希望释放。如果期望行为真的发生，那么总有恰好一个输入符号在涟波中，并且当这个符号被处理时，释放的编码符号覆盖未被处理的输入符号中的一个，以便重建这个条件，等等。

然而，这个启发式的分析基于完全不切实际的假设——期望行为是真是发生的，这远非现实。事实上，理想孤子分布在实际中工作的非常无力，因为期望的涟波尺寸为1，甚至一个最小的变化将导致涟波消失，这样整个程序将不能覆盖和处理所有输入符号。

注意，对于理想孤子分布，k个编码符号的度的总和平均为k · ln(k)。回忆对于均匀分布，以固定的概率平均需要k · ln(k)的编码符号恢复所有的输入符号。有趣的是，对于理想孤子分布符号操作的数量和对于均匀分布的符号操作的

数量是一致的，即使编码符号的数量相当不同。这给了我们一个直觉，即对于任意一种分布，需要的编码符号的度的总和总是在k · ln(k)在附近，以便于覆盖所有输入符号，但是理想孤子分布压缩这个数量为可能的编码符号的最小数量。这样，在这两个例子中，计算总量是相同的（因为这是与所有的编码符号的度的总和成比例的）。然而，需要接收的信息总量（与编码符号的数量成比例）通过理想孤子分布被压缩为最小的可能值。

3.3 鲁棒孤子分布

虽然在实际应用中，理想孤子分布工作的十分无力，但是它给了鲁棒分布深入的了解。理想孤子分布的难题在于期望的涟波尺寸太小。在涟波尺寸上的任何变化都可能使涟波消失甚至整体程序失败。鲁棒孤子分布确保在程序中的各个点涟波尺寸是足够大的以便于其以很高的概率从不消失。在另一方面，为了最小化全部使用到的编码符号的数量，最小化期待涟波尺寸也是很重要的，以便于不是太多的释放的编码符号多余的覆盖在已经在涟波中的输入符号。

对于一个给定的编码符号数量K，令为了恢复数据可以接受的译码器失败概率为 。这里的想法是设计度分布以便期望的涟波尺寸在程序始终总是大约为

。

正如我们下面描述的，得到这样的结果，使用 个编码符号。直觉是以超过 的涟波尺寸，概率至多为 ，以步长为l在其均值做随机漫步。

定义 11（鲁棒孤子分布）：鲁棒孤子分布为 定义如下。令R =对于一些合适的常数c>0。定义:

i =1 ,...,k/R−1

i =k/R

i =k/R +1 ,...,k

向 添加理想孤子分布 ，并且归一化活动 ：

·

·对于i =1 ,...,k,

增补 的灵感如下。在开始时， 确保涟波合理的尺寸开始。考虑到程序在中间。假设一个输入符号被处理和L个剩余的输入符号未被处理。因为涟波尺寸以每当一个输入符号被处理就减1的速度减小，平均上说，涟波尺寸应该加1以补偿这个损失。如果涟波尺寸是R，那么一个释放的编码符号被加到涟波中，尺寸平均变为(L − R)/L。根据命题7，有可能证明，当L个剩余的输入符号未被处理时，对于带有固定因数k/L的i来说，度为i的编码符号的释放率组成了释放率的一个固定部分。这样，如果涟波尺寸被维持在近似于R，那么度为i = k/L的编码符号的密度应该与下式相称

对于i =2 ,...,k/R− 1。最后的毛刺 确保当所有L=R个输入符号被完全覆盖时，所有的输入符号未被处理。当R个剩余的输入符号未被处理去一次性覆盖他们所有时，这类似于同时释放 个编码符号。这样，这个由释放足够的编码符号去至少一次覆盖这些输入符号中的每个而引起的损耗，仅仅是输入符号的总数k的一小部分。我们将编码符号的数量设定为 这意味着 是期望的度为i的编码符号的数量。

3.4 鲁棒孤子分布的分析

这一小节我们提供了对鲁棒孤子分布性能理论上的分析。当证明定理时，情况往往是这样，为了使能一个简单的，综合的，完整的分析，我们在几个地方做了悲观的估计。基于计算机模拟的启发式技术能被用于提供一个设计和分析，这些设计和分析导致更低的接收开销和平均度，但是关于此的描述，超出了本文的范围。

定理 12（编码符号的数量）：编码符号的数量为

证明：

定理 13 （编码符号的平均度）

证明：

下面的命题被用来证明如下的理论，即LT程序的高成功率。

定理 14 （鲁棒平均释放概率）：对于所有的L = k− 1 ,...,R, K · r(L) ≥ L/(L−

θR)，其中θ ≥ 0为一个合适的常数，排除 的影响。

证明：（梗概）这个证明使用了 的贡献，和理想孤子分布

对于L = k/2 ,...,k – 1，使用命题7和命题10，

更通常的，对于L ≥ R，

那么，使用命题7和命题10，

对于所有的

这样，

整理得，

对于

。

命题15 （末段鲁棒释放概率）：仅使用 的贡献，对于合适的常数

证明：（梗概）在2R与R之间固定L。对于适当的常数

不难显示

，

命题 16（悲观的过滤）：当L个剩余的输入符号未被处理而且有X个输入符号在涟波中，假定一个特殊的编码符号被释放。如果，编码符号落在当前不在涟波中的概率的概率为至多为 的某个值，那么LT程序成功的概率至多在它被修正之前。

命题 17（高回复率）：从一组K个编码符号出发，译码器恢复数据失败的概率至多为 。

证明（梗概）：证明的要点为对于随机漫步涟波尺寸是非常小的，并且在k步内，以 的倍数，涟波尺寸偏离它的期望值的概率是小的。

因为度为1的编码符号的期望数量为R，切尔诺夫界限表明，以概率至少为

，由于度为1的编码符号， 涟波的初始尺寸至少为 ，我们能过滤低于θR/2的涟波尺寸。争议在于，对于L = k − 1 ,...,R，涟波不以高概率消失，并且部分争议在于不适用毛刺 添加到分布，因为毛刺被分别用于表明至少R个输入符号被覆盖了。使用命题16和命题14，我们能悲观的过滤对于K中每个编码符号的分布，以便于令 为编码符号的数量 由于那些在这个被过滤的分布中离开L个未被处理的输入符号，被处理的输入符号的数量，也就是 。

假设当前的涟波尺寸总是在0和θR之间，并且稍后这个假设将被清除。当L个剩余的未被处理的输入符号以概率至少为被添加到涟波中

时，每次一个编码符号被释放。使用命题16，每个这样被释放的编码符号会被悲观的过滤以便它以恰好为 的概率被添加到涟波中。令 为0-1值随机变化，以便

。注意，对于任一

为基于上述假设当L个剩下的输入符号未被处理时的涟波尺寸。注意：

使用切尔诺夫界限，其能被表示为

和

且

于此它遵照下面的假设，涟波尺寸从它的初始值θR/2，至少为θR/2，超过区间I，变化的概率至多为。这显示为

概括为以至少为的概率涟波尺寸大于0，并且在区间I的结尾处至多为θR。因为有k-R个区间，这表明涟波对于所有的区间都严格的大于0小于θR。这表明关于涟波尺寸的最大值的假设是真的，并且程序是成功的直到以至少1 −δ/3的概率R个剩下的输入符号未被处理。

我们现在考虑最后R个符号的恢复和处理。命题15能被用来表明，当2R和R之间个剩下的输入符号未被处理时，足够多的编码符号被释放以至少1 − δ/3的概率去覆盖最后R个未被处理的输入符号。

总得来说，LT程序以至少1 – δ的概率完全成功。比较遵从均匀分布的LT程序和遵从鲁棒孤子分布的LT程序，有一个很有趣的事。用于恢复所有k个输入符号的编码符号的度的总和大约都为均匀分布的编码符号对应于经典程序，它需要大约。然而，因为度为1的遵从个编码符号去恢复所有的输入符号。在鲁棒孤子分布中，相同的度的总量本质上在可能的编码符号数量的最小值之中，这导致它需要接近于最小数量的编码符号去恢复所有k个输入符号。

参考文献：略