RS纠错编码原理.docx

RS基本概念GF(2m)域域在RS 编码理论中起着至关重要的作用。简单点说域 有 (设 = q )个符号 且具有以下性质：域中的每个元素都可以用a0，a1，a2，am-1 的和来表示。除0、1外其余所有元素由本原多项式P(x)生成。本原多项式的特性是得到的余式等于0。在纠错编码运算过程中，加、减、乘和除的运算是在伽罗华域中进行在GF域上的加、减、乘、除运算定义如下（GF()为例）：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() 的所有元素例： m=4,本原多项式 求GF() 的所有元素： 因为 为p(x)的根 得到=0 或 (根据运算规则)由此可以得到域的所有元素元素多项式表示二进制表示十六进制表示0000000a0100011a1a00102a2a201004a3a310008a4a+100113a5a2+a mod p(a)01106a6a3+a2 mod p(a)1100Ca7a3+a+1 mod p(a)1011Ba8a2+1 mod p(a)01015a9a3+a mod p(a)1010Aa10a2+a+1 mod p(a)01117a11a3+a2+1 mod p(a)1110Ea12a3+a2+a+1 mod p(a)1111Fa13a3+a2+1 mod p(a)1101Da14a3+1 mod p(a)10019符号(n，k)RS在介绍之前需要说明一些符号。在域中，符号(n，k)RS的含义如下：m表示符号的大小，如m = 8表示符号由8位二进制数组成n表示码块长度，k 表示码块中的信息长度K=nk = 2t表示校验码的符号数t表示能够纠正的错误数目RS的编码算法本项目RS纠错算法选择在域上的RS(15,11)码，码长n=15字符，码元长k=11字符，码距d=5，纠错能力t=2字符，每字符为4bits，即一个码组合7.5字节。每11个有效字节加4个纠错字节。每一帧报文分成若干组，以11个字节为一组，对这11个字节作纠错，生成4字节里德-所罗门码纠错码，和前11个字节一起共15个字节构成纠错后的一组报文。一帧报文以每11个字节分组后，若最后一组字节数不满11个字节，剩余字节填77H，凑满11个字节再进行纠错。对一个信息码符多项式，RS校验码生成多项式的一般形式为(132)式中，m0是偏移量，通常取K0 = 0或K0 = 1，而(n-k)2t (t为要校正的错误符号数)。对于R（15，11）对应生成多项式为g(x)= 信息码符多项式为 (133)并假设RS校验码的4个符号为Q3 Q2Q1和Q0，的剩余多项式为这个多项式的阶次比的阶次少一阶。如果K0 = 1，t = 1，由式(132)导出的RS校验码生成多项式就为= (134)根据多项式的运算，由式(133)和式(134)可以得到 M(x)+R(x)= Q(x)当用代入上式时，得到下面的方程组，令=n0=n1=n2=n3解得：= = = = RS码的纠错算法RS码的错误纠正过程分三步： (1)计算校正子(syndrome)，(2)计算错误位置，(3)计算错误值。现以例13.3为例介绍RS码的纠错算法。1、 求出校正子：对于一组接收到的数据：接收到的数据：68 31 00 31 00 68 4b 05 35 01 00 b7 2a 55 dc分两小组：08 06 01 03 00 00 01 03 00 00 08 07 0b 0a 02 (I-1) 06 0b 04 05 00 05 03 01 00 00 00 05 05 0c 0d (I-2) 对应r14r0代入上式求出s1,s2,s3,s4(sj);2、 判断若Sj (j=1,2,3,4) 均为0，则无错；否则执行下面的步骤以求出错值及位置。3、 求出错位多项式d(x)=dz2x2+dz0x+dz1=0的根，即为错值位置，其中：若dz2=0，则只有一个根x1=s3/s2 。否则用代入法求出x1，x2，即把x的所有15个可能值代入错位多项式，若结果为0，则即是一个根。4、 求出错值ew1,ew2。若dz2=0，ew=s12/s2，否则 5、 纠错时在对应的x=ay，r(14-y