维基百科

盧比變換碼

盧比變換碼（LT碼，英文：Luby transform codes, LT codes）是第一個最接近完善的抹除碼（erasure correcting codes）的實用湧泉碼（fountain codes），由Michael Luby （页面存档备份，存于互联网档案馆）在1998年發明並於2002年發表。LT碼一個顯著的特徵是採用簡單且基礎的異或（XOR，）來編碼（encode）以及解碼（decode）。

LT碼的另一個特徵是它rateless，由於它可以產生無限量的訊息封包，因此必須將接收到的封包進行解碼的百分比極小。而LT碼之所以屬於抹除碼之一的原因是它可以用在二進位抹去通道（英语：Binary_erasure_channel）（Binary erasure channel, BEC）上進行傳輸。

為何要使用LT碼 编辑

在傳統'抹去通道'（erasure channel）上的傳輸，通常得仰賴發送端以及接收端持續性的雙向溝通：

  • 發送端（sender）進行編碼（encode）以及傳送帶有訊息（message）的封包（packet）。
  • 接收端（receiver）這邊在收到每個封包時會對其進行評估，如果該封包可以被解碼（decode），則傳送一個確認（acknowledgment）給發送端；反之，丟棄毀壞的封包，並傳送請求讓發送端再次發送該封包。
  • 該雙向溝通會持訊進行值到所有訊息的封包都被成功傳送且解碼為止。

然而，在現今網路上，出現許多如多點傳輸（multicast）的情形，此時發送端不可能持續性地跟所有接收端一一確認封包傳遞與否，然而為維持傳輸的正確性，必須使用湧泉碼（fountain codes），特別是盧比變換碼（LT碼）這類型的方式傳輸：

  • 發送端同樣進行編碼（encode）以及傳送帶有訊息（message）的封包（packet）。
  • 接收端對每個收到的封包進行評估，如果出現錯誤，則丟棄該封包；反之則收納作為訊息的一部份。
  • 當接收端逐一收取封包直到擁有足夠且可以完整解碼（decode）的有效訊息時，才發送確認給發送端，停止傳送封包。

LT編碼（Encoding） 编辑

將待傳送的訊息分割成等長度的 個封包（packet），

  • 透過随机数產生器（random number generator）依特定的機率分布（probability distribution）產生一個整數degree d，且 ，代表著一組訊息需要包含的封包數量。
  • 接著在 組封包中，以離散型均勻分布（uniform distribution）的方式，選取d組封包出來。
  • 接下來將d組封包之間做異或（XOR）運算，因此要傳送的其中一個封包便是：

　　 

　　　　其中 是總共n組封包中被挑選出來的d組

  • 該傳送的封包前面還須附加一些額外訊息，包括整份訊息有多少個封包（n個）、是哪d個封包被做了XOR運算
  • 最後，一些形式的偵錯碼將被附加在封包的最後（可能是某種循環冗餘校驗（cyclic redundancy check）），該封包才會被進行傳輸。

以上這些步驟將不斷重複進行，直到接收端判斷該訊息已被完整接收且成功地解碼出來。

LT解碼（Decoding） 编辑

解碼過程中同樣使用"異或"（XOR,  ）來還原被編碼的訊息。

  • 如果當前這個封包格式錯誤（偵錯碼發生問題），或者該封包是個已處理過封包的複製品，丟棄該封包。
  • 排除以上情形，便可開始處理解碼程序；其工作原理是利用 的特性去逐步消去每個封包（packet）裡的degree，直到總共有n個degree為1的不同packet為止。範例如下：

　　　　 

　　 

　　 

　　 

參考資料 编辑

^ M.Luby, "LT Codes", The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. （页面存档备份，存于互联网档案馆）

取自“https://zh.wikipedia.org/w/index.php?title=盧比變換碼&oldid=69747024”