裡德-所羅門碼

裡德-所羅門碼是一種前向錯誤更正的通道編碼，對由校正過取樣資料所產生的有效多項式。編碼過程首先在多個點上對這些多項式求冗餘，然後將其傳輸或者儲存。對多項式的這種超出必要值的取樣使得多項式超定。當接收器正確地收到足夠的點後，它就可以恢復原來的多項式，即使接收到的多項式上有很多點被噪聲干擾失真。裡德-所羅門碼被廣泛地應用於各種商業用途，最顯著的是在 CD、DVD、藍光光碟和QR code上的使用；在資料傳輸中，它也被用於 DSL 和 WiMAX；廣播系統中 DVB 和 ATSC 也閃現著它的身影；在計算機科學裡，它是 RAID 6 標準的重要成員。概述.裡德-所羅門碼是定長碼。這意味著一個固定長度輸入的資料將被處理成一個固定長度的輸出資料。在最常用的被編碼成255個輸出符號。裡德-所羅門碼，如同卷積碼一樣，是一種透明碼。這代表如果通道符號在佇列的某些地方被反轉，解碼器一樣可以工作。解碼結果將是原始資料的補充。但是，裡所碼在縮短後會失去透明性。在縮短了的碼中，「丟失」的位元需要被0或者1替代，這由資料是否需要補足而決定。。定義.概述.在裡德-所羅門資料編碼背後的核心可以形象化的表示為多項式。這種碼依靠一個代數理論，這個代數理論說明任何長度為k的碼可唯一表示成一個階數(degree)至多為k-1的多項式。傳送者表明一個在有限域中的k-1階的多項式，它表示k個數據點。這個多項式就根據它在各點的賦值被“編碼”，實際傳送的是這些值。 在資訊傳輸中，一些值會被破壞。所以，實際傳送的點不止k個。只要正確地接收了足量的數值，接收方就可以推算出原始多項式，進而譯出原始資料。同樣的，我們可以透過插值來修正曲線。RS碼可以將一組有錯誤序列的資訊碼轉換到找回畫出原始曲線的多項式的係數。數學公式.給定一個有限域F和多項式環F[x]，令n和k滿足formula_1.選擇F中的n個確定元素，記作formula_2.碼本C是透過計算F中每個formula_3的階數小於k的多項式得到的值，即formula_4C是formula_5碼;換句話說，是F中長為n，維度為k，最小漢明距離為n-k+1的線性碼。一個RS碼滿足以上的形式，並遵循:集合formula_2是formula_7域中所有非零元素組成的集合。注意.RS碼在實際應用中，常常使用一個有formula_9個元素的有限域F。這樣，每個符號就可以表示為一個m位元的數值。傳送方以編碼塊的形式傳送資料點，編碼塊的符號數量為formula_10個。這樣，一個用於8位元符號的RS碼每塊有formula_11個符號。 (在位元組型計算機系統普及的今天，這個數字很實用。)編碼塊中的資料符號k是一個設計引數，formula_12。在一個n = 255的符號塊中，常用formula_13的8位元資料符加上32個8位元校驗符來編碼，用formula_14表示，每塊最多可以校正16個符號錯誤。由有限域中的非零元素構成的集合formula_15可以寫作formula_16，formula_17是一個"單位的n次本原根"。習慣上按照這種順序對RS碼進行編碼。由於formula_18，並且對於每個多項式formula_19，函式formula_20是與它同次的多項式，因而RS碼是迴圈的。RS碼與BCH碼的關係.1968年，埃爾溫·伯利坎普發現了一種BCH碼解碼演算法。由於RS碼可以看作是BCH碼的特例，該演算法也可用於解碼RS碼。透過RS碼的另一種定義方法，可以很容易的看出RS碼是BCH碼的一種特例。令有限域formula_21大小為formula_22, formula_17為formula_7的formula_25次原單位根，亦即formula_18，且對所有小於formula_25的正整數formula_28,均有formula_29。給定formula_30, formula_31是RS碼的碼字當且僅當formula_32是多項式formula_33的根。這樣，很容易可以看出RS碼是一種多項式碼，也就是BCH碼。生成多項式formula_34為formula_32的最小多項式，而碼字為能夠整除多項式formula_34的多項式。RS碼的兩種定義的等價性.RS碼的兩種定義方式有著非常大的區別，而它們的等價關係並不是顯而易見的。在第一種定義中，碼字是多項式的值，而在第二種定義中，碼字是多項式的係數。另外，第一種定義要求多項式具有特定的比較小的冪次，而在第二種定義中，多項式需要有特定的根。這兩種定義的等價性可以透過有限域上的離散傅立葉變換來證明。離散傅立葉變換建立起了多項式的係數與值之間的對偶關係。這種對偶關係可以不嚴格的概述如下：令formula_19和formula_38為兩個次數小於formula_25的多項式。如果多項式 formula_19的在formula_41處的值是formula_38的係數，那麼formula_38在這些點上的取值在經過乘以一個特定的係數和重新排列以後就成為了formula_19的係數。嚴格的說，令formula_47,formula_48同時假定formula_19和formula_38為離散傅立葉變換對，那麼formula_19和formula_38的係數和取值有如下關係：對所有的formula_42，formula_54並且formula_55.這樣，我們可以得出formula_56是滿足RS碼第一種定義方式的碼字這樣，兩種定義方式的等價性便得到了證明。歷史.裡德所羅門碼由麻省理工學院林肯實驗室的工作人員 Irving S.Reed 和 Gustave Solomon 於1960年開發出來。他們開創性的文章題目為"Polynomial Codes over Certain Finite Fields".(Reed &amp; Solomon 1960)。Reed和Solomon文章中描述的原始編碼方案使用基於要編碼的資訊的可變多項式，其中編碼器和解碼器只知道要編碼的一組固定值的子集生成潛在多項式，選擇最流行的多項式作為正確的多項式，除了最簡單的情況，這種方案几乎對於所有人都是不切實際的。最初的解決辦法是透過將原始方案更改為基於編碼器和解碼器都已知的固定多項式的類BCH碼方案，但後來發展了基於原始方案的實用解碼器，儘管比 BCH 方案慢。這樣做的結果是，有兩種主要型別的裡德-所羅門碼，一種使用原始編碼方案，一種使用 BCH 編碼方案。同樣在1960年，在Zierler於1960年1月的麻省理工學院林肯實驗室報告中，以及後來在1961年6月的一篇論文中，描述了由 Daniel Gorenstein 和 Neal Zierler 開發的BCH碼的實用固定多項式解碼器。Gorenstein-Zierler 解碼器和 BCH 碼的相關工作在 W. Wesley Peterson 的《Error Correcting Codes》(1961)一書中進行了描述。到1963年認識到裡德-所羅門碼可以使用使用固定生成多項式的 BCH 方案，使此類碼成為一種特殊的BCH碼，但基於原始編碼的裡德-所羅門碼方案，不是一種BCH碼，並且根據評估點的集合，它們甚至不是迴圈碼。1969 年，埃爾溫·伯利坎普和James Massey開發了一種改進的 BCH 方案解碼器，此後被稱為伯利坎普－梅西演算法解碼演算法。1975 年，Yasuo Sugiyama在擴充套件歐幾里得演算法的基礎上開發了另一種改進的 BCH 方案解碼器。1977 年，Reed-Solomon 碼以級聯糾錯碼的形式在旅行者計劃中實現。 1982 年，在大批次消費產品中的首次商業應用出現在光碟上，其中使用了兩個交錯的裡德-所羅門碼。今天，裡德-所羅門碼在數字儲存裝置和數字通訊標準中得到廣泛應用，儘管它們正慢慢被 Bose-Chaudhuri-Hocquenghem (BCH) 碼取代。例如，裡德-所羅門碼與卷積內碼一起用於數字影片廣播 (DVB) 標準 DVB-S，但 BCH 碼與 LDPC 一起在其後繼者 DVB-S2 中使用。1986 年，開發了一種稱為伯利坎普－韋爾奇演算法的原始方案解碼器。1996 年，Madhu Sudan 和其他人開發了稱為列表解碼器或軟解碼器的原始方案解碼器的變體，並且這些型別的解碼器的工作仍在繼續——uruswami-Sudan 列表解碼演算法。2002年，Shuhong Gao基於擴充套件歐幾里得演算法開發了另一種獨創的方案解碼器。性質.RS碼是一個formula_67碼，是一種定義在有限域formula_7上的長度為formula_25,資訊長度為formula_58，最短漢明距離為formula_71的線性分組碼。由於這種編碼滿足Singleton界，因此它是一種最大距離可分碼。由於碼長為formula_25資訊長度為formula_58的碼的最大漢明距離為formula_71，所以在這種意義下RS碼是一種最優的編碼方法。RS碼的糾錯能力由最短漢明距離決定，為formula_71。如果預先並不知道錯誤的位置，RS碼最多可以糾正formula_76個錯誤。而在某些情況下，我們可以預知錯誤的位置，此時RS碼最多可以糾正formula_77個錯誤。如果我們可以預先知道formula_78個錯誤位置，而此外還有formula_79個未知的錯誤位置，那麼在滿足formula_80的情況下，我們可以完全糾正這些錯誤。在實際應用中，RS碼經常使用大小為formula_9的有限域。在這種情況下，每個符號都包含有formula_82位元的資訊。傳送者將編碼後的分組傳送給接受者，每個分組通常含有formula_83個符號。例如，定義在formula_84上的RS碼每個分組包含有formula_85個符號。由於計算機通常以位元組為單位來處理資料，因此定義在formula_84的RS碼非常流行。設計引數formula_58需要滿足formula_88，對於定義在formula_84上的RS碼，通常選擇formula_90。這個RS碼包含有223個數據符號和32個校驗符號，表示為formula_91RS碼，它最多可以糾正16個符號錯誤。RS碼的這種性質使得它非常適合糾正傳輸系統中的突發錯誤。這是由於不論一個符號中有多少個位元發生錯誤，都只發生了一個符號錯誤。而對於不發生突發錯誤的傳輸系統，RS碼的效能通常不如普通的二元碼，