LT码（Luby transform code）设计与分析

本文来自 BitRipple 的演讲，由CEO Michael Luby 带来，主题为LT码的设计与分析。

首先 Michael 带大家回顾了纠删码（Erasure code）技术。纠删码是在比特擦除（而不是比特错误）假设下的前向纠错（FEC）码，它将k个符号的消息转换成一个较长的带有n个符号的消息（码字），使得可以从n 个符号的子集中恢复原始消息。

然后，Michael 介绍了 LT 码的基础版：复制编码（copy encoding）与复制解码（copy decoding)技术。复制编码就是简单地从源中随机选择一个符号并且复制传输，在解码端可以建立源符号与编码符号的图，对接受到的符号进行恢复，如果对应源符号已经被恢复，就丢弃这个接收到的符号。这种编码方式非常简单，它的问题在于接收开销（reception overhead)极大，为了回复 K 个符号的源，期望接收符号数的额外开销为 K*(ln(K)-1) 个，解码复杂度为 K*ln(K)，可以接受。

在编码理论中，喷泉码是一类纠删码，其特性是可以从给定的一组源符号中生成潜在无限的编码符号序列，从而理想情况下原始源符号可以是从大小等于或仅略大于源符号数量的编码符号的任何子集中恢复。如果可以从任何k 个成功接收的编码符号中恢复原始k 个源符号，则喷泉码是最佳的。

LT码（Luby transform code）是第一类实用的喷泉码，是接近最优的纠删码。它们由本文演讲者Michael Luby于 1998 年发明并于 2002 年发布。与其他一些喷泉码一样，LT码依赖于稀疏二部图来交换接收开销以换取编码和解码速度。LT码的显着特点是采用了一种基于异或运算的特别简单的算法对消息进行编码和解码。LT码根据一个度概率分布表进行类似复制编解码的工作，LT码的具体设计细节可以在本文演讲中获取，此处不再赘述。LT码通过设计LT度概率分布表来达到低接收开销，理想的LT解码过程具有零接收开销的特性，而解码复杂度与复制解码相同，为 K*ln(K)。

LT码是设计后续更高级喷泉码的基础。LT码之后的下一代是Raptor码（参见IETF RFC 5053或IETF RFC 6330），它们具有线性时间编码和解码。Raptor码基本上是基于LT码的，Raptor码的编码使用两个编码阶段，其中第二个阶段是LT编码。类似地，使用 Raptor码进行解码主要依赖于LT解码，但 LT 解码与更高级的解码技术混合使用。IETF RFC 6330 中指定的 RaptorQ 代码是最先进的喷泉代码，与仅使用 LT 代码相比，它具有非常出色的解码概率和性能。Rq SDK是一种高性能的商用级SDK实现的RaptorQ代码，由Michael Luby共同创立的公司BitRipple提供，在受挑战的网络上实现大规模数据分发。

详细关于 RaptorQ码 的信息可参考论文：

Amin Shokrollahi and Michael Luby (2011). "Raptor Codes". Foundations and Trends in Communications and Information Theory. Now Publishers. 6 (3–4): 213–322. doi:10.1561/0100000060.