里德-所罗门编码(Reed-Solomon Codes)

里德-所罗门编码(Reed-Solomon Codes)

本站内容版权属于本人。转载须告知本人,写明出处,并在文首提供指向本站对应文章的链接。
本文链接:里德-所罗门编码(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$$的码,在此不再详述。

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

*

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据