裏德-所羅門碼

裏德-所羅門碼（又稱裏所碼，Reed-solomon codes，簡稱RS codes）是一種前向錯誤更正的信道編碼，對由校正過採樣數據所產生的有效多項式。編碼過程首先在多個點上對這些多項式求冗餘，然後將其傳輸或者存儲。對多項式的這種超出必要值得采樣使得多項式超定（過限定）。當接收器正確的收到足夠的點後，它就可以恢復原來的多項式，即使接收到的多項式上有很多點被噪聲干擾有損。

裏德-所羅門碼被廣泛的應用於各種商業用途，最顯著的是在CD、DVD和藍光光盤上的使用；在數據傳輸中，它也被用於DSL和WiMAX；廣播系統中DVB和ATSC也閃現着它的身影；在計算機科學裏，它是RAID 6標準的重要成員。 ^[1] 

裏德-所羅門碼是定長碼。這意味着一個固定長度輸入的數據將被處理成一個固定長度的輸出數據。在最常用的（255,223）裏所碼中，223個裏德-所羅門輸入符號（每個符號有8個比特）被編碼成255個輸出符號。

裏德-所羅門碼，如同卷積碼一樣，是一種透明碼。這代表如果信道符號在隊列的某些地方被反轉，解碼器一樣可以工作。解碼結果將是原始數據的補充。但是，裏所碼在縮短後會失去透明性。在縮短了的碼中，“丟失”的比特需要被0或者1替代，這由數據是否需要補足而決定。（如果符號這時候反轉，替代的0需要變成1）。於是乎，需要在裏所解碼前對數據進行強制性的偵測決定（“是”或者“補足”）。 ^[1] 

在裏德-所羅門數據編碼背後的核心可以形象化的表示為多項式。這種碼依靠一個代數理論，這個代數理論説明任何k個唯一的確定點表示一個階數至少為k-1的多項式。

發送者表明一個在有限域中的k-1階的多項式，它表示k個數據點。這個多項式就根據它在各點的賦值被“編碼”，實際傳送的是這些值。在傳輸中，一些值會被破壞。所以，實際發送的點不止k個。只要正確地接收了足量的數值，接收方就可以推算出原始多項式，進而譯出原始數據。

同樣的，我們可以通過插值來修正曲線。RS碼可以將一組有錯誤序列的信息碼轉換到找回畫出原始曲線的多項式的係數。 ^[1] 

RS碼是一個[n,k,n-k+1]碼，是一種定義在有限域F上的長度為n，信息長度為k，最短漢明距離為n-k+1的線性分組碼。由於這種編碼滿足Singleton界，因此它是一種最大距離可分碼。由於碼長為n信息長度為k的碼的最大漢明距離為n-k+1，所以在這種意義下RS碼是一種最優的編碼方法。

RS碼的糾錯能力由最短漢明距離決定，為n-k+1。如果預先並不知道錯誤的位置，RS碼最多可以糾正(n-k)/2個錯誤。而在某些情況下，我們可以預知錯誤的位置（比如BEC信道），此時RS碼最多可以糾正n-k個錯誤。如果我們可以預先知道S個錯誤位置，而此外還有E個未知的錯誤位置，那麼在滿足2E+S<n-k的情況下，我們可以完全糾正這些錯誤。

在實際應用中，RS碼經常使用大小為2^m的有限域。在這種情況下，每個符號都包含有m比特的信息。發送者將編碼後的分組發送給接受者，每個分組通常含有2^m-1個符號。

RS碼的這種性質使得它非常適合糾正傳輸系統中的突發錯誤。這是由於不論一個符號中有多少個比特發生錯誤，都只發生了一個符號錯誤。而對於不發生突發錯誤的傳輸系統，RS碼的性能通常不如普通的二元碼。