rs编码与纠错算法

《rs编码与纠错算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、13.2RS编码和纠错算法13.2.1.GF(2m)域RS(Reed-Solomon)码在伽罗华域(GaloisField，GF)中运算的，因此在介绍RS码之前先简要介绍一下伽罗华域。CD-ROM中的数据、地址、校验码等都可以看成是属于GF(2m)=GF(28)中的元素或称符号。GF(28)表示域中有256个元素，除0，1之外的254个元素由本原多项式P(x)生成。本原多项式的特性是得到的余式等于0。CD-ROM用来构造GF(28)域的是(13－1)而GF(28)域中的本原元素为α=(00000010)下面以一个较简单例子说明域的构造。[例13.1]构造GF(23)域的本原多项式假定

2、为α定义为=0的根，即α3＋α＋1=0和α3=α＋1GF(23)中的元素可计算如下：0mod(α3＋α＋1)=0α0mod(α3＋α＋1)=α0=1α1mod(α3＋α＋1)=α1α2mod(α3＋α＋1)=α2α3mod(α3＋α＋1)=α＋1α4mod(α3＋α＋1)=α2＋αα5mod(α3＋α＋1)=α2＋α1＋1α6mod(α3＋α＋1)=α2＋1α7mod(α3＋α＋1)=α0α8mod(α3＋α＋1)=α1……　用二进制数表示域元素得到表13-01所示的对照表表13-01GF(23)域中与二进制代码对照表,GF(23)域元素二进制对代码0(000)α0(001)α1(0

3、10)α2(100)α3(011)α4(110)α5(111)α6(101)这样一来就建立了GF(23)域中的元素与3位二进制数之间的一一对应关系。用同样的方法可建立GF(28)域中的256个元素与8位二进制数之间的一一对应关系。在纠错编码运算过程中，加、减、乘和除的运算是在伽罗华域中进行。现仍以GF(23)域中运算为例：加法例：α0＋α3=001＋011=010=α1减法例：与加法相同乘法例：α5·α4=α(5＋4)mod7=α2除法例：α5/α3=α2α3/α5=α－2=α(－2＋7)=α5取对数：log(α5)=5这些运算的结果仍然在GF(23)域中。13.2.2RS的编码算法

4、RS的编码就是计算信息码符多项式除以校验码生成多项式之后的余数。在介绍之前需要说明一些符号。在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校验码生成多项式的一般形式为(13－2)式中

5、，m0是偏移量，通常取K0=0或K0=1，而(n-k)≥2t(t为要校正的错误符号数)。下面用两个例子来说明RS码的编码原理。[例13.2]设在GF(23)域中的元素对应表如表13-01所示。假设(6，4)RS码中的4个信息符号为m3、m2、m1和m0，信息码符多项式为(13－3)并假设RS校验码的2个符号为Q1和Q0，的剩余多项式为这个多项式的阶次比的阶次少一阶。如果K0=1，t=1，由式(13－2)导出的RS校验码生成多项式就为=(13－4)根据多项式的运算，由式(13－3)和式(13－4)可以得到m3x5＋m2x4＋m1x3＋m0x2＋Q1x＋Q0=(x－α)(x－α2)Q(x

6、)当用x=α和x=α2代入上式时，得到下面的方程组，经过整理可以得到用矩阵表示的(6，4)RS码的校验方程：求解方程组就可得到校验符号：在读出时的校正子可按下式计算：　[例13.3]在例13.2中，如果K0=0，t=1，由式(13－2)导出的RS校验码生成多项式就为=(13－5)根据多项式的运算，由(13－3)和(13－5)可以得到下面的方程组：方程中的αi也可看成符号的位置，此处i=0，1，…，5。求解方程组可以得到RS校验码的2个符号为Q1和Q0，(13－6)假定mi为下列值：信息符号m3=α0=001m2=α6=101m1=α3=011m0=α2=100校验符号Q1=α6=10

7、1Q0=α4=110校正子s0=0s1=0代入(13－6)式可求得校验符号：Q1=α6=101Q0=α4=11013.2.3RS码的纠错算法RS码的错误纠正过程分三步：(1)计算校正子(syndrome)，(2)计算错误位置，(3)计算错误值。现以例13.3为例介绍RS码的纠错算法。校正子使用下面的方程组来计算：为简单起见，假定存入光盘的信息符号m3、m2、m1、m0和由此产生的检验符号Q1、Q0均为0，读出的符号为m3′、m2′、m1′、m0′、Q1′和