RS编码原理分析

  • 更新时间: 2015-11-14
  • 来源: 原创或网络
  • 浏览数: 88次
  • 字数: 17189
  • 发表评论

1 GF(2m)域

RS(Reed-Solomon)码是在伽罗华域(Galois Field,GF)中运算的,先简要介绍一下伽罗华域.

域在RS 编码理论中起着至关重要的作用。

简单点说域GF(2m)有 2m(设 2m= q )个符号且具有以下性质:
域中的每个元素都可以用a0,a1,a2,am-1 的和来表示。除0、1外其余所有元素由本原多项式 P(x)生成。本原多项式p(x)的特性是RS编码原理分析,by 5lulu.com得到的余式等于0。
在纠错编码运算过程中,加、减、乘和除的运算是在伽罗华域中进行
在GF域上的加、减、乘、除运算定义如下(GF(2
4)为例):
1、 加、减运算均定义为元素的二进制表示方式进行异或运算。如:a8+a10 ,先查表,
将其化为二进制表示方式得0101+0111,经过异或运算得0010,再查表得a1,即:a8+a10= a1 。 减运算与加运算相同,即:a8-a10= a1
2、 乘运算定义为元素的指数相加后进行模15运算后所得的新元素,但若有一个元素 为0,则相乘结果为0。如:a7*a13,(7+13) mod 15=5,即a7*a13= a5
3、 除运算定义为元素的指数相减后进行模15运算后所得的新元素(指数为正数)。若被除数为0,则结果为0。如:a5/a9,(5-9)mod 15=11,即a5/a9= a11

-------------------------------------------------------------

GF(24) 的所有元素

例:m=4,本原多项式 p(x)=x4+x+1求GF(24) 的所有元素:

因为α为p(x)的根得到a4+a+1=0 或a4=a+1 (根据运算规则)

由此可以得到域的所有元素

元素 多项式表示 二进制表示 十六进制表示
0 0 0000 0
a0 1 0001 1
a1 a 0010 2
a2 a2 0100 3
a3 a3 1000 4
a4 a+1 0011 8
a5 a2+a  mod p(a) 0110 3
a6 a3+a2 mod p(a) 1100 C
a7 a3+a+1 mod p(a) 1011 B
a8 a2+1 mod p(a) 0101 5
a9 a3 +a  mod p(a)

1010

A


-------------------------------------------------------------

CD-ROM中的数据、地址、校验码等都可以看成是属于GF(2m) = GF(28)中的元素或称符号。GF(28)表示域中有256个元素,除0,1之外的254个元素由本原多项式P(x)生成。本原多项式P(x)的特性是RS编码原理分析,by 5lulu.com得到的余式等于0。CD-ROM用来构造GF(28)域的P(x)是



P(x)=x8+x4+x3+x2+1                                      (13-1)
而GF(28)域中的本原元素为
α = (0 0 0 0 0 0 1 0)
下面以一个较简单例子说明域的构造。
[例16.1] 构造GF(23)域的本原多项式P(x)假定为
P(x)=x3+x+1
α定义为P(x) = 0的根,即
α3+α+1 = 0
和α3 = α+1
GF(23)中的元素可计算如下:
0 mod(α3+α+1) = 0
α0 mod(α3+α+1) = α0 = 1
α1 mod(α3+α+1) = α1
α2 mod(α3+α+1) = α2
α3 mod(α3+α+1) = α+1
α4 mod(α3+α+1) = α2
α5 mod(α3+α+1) = α21+1
α6 mod(α3+α+1) = α2+1
α7 mod(α3+α+1) = α0
α8 mod(α3+α+1) = α1
……

用二进制数表示域元素得到表16-01所示的对照表

表16-01 GF(23)域中与二进制代码对照表, P(x)=x3+x+1
GF(23)域元素 二进制对代码
0 (000)
α0 (001)
α1 (010)
α2 (100)
α3 (011)
α4 (110)
α5 (111)
α6 (101)

这样一来就建立了GF(23)域中的元素与3位二进制数之间的一一对应关系。用同样的方法可建立GF(28)域中的256个元素与8位二进制数之间的一一对应关系。在纠错编码运算过程中,加、减、乘和除的运算是在伽罗华域中进行。

现仍以GF(23)域中运算为例:

加法例:α03 = 001+011
= 010 = α1

减法例:与加法相同

乘法例:α5·α4 = α(5+4) mod7
= α2
除法例:α53 = α2
α35 = α-2
= α(-2+7)
= α5
取对数:log(α5) = 5
这些运算的结果仍然在GF(23)域中。


2 RS的编码算法


RS的编码就是计算信息码符多项式M(x)除以校验码生成多项式G(x)之后的余数。
在介绍之前需要说明一些符号。在GF(2m)域中,符号(n,k)RS的含义如下:

