里德-所罗门码

**里德 - 所羅門碼**（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) （頁面存檔備份，存於網際網路檔案館）