里德-所羅門碼

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

里德-所羅門碼被廣泛地應用於各種商業用途，最顯著的是在CD、DVD、藍光光盤和QR code上的使用；在數據傳輸中，它也被用於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的碼可唯一表示成一個階數(degree)至多為k-1的多項式。

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

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

數學公式

給定一個有限域F和多項式環F[x]，令n和k滿足$1\leq k\leq n\leq |F|$.選擇F中的n個確定元素，記作$\{x_{1},x_{2},\dots ,x_{n}\}$.碼本C是通過計算F中每個$x_{i}$的階數小於k的多項式得到的值，即

$\mathbf {C} =\left\{\left(f(x_{1}),f(x_{2}),\dots ,f(x_{n})\right)|f\in F[x],\operatorname {deg} (f)<k\right\}.$

C是$[n,k,n-k+1]$碼;換句話說，是F中長為n，維度為k，最小漢明距離為n-k+1的線性碼。

一個RS碼滿足以上的形式，並遵循:集合$\{x_{1},x_{2},\dots ,x_{n}\}$是$F$域中所有非零元素組成的集合（因而,$n=|F|-1$）。

注意

RS碼在實際應用中，常常使用一個有$2^{m}$個元素的有限域F。這樣，每個符號就可以表示為一個m比特的數值。發送方以編碼塊的形式發送數據點，編碼塊的符號數量為$n=2^{m}-1$個。這樣，一個用於8比特符號的RS碼每塊有$n=2^{8}-1=255$個符號。 (在字節型計算機系統普及的今天，這個數字很實用。)編碼塊中的數據符號k是一個設計參數，$k<n$。在一個n = 255的符號塊中，常用$k=223$的8比特數據符加上32個8比特校驗符來編碼，用$(n,k)=(255,223)$表示，每塊最多可以校正16個符號錯誤。

由有限域中的非零元素構成的集合$\{x_{1},...,x_{n}\}$可以寫作$\{1,\alpha ,\alpha ^{2},...,\alpha ^{n-1}\}$，$\alpha$是一個"單位的n次本原根"。習慣上按照這種順序對RS碼進行編碼。由於$\alpha ^{n}=1$，並且對於每個多項式$p(x)$，函數$p(\alpha x)$是與它同次的多項式，因而RS碼是循環的。

RS碼與BCH碼的關係

1968年，埃爾溫·伯利坎普發現了一種BCH碼解碼算法。由於RS碼可以看作是BCH碼的特例，該算法也可用於解碼RS碼。

通過RS碼的另一種定義方法，可以很容易的看出RS碼是BCH碼的一種特例。令有限域$F$大小為$q$, $\alpha$為$F$的$n$次原單位根，亦即$\alpha ^{n}=1$，且對所有小於$n$的正整數$i$,均有$\alpha ^{i}\neq 1$。給定$1\leq k\leq n$, $(f_{0},f_{1},...,f_{n-1})$是RS碼的碼字當且僅當$\alpha ,\alpha ^{2},...,\alpha ^{n-k}$是多項式$p(x)=f_{0}+f_{1}x+...+f_{n-1}x^{n-1}$的根。這樣，很容易可以看出RS碼是一種多項式碼，也就是BCH碼。生成多項式$g(x)$為$\alpha ,\alpha ^{2},...,\alpha ^{n-k}$的最小多項式，而碼字為能夠整除多項式$g(x)$的多項式。

RS碼的兩種定義的等價性

RS碼的兩種定義方式有着非常大的區別，而它們的等價關係並不是顯而易見的。在第一種定義中，碼字是多項式的值，而在第二種定義中，碼字是多項式的係數。另外，第一種定義要求多項式具有特定的比較小的冪次，而在第二種定義中，多項式需要有特定的根。

這兩種定義的等價性可以通過有限域上的離散傅立葉變換來證明。離散傅立葉變換建立起了多項式的係數與值之間的對偶關係。這種對偶關係可以不嚴格的概述如下：令$p(x)$和$q(x)$為兩個次數小於$n$的多項式。如果多項式 $p(x)$的在$x=\alpha ^{i}$（$i=0,\dots ,n-1$, $\alpha$是1的n次本原單位根）處的值是$q(x)$的係數，那麼$q(x)$在這些點上的取值在經過乘以一個特定的係數和重新排列以後就成為了$p(x)$的係數。