m 表示符号的大小,如m = 8表示符号由8位二进制数组成
n 表示码块长度
k 表示码块中的信息长度
K=n-k = 2t 表示校验码的符号数
t 表示能够纠正的错误数目

例如,(28,24)RS码表示码块长度共28个符号,其中信息代码的长度为24,检验码有4个检验符号。在这个由28个符号组成的码块中,可以纠正在这个码块中出现的2个分散的或者2个连续的符号错误,但不能纠正3个或者3个以上的符号错误。
对一个信息码符多项式 ,RS校验码生成多项式的一般形式为

RS编码原理分析,by 5lulu.com (13-2)

式中,K0是偏移量,通常取K0 = 0或K0 = 1,而(n-k)≥2t (t为要校正的错误符号数)。

下面用两个例子来说明RS码的编码原理

[例16.2] 设在GF(23)域中的元素对应表如表16-01所示。假设(6,4)RS码中的4个信息符号为m3、m2、m1和m0,信息码符多项式M(x)为


RS编码原理分析,by 5lulu.com (13-3)

并假设RS校验码的2个符号为Q1和Q0RS编码原理分析,by 5lulu.com的剩余多项式R(x)为
R(x)=Q1x + Q0
这个多项式的阶次比G(x)的阶次少一阶。
如果K0 = 1,t = 1,由式(13-2)导出的RS校验码生成多项式就为

RS编码原理分析,by 5lulu.com (13-4)
根据多项式的运算,由式(13-3)和式(13-4)可以得到

m3x5+m2x4+m1x3+m0x2+Q1x+Q0 = (x-α)(x-α2)Q(x)

当用x = α和x = α2代入上式时,得到下面的方程组,RS编码原理分析,by 5lulu.com

经过整理可以得到用矩阵表示的(6,4)RS码的校验方程:

RS编码原理分析,by 5lulu.com

求解方程组就可得到校验符号:

RS编码原理分析,by 5lulu.com

在读出时的校正子可按下式计算:

RS编码原理分析,by 5lulu.com

[例16.3] 在例16.2中,如果K0 = 0,t = 1,由式(13-2)导出的RS校验码生成多项式就为

RS编码原理分析,by 5lulu.com (13-5)

根据多项式的运算,由(13-3)和(13-5)可以得到下面的方程组:

RS编码原理分析,by 5lulu.com

方程中的αi也可看成符号的位置,此处i = 0,1,…,5。
求解方程组可以得到RS校验码的2个符号为Q1和Q0

RS编码原理分析,by 5lulu.com (13-6)

假定mi为下列值:

信息符号 m3 = α0 = 001
m2 = α6 = 101
m1 = α3 = 011
m0 = α2 = 100
校验符号 Q1 = α6 = 101
Q0 = α4 = 110
校正子 s0 = 0
s1 = 0

代入(13-6)式可求得校验符号:
Q1 = α6 = 101
Q0 = α4 = 110

3 RS码的纠错算法

RS码的错误纠正过程分三步: (1)计算校正子(syndrome),(2)计算错误位置,(3)计算错误值。现以例16.3为例介绍RS码的纠错算法。
校正子使用下面的方程组来计算:

RS编码原理分析,by 5lulu.com

为简单起见,假定存入光盘的信息符号m3、m2、m1、m0和由此产生的检验符号Q1、Q0均为0,读出的符号为m3′、m2′、m1′、m0′、Q1′和Q0′。
如果计算得到的s0和s1不全为0,则说明有差错,但不知道有多少个错,也不知道错在什么位置和错误值。如果只有一个错误,则问题比较简单。假设错误位置为αx,错误值为mx,那么可通过求解下面的方程组:

RS编码原理分析,by 5lulu.com

得知错误的位置和错误值。
如果计算得到s0 = α2和s1 = α5,可求得αx = α3和mx = α2,说明m1出了错,它的错误值是α2。校正后的m1 = m1′+mx ,本例中m1=0。
如果计算得到s0 = 0,而s1≠0,那基本可断定至少有两个错误,当然出现两个以上的错误不一定都是s0 = 0和s1≠0。如果出现两个错误,而又能设法找到出错的位置,那么这两个错误也可以纠正。如已知两个错误mx1和mx2的位置αx1和αx2,那么求解方程组:

RS编码原理分析,by 5lulu.com

就可知道这两个错误值。
CD-ROM中的错误校正编码CIRC和里德-索洛蒙乘积码(Reed Solomon Product-like Code,RSPC)就是采用上述方法导出的。

我来评分 :6
2

转载注明:转自5lulu技术库

本站遵循:署名-非商业性使用-禁止演绎 3.0 共享协议

相关推荐