RS码编码及译码.docx

：RS码的编码和译码算法的实现RS码的编码和译码算法的实现摘要：RS码是对突发错误具有良好纠错能力的通信信道编码。本文主要讨论了RS码的编码和译码，主要推导了伽罗华域的生成方法和BM迭代译码算法。关键词：RS码；伽罗华域；编码；BM译码1 RS码的基本介绍 RS码是一类有很强纠错能力的BCH码，也是一类典型的代数几何码 王新梅，肖国镇.纠错码原理与方法M.西安:西安电子科技大学出版社.1996.，是由里德和索罗蒙于1960年构造出来的。RS码是非二进制BCH码的一个重要子类，是一类最大距离可分组码。RS码已经被广泛应用于通信和存储系统中，以进行差错控制。 m=1的q进制的BCH码是q进制BCH码中最重要的一个子类。这一子类的编码被称为里德所罗门(Reed-Solomon,RS)码。令为GF(q)中的本原元。符号取自GF(q)、纠正t个错误的RS码，其生成多项式g(x)以，2，2t为其全部的根。由于i是GF(q)中的元素，因此其最小多项式i(x)即为X-i。因此，得到gX=X-X-2X-2t=g0 + g1 X+ g1 X2 +g2t-1 X2t-1 +X2t 其中giGF(q)，0i2t。由于，2，2t 是Xq-1-1的根，因此Xq-1-1能够被g(X)整除。所以，g(X)将生成恰好具有2t个奇偶校验符号、长度为n = q 1的q 进制循环码（美）林舒等著，晏坚译.差错控制编码M.北京：机械工业出版社.2007.。符号取自GF(q)、纠正t个错误的RS码具有如下参数：分组长度： n = q - 1奇偶校验符号数: n k = 2t维数: k = q 1 2t最小距离: dmin= 2t + 1于是，我们看到RS码具有如下特性：（1）码的长度比码字母表的大小少1；（2）最小距离比奇偶校验符号数多1。最小距离比奇偶校验符号数多1的编码称为极大最小距离可分（Maximum Distance Separable，MDS）码。2 伽罗华域元素和二进制代码表的生成 伽罗华域是以q=pm为元素的有限域，p为素数，m为正整数。其特征是域中各元素可以用基本元素及其表达式来表示，并且域中各元素经过域内运算，其结果仍为域内元素。在计算机中，数据是以二进制的形式存在，所以p通常取值为2 武炜，董志学.RS编译码算法的实现J.福建电脑.2006(3).。在计算机的编程过程中，最常生成的是GF(28)域，共含有256个元素，其中除0，1之外的28-2个元素都是由本原多项式P(X)生成。本原多项式的特征是xq-1-1P(X)得到的余式等于0。在我们编写RS编码程序之前，必须首先生成GF(2m)域中元素与二进制数之间的对照表。方法就是用GF(2m)中的元素0，0q-2，分别模2除以本原多项式P(X)。这样一来就建立了GF(2m)域中元素与二进制数之间的一一对应的关系。为了使用方便，存储一个字节的十进制整数形式，避免存储成二进制数组的形式。在本次仿真中m = 4，多项式P(X) = 1 + X + X4是GF(2)上的一个本原多项式。设P() = 1+4=0即4= 1 +，用这个关系式可以构造GF(24)。在构造GF(24)元素的多项式表示中重复使用等式4= 1 +。例如，5 =4 =(1+)= +26 =5=(+2)= 2+37 =6=(2+3)= 3+4=3+1+=1+3将元素i和j相乘，只要简单的把它们的指数相加并且使用关系式15=1。在RS码的编译码运算过程中，所有的运算都是在伽罗华域中进行的，因此，在编写程序之前要先按照上述方法将GF(2m)域中元素与二进制数的对照表生成。本次仿真的GF(24)的三种表示形式均在表1中给出。表1 由P(X) = 1 + X + X4生成的GF(24)的元素的三种表示法幂表示多项式表示4维向量表示000000111000010022001033000141 +11005+2011062+3001171+3110181+210109+30101101+2111011+2+30111121+2+31111131+2+31011141+310013 RS码的编码 RS码的编码与二进制情况类似。令aX= a0 +a1X+a2 X2+ak-1 Xk-1为需要编码的信息，其中k = n 2t。在系统码的形式下，2t个奇偶校验符号恰好是X2taX除以生成多项式得到的余式bX= b0 +b1X+b2 X2+b2t-1 X2t-1的系数。在硬件实现中，可以通过图1的除法电路完成。一旦信息aX已经进入信道和电路，则奇偶校验符号就出现在寄存器中2。图1 生成多项式为gX= g0 +g1X+g2 X2+g2t X2t的q进制RS码的编码电路编码实现的过程如下，在RS码的运算过程中，所有加减乘除的运算都是定义在伽罗华域上的模2运算。1. 采集进来的数据，查前面生成的GF(2m)域与二进制数对照表，转化为GF(2m)域上的元素。2. 编码的过程，当门开启后，k个信息位串行移位进入电路中，同时送入通信信道。一旦消息全部进入到电路中，则寄存器就构成了余式多项式，即为校验位。3. 关闭门，断开反馈连接。4. 将校验位移出到信道中。并且与消息位构成了一个完整的码字。4 RS码的译码RS码译码的主要目的就是对接收到的可能出错的码字，通过一定的算法设计出原始发送的码字。译码的实现过程比编码复杂的多。RS码的译码算法主要有PGZ算法、BM算法、Forney算法。本文主要讨论BM迭代译码算法。主要的译码步骤分为以下几步。1. 通过接收多项式r(X)求n-k个伴随式的值。2. 计算错误位置。求解错误多项式，错误位置多项式的根就是错误位置。3. 求出错误值，加到对应位置上，完成整个纠错过程。Berlekamp提出了求解错误位置多项式的迭代算法。错误位置多项式可表示为X= 0 +1X+2 X2+t Xt与错误位置数的关系由牛顿恒等式确定 谢瑞云，樊小琴，张焱.RS码的编译码程序的实现J.信息安全与通信保密.2014(8)。这一步是译码过程中最为复杂的一步，在下面的部分将进行介绍。RS译码过程是一个很复杂的计算过程。在此处给出RS译码的模块图。C(X)siXiv计算伴随式计算系数矩阵的秩解方程组Chien搜索代入(1)纠正错误r(X)siir(X)Xi图2 RS译码模块图4.1 伴随式的生成译码过程的第一步就是根据接收多项式的值求解伴随多项式，其主要目的是把错误符号的范围从2n缩减到2n-k。由伴随式的定义计算sj=r(aj)分别解出sj的值。这2t个值的大小只与校验码有关。如果计算得到的sj全部为0则说明接收到的码字没有错误；如果计算的码字不全为0，则说明在码字传递的过程中发生了错误。4.2 计算错误位置和错误值在上一步骤确定了码字传输有误，由sj求出错误位置多项式X，X的根即为错误位置。错误位置多项式X= 0 +1X+2 X2+t Xt与错误位置数的关系由牛顿恒等式确定。0 =1 1 = 1 +2 +v v = 1 2 v 迭代的第一个步骤为求出系数满足第一个牛顿恒等式的最低次多项式1(X)并且检验该多项式是否满足第二个牛顿恒等式。如果满足2X=1(X)，否则在1(X)基础上增加修正项，使得2(X)满足第二个牛顿恒等式。以此类推，直到求出2t(X)。2t(X)就是错误位置多项式4。一般进行2t次迭代来完成。(X)到+1(X)的迭代表达式如下： +1X=-dd-1X-(X) 其中，d= S+11S+t()S+1-l。在编程过程中输入接收到的码字序列，计算出校正子。在实际实现过程中，计算错位位置是由钱搜索电路来完成的。用钱搜索解出X的根，得到错误位置数，确定错误位置。钱搜索电路如下图。图3 钱搜索电路图 计算出错误位置带入 Sv = e1(x)12t+ev(x)v2t(1)可直接求解出错误值。带入c(x)=r(x)+e(x)，把求得的错误值加到对应的错误位置上就完成了纠错。4.3 BM迭代算法的实例本次仿真实现是基于GF(24)伽罗华域上16元(15,9,7)RS码的实现。因此，此次实现一个GF(24)上