Agfdhyk

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

里德-所罗门码被广泛的应用于各种商业用途，最显著的是在CD、DVD和蓝光光盘上的使用；在数据传输中，它也被用于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个唯一的确定点表示一个阶数至少为k-1的多项式。

发送者表明一个在有限域中的k-1阶的多项式，它表示k个数据点。这个多项式就根据它在各点的赋值被“编码”，实际传送的是这些值。在传输中，一些值会被破坏。所以，实际发送的点不止k个。只要正确地接收了足量的数值，接收方就可以推算出原始多项式，进而译出原始数据。

同样的，我们可以通过插值来修正曲线。RS码可以将一组有错误序列的信息码转换到找回画出原始曲线的多项式的系数。

数学公式

给定一个有限域F和多项式环F[x]，令n和k满足1≤k≤n≤|F|{displaystyle 1leq kleq nleq |F|}.选择F中的n个确定元素，记作{x1,x2,…,xn}{displaystyle {x_{1},x_{2},dots ,x_{n}}}.码本C是通过计算F中每个xi{displaystyle x_{i}}的阶数小于k的多项式得到的值，即

C={(f(x1),f(x2),…,f(xn))|f∈F[x],deg⁡(f)<k}.{displaystyle mathbf {C} =left{left(f(x_{1}),f(x_{2}),dots ,f(x_{n})right)|fin F[x],operatorname {deg} (f)<kright}.}

C是[n,k,n−k+1]{displaystyle [n,k,n-k+1]}码;换句话说，是F中长为n，维为k，最小汉明距离为n-k+1的线性码。

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

注意

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

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

RS码与BCH码的关系

1968年，Berlekamp发现了一种BCH码解码算法。由于RS码可以看作是BCH码的特例，该算法也可用于解码RS码。

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

RS码的两种定义的等价性

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

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

严格的说，令

p(x)=v0+v1x+v2x2+⋯+vn−1xn−1{displaystyle p(x)=v_{0}+v_{1}x+v_{2}x^{2}+dots +v_{n-1}x^{n-1}},

q(x)=f0+f1x+f2x2+⋯+fn−1xn−1{displaystyle q(x)=f_{0}+f_{1}x+f_{2}x^{2}+dots +f_{n-1}x^{n-1}}

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

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

• 当且仅当p(x){displaystyle p(x)}的次数小于k{displaystyle k}（由于f0,…,fn1{displaystyle f_{0},ldots ,f_{n_{1}}}是p(x){displaystyle p(x)}的值），


• 当且仅当如果i=k,...,n−1{displaystyle i=k,...,n-1}，vi=0{displaystyle v_{i}=0}，


• 当且仅当对所有的i=1,...,n−k{displaystyle i=1,...,n-k}，q(αi)=0{displaystyle q(alpha ^{i})=0}（由于q(αi)=nvn−i{displaystyle q(alpha ^{i})=nv_{n-i}}）,


• 当且仅当(f0,…,fn1){displaystyle (f_{0},ldots ,f_{n_{1}})}是RS码在第二种定义方式下的码字。

这样，两种定义方式的等价性便得到了证明。

历史

性质

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

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

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