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

简介

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

必要知识

群，环，域

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

线性分组码

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

所谓线性，就是若$C_{(n)}=f(M_{(k)})$为编码过程，那么$f(M)$有性质$f(aM_1+bM_2)=af(M_1)+bf(M_2)$，当然，这里的加法和乘法运算都是域中定义的运算，和一般的加法和乘法可能不同。

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

$$C_{n \times 1}=G_{n \times k} \cdot M_{k \times 1}$$

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

$$R = C + E$$

有校验矩阵$H$，要求$H \cdot G = \mathbf{0}$，校验过程可以看作是校验矩阵$H$与收到信息$R$的乘法，其中$S$称为伴随矩阵：

$$S_{n-k \times 1} = H_{n-k \times n} \cdot R_{n \times 1}$$

即：

$$S = HR = H(C + E) = HGM + HE = (HG)M + HE = HE$$

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

系统码

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

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

$$g(x)=a_0+a_1x+a_2x^2+\cdots+a_{n-k}x^{n-k}$$

其中$a_i (i=0,1,...,n-k)$属于编码$C$中元素所在的域，在计算机中常用的域为$GF(2)$（BCH码）, $GF(2^8)$（RS码）等。

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

$$M(x)=m_0+m_1x+m_2x^2+\cdots+m_kx^k$$

$$C(x)=c_0+c_1x+c_2x^2+\cdots+c_nx^n$$

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

$$C(x)=M(x)x^{n-k}-(M(x)x^{n-k}\mod g(x))$$

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

$$C(x) \equiv 0 \pmod{g(x)}$$

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

定理 对于任意一个元素在域$GF(q)$上的系统码，其生成多项式$g(x)$一定可以整除$x^{n-1}-1$（其中$n$为码长）。反之，对于$x^{n-1}-1$的任意一个因式组合乘积，都是一个系统码的生成多项式。

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

编码过程

选择生成多项式

里德-所罗门编码是在$GF(2^m)$域上，长度为$2^m$的编码。

根据有限域的性质，对于任意$a \in GF(2^m)$，都有$a^{n-1}=1$（$n=2^m$），即$a^{n-1}-1=0$，所以$GF(2^m)$的所有元素都是$x^{n-1}-1=0$的根，而每个元素都不同。所以（$\alpha$为生成元）：

$$x^{n-1}-1=(x-1)(x-\alpha)(x-\alpha^2)\cdots(x-\alpha^{n-2})$$

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

比如，在$GF(2^8)$域上，取前两个因式，就可以得到生成多项式：

$$g(x)=(x-1)(x-\alpha)=x^2-\alpha^25x+\alpha$$

编码

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

值得注意的一点：$GF(2^m)$中的一个元素具体形式是多项式$a_0+a_1x+a_2x^2+\cdots+a_{m-1}x^{m-1}, a_i \in \{0, 1\}, i=0, 1, \dots, m-1$，在计算机编码中可以直接使用$a_i$作为编码的一位。在这种情况下，需要为这个域选取合适的生成多项式。

例子

在$GF(2^3)$中，有8个元素，分别为$0, 1, x, x+1, \dots, x^2+x+1$，标记为$000, 001, 010, 011, \dots, 111$。定义此域的生成多项式为$X^3+X+1$，令生成多项式等于$0$即得$x^3=x+1$，定义生成元为$x$。所以有以下关系：

$$0=000, 1=001, \alpha=010, \alpha^2=100, \alpha^3=011, \alpha^4=110, \alpha^5=111, \alpha^6=101$$

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

$$g(x)=(x-1)(x-\alpha)=x^2-(1+\alpha)x+\alpha=x^2+\alpha^3x+\alpha$$

如果待编码的内容为$3\times6=18$bit的串011010001000100100，进行如下处理：

$$011010001000100100 \to 011,010,001,000,100,100 \to \alpha^3, \alpha, 1, 0, \alpha^2, \alpha^2$$

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

$$C(x)=M(x)x^{n-k}-(M(x)x^{n-k}\mod g(x))$$

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

