里德-所罗门码

里德-所罗门码（Reed-solomon codes，簡稱里所码或 RS codes）是一种前向錯誤更正的信道编码，对由校正过采样数据所产生的有效多项式。编码过程首先在多个点上对这些多项式求冗余，然后将其传输或者存储。对多项式的这种超出必要值的采样使得多项式超定（过限定）。当接收器正确地收到足够的点后，它就可以恢复原来的多项式，即使接收到的多项式上有很多点被噪声干扰失真。

里德-所罗门码被广泛地应用于各种商业用途，最显著的是在 CD、DVD、蓝光光盘和QR code上的使用；在数据传输中，它也被用于 DSL 和 WiMAX；广播系统中 DVB 和 ATSC 也闪现着它的身影；在计算机科学里，它是 RAID 6 标准的重要成员。

概述

里德-所罗门码是定长码。这意味着一个固定长度输入的数据将被处理成一个固定长度的输出数据。在最常用的（255,223）里所码中，223个里德-所罗门输入符号（每个符号有8个位元）被编码成255个输出符号。

• 大多数里所错误校正编码流程是成体系的（Systematic code（英语：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满足${\displaystyle 1\leq k\leq n\leq |F|}$ .选择F中的n个确定元素，记作${\displaystyle \{x_{1},x_{2},\dots ,x_{n}\}}$ .码本C是通过计算F中每个${\displaystyle x_{i}}$ 的阶数小于k的多项式得到的值，即

