里德－所羅門碼
里德-所羅門碼
里德-所羅門碼（又稱里所碼，Reed-solomon codes，簡稱RS codes）是一種前向錯誤更正的通道編碼，對由校正過採樣數據所產生的有效多項式。編碼過程首先在多個點上對這些多項式求冗餘，然後將其傳輸或者存儲。對多項式的這種超出必要值得採樣使得多項式超定（過限定）。當接收器正確的收到足夠的點后，它就可以恢復原來的多項式，即使接收到的多項式上有很多點被雜訊干擾有損。
里德-所羅門碼被廣泛的應用於各種商業用途，最顯著的是在CD、DVD和藍光光碟上的使用；在數據傳輸中，它也被用於DSL和WiMAX；廣播系統中DVB和ATSC也閃現著它的身影；在計算機科學里，它是RAID 6標準的重要成員。
里德-所羅門碼是定長碼。這意味著一個固定長度輸入的數據將被處理成一個固定長度的輸出數據。在最常用的（255,223）里所碼中，223個裡德-所羅門輸入符號（每個符號有8個比特）被編碼成255個輸出符號。
• 大多數里所錯誤校正編碼流程是成體系的（Systematic code）。這意味著輸出的碼字中有一部分包含著輸入數據的原始形式。
• 符號大小為8位的里所碼迫使碼長（編碼長度）最長為255個符號。
• 標準的（255,223）里所碼可以在每個碼字中校正最多16個裡所符號的錯誤。由於每個符號事實上是8個比特，這意味著這個碼可以校正最多16個短爆發性錯誤。
里德-所羅門碼，如同卷積碼一樣，是一種透明碼。這代表如果通道符號在隊列的某些地方被反轉，解碼器一樣可以工作。解碼結果將是原始數據的補充。但是，里所碼在縮短後會失去透明性。在縮短了的碼中，“丟失”的比特需要被0或者1替代，這由數據是否需要補足而決定。（如果符號這時候反轉，替代的0需要變成1）。於是乎，需要在里所解碼前對數據進行強制性的偵測決定（“是”或者“補足”）。
在里德-所羅門數據編碼背後的核心可以形象化的表示為多項式。這種碼依靠一個代數理論，這個代數理論說明任何k個唯一的確定點表示一個階數至少為k-1的多項式。
發送者表明一個在有限域中的k-1階的多項式，它表示k個數據點。這個多項式就根據它在各點的賦值被“編碼”，實際傳送的是這些值。在傳輸中，一些值會被破壞。所以，實際發送的點不止k個。只要正確地接收了足量的數值，接收方就可以推算出原始多項式，進而譯出原始數據。
同樣的，我們可以通過插值來修正曲線。RS碼可以將一組有錯誤序列的信息碼轉換到找回畫出原始曲線的多項式的係數。
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
在實際應用中，RS碼經常使用大小為2 的有限域。在這種情況下，每個符號都包含有m比特的信息。發送者將編碼后的分組發送給接受者，每個分組通常含有2 個符號。
RS碼的這種性質使得它非常適合糾正傳輸系統中的突發錯誤。這是由於不論一個符號中有多少個比特發生錯誤，都只發生了一個符號錯誤。而對於不發生突發錯誤的傳輸系統，RS碼的性能通常不如普通的二元碼。
基本信息
- 中文名
- 里德－所羅門碼
- 外文名
- Reed-solomon codes
- 別名
- 里所碼
目錄