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

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

简介

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

必要知识

群,环,域

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

线性分组码

所谓分组,就是将m长度待传输串分成Nk长度的串(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}=1n=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-1x-\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=18bit的串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_vv个变量,即可求得错误位置函数\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的码,在此不再详述。

发表评论

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

*