RS码编码及译码.docx

RS码的编码和译码算法的实现摘要:RS码是对突发错误具有良好纠错能力的通信信道编码。本文主要讨论了RS码的编码和译码,主要推导了伽罗华域的生成方法和BM迭代译码算法。关键词:RS码;伽罗华域;编码;BM译码1RS码的基本介绍RS码是一类有很强纠错能力的BCH码,也是一类典型的代数几何码[[]王新梅,——原理与方法[M].西安:.],是由里德和索罗蒙于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-α2…X-α2t=g0+g1X+g1X2+…+g2t-1X2t-1+X2t其中gi∈GF(q),0≤i<2t。由于α,α2,…,α2t是Xq-1-1的根,因此Xq-1-1能够被g(X)整除。所以,g(X)将生成恰好具有2t个奇偶校验符号、长度为n=q–1的q进制循环码[[](美)林舒等著,[M].北京:***.]。符号取自GF(q)、纠正t个错误的RS码具有如下参数:分组长度:n=q-1奇偶校验符号数:n–k=2t维数:k=q–1–2t最小距离:dmin=2t+1于是,我们看到RS码具有如下特性:(1)码的长度比码字母表的大小少1;(2)最小距离比奇偶校验符号数多1。最小距离比奇偶校验符号数多1的编码称为极大最小距离可分(MaximumDistanceSeparable,MDS)码。2伽罗华域元素和二进制代码表的生成伽罗华域是以q=pm为元素的有限域,p为素数,m为正整数。其特征是域中各元素可以用基本元素及其表达式来表示,并且域中各元素经过域内运算,其结果仍为域内元素。在计算机中,数据是以二进制的形式存在,所以p通常取值为2[[]武炜,[J].(3).]。在计算机的编程过程中,最常生成的是GF(28)域,共含有256个元素,其中除0,1之外的28-2个元素都是由本原多项式P(X)生成。本原多项式的特征是xq-1-1P(X)得到的余式等于0。在我们编写RS编码程序之前,必须首先生成GF(2m)域中元素与二进制数之间的对照表。方法就是用GF(2m)中的元素0,α0…αq-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+α)=α+α2α6=α﹒α5=α(α+α2)=α2+α3α7=α﹒α6=α(α2+α3)=α3+α4=α3+1