嚴格的說，令

$p(x)=v_{0}+v_{1}x+v_{2}x^{2}+\dots +v_{n-1}x^{n-1}$,

$q(x)=f_{0}+f_{1}x+f_{2}x^{2}+\dots +f_{n-1}x^{n-1}$

同時假定$p(x)$和$q(x)$為離散傅立葉變換對，那麼$p(x)$和$q(x)$的係數和取值有如下關係：對所有的$i=0,\dots ,n-1$，$f_{i}=p(\alpha ^{i})$並且$\textstyle v_{i}={\frac {1}{n}}q(\alpha ^{n-i})$.

這樣，我們可以得出$(f_{0},\ldots ,f_{n_{1}})$是滿足RS碼第一種定義方式的碼字

• 當且僅當$p(x)$的次數小於$k$（由於$f_{0},\ldots ,f_{n_{1}}$是$p(x)$的值），
• 當且僅當如果$i=k,...,n-1$，$v_{i}=0$，
• 當且僅當對所有的$i=1,...,n-k$，$q(\alpha ^{i})=0$（由於$q(\alpha ^{i})=nv_{n-i}$）,
• 當且僅當$(f_{0},\ldots ,f_{n_{1}})$是RS碼在第二種定義方式下的碼字。

這樣，兩種定義方式的等價性便得到了證明。

歷史

里德所羅門碼由麻省理工學院林肯實驗室的工作人員 Irving S.Reed 和 Gustave Solomon 於1960年開發出來。他們開創性的文章題目為"Polynomial Codes over Certain Finite Fields".(Reed & Solomon 1960)。Reed和Solomon文章中描述的原始編碼方案使用基於要編碼的信息的可變多項式，其中編碼器和解碼器只知道要編碼的一組固定值（評估點）。最初的理論解碼器根據接收到的消息的 n（編碼消息長度）值中的 k（未編碼消息長度）的子集生成潛在多項式，並選擇最常用的多項式作為正確的多項式，除了最簡單的情況，這種方案幾乎對於所有人而言都是不切實際的。最初解決這個問題的辦法是將原始方案改為類似 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年（或可能更早），J. J. Stone（和其他人）認識到里德-所羅門碼可以使用使用固定生成多項式的 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 等人開發出了原始方案解碼器的變體，稱為列表解碼器或軟解碼器，有關這類解碼器的工作仍在繼續——參見Guruswami-Sudan 列表解碼算法（英文維基百科詞條：Guruswami–Sudan list decoding algorithm）。

2002年，Shuhong Gao基於擴展歐幾里得算法開發了另一種獨創的方案解碼器。

性質

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$個符號。例如，定義在$GF(2^{8})$上的RS碼每個分組包含有$255=2^{8}-1$個符號。由於計算機通常以字節為單位來處理數據，因此定義在$GF(2^{8})$的RS碼非常流行。設計參數$k$需要滿足$k<n$，對於定義在$GF(2^{8})$上的RS碼，通常選擇$k=223$。這個RS碼包含有223個數據符號和32個校驗符號，表示為$(255,223)$RS碼，它最多可以糾正16個符號錯誤。

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

參考資料

• F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Code, New York: North-Holland Publishing Company, 1977.
• Irving S. Reed and Xuemin Chen, Error-Control Coding for Data Networks", Boston: Kluwer Academic Publishers, 1999.

外部連結

• Schifra Open Source C++ Reed–Solomon Codec （頁面存檔備份，存於網際網路檔案館）
• Henry Minsky's RSCode library, Reed–Solomon encoder/decoder （頁面存檔備份，存於網際網路檔案館）
• A thesis on Algebraic soft-decoding of Reed–Solomon codes （頁面存檔備份，存於網際網路檔案館）. It explains the basics as well.
• Matlab implementation of errors-and-erasures Reed-Solomon decoding
• FEC (Forward Erasure Encoding) Open Source Library (with Python bindings) （頁面存檔備份，存於網際網路檔案館）