里德-所罗门编码（Reed-Solomon Codes）

简介

里德-所罗门编码是一种纠错码，被广泛使用在通信领域。主要原理是在传输数据的同时，也传输一定量的校验信息，当传输出现少量错误时，可以用这些信息恢复出原信息。

必要知识

群，环，域

参考相关资料，不作详述。

线性分组码

所谓分组，就是将长度待传输串分成个长度的串（），将每个长度的串分进行编码，得到长度编码后的串（），再以一定的规则连接起来进行传输。分组并不是编码的一部分，在编码前可以以任意方式进行分组，只要求进行编码的串大小为。

所谓线性，就是若为编码过程，那么有性质，当然，这里的加法和乘法运算都是域中定义的运算，和一般的加法和乘法可能不同。

线性分组码可以用矩阵来表示，比如线性分组码的编码过程可以看作是生成矩阵与信息的乘法运算：

若发送信息为，误码为，那么接收信息为，其关系为：

有校验矩阵，要求，校验过程可以看作是校验矩阵与收到信息的乘法，其中称为伴随矩阵：

即：

所以中包含了误码的信息，用可以进行译码。

系统码

系统码是一种线性分组码，其中的前个元素和相同。

系统码可以用生成多项式表示，的一般形式为：

其中属于编码中元素所在的域，在计算机中常用的域为（BCH码）, （RS码）等。

类似地，也可以将信息写成多项式形式：

系统码的编码方式可以用下式概括：

从上式可以得出一条性质：

系统码的生成多项式不能随意选取，而是要根据以下定理：

定理 对于任意一个元素在域上的系统码，其生成多项式一定可以整除（其中为码长）。反之，对于的任意一个因式组合乘积，都是一个系统码的生成多项式。

有了这个定理，就很容易找到生成多项式，从而构造系统码了。

编码过程

选择生成多项式

里德-所罗门编码是在域上，长度为的编码。

根据有限域的性质，对于任意，都有（），即，所以的所有元素都是的根，而每个元素都不同。所以（为生成元）：

里德-所罗门编码取其中连续的个因式，组成生成多项式。一般从或开始选取。

比如，在域上，取前两个因式，就可以得到生成多项式：

编码

有了生成多项式，就可以使用一般方式进行编码了。不作详述。

值得注意的一点：中的一个元素具体形式是多项式，在计算机编码中可以直接使用作为编码的一位。在这种情况下，需要为这个域选取合适的生成多项式。

例子

在中，有8个元素，分别为，标记为。定义此域的生成多项式为，令生成多项式等于即得，定义生成元为。所以有以下关系：

设计一个长度为8，纠错码长为2的码，其生成多项式为：

如果待编码的内容为bit的串011010001000100100，进行如下处理：

将串看作多项式，使用公式：

前6项为原串，后2项为纠错位。纠错位用多项式求余即可做到：

所以纠错位为，编码完成。

解码过程

计算伴随式

编码之后的信息经过信道后被接收，得到，设错误为，则：

如果编码使用生成多项式：

因为

所以

所以

记

称为伴随式，其中只包含了误码信息，和原码无关。

解码

错误多项式可以记作错误位置和错误值的组合：

则

设：

定义错误位置函数：

所以

即

在两边同乘：

将这个式子相加：

于是有个线性方程，这个变量，即可求得错误位置函数。通过测试可以得到所有的错误位置。得到错误位置后，代入的定义式中得到另一个方程组，解得所有的错误值。

例子

使用和编码时相同的有限域和生成多项式，编码长度为8，纠错码长为2。接收信息为

将信息转为多项式：

设有1个错误（）：

所以

所以

所以

所以

解码得到的信息为

总结

里德-所罗门编码是一种简单常用的纠错码，只需要实现一些基本的有限域操作就可以完成编码和解码。

除了标准形式，码长和元素空间长度相等以外，里德-所罗门编码还可以有其他形式，比如在编解码时设前位为0的编长为的码，在此不再详述。