$$(\alpha^3x^7+\alpha x^6+x^5+\alpha^2x^3+\alpha^2x^2) \mod (x^2+\alpha^3x+\alpha)=\alpha^6x+\alpha^6$$

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

解码过程

计算伴随式

编码之后的信息$C(x)$经过信道后被接收，得到$R(x)$，设错误为$E(x)$，则：

$$R(x)=C(x)+E(x)$$

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

$$g(x)=(x-\alpha^{p})(x-\alpha^{p+1})(x-\alpha^{p+2})\cdots(x-\alpha^{p+n-k-1})$$

因为

$$C(x) \equiv 0 \pmod{g(x)}$$

所以

$$C(\alpha^i)=0, i=p,p+1,\dots,p+n-k-1$$

所以

$$R(\alpha^i)=C(\alpha^i)+E(\alpha^i)=E(\alpha^i), i=p,p+1,\dots,p+n-k-1$$

记

$$S_i=R(\alpha^i)=E(\alpha^i), i=p,p+1,\dots,p+n-k-1$$

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

解码

错误多项式$E(x)$可以记作错误位置$X_i(x)=x^{e_i}$和错误值$Y_i$的组合：

$$E(x)=\sum_{i=1}^vY_iX_i(x)$$

则

$$S_j=\sum_{i=1}^vY_iX_i(\alpha)^j, j=p,p+1,\dots,p+v-1$$

设$X_1=X_1(\alpha)$：

$$S_j=\sum_{i=1}^vY_iX_i^j, j=p,p+1,\dots,p+v-1$$

定义错误位置函数：

$$\Lambda(x)=\prod_{i=1}^v(1-xX_i)=1+\sum_{k=1}^v\Lambda_kx^k$$

所以

$$\Lambda(X_i^{-1})=0, i=1,2,\dots,v$$

即

$$1+\sum_{k=1}^v\Lambda_kX_i^{-k}=0, i=1,2,\dots,v$$

在两边同乘$Y_iX_i^{j+v}$：

$$Y_iX_i^{j+v}+Y_iX_i^{j+v}\sum_{k=1}^v\Lambda_kX_i^{-k}=0, i=1,2,\dots,v, j=p,p+1,\dots,p+v-1$$

将这$v$个式子相加：

$$\sum_{i=1}^v(Y_iX_i^{j+v}+Y_iX_i^{j+v}\sum_{k=1}^v\Lambda_kX_i^{-k})=0, j=p,p+1,\dots,p+v-1$$

$$\sum_{i=1}^vY_iX_i^{j+v}+\sum_{i=1}^v(Y_iX_i^{j+v}\sum_{k=1}^v\Lambda_kX_i^{-k})=0, j=p,p+1,\dots,p+v-1$$

$$\sum_{i=1}^vY_iX_i^{j+v}+\sum_{k=1}^v(\Lambda_k\sum_{i=1}^vY_iX_i^{j+v-k})=0, j=p,p+1,\dots,p+v-1$$

$$S_{j+v}+\sum_{k=1}^v\Lambda_kS_{j+v-k}=0, j=p,p+1,\dots,p+v-1$$

于是有$v$个线性方程，$\Lambda_1, \dots, \Lambda_v$这$v$个变量，即可求得错误位置函数$\Lambda(x)$。通过测试$\Lambda(\alpha^i)=0$可以得到所有的错误位置。得到错误位置后，代入$S_j$的定义式中得到另一个方程组，解得所有的错误值。

例子

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

$$011,010,001,101,100,100,101,101$$

将信息转为多项式：

$$R(x)=\alpha^3x^7+\alpha x^6+x^5+\alpha^6x^4+\alpha^2x^3+\alpha^2x^2+\alpha^6x+\alpha^6$$

$$S_0=\alpha^6, S_1=\alpha^3$$

设有1个错误（$v=1$）：

$$S_1+\Lambda_1S_0=0$$

所以

$$\Lambda(x)=1+\alpha^4x$$

所以

$$X_1=\alpha^4$$

所以

$$Y_1=S_0=\alpha^6$$

所以

$$E(x)=Y_1X_1(x)=\alpha^6x^4$$

解码得到的信息为

$$011,010,001,000,100,100$$

总结

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

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