本文链接:里德-所罗门编码(Reed-Solomon Codes)
简介
里德-所罗门编码是一种纠错码,被广泛使用在通信领域。主要原理是在传输数据的同时,也传输一定量的校验信息,当传输出现少量错误时,可以用这些信息恢复出原信息。
必要知识
群,环,域
参考相关资料,不作详述。
线性分组码
所谓分组,就是将长度待传输串分成
个
长度的串(
),将每个
长度的串分进行编码,得到
长度编码后的串(
),再以一定的规则连接起来进行传输。分组并不是编码的一部分,在编码前可以以任意方式进行分组,只要求进行编码的串大小为
。
所谓线性,就是若为编码过程,那么
有性质
,当然,这里的加法和乘法运算都是域中定义的运算,和一般的加法和乘法可能不同。
线性分组码可以用矩阵来表示,比如线性分组码的编码过程可以看作是生成矩阵与信息
的乘法运算:
若发送信息为,误码为
,那么接收信息为
,其关系为:
有校验矩阵,要求
,校验过程可以看作是校验矩阵
与收到信息
的乘法,其中
称为伴随矩阵:
即:
所以中包含了误码
的信息,用
可以进行译码。
系统码
系统码是一种线性分组码,其中的前
个元素和
相同。
系统码可以用生成多项式表示,
的一般形式为:
其中属于编码
中元素所在的域,在计算机中常用的域为
(BCH码),
(RS码)等。
类似地,也可以将信息写成多项式形式:
系统码的编码方式可以用下式概括:
从上式可以得出一条性质:
系统码的生成多项式不能随意选取,而是要根据以下定理:
定理 对于任意一个元素在域上的系统码,其生成多项式
一定可以整除
(其中
为码长)。反之,对于
的任意一个因式组合乘积,都是一个系统码的生成多项式。
有了这个定理,就很容易找到生成多项式,从而构造系统码了。
编码过程
选择生成多项式
里德-所罗门编码是在域上,长度为
的编码。
根据有限域的性质,对于任意,都有
(
),即
,所以
的所有元素都是
的根,而每个元素都不同。所以(
为生成元):
里德-所罗门编码取其中连续的个因式,组成生成多项式。一般从
或
开始选取。
比如,在域上,取前两个因式,就可以得到生成多项式:
编码
有了生成多项式,就可以使用一般方式进行编码了。不作详述。
值得注意的一点:中的一个元素具体形式是多项式
,在计算机编码中可以直接使用
作为编码的一位。在这种情况下,需要为这个域选取合适的生成多项式。
例子
在中,有8个元素,分别为
,标记为
。定义此域的生成多项式为
,令生成多项式等于
即得
,定义生成元为
。所以有以下关系:
设计一个长度为8,纠错码长为2的码,其生成多项式为:
如果待编码的内容为bit的串011010001000100100,进行如下处理:
将串看作多项式,使用公式:
前6项为原串,后2项为纠错位。纠错位用多项式求余即可做到:
所以纠错位为,编码完成。
解码过程
计算伴随式
编码之后的信息经过信道后被接收,得到
,设错误为
,则:
如果编码使用生成多项式:
因为
所以
所以
记
称为伴随式,其中只包含了误码信息,和原码无关。
解码
错误多项式可以记作错误位置
和错误值
的组合:
则
设:
定义错误位置函数:
所以
即
在两边同乘:
将这个式子相加:
于是有个线性方程,
这
个变量,即可求得错误位置函数
。通过测试
可以得到所有的错误位置。得到错误位置后,代入
的定义式中得到另一个方程组,解得所有的错误值。
例子
使用和编码时相同的有限域和生成多项式,编码长度为8,纠错码长为2。接收信息为
将信息转为多项式:
设有1个错误():
所以
所以
所以
所以
解码得到的信息为
总结
里德-所罗门编码是一种简单常用的纠错码,只需要实现一些基本的有限域操作就可以完成编码和解码。
除了标准形式,码长和元素空间长度相等以外,里德-所罗门编码还可以有其他形式,比如在编解码时设前位为0的编长为
的码,在此不再详述。