盧比變換碼（LT碼，英文：Luby transform codes, LT codes）是第一個最接近完善的抹除碼(erasure correcting codes)的實用湧泉碼(fountain codes），由Michael Luby在1998年發明並於2002年發表。
基本介紹
- 中文名：盧比變換碼
- 外文名：Luby transform codes
特徵,盧比變換碼（LT碼）,編碼（coding）,解碼（decoding),抹除碼（erasure correcting codes）,湧泉碼（又稱噴泉碼，fountain codes）,為何要使用湧泉碼,湧泉碼的基本思想,使用湧泉碼之後的訊息傳輸過程,數字噴泉碼和分組碼的差別,湧泉碼與盧比變換碼,套用,
特徵
LT碼的另一個特徵是rateless,即它的碼率不存在。由於它可以產生無限量的訊息封包，因此必須將接收到的封包進行解碼的百分比極小。而LT碼之所以屬於抹除碼之一的原因是它可以用在二進制抹去通道(Binary erasure channel, BEC）上進行傳輸。
盧比變換碼（LT碼）
編碼（coding）
將待傳送的訊息分割成等長度的n個封包（packet），透過隨機數產生器（randomnumbergenerator）依特定的機率分布（probabilitydistribution）產生一個整數degreed，且1<=d<=n，代表著一組訊息需要包含的封包數量。
接著在n組封包中，以離散型均勻分布（uniformdistribution）的方式，選取d組封包出來。
接下來將d組封包之間做異或（XOR）運算，因此要傳送的其中一個封包便是：M1⊕M2⊕…⊕Md，其中M1,M2,…Md是總共n組封包中被挑選出來的d組。
該傳送的封包前面還須附加一些額外訊息，包括整份訊息有多少個封包（n個）、是哪d個封包被做了XOR運算。
最後，一些形式的偵錯碼將被附加在封包的最後（可能是某種循環冗餘校（cyclicredundancycheck）），該封包才會被進行傳輸。
以上這些步驟將不斷重複進行，直到接收端判斷該訊息已被完整接收且成功地解碼出來。
解碼（decoding)
解碼過程中同樣使用"異或"（XOR,⊕）來還原被編碼的訊息。
如果當前這個封包格式錯誤（偵錯碼發生問題），或者該封包是個已處理過封包的複製品，丟棄該封包。
排除以上情形，便可開始處理解碼程式；其工作原理是利用A⊕A=0的特性去逐步消去每個封包里的degree，直到總共有n個degree為1的不同封包為止。
對封包Mk解碼的範例如下:
(M1⊕…⊕Md)⊕(M1⊕…⊕Mk-1⊕Mk+1⊕…Md)
=M1⊕M1⊕…⊕Mk-1⊕Mk-1⊕Mk⊕Mk+1⊕Mk+1⊕…⊕Md⊕Md
=0⊕…⊕0⊕Mk⊕0⊕…⊕0
=Mk
重複以上步驟，就可以完成解碼過程。
抹除碼（erasure correcting codes）
抹除碼是相對於複製而言的。使用複製的情況，我們對一個檔案做幾個副本，放在不同的地方，再去管理它們。
抹除碼的思路，簡單來說，是將檔案轉換成一個碎片集合，每一個碎片很小，碎片被打散分布到一組伺服器資源池裡。只要存留的碎片數量足夠，就可以合成為原本的檔案。這可以在保持原本的數據健壯性的基礎上大大減少需要的存儲空間。
湧泉碼（又稱噴泉碼，fountain codes）
為何要使用湧泉碼
在傳統“抹去通道”上的傳輸，通常得仰賴傳送端以及接收端持續性的雙向溝通：首先傳送端進行編碼以及傳送帶有訊息的封包，然後接收端這邊在收到每個封包時會對其進行評估，如果該封包可以被解碼，則傳送一個確認（ACK信息）給傳送端；反之，丟棄毀壞的封包，並傳送請求讓傳送端再次傳送該封包。該雙向溝通會持訊進行值到所有訊息的封包都被成功傳送且解碼為止。
然而當用戶數很大時，可能出現一種情況：用戶傳送的ACK信息占據了絕大多數的網路資源，使得正常的通信不能順利進行，這種情況稱為"反饋風暴"。
在這種情況下，重傳方式完全不起作用，前向糾錯方法的效率也不高。而湧泉碼就可以有效地解決反饋風暴問題，並且採用隨機編碼，保證每次傳送的信息對接收節點是有用信息。
湧泉碼的基本思想
湧泉碼的基本思想是單個源節點S不停的向周圍的多個桶K(表示多個接收端的快取)傳送"水滴"(表示數據包)，當一個桶里的水滿了以後(快取滿)，它才向源節點傳送一個反饋。每次傳送的水滴是一幀裡面隨機選擇的一些包組合起來的包，這種組合可以是線性的，也可以是非線性的，在桶里的水滿了以後進行相應的解碼，當源節點收到所有桶的ACK以後，再傳送新的一幀，否則繼續傳送組合包。湧泉碼還可以有效提高信道容量及網路的魯棒性。
所謂湧泉碼，是指這種編碼的傳送端可以由k個原始分組生成任意數量的編碼分組，接收端只要收到k(1+ε)個編碼分組的任意子集，即可通過解碼以高機率成功(和ε有關)恢復全部原始分組，精心設計的數字噴泉碼不僅擁有很小的解碼開銷ε，而且具有簡單的編解碼方法和很小的編解碼複雜度。可以看到，上述編碼過程就如同源源不斷產生水滴(編碼分組)的噴泉(編碼器)，而我們只要用杯子(解碼器)接收足夠數量的水滴，即可達到飲用(成功解碼)的目的,而不必關心是那一點水(編碼分組)流入你的杯中。正因為如此，這種編碼被稱為湧泉碼(FountainCodes)。需要特別指出的，湧泉碼與LDPC碼的最大區別在於其中不存在碼長n的定義，或者說碼長趨於無窮;相應地，碼率R=k/n的定義也不存在，因此湧泉碼也被稱為無率碼(RatelessCodes)。
使用湧泉碼之後的訊息傳輸過程
傳送端同樣進行編碼以及傳送帶有訊息的封包。接收端對每個收到的封包進行評估，如果出現錯誤，則丟棄該封包；反之則收納作為訊息的一部分。當接收端逐一收取封包直到擁有足夠且可以完整解碼的有效訊息時，才傳送確認給傳送端，停止傳送封包。
數字噴泉碼和分組碼的差別
1、對於傳統的分組碼，碼的結構在信息傳輸之前確定;而數字噴泉碼可"線上(online)"編碼產生。
2、 當採用傳統的分組碼傳輸信息時，傳送者與接收者之間都知道所採用的編碼方法;而對於數字噴泉碼情況並不是這樣。由於編碼的輸出符號與數據的傳輸並發產生，因此，為了從輸出符號恢復原信息，必須將採用的編碼方法與輸出符號一併傳輸。在符號對應於包的網路環境中，可以給每個傳輸包增加用來表示該輸出符號是由那些輸入符號產生的頭信息，於是，描寫輸入與輸出符號之間關係的信息在接收端就可通過數據包頭來獲得，或者可通過傳送端與接收端之間依賴於套用的同步方法來獲得。
湧泉碼與盧比變換碼
盧比變換碼，即LT碼，是噴泉碼的第一次具體實現，是由MichaelLuby提出的，後來AminShokrollahi對LT碼做出了改進，提出了第二類噴泉碼，即Raptor碼。
