RS码编码及译码.docx

RS码编码及译码.docx西安电子科技大学学报(自然科学版)OURNALOFXIDIANUNIVERSITYRS码的编码和译码算法的实现扌緩:RS码是对突发错误M有良好纠错能力的通信信道编码本文主要讨论了RS码的编码?M睪码,主要推导了伽罗华t删生成方法和BM迭代译码算法。关键词:RS码;伽罗华域;编®;BM译码1RS码的基本介绍RS码是一类有彳艮强纠错能力的BCH码,也是一类典型的代数几何码叫是由里德和索罗蒙丁-1960年构造川来的。RS码是非二进制BCH码的一个重要子类,是一类最大距离可分组码。RS码已经被广泛应用于通信和存储系统中,以进行羞错控制。m=1的q进制的BCH码是q进制BCH码屮最重要的一个了类。这一了类的编码被称为里徳一所罗门(Reed-Solomon,RS)码。令a为GF(q)中的木原元。符号取自GF(q)、纠正t个错误的RS码,英生成多项式g(x)以a,a2,...»Qt为其全部的根。由丁&是GF(q)中的元素,因此其最小多项式0((x)即为X—&。因此,得到g(X)=(X-a)(X一a2)...(X一a2t)=%+5X+山X?+…+ 其中山wGF(q),0<i<2U由于a,a2,…,a2t是X—1的根,因此能够被g(X)整除。所以,g(X)将生成恰好具有2t个奇偶校验符号、长度为n二q-1的q进制循环码役符号取自GF(q)、纠正t个错误的RS码具有如下参数:分组 n=q-l奇偶校验符号数:n-k=2t维数:k=q-l-2t最小距离:dmin=2t+l丁是,我们看到RS码具有如下特性:⑴码的氏度比码字母表的大小少1;(2)最小距离比奇偶校验符号数多1。最小距离比奇偶校验符号数多1的编码称为极大最小距离可分(MaximumDistanceSeparable,MDS)码。2伽罗华域元素和二进制代码表的生成伽罗华域是以为元素的有限域,P为素数,m为正整数。其特征是域屮各元素可以用基本元素及其表达式来表示,并且域中各元素经过域内运算,其结果仍为域内元素。在计算机中,数据是以二进制的形式存在,所以P通常取值为2叫在计算机的编程过程中,最常生成的是GF(2&)域,共含有256个元素,其中除0,1Z外的28-2个元素都是由本原多项式P(X)生成。本原多项式的特征是氓孑得到的余式等于0。在我们编写RS编码稈丿芋之前,必须首先生成GF(2®域屮元素与一•进制数之间的对照表。方法就是用GF(2^)中的元素0,込・.凶-2,分别模2除以木原多项式P(X)。这样一来就建立了GF(2T域中元素与二进制数之间的一一对应的关系。为了使用方便,存储一个字节的十进制整数形式,避免存储成二进制数组的形式。:RS码的编码和译码算法的实现在本次仿真中m=4,多项式P(X)二1+X+X4是GF⑵上的一个本原多项式。设P(a)=l+a+a4=OBPa4=1+ct,用这个关系式可以构造GF0)。在构造GF(29元素的多项式表示屮重复使用等式1+仏例如,a5=a•a4=a(14-a)=a+a2a6=a•a5=a(a+a2)=a2+a3a7=a•a6=a(a2+a3)=a3+a4=a3+14-a=14-a4-a3将元素卅和Q相乘,貝要简单的把它们的指数相加并且使用关系式0=1。在RS码的编译码运算过程屮,所有的运算都是在伽罗华域中进行的,因此,在编写程序之前要先按照上述方法将GF(2")域中元素与二进制