今天的主題是噴泉碼，或者稱為“無率碼”。噴泉碼是將一些數(shù)據(jù)，例如文件，轉化為一個有效的任意數(shù)量的編碼包的方法，這樣只要你接收到稍大于信源數(shù)據(jù)包數(shù)量的編碼包的子集，就可以恢復信源數(shù)據(jù)。換句話說，你創(chuàng)建了一個編碼數(shù)據(jù)的“噴泉”，只要接收端接收到足夠的“水滴”，就可以恢復文件，而不管它們接到哪一個遺漏了哪一個。
讓噴泉碼如此知名的原因是，它允許你在有損連接(比如說因特網(wǎng))的情況下傳輸文件，而且傳輸過程不依賴于你是否知道丟包率，也不需要接收端反饋哪些數(shù)據(jù)包丟失了?？梢钥吹皆诤芏鄨鼍?，從通過廣播媒介傳送一個靜態(tài)文件，比如點播電視，到在多源并行下載中傳播文件包，像BitTorrent那樣，噴泉碼都得到了很好的應用。
雖然從根本上噴泉碼驚人地簡單。它有許多種類，但是在本文中我們只介紹最簡單的——LT碼，或者Luby變換碼。LT碼生成編碼包的步驟如下：
1、在 l 和 k 的之間隨機選取一個數(shù)字 d，d 代表文件中塊的數(shù)量。我們將會在后面的內容中討論如何選取最佳的d。
2、從文件中隨機選取 d 塊，并把它們組合起來。這里我們可以用異或運算來組合這些塊。
3、傳送合并的塊，同時發(fā)送它由哪些塊構成的信息。
這些非常簡單是不是?主要依賴于我們怎么選取塊的數(shù)量并組合起來(叫做度分布)，在接下來我們會簡短的介紹一下。你可以從上面的描述中看到有些編碼塊最后只由單一源碼塊組成，而大部分將由多個源碼塊組成。
另外一個可能不是立刻顯現(xiàn)的事情是，雖然我們確實不得不讓接收端知道輸出碼塊由哪些碼塊合并產(chǎn)生的，我們不需要詳細地發(fā)送那個列表。如果發(fā)送端和接收端使用相同的偽隨機數(shù)生成器(pseudo-random number generator，PRNG)，我們可以用一個隨機選擇的種子來生成PRNG，并且用這個來選擇度和該組源碼塊。然后我們只需要在發(fā)送編碼塊的同時發(fā)送種子，我們的接收端可以用相同的過程來重建我們使用過的源碼塊列表。
解碼的過程有一點復雜，但是沒有很復雜：
1、重建用于生成編碼塊的源碼塊列表。
2、對于列表中的每一個源碼塊，如果已經(jīng)解碼了，將它和編碼塊做異或運算，并且把它從源碼塊列表中移除。
3、如果在列表剩下至少兩個源碼塊，將編碼塊加入到一個等候區(qū)。
4、如果在列表中只剩下一個源碼塊，我們已經(jīng)成功的把另一個源碼塊解碼了，那么把它加入到已解碼文件中，迭代等候列表，重復以上過程直到有編碼塊包含它。
讓我們通過一個譯碼實例來更清晰說明這個過程。假設我們收到5個編碼塊，每個長度是一個字節(jié)，并且我們知道每個源碼塊由哪些構成。我們可以用圖來表示數(shù)據(jù)，如下所示：
左邊的結點代表我們收到的編碼塊，右邊的節(jié)點代表源碼塊。我們收到的第一結點0×48只由一個源碼塊(第一個源碼塊)構成，所以已經(jīng)知道是哪個塊。沿著指向第一個源碼塊箭頭的反向，可以看到第二個和第三個編碼塊都只依賴于第一個源碼塊和另外一個源碼塊，由于我們知道第一個源碼塊，我們可以對它們做異或運算，如下圖所示：
重復以上過程，我們可以看到我們現(xiàn)在有了足夠的信息來解碼第四個編碼塊，它依賴于第二個和第三個源碼塊，而這兩個我們現(xiàn)在都知道了。對它們做異或運算，可以得到第五個也是最后一個源碼塊，如下所示：
最后，我們可以解碼最后剩下的源碼塊，得到剩余的信息：
應該承認的是這是一個非常特殊的例子，這個例子剛好接收到我們在譯碼這個信息時需要的塊，沒有剩余的，并且是一個非常簡單的順序，但是這個例子很好的演示算法的原理。我確定你可以看到這個算法應用到大規(guī)模碼塊和大規(guī)模文件中會相當簡單。