您好,欢迎访问三七文档
西安电子科技大学学报(自然科学版)OURNALOFXIDIANUNIVERSITYRS码的编码和译码算法的实现摘要:RS码是对突发错误具有良好纠错能力的通信信道编码。本文主要讨论了RS码的编码和译码,主要推导了伽罗华域的生成方法和BM迭代译码算法。关键词:RS码;伽罗华域;编码;BM译码1RS码的基本介绍RS码是一类有很强纠错能力的BCH码,也是一类典型的代数几何码[1],是由里德和索罗蒙于1960年构造出来的。RS码是非二进制BCH码的一个重要子类,是一类最大距离可分组码。RS码已经被广泛应用于通信和存储系统中,以进行差错控制。m=1的q进制的BCH码是q进制BCH码中最重要的一个子类。这一子类的编码被称为里德—所罗门(Reed-Solomon,RS)码。令α为GF(q)中的本原元。符号取自GF(q)、纠正t个错误的RS码,其生成多项式g(x)以α,α2,…,α2𝑡为其全部的根。由于α𝑖是GF(q)中的元素,因此其最小多项式Ø𝑖(x)即为X−α𝑖。因此,得到g(X)=(X−α)(X−α2)…(X−α2𝑡)=𝑔0+𝑔1𝑋+𝑔1𝑋2+⋯+𝑔2𝑡−1𝑋2𝑡−1+𝑋2𝑡其中𝑔𝑖∈GF(q),0≤i2t。由于α,α2,…,α2𝑡是𝑋𝑞−1-1的根,因此𝑋𝑞−1-1能够被g(X)整除。所以,g(X)将生成恰好具有2t个奇偶校验符号、长度为n=q–1的q进制循环码[2]。符号取自GF(q)、纠正t个错误的RS码具有如下参数:分组长度:n=q-1奇偶校验符号数:n–k=2t维数:k=q–1–2t最小距离:𝑑min=2t+1于是,我们看到RS码具有如下特性:(1)码的长度比码字母表的大小少1;(2)最小距离比奇偶校验符号数多1。最小距离比奇偶校验符号数多1的编码称为极大最小距离可分(MaximumDistanceSeparable,MDS)码。2伽罗华域元素和二进制代码表的生成伽罗华域是以q=𝑝𝑚为元素的有限域,p为素数,m为正整数。其特征是域中各元素可以用基本元素及其表达式来表示,并且域中各元素经过域内运算,其结果仍为域内元素。在计算机中,数据是以二进制的形式存在,所以p通常取值为2[3]。在计算机的编程过程中,最常生成的是GF(28)域,共含有256个元素,其中除0,1之外的28-2个元素都是由本原多项式P(X)生成。本原多项式的特征是𝑥𝑞−1−1𝑃(𝑋)得到的余式等于0。在我们编写RS编码程序之前,必须首先生成GF(2𝑚)域中元素与二进制数之间的对照表。方法就是用GF(2𝑚)中的元素0,α0…α𝑞−2,分别模2除以本原多项式P(X)。这样一来就建立了GF(2𝑚)域中元素与二进制数之间的一一对应的关系。为了使用方便,存储一个字节的十进制整数形式,避免存储成二进制数2:RS码的编码和译码算法的实现组的形式。在本次仿真中m=4,多项式P(X)=1+X+𝑋4是GF(2)上的一个本原多项式。设P(α)=1+α+α4=0即α4=1+α,用这个关系式可以构造GF(24)。在构造GF(24)元素的多项式表示中重复使用等式α4=1+α。例如,α5=α﹒α4=α(1+α)=α+α2α6=α﹒α5=α(α+α2)=α2+α3α7=α﹒α6=α(α2+α3)=α3+α4=α3+1+α=1+α+α3将元素α𝑖和α𝑗相乘,只要简单的把它们的指数相加并且使用关系式α15=1。在RS码的编译码运算过程中,所有的运算都是在伽罗华域中进行的,因此,在编写程序之前要先按照上述方法将GF(2𝑚)域中元素与二进制数的对照表生成。本次仿真的GF(24)的三种表示形式均在表1中给出。表1由P(X)=1+X+𝑋4生成的GF(24)的元素的三种表示法幂表示多项式表示4维向量表示000000111000αα0100α2α20010α3α30001α41+α1100α5α+α20110α6α2+α30011α71+α+α31101α81+α21010α9α+α30101α101+α+α21110α11α+α2+α30111α121+α+α2+α31111α131+α2+α31011α141+α310013RS码的编码RS码的编码与二进制情况类似。令𝑎(𝑋)=𝑎0+𝑎1𝑋+𝑎2𝑋2+…+𝑎𝑘−1𝑋𝑘−1为需要编码的信息,其中k=n–2t。在系统码的形式下,2t个奇偶校验符号恰好是𝑋2𝑡𝑎(𝑋)除以生成多项式得到的余式𝑏(𝑋)=𝑏0+𝑏1𝑋+𝑏2𝑋2+…+𝑏2𝑡−1𝑋2𝑡−1的系数。在硬件实现中,可以通过图1的除法电路完成。一旦信息𝑎(𝑋)已经进入信道和电路,则奇偶校验符号就出现在寄存器中[2]。:RS码的编码和译码算法的实现图1生成多项式为𝑔(𝑋)=𝑔0+𝑔1𝑋+𝑔2𝑋2+…+𝑔2𝑡𝑋2𝑡的q进制RS码的编码电路编码实现的过程如下,在RS码的运算过程中,所有加减乘除的运算都是定义在伽罗华域上的模2运算。1.采集进来的数据,查前面生成的GF(2𝑚)域与二进制数对照表,转化为GF(2𝑚)域上的元素。2.编码的过程,当门开启后,k个信息位串行移位进入电路中,同时送入通信信道。一旦消息全部进入到电路中,则寄存器就构成了余式多项式,即为校验位。3.关闭门,断开反馈连接。4.将校验位移出到信道中。并且与消息位构成了一个完整的码字。4RS码的译码RS码译码的主要目的就是对接收到的可能出错的码字,通过一定的算法设计出原始发送的码字。译码的实现过程比编码复杂的多。RS码的译码算法主要有PGZ算法、BM算法、Forney算法。本文主要讨论BM迭代译码算法。主要的译码步骤分为以下几步。1.通过接收多项式r(X)求n-k个伴随式的值。2.计算错误位置。求解错误多项式,错误位置多项式的根就是错误位置。3.求出错误值,加到对应位置上,完成整个纠错过程。Berlekamp提出了求解错误位置多项式的迭代算法。错误位置多项式可表示为𝜎(𝑋)=𝜎0+𝜎1𝑋+𝜎2𝑋2+…+𝜎𝑡𝑋𝑡与错误位置数的关系由牛顿恒等式确定[4]。这一步是译码过程中最为复杂的一步,在下面的部分将进行介绍。RS译码过程是一个很复杂的计算过程。在此处给出RS译码的模块图。图2RS译码模块图C(X)𝑠𝑖𝑋𝑖v计算伴随式计算系数矩阵的秩解方程组Chien搜索代入(1)纠正错误r(X)𝑠𝑖𝜎𝑖r(X)𝑋𝑖4:RS码的编码和译码算法的实现4.1伴随式的生成译码过程的第一步就是根据接收多项式的值求解伴随多项式,其主要目的是把错误符号的范围从2𝑛缩减到2n−k。由伴随式的定义计算𝑠𝑗=𝑟(𝑎𝑗)分别解出𝑠𝑗的值。这2t个值的大小只与校验码有关。如果计算得到的𝑠𝑗全部为0则说明接收到的码字没有错误;如果计算的码字不全为0,则说明在码字传递的过程中发生了错误。4.2计算错误位置和错误值在上一步骤确定了码字传输有误,由𝑠𝑗求出错误位置多项式𝜎(𝑋),𝜎(𝑋)的根即为错误位置。错误位置多项式𝜎(𝑋)=𝜎0+𝜎1𝑋+𝜎2𝑋2+…+𝜎𝑡𝑋𝑡与错误位置数的关系由牛顿恒等式确定。𝜎0=1𝜎1=𝛽1+𝛽2+⋯+𝛽𝑣…𝜎𝑣=𝛽1𝛽2𝛽𝑣迭代的第一个步骤为求出系数满足第一个牛顿恒等式的最低次多项式𝜎(1)(𝑋)并且检验该多项式是否满足第二个牛顿恒等式。如果满足𝜎(2)(𝑋)=𝜎(1)(𝑋),否则在𝜎(1)(𝑋)基础上增加修正项,使得𝜎(2)(𝑋)满足第二个牛顿恒等式。以此类推,直到求出𝜎(2𝑡)(𝑋)。𝜎(2𝑡)(𝑋)就是错误位置多项式[4]。一般进行2t次迭代来完成。𝜎(𝜇)(𝑋)到𝜎(𝜇+1)(𝑋)的迭代表达式如下:𝜎(𝜇+1)(𝑋)=𝜎(𝜇)−𝑑𝜇𝑑𝜌−1𝑋(𝜇−𝜌)𝜎(𝜌)(𝑋)其中,𝑑𝜇=𝑆𝜇+1𝜎1𝜇𝑆𝜇+⋯+𝜎𝑡𝜇(𝜇)𝑆𝜇+1−𝑙𝜇。在编程过程中输入接收到的码字序列,计算出校正子。在实际实现过程中,计算错位位置是由钱搜索电路来完成的。用钱搜索解出𝜎(𝑋)的根,得到错误位置数,确定错误位置。钱搜索电路如下图。图3钱搜索电路图计算出错误位置带入𝑆𝑣=𝑒1(𝑥)12𝑡++…+𝑒𝑣(𝑥)𝑣2𝑡(1)可直接求解出错误值。带入c(x)=r(x)+e(x),把求得的错误值加到对应的错误位置上就完成了纠错。:RS码的编码和译码算法的实现4.3BM迭代算法的实例本次仿真实现是基于GF(24)伽罗华域上16元(15,9,7)RS码的实现。因此,此次实现一个GF(24)上BM迭代算法的实现。生成多项式g(X)=(X−α)(X−α2)…(X−α6)。已知r(X)=α6𝑋4+α11X12,求解错误位置。计算伴随式𝑆1=α,𝑆2=α12,𝑆3=α6,𝑆4=α,𝑆6=α2。使用迭代法求𝜎(𝑋)的过程如图3所示。图4迭代法求𝜎(𝑋)的过程得到𝜎(𝑋)=1+α6𝑋+αX2,解得𝜎(𝑋)根为α11和α13,求得错误位置是𝑋1=α4和𝑋2=α12,所以判断X4和X12位置发生了错误。参考文献:[1]王新梅,肖国镇.纠错码——原理与方法[M].西安:西安电子科技大学出版社.1996.[2](美)林舒等著,晏坚译.差错控制编码[M].北京:机械工业出版社.2007.[3]武炜,董志学.RS编译码算法的实现[J].福建电脑.2006(3).[4]谢瑞云,樊小琴,张焱.RS码的编译码程序的实现[J].信息安全与通信保密.2014(8)
本文标题:RS码编码及译码
链接地址:https://www.777doc.com/doc-2856114 .html