《RS编码和纠错算法》由会员分享，可在线阅读，更多相关《RS编码和纠错算法（14页珍藏版）》请在金锄头文库上搜索。
1、Data Matrix 将有效信息 (数字字母等 ) 编码成 0255 内的数字表示 (编码方式参考： http:/en.wikipedia.org/wiki/Data_Matrix)。为了及时发现数据传输时的错误，使用RS编解码 来进行错误检测校验。RS码可以看成伽罗华域GF(2F)上的元素，dm码的元素0255正好 对应伽罗华域GF(28)上的256个元素。通过编码时添加冗余信息，可以有效校验数据是否 正确传输。以下为文献概要：1) 介绍如何生成GF(2Am)域，伽罗华域的加法运算为异或运算，乘法运算为指数相加后 mod(2Am)02) 实例分析如何编码及纠错。(实际上就是求解多项式方程组
2、的过程，在实际工程算法中 运用到的钱氏搜索法(Chien Search)，Berlekamp-Massey算法都是为了快速求解方 程组，从而纠错)。3) 附录部分为GF(2A8)上的元素列表。13.2 RS编码和纠错算法13.2.1. GF(2m)域RS(Reed-Solomon)码在伽罗华域(Galois Field，GF)中运算的，因此在介绍RS码之前先 简要介绍一下伽罗华域。CD-ROM中的数据、地址、校验码等都可以看成是属于GF(2m) = GF(20中的元素或称符 号。GF(28)表示域中有256个元素，除0,1之外的254个元素由本原多项式P(x)生成。严L+1本原多项式的特性是
3、巩对 得到的余式等于0。CD-ROM用来构造GF(28)域的尸山 是fw=?+/+?+?+i(13_1)而GF(28)域中的本原元素为a = (0 0 0 0 0 0 1 0)下面以一个较简单例子说明域的构造。例13.1构造GF(23)域的本原多项式假定为a定义为尸W = 0的根，即a 3+a+l = 0 和 a3 二 a+1GF(23)中的元素可计算如下:0mod( aa 0mod( aa 1mod( aa 2mod( aa 3mod( aa 4mod( aa 5mod( aa 6mod( aa 7mod( aa 8mod( a3+a+l) = 03 +a+1) = a 0= 13 +a+1
4、) = a 13 +a+1) = a 23+a+1) = a+13 +a+1) = a 2+a3 +a+1) = a 2 +a 1 +13+a+1) = a2+13 -a-1) = a 03 a 1) = a 1用二进制数表示域元素得到表13-01所示的对照表表13-01 GF(23)域中与二进制代码对照表，尸GF(23)域兀素二进制对代码0(000)a 0(001)a 1(010)a 2(100)a 3(011)a 4(110)a 5(111)a 6(101)这样一来就建立了 GF(23)域中的元素与3位二进制数之间的一一对应关系。用同样的方法 可建立GF(28)域中的256个元素与8位二进
5、制数之间的一一对应关系。在纠错编码运算过 程中，加、减、乘和除的运算是在伽罗华域中进行。现仍以GF(23)域中运算为例：加法例：a0a3 = 001 + 011=010 = a 1减法例：与加法相同乘法例： a5a4= a (5+4) mod7=a 2除法例：a5/a3 = a 2a3/a5 二 a-2=a(2+7)=a 5取对数：log(a 5) = 5这些运算的结果仍然在GF(23)域中。13.2.2 RS的编码算法RS的编码就是计算信息码符多项式除以校验码生成多项式启之后的余数。在介绍之前需要说明一些符号。在GF(2n)域中，符号(n, k)RS的含义如下：m表示符号的大小，如m = 8
6、表示符号由8位二进制数组成n表示码块长度，k表示码块中的信息长度K=nk =表示校验码的符号数2tt表示能够纠正的错误数目例如，(28，24)RS码表示码块长度共28个符号，其中信息代码的长度为24，检验码有4 个检验符号。在这个由28个符号组成的码块中，可以纠正在这个码块中出现的2个分散 的或者2个连续的符号错误，但不能纠正3个或者3个以上的符号错误。对一个信息码符多项式，RS校验码生成多项式的一般形式为G(沪打(S)(13 2)式中，m0是偏移量，通常取 数)。=0或K = 1,而(n-k)三2t0(t为要校正的错误符号F面用两个例子来说明RS码的编码原理。例13.2设在GF(23)域中的
7、元素对应表如表13-01所示。假设(6, 4)RS码中的4个信 息符号为巴、叫、皿1和m0,信息码符多项式为(13-3)艇严=皿*并假设RS校验码的2个符号为和Qo，不)阴 的剩余多项式用(门为 应=Qk十Q。这个多项式的阶次比(力的阶次少一阶。如果Ko = 1,t = 1,由式(13 2)导出的RS校验码生成多项式就为%)二广(工-/为片W=()_)(134)根据多项式的运算，由式(13 3)和式(134)可以得到m X5+m X4+m X3+m X2+Q x+Q = (xa)(xa2)Q(x)321010当用x = 0和灭=a2代入上式时，得到下面的方程组，叫工4氓工斗4均议3_|_供规2
8、_|_0_|_|=口、.tn5( )5 +)4丰垃(鼻爭亠帧秽_|_Q农丰Qq = o经过整理可以得到用矩阵表示的(6, 4)RS码的校验方程:求解方程组就可得到校验符号QL = nag试3 丰 m2 丰 ni a。4mo 佚斗 ” Q o = g 鼻 4-ni? 4-% 护 4-坯 妒在读出时的校正子可按下式计算：耳j_N牛屯=mg罠4- 罠 4 mi罠 4 g罠 4 Q 罠+ Q。、.岂= mgo?y 4g(o/y 4nii(o?F + g( oc,3)3 + Qi oc3 + Q例13.3在例13.2中，如果K0 = 0, t = 1,由式（13 2）导出的RS校验码生成多 项式就为恥）
9、=门匕-o 1i-o=（xp ）乜-巧（13 5）根据多项式的运算，由（13 3）和（13 5）可以得到下面的方程组： 严汁叫亠g亠QiZo =0lm3a,j + maa,4-l-m1a3-l-na-2-l-Q1atL-l-Qo = O方程中的ai也可看成符号的位置，此处i = 0,1,，5。求解方程组可以得到RS校验码的2个符号为和Q0,IrQ1 = ocm3 4- a m2 +- gl mL 4- gc moQn = tx3m+ QC5iTL-5+ a4mi -I- amnk(13 6) 假定m.为下列值:i信息符号m3二a 0二001m2=a 6=101m1=a 3=011m0=a 2=
10、100校验符号Q1二a 6二101Q二a 4二1100校正子 s = 00s = 01代入(13 6)式可求得校验符号Q = a6 = 1011Q = a 4 = 110013.2.3 RS码的纠错算法RS码的错误纠正过程分三步：(1)计算校正子(syndrome), (2)计算错误位置，(3)计算错误值。现以例13.3为例介绍RS码的纠错算法。校正子使用下面的方程组来计算：r s0 = m3 + ma 4- ni! mo Qz + Qa$i =洪畀口+ 4Qo为简单起见，假定存入光盘的信息符号m、m、m、m和由此产生的检验符号Q、Q均为3210100,读出的符号为m、m、m、m、Q和Q。32
11、1010如果计算得到的s/HS不全为0,则说明有差错，但不知道有多少个错，也不知道错在什 么位置和错误值。如果只有一个错误，则问题比较简单。假设错误的位置为a,错误值为Xm,那么可通过求解下面的方程组：X得知错误的位置和错误值。如果计算得到s = a 2和s = a5,可求得a = a 3和m = a 2，说明m出了错，它01xx1的错误值是a2。校正后的m = m z+m ，本例中m=0。11x1如果计算得到s0 = 0,而s10,那基本可断定至少有两个错误，当然出现两个以上的错 误不一定都是J = 0和sM0。如果出现两个错误，而又能设法找到出错的位置，那么这 0 1期厂广厂r两个错误也可
12、以纠正。如已知两个错误1和 的位置 讥和 池，那么求解方程组：叫+叫=旬I喘机国1 +叫厲2 = S1就可知道这两个错误值。CD-ROM中的错误校正编码CIRC和里德-索洛蒙乘积码(Reed Solomon Product likeCode, RSPC)就是采用上述方法导出的。CopyRight Octopus 2000附录1GF(8)元素如下 GF(2入8)1+x入2+x入3+x入4+x入8Field element(polynomial notation) 4-tuple representation00000_0000(0 )10000_0001(1 )a入10000_0010(2 )a
13、入20000_0100(4)a入30000_1000(8 )a入40001_0000(16 )a入50010_0000(32 )a入60100_0000(64 )a入71000_0000(128)a入80001_1101(29 )a入90011_1010(58 )aTO0111_0100(116)a111110_1000(232)a入121100_1101(205)a入131000_0111(135)a入140001_0011(19 )a入150010_0110(38 )a入160100_1100(76 )a入171001_1000(152)a入180010_1101(45 )a入190101
14、_1010(90 )a入201011_0100(180)a入210111_0101(117)a入221110_1010(234)a入231100_1001(201)a入241000_1111(143)a入250000_0011(3)a入260000_0110(6 )a入270000_1100(12 )a入280001_1000(24 )a入290011_0000(48 )a入300110_0000(96 )a入311100_0000(192)a入321001_1101(157)a入330010_0111(39 )a入340100_1110(78 )a入351001_1100(156)a入360010_0101(37 )a入370100_1010(74 )a入381001_0100(14
