噴泉編碼是一種刪除編碼，與物理層信道編碼不同，它以符號(比特組)為編碼單位。
基本介紹
- 中文名：噴泉編碼
- 類型：編碼
- 分類：刪除編碼
- 編碼單位：符號（比特組）
- 分為：LT碼、Raptor碼
- 特點：符號可用圖中的節點表示
簡介,主要分類,LT碼,Raptor碼,RU碼,
簡介
噴泉編碼是一種刪除編碼，與物理層信道編碼不同，它以符號(比特組)為編碼單位。在用二分圖描述編碼時，符號可用圖中的節點表示，因此在後面的敘述中我們將節點、符號和包這幾個概念視作同義。我們稱待編碼的原始符號為輸入符號或輸入節點，編碼後得到的符號為編碼符號或編碼節點。
主要分類
LT碼
M. Luby提出的LT（Luby Transform）碼是第一個可以實用的噴泉編碼，它是基於不規則稀疏二分圖構造出來的一種非系統碼。其編碼算法如下：
1．假設輸入符號個數為 ，編碼器首先在1～ 範圍任選一個服從某一分布的整數 作為該編碼符號的度
2．在所有輸入符號中隨機均勻地選取 個符號作為該編碼符號的鄰節點符號
3．將這 個輸入符號求異或，得到一個編碼符號
所有的編碼符號都是採用這一流程獨立生成的。
LT碼的解碼採用疊代的方法進行。在解碼的每一步，解碼器都在編碼符號集合中尋找度為1的符號，從而直接恢復出它們所連線的輸入符號，然後將這些輸入符號與跟它們有連線的編碼符號進行異或並將結果取代該編碼符號原來的值，完成之後刪去它們之間的連線關係，並相應地修改編碼符號的度。重複上述過程直至不存在度為1的符號為止。如果所有輸入符號都被恢復則解碼成功，否則解碼失敗。
LT碼的單位符號的編碼和解碼平均算術複雜度（符號異或操作）均為 ，比經典的RS碼大為降低（RS碼為 ）。收端平均只需接收略大於 個編碼符號( + )即可以 的機率成功解碼。
成功解碼必須的編碼符號個數與原始輸入符號之比的小數部分稱為解碼開銷（overhead）。LT碼實際上是通過略為增加了一些解碼開銷（RS碼的解碼開銷為0）來降低編解碼複雜度。
Raptor碼
Raptor碼是LT碼的改進版。它首先對原始信息進行預編碼，然後採用一個弱化的LT碼對數據進行編碼並傳送。弱化LT碼能以很高的機率恢復出大多數符號，而剩餘的符號依靠預編碼恢復。通過聯合最佳化這兩部分編碼的碼率和參數，Raptor可以在相同解碼開銷下實現更高解碼成功率。
Raptor碼的單位符號的編碼和解碼平均算術複雜度為 ，其中 是解碼開銷。因此Raptor碼的單位編解碼複雜度是與碼長成線性關係，比LT碼的對數關係又有所進步。