${\displaystyle \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是${\displaystyle [n,k,n-k+1]}$ 码;换句话说，是F中长为n，维度为k，最小汉明距离为n-k+1的线性码。

一个RS码满足以上的形式，并遵循:集合${\displaystyle \{x_{1},x_{2},\dots ,x_{n}\}}$ 是${\displaystyle F}$ 域中所有非零元素组成的集合（因而,${\displaystyle n=|F|-1}$ ）。

注意

RS码在实际应用中，常常使用一个有${\displaystyle 2^{m}}$ 个元素的有限域F。这样，每个符号就可以表示为一个m比特的数值。发送方以编码块的形式发送数据点，编码块的符号数量为${\displaystyle n=2^{m}-1}$ 个。这样，一个用于8比特符号的RS码每块有${\displaystyle n=2^{8}-1=255}$ 个符号。 (在字节型计算机系统普及的今天，这个数字很实用。)编码块中的数据符号k是一个设计参数，${\displaystyle k<n}$ 。在一个n = 255的符号块中，常用${\displaystyle k=223}$ 的8比特数据符加上32个8比特校验符来编码，用${\displaystyle (n,k)=(255,223)}$ 表示，每块最多可以校正16个符号错误。

由有限域中的非零元素构成的集合${\displaystyle \{x_{1},...,x_{n}\}}$ 可以写作${\displaystyle \{1,\alpha ,\alpha ^{2},...,\alpha ^{n-1}\}}$ ，${\displaystyle \alpha }$ 是一个"单位的n次本原根"。习惯上按照这种顺序对RS码进行编码。由于${\displaystyle \alpha ^{n}=1}$ ，并且对于每个多项式${\displaystyle p(x)}$ ，函数${\displaystyle p(\alpha x)}$ 是与它同次的多项式，因而RS码是循环的。

RS码与BCH码的关系

1968年，埃尔温·伯利坎普发现了一种BCH码解码算法。由于RS码可以看作是BCH码的特例，该算法也可用于解码RS码。

通过RS码的另一种定义方法^[1]，可以很容易的看出RS码是BCH码的一种特例。令有限域${\displaystyle F}$ 大小为${\displaystyle q}$ , ${\displaystyle \alpha }$ 为${\displaystyle F}$ 的${\displaystyle n}$ 次原单位根，亦即${\displaystyle \alpha ^{n}=1}$ ，且对所有小于${\displaystyle n}$ 的正整数${\displaystyle i}$ ,均有${\displaystyle \alpha ^{i}\neq 1}$ 。给定${\displaystyle 1\leq k\leq n}$ , ${\displaystyle (f_{0},f_{1},...,f_{n-1})}$ 是RS码的码字当且仅当${\displaystyle \alpha ,\alpha ^{2},...,\alpha ^{n-k}}$ 是多项式${\displaystyle p(x)=f_{0}+f_{1}x+...+f_{n-1}x^{n-1}}$ 的根。这样，很容易可以看出RS码是一种多项式码，也就是BCH码。生成多项式${\displaystyle g(x)}$ 为${\displaystyle \alpha ,\alpha ^{2},...,\alpha ^{n-k}}$ 的最小多项式，而码字为能够整除多项式${\displaystyle g(x)}$ 的多项式。

RS码的两种定义的等价性

RS码的两种定义方式有着非常大的区别，而它们的等价关系并不是显而易见的。在第一种定义中，码字是多项式的值，而在第二种定义中，码字是多项式的系数。另外，第一种定义要求多项式具有特定的比较小的幂次，而在第二种定义中，多项式需要有特定的根。

这两种定义的等价性可以通过有限域上的离散傅立叶变换来证明。离散傅立叶变换建立起了多项式的系数与值之间的对偶关系。这种对偶关系可以不严格的概述如下：令${\displaystyle p(x)}$ 和${\displaystyle q(x)}$ 为两个次数小于${\displaystyle n}$ 的多项式。如果多项式 ${\displaystyle p(x)}$ 的在${\displaystyle x=\alpha ^{i}}$ （${\displaystyle i=0,\dots ,n-1}$ , ${\displaystyle \alpha }$ 是1的n次本原单位根）处的值是${\displaystyle q(x)}$ 的系数，那么${\displaystyle q(x)}$ 在这些点上的取值在经过乘以一个特定的系数和重新排列以后就成为了${\displaystyle p(x)}$ 的系数。

严格的说，令

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

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

同时假定${\displaystyle p(x)}$ 和${\displaystyle q(x)}$ 为离散傅立叶变换对，那么${\displaystyle p(x)}$ 和${\displaystyle q(x)}$ 的系数和取值有如下关系：对所有的${\displaystyle i=0,\dots ,n-1}$ ，${\displaystyle f_{i}=p(\alpha ^{i})}$ 并且${\displaystyle \textstyle v_{i}={\frac {1}{n}}q(\alpha ^{n-i})}$ .

这样，我们可以得出${\displaystyle (f_{0},\ldots ,f_{n_{1}})}$ 是满足RS码第一种定义方式的码字

• 当且仅当${\displaystyle p(x)}$ 的次数小于${\displaystyle k}$ （由于${\displaystyle f_{0},\ldots ,f_{n_{1}}}$ 是${\displaystyle p(x)}$ 的值），
• 当且仅当如果${\displaystyle i=k,...,n-1}$ ，${\displaystyle v_{i}=0}$ ，
• 当且仅当对所有的${\displaystyle i=1,...,n-k}$ ，${\displaystyle q(\alpha ^{i})=0}$ （由于${\displaystyle q(\alpha ^{i})=nv_{n-i}}$ ）,
• 当且仅当${\displaystyle (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码的实用固定多项式解码器^[2]。Gorenstein-Zierler 解码器和 BCH 码的相关工作在 W. Wesley Peterson 的《Error Correcting Codes》(1961)一书中进行了描述^[3]。到1963年（或更早），J. J. Stone（和其他人）认识到里德-所罗门码可以使用使用固定生成多项式的 BCH 方案，使此类码成为一种特殊的BCH码^[4]，但基于原始编码的里德-所罗门码方案，不是一种BCH码，并且根据评估点的集合，它们甚至不是循环码。

1969 年，埃尔温·伯利坎普和James Massey开发了一种改进的 BCH 方案解码器，此后被称为伯利坎普－梅西算法解码算法。

1975 年，Yasuo Sugiyama在扩展欧几里得算法的基础上开发了另一种改进的 BCH 方案解码器。^[5]

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基于扩展欧几里得算法开发了另一种独创的方案解码器。^[6]

性质

RS码是一个${\displaystyle [n,k,n-k+1]}$ 码，是一种定义在有限域${\displaystyle F}$ 上的长度为${\displaystyle n}$ ,信息长度为${\displaystyle k}$ ，最短汉明距离为${\displaystyle n-k+1}$ 的线性分组码。由于这种编码满足Singleton界，因此它是一种最大距离可分码。由于码长为${\displaystyle n}$ 信息长度为${\displaystyle k}$ 的码的最大汉明距离为${\displaystyle n-k+1}$ ，所以在这种意义下RS码是一种最优的编码方法。

RS码的纠错能力由最短汉明距离决定，为${\displaystyle n-k+1}$ 。如果预先并不知道错误的位置，RS码最多可以纠正${\displaystyle (n-k)/2}$ 个错误。而在某些情况下，我们可以预知错误的位置（比如BEC信道），此时RS码最多可以纠正${\displaystyle n-k}$ 个错误。如果我们可以预先知道${\displaystyle S}$ 个错误位置，而此外还有${\displaystyle E}$ 个未知的错误位置，那么在满足${\displaystyle 2E+S<n-k}$ 的情况下，我们可以完全纠正这些错误。

在实际应用中，RS码经常使用大小为${\displaystyle 2^{m}}$ 的有限域。在这种情况下，每个符号都包含有${\displaystyle m}$ 比特的信息。发送者将编码后的分组发送给接受者，每个分组通常含有${\displaystyle 2^{m}-1}$ 个符号。例如，定义在${\displaystyle GF(2^{8})}$ 上的RS码每个分组包含有${\displaystyle 255=2^{8}-1}$ 个符号。由于计算机通常以字节为单位来处理数据，因此定义在${\displaystyle GF(2^{8})}$ 的RS码非常流行。设计参数${\displaystyle k}$ 需要满足${\displaystyle k<n}$ ，对于定义在${\displaystyle GF(2^{8})}$ 上的RS码，通常选择${\displaystyle k=223}$ 。这个RS码包含有223个数据符号和32个校验符号，表示为${\displaystyle (255,223)}$ RS码，它最多可以纠正16个符号错误。

RS码的这种性质使得它非常适合纠正传输系统中的突发错误。这是由于不论一个符号中有多少个比特发生错误，都只发生了一个符号错误。而对于不发生突发错误的传输系统，RS码的性能通常不如普通的二元码，

参见

参考资料

1. Lidl, Rudolf; Pilz, Günter. Applied Abstract Algebra 2nd. Wiley. 1999: 226. 
2. D. Gorenstein and N. Zierler, "A class of cyclic linear error-correcting codes in p^m symbols", J. SIAM, vol. 9, pp. 207-214, June 1961
3. Error Correcting Codes by W_Wesley_Peterson, 1961
4. Error Correcting Codes by W_Wesley_Peterson, second edition, 1972
5. Yasuo Sugiyama, Masao Kasahara, Shigeichi Hirasawa, and Toshihiko Namekawa. A method for solving key equation for decoding Goppa codes. Information and Control, 27:87–99, 1975.
6. http://www.math.clemson.edu/~sgao/papers/RS.pdf （页面存档备份，存于互联网档案馆）^[裸網址]

• 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.
• FEC (Forward Erasure Encoding) Open Source Library (with Python bindings) （页面存档备份，存于互联网档案馆）