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

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

本站内容版权属于本人。转载须告知本人,写明出处,并在文首提供指向本站对应文章的链接。
本文链接:里德-所罗门编码(Reed-Solomon Codes)

简介

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

必要知识

群,环,域

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

线性分组码

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

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

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

若发送信息为,误码为,那么接收信息为,其关系为:

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

即:

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

系统码

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

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

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

类似地,也可以将信息写成多项式形式:

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

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

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

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

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

编码过程

选择生成多项式

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

根据有限域的性质,对于任意,都有),即,所以的所有元素都是的根,而每个元素都不同。所以(为生成元):

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

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

编码

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

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

例子

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

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

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

将串看作多项式,使用公式:

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

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

解码过程

计算伴随式

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

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

因为

所以

所以

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

解码

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

定义错误位置函数:

所以

在两边同乘

将这个式子相加:

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

例子

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

将信息转为多项式:

设有1个错误():

所以

所以

所以

所以

解码得到的信息为

总结

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

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

发表评论

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

*

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