里德-所罗门编码（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$$的码，在此不再详述。