今天的主题是喷泉码，或者称为“无率码”。喷泉码是将一些数据，例如文件，转化为一个有效的任意数量的编码包的方法，这样只要你接收到稍大于信源数据包数量的编码包的子集，就可以恢复信源数据。换句话说，你创建了一个编码数据的“喷泉”，只要接收端接收到足够的“水滴”，就可以恢复文件，而不管它们接到哪一个遗漏了哪一个。
让喷泉码如此知名的原因是，它允许你在有损连接(比如说因特网)的情况下传输文件，而且传输过程不依赖于你是否知道丢包率，也不需要接收端反馈哪些数据包丢失了。可以看到在很多场景，从通过广播媒介传送一个静态文件，比如点播电视，到在多源并行下载中传播文件包，像BitTorrent那样，喷泉码都得到了很好的应用。
虽然从根本上喷泉码惊人地简单。它有许多种类，但是在本文中我们只介绍最简单的——LT码，或者Luby变换码。LT码生成编码包的步骤如下：
1、在 l 和 k 的之间随机选取一个数字 d，d 代表文件中块的数量。我们将会在后面的内容中讨论如何选取最佳的d。
2、从文件中随机选取 d 块，并把它们组合起来。这里我们可以用异或运算来组合这些块。
3、传送合并的块，同时发送它由哪些块构成的信息。
这些非常简单是不是?主要依赖于我们怎么选取块的数量并组合起来(叫做度分布)，在接下来我们会简短的介绍一下。你可以从上面的描述中看到有些编码块最后只由单一源码块组成，而大部分将由多个源码块组成。
另外一个可能不是立刻显现的事情是，虽然我们确实不得不让接收端知道输出码块由哪些码块合并产生的，我们不需要详细地发送那个列表。如果发送端和接收端使用相同的伪随机数生成器(pseudo-random number generator，PRNG)，我们可以用一个随机选择的种子来生成PRNG，并且用这个来选择度和该组源码块。然后我们只需要在发送编码块的同时发送种子，我们的接收端可以用相同的过程来重建我们使用过的源码块列表。
解码的过程有一点复杂，但是没有很复杂：
1、重建用于生成编码块的源码块列表。
2、对于列表中的每一个源码块，如果已经解码了，将它和编码块做异或运算，并且把它从源码块列表中移除。
3、如果在列表剩下至少两个源码块，将编码块加入到一个等候区。
4、如果在列表中只剩下一个源码块，我们已经成功的把另一个源码块解码了，那么把它加入到已解码文件中，迭代等候列表，重复以上过程直到有编码块包含它。
让我们通过一个译码实例来更清晰说明这个过程。假设我们收到5个编码块，每个长度是一个字节，并且我们知道每个源码块由哪些构成。我们可以用图来表示数据，如下所示：
左边的结点代表我们收到的编码块，右边的节点代表源码块。我们收到的第一结点0×48只由一个源码块(第一个源码块)构成，所以已经知道是哪个块。沿着指向第一个源码块箭头的反向，可以看到第二个和第三个编码块都只依赖于第一个源码块和另外一个源码块，由于我们知道第一个源码块，我们可以对它们做异或运算，如下图所示：
重复以上过程，我们可以看到我们现在有了足够的信息来解码第四个编码块，它依赖于第二个和第三个源码块，而这两个我们现在都知道了。对它们做异或运算，可以得到第五个也是最后一个源码块，如下所示：
最后，我们可以解码最后剩下的源码块，得到剩余的信息：
应该承认的是这是一个非常特殊的例子，这个例子刚好接收到我们在译码这个信息时需要的块，没有剩余的，并且是一个非常简单的顺序，但是这个例子很好的演示算法的原理。我确定你可以看到这个算法应用到大规模码块和大规模文件中会相当简单。