纠错编码的仿真课程设计

1、纠错编码的MATLAB仿真课程设计1/32编号:料件雷孑科津次冷GUILINUNIVERSITYOFELECTRONICTECHNOLOGY课程设计说明书题目：RS目55,223）纠错编码的MATLAB仿真院（系）:专业:学生姓名:学号：指导教师:2013年12月10日纠错编码的MATLAB仿真课程设计目录1引言错误!未指定书签。1.1信道编码理论与技术的发展历程及应用错误!未指定书签。L2纠错编码简介错误!未指定书签。2Reed-Solomon编码概述错误!未指定书签。3Reed-Solomon编码抽象代数基础错误!未指定书签。31群错误!未指定书签。3.2环和域错误!未指定书签。33有限域

2、错误!未指定书签。3.4欧儿里得算法错误!未指定书签。4BCH码、RS码及其编码错误!未指定书签。4.1BCH码、RS码简介错误!未指定书签。错误!未指定书签。4.2RS码的构造方法5RS码的译码错误!未指定书签。5.1关键方程的引入错误!未指定书签。5.2多项式的欧儿里得算法错误！未指定书签。5.3BCH/RS码的解码步骤错误!未指定书签。6MATLAB主要程序及其仿真结果错误!未指定书签。7总结错误!未指定书签。致谢错误!未指定书签。参考文献错误!未指定书签。附录错误!未指定书签。#/32纠错编码的MATLAB仿真课程设计摘要在纠错码领域中Reed-Solomon码是一类具有严格代数结构的

3、线性分组码。由于它突出的纠错能力(特别是纠突发错误的能力)，常被应用于数据存储以及现代数字通信系统中。在卫星通讯中，差错控制编码技术对降低误码率、提高通信的可靠性具有非常重要的作用。RS(Reed-Solomon)码是差错控制领域中一种性能优异的线性分组循环码，由于其具有很强的随机错误和突发错误的纠错能力，所以被CCSDS、NASA.ESA等空间组织接受，广泛用于深空探测中。目前我国还没有高码速率的RS硬件译码器，虽然“双星计划”已经采用RS纠错编码技术，在卫星上使用RS(255,223)硬件编码器进行编码，但是由于硬件译码器的复杂性，地面接收系统采用的是软件译码，无法保证通信的实时性。为此，

4、本文在详细介绍RS(255,223)编码译码的基础上，利用MATLAB软件对该理论进行仿真。关键词：Reed-Solomon编码;抽象代数：RS码编码;RS码译码算法；RS(255,223)仿真;MATLAB3/32纠错编码的MATLAB仿真课程设计1引言1.1 信道编码理论与技术的发展历程及应用Shannon的信道编码定理给出了有噪信道通信的最大速率，证明了好码的存在性，但对该定理证明是非构造性的，它没有告诉我们怎么构造好码。如何通过不可靠信道进行可靠的通信，是编码理论所要研究的问题。半个多世纪以来，众多的学者为构造逼近容量限的纠错码做了大量的工作，但这一问题直到45年后才基本得到解决。但是

5、，“过程比目标更重要”，在应对这一挑战的过程中，编码理论家和工程师们应用组合数学、线性代数、概率论、有限域理论等数学工具，建立了纠错码的性能参数限,发现了许多构造纠错码的方法，并设计了有效的编译码算法，为信息技术的蓬勃发展建立了不朽的功勋！在Shannon的论文发表之前，RichardHamming就已经为早期的计算机设计了一种纠单个错误的码，迈出了信道编码理论与技术研究的第一步。之后，信道编码理论与与技术的大致经历了以下几个发展阶段：1. 50年代至60年代初这是编码理论从无到有并得到迅速发展的年代，现代编码理论的许多思想都起源于这一时期。1）发现了几种线性分组码，如Golay码、Reed-

6、Muller码（RM码）、Reed-Solomon码（RS码）、Bose-Chaudhuri-Hocquengham码（BCH码）、低密度校验码（LDFC码）等,以及卷积码；2）为这些码设计了有效的译码算法，如用于RS码和BCH码译码的PGZ算法、用于卷积码译码的Fan。译码算法；3）证明了纠错码的几个最小码距限，如Hamming限（H限）、Singleton限、Plotkin限（P限）、GiIbert-Varshamove限（GV限），其证明可以在编码理论的基础教材中找到；4） 1957年，Elias提出了一种概念译码器表单译码器（ListDecoder）,以突破传统的限定距离译码（BDD）

7、的半最小码距的纠错半径；5） 1961年，W.W.Peterson编写了第一本关于纠错码理论的专著，系统地阐述了纠错码的基本理论。2. 60年代至70年代初这是纠错码发展最为活跃的时期之一。在此期间，以代数方法特别是以有限域理论为基础的线性分组码理论已趋成熟。1）提出了许多有效的编、译码方法。1965年，E.R.Berlekamp提出了一种实用分组码的代数译码算法，1969年,J.L.Massey从序列综合的角度重新推导了这一算法，后人称之为Berlekamp-Massey算法（BM算法）。BM算法的提出，是分组码走向实用的一个重要里程碑。1966年，G.D.Forney第一次采用简单的分量码

8、构造级联码，以提高码的性能。第一个成功的级联码是采用卷积码作内码、RS码作外码的串行级联码，其典型应用是在卫星通信、深空探测等领域，如Voyager、Galileo、Cassini等任务，这种编码方式还被应用于美国的数字电视（ATSC）、欧洲的数字视频广播（DVB）和数字音频广播（DAB）等系统中；另一种典型的级联码是CBerrou于1993年发现的并行级联卷积码（PCCC）,即我们通常所称的Turbo码，这是一种逼近Shannon限的码。1967年，A.J.Viterbi提出了卷积码的最大似然译码算法，实现了数字通信中信道编码技术的一次实质性突破。Viterbi算法还在其它领域得到了广泛应用

9、。1974年，Bahl等提出了一种最大后验概率（MAP）译码算法（也称为BCJR算法），其误比特率（BER）性能优于Viterbi算法。但由于计算复杂度大大增加,MAP算法直到1993年Berrou发现Turbo码之后才得到广泛应用。由于硬判决译码通常较软判决译码损失2、3dB,对分组码的软判决译码算法的研究也逐渐成为一个重要的课题。对于卷积码，硬判决译码和软判决译码通过相同的格图进行译码，其复杂度大体相同。而对于分组码，基于格图的译码与代数译码相比，复杂度会大大增加，因此次优的译码算法成为首选。在这方面，著名的有广义最小距离（GMD）译码算法、Chase算法等。2）研究了与码的性能有关的各种

10、问题，如码的重量分布、译码错误概率和不可检错误概率的计算、信道的模型化等，所有这些问题的研究为信道编码技术的实用化打下了坚实的基础。3. 70年代初至80年代这是信道编码发展史中最具重要意义的时期，信道编码在理论和实践方面都取得了丰硕的成果。1）在理论上，以Goppa为首的一批学者在70年代初较系统地构造了一类逼近Shannon限的有理多项式码Goppa码,这在纠错码的历史上具有划时代的意义。80年代初，Goppa等将代数几何的理论与方法系统地应用于编码理论中，由Goppa码引出了代数几何码，使得Goppa码日益引起了人们的极大兴趣。1987年，G.Ungerboeck提出了著名的格图编码调制

11、（TCM）技术，展示了如何将编码和调制结合起来，改善系统的整体性能，这是编码理论的乂一重要里程碑。之后，众多研究者开始对TCM进行了深入研究，并将这一概念推广到分组编码调制（BCM）o2）这期间微电子技术的迅速发展，为编码技术的实用化打下了坚实的物质基础；各种实际应用也带动了信道编码技术的发展，编码技术的实用化得到了极大关注，并取得了巨大的进展。例如，用于RS码译码的BM算法进一步发展成熟，出现了无求逆的BM（iBM）算法、Euclid算法、Welch-Berlekamp算法（WB算法）等，其超大规模集成电路（VLSI）实现也得到了充分的发展。信道编码技术最成功的应用在于卫星通信和深空探测领域

12、，这使得宇宙飞船从遥远的太空传回了许多极其宝贵的天文学资料。特别值得一提的是，在1989年的Galileo任务中，由于主天线的故障，数据传输的速率比原设计指标大大下降，喷气式推进实验室（JPL）的科学家们从地面发送指令，重新配置板上计算机，在数据传输之前进行了更多的编码处理，使得由于硬件故障引起的数据传输速率下降得以部分恢复，从而挽救了整个探测计划。若不应用信道编码技术，这些成就的取得是不可企及的。此外，信道编码技术还用于数据存储系统，提高数据存储密度；用于数据传输系统,提高数据传输速率；用于各种数字通信系统，提高通信质量；用于数字音频/视频传输系统以及视听娱乐设备，为我们的生活带来美妙的音乐

13、和完美的视觉享受；而且纠错码技术还应用于超大规模集成电路设计中，以提高集成电路芯片的成品率，降低芯片的生产成本。4. 90年代以后这一时期，编码理论的重大发现当首推1993年Berrou等发现的Turbo码。Turbo码是一种利用伪随机交织器构造的具有随机码行为的长码，它采用并行级联卷积码的方式进行编码，用最大后验概率（MAP）译码器进行迭代译码，分量译码器之间通过传递所谓的外信息来减少信息损失，其性能非常接近Shannon限，这一惊人的性能打破了长期以来的猜想：利用二元卷积码和序列译码是达到截止速率R（即所谓的“实际容量”）的一种可实现的方法。在迭代译码器中，所采用的分量码MAP译码器可以用

14、软入输出Viterbi算法（SOVA）代替，这会使Turbo码译码性能略有下降，但大大降低了计算复杂度和存储量要求。更为实用的分量码译码器是Koch等提出的Max-Log-MAP译码算法和Robertson等提出的Log-MAP译码算法。后来，HagenauerPyndiah乂分别将Turbo码迭代译码的思想用于级联二元分组码和乘积码。现在，Turbo码的迭代算法已经成为“Turbo原理”，广泛应用于各种级联系统，如均衡、编码调制、信源压缩、信源信道联合编码以及信号检测等。另一方面，在探究Turbo码迭代算法的过程中，Mackay和Neal于1996年重新发现了Gallager于60年代提出的

15、具有稀疏校验矩阵的线性分组码一一LDPC码，基于Tanner图进行迭代译码，其性能与Turbo码差不多。最近，采用BCH码作外码、LDPC码作内码的级联码已经被DVB-S2采纳。3/32纠错编码的MATLAB仿真课程设计1998年，Tarokh、Seshadri和Calderbank提出的格图空时码，在时间和空间上都引入了编码，集前向纠错(FEC)、发送分集和接收分集于一体，能获得较大的编码增益和分集增益，实现数据的高速传输。几个月后，Alamouti发明了低复杂度的分组空时码。空时码的基本思想是采用多个发射天线和多个接收天线来提高系统容量，关于空时码已有许多研究文献。由于RS码在众多数字通信

16、系统、数据存储系统中的成功应用，以及其软判决译码性能的巨大潜力，RS码的软判决译码问题也得到了很大的关注。其中，Sudan于1997年提出了多项式复杂度的表单译码(ListDecoding)算法，将RS译码问题转化成有限域上的曲线拟合问题，给出并证明了几个重要的定理，奠定了RS码表单译码的基础。但Sudan算法只适用于码率不大于1/3的RS码，而1999年提出的Guruswami-Sudan算法则可适用于任意码率的RS码和代数几何码。另一方面，Koetter和Vardy基于Guruswami-Sudan算法，将接收符号的软信息转化为一系列的代数条件，用代数方法实现了RS码的软判决译码。1.1纠

17、错编码简介我们知道，在计算机和数据通信中，经常需要将二进制数字信号进行传递，这种传递的距离近则数米!数毫米，远则超过数千公里。在传递信息过程中，由于存在着各种干扰,可能会使二进制信号产生失真现象,即在传递过程中二进制信号0可能会变成1,1可能会变成Oo试想一个二进制信号传递的简单模型,它有一个发送端和一个接收端,二进制信号申从发送端发出经传输介质而至接收端。由于存在着干扰，因而接收端接收到的二进制信号串可能与原来的二进制信号串不相等,从而产生了二进制信号的错误传递。由于在计算机和数据通信系统中的信号传递是非常的频繁与广泛，因此,如何防止传输错误就变得相当重要了，当然，要解决这个问题可以有不同的

18、途径。人们所想到的第一个途径是提高设备的抗干扰能力和信号的抗干扰能力。但是,大家都知道,这种从物理角度去提高抗干扰能力并不能完全消除错误的出现。第二个途径就是我们所要谈到的采用纠错码(Errorcorrectingcode)的方法以提高抗干扰能力。这种纠错码的方法是从编码上下功夫，使得二进制数码在传递过程中一旦出错，在接收端的纠错码装置就能立刻发现错误,并将其纠正。由于这种方法简单易行,因此目前在计算机和数据通信系统中被广泛采用采用这种方法后，二进制信号传递模型就可以变为纠错码模型了。由纠错码模型可以想到，当二进制信号串从发送端发送时:需按规定转换成具有抗干扰能力的纠错码，然后才发送出去。在接

19、收端，当接收到二进制信号串后立即对接收到的纠错码进行检查,查对在途中是否失真,如失真则负责纠正。该模型的一个典型实现，就是在远程数据传输系统中具有纠错能力的数据传输装置，该装置的纠错过程是二进制信号发生器发出信号(二进制信号发生器可以是计算机，或者是山人控制的某些装置如终端)，经差错控制器形成纠错码，然后经调制器使二进制信号变成为适宜于信道传播的电信号,这种信号通过信道传输至接收端，首先通过解调器将其还原为原来的二进制信号，再经差错控制器检验经信道传输后是否产生失真，并采取措施进行纠正。经纠正后的二进制信号送入二进制信号接收器，从而完成整个传输过程二进制信号接收器可以是计算机,或其他接收装置如

20、终端等。但是，为什么纠错码具有发现错误！纠正错误的能力呢？纠错码乂是按什么样的原理去编的呢？为了说明这些问题，我们首先介绍一些基本概念：由0和1组成的串称为字(Word),一些字的集合称为码(Code)。码中的字称为码字(CodeWord)。不在码中的字称为废码(InvalidCode)。码中的每个一.进制信号0或1称为码元(CodeLetter)。我们下面举出几个关于纠错码的例子。设有长度为2的字,它们一共可有2x2=4个，创门所组成的字集S,=00,01,10,11o当选取编码为52时，这种编码不具有抗干扰能力。因为当52中的一个字如10,在传递过程中其第一个码元1变为0,因而整个字成为0

21、0时，由于00也是52中的字，故我们不能发现传递中是否出错。但是，当我们选取52的一个子集如C2二00,川作为编码时就会发生另一种完全不同的情况。因为此时01和10均为废码,而当H在传递过程中第一个码元由1变为0,即整个字成为01时，由于01是废码，因而我们发现传递过程中出现了错误。对00也有同样的情况。但是，这种编码有一个缺点，即它只能发现错误而不能纠正错误，因此我们还需要选择另一种能纠错的编码现在我们考虑长度为3的字，它们一共可有2!3=8个，它们所组成的字集凡000,001,010,011,100,101,110,111中我们选取编码q二001,110o利用此编码我们不仅能发现错误而且能

22、纠正错误。因为码字001出现错误后将变为：ooo,on,101,而码字no出现错误后将变为:m,wo,010。故如码字ooi在传递过程中任何一个码元出现了错误，整个码字只会变为101!011或000,但是都可知其原码为001o对于码字110也有类似的情况故对编码Q,我们不仅能发现错误而且能纠正错误”当然,上述编码还有一个缺点,就是它只能发现并纠正单个错误。当错误超过两个码元时,它就既不能发现错误,更无法纠正了。2Reed-SoIomon编码概述Reed-Solomon码(RS码)是Reed和Solomon于1960年发现的一类多元最大距离可分(MDS)码,其最小距离达到了Singletonmi

23、nd=n-k+l,从这个意义上讲,RS码是最佳的。之后儿十年里，RS码的硬判决译码得到了深入的研究，其理论和技术都已经非常成熟。因而，RS码在现代数字通信、数据存储系统中得到了广泛的应用，见下表应用领域编码方案硬盘驱动器RS(32,28,5)码CD交叉交织RS码(CIRC)DVDRS(208,192,17)码、RS(182,172,11)码乘积码5/32纠错编码的MATLAB仿真课程设计DAB、DVB内码为卷积码、外码为RS(204,188,17)码的级联码ATSC内码为卷积码、外码为RS(207,187,21)码的级联码深空通信内码为卷积码、外码为RS(255,223,33)码的级联码光纤通

24、信RS(255,239,17)码有限域算术是RS码的基础，并行通用有限域乘法器的时延决定了RS码译码器的工作频率。如何用现场可编程门阵列(FPGA)实现通用有限域乘法器，降低其运算时延，是软件无线电中RS码译码子系统设计过程中要考虑的一个关键的问题。在工程实践中通常采用的“直接二级逻辑设计”仅仅依靠综合工具对所设计的电路进行优化，不能有效地利用FPGA所提供的资源，降低有限域乘法器的时延。就作者所知，目前还没有一种系统的方法，可以用来设计高速并行有限域乘法器。RS码的硬判决译码器不能充分地利用接收信息，造成了一定的性能损失。众所周知，从最小化不正确译码概率的意义上讲，最大似然译码(MLD)是最

25、好的方法。在AWGN信道条件下，RS码的最大似然译码与硬判决距离译码相比，会有2.5、3.2dB的软判决译码增益；在衰落信道条件下，其软判决译码增益会更大。2005年，Guruswami和Vardy90在IEEE信息论会刊上撰文指出，RS码的最大似然译码是NP-Hard问题。因此，低复杂度的次优译码算法成为人们研究的热点。现有的RS码软判决译码算法主要有以下四类： 基于代数译码器的软判决译码：主要有纠错纠删译码、广义最小距离(GMD)译码算法、Chase算法、Lacan算法、有序统计量译码(OSD)算法等； 基于格图的译码：主要有Vardy和Beery提出的比特级软判决译码算法、Ponnamp

26、alam和Vucetic提出的简化的比特级软判决译码算法等； 基于Tanner图的译码：基于自适应校验矩阵的软判决译码算法、基于临界抽取滤波器组表示的软判决译码算法等； 表单译码：主要有Koetter-Vardy算法等。这些译码算法各有千秋，就实用性而言，GMD算法、Chase-II算法和Koetter-Vardy算法略胜一筹。3Reed-Solomon编码抽象代数基础3.1 群定义设G是一个非空集合，称映射0:GxGfG为G上的一个二元运算，即对于G中仍以两个元a和6,唯一确定c=(a,b).记为c=a-b,为了方便起见，可写成c=ab.定义设G是一个非空集合，是G上的一个二元运算，如果G满

27、足下列条件：(结合律)对于任意4,ceG,有(a-b),c=aQ-c)(单位元)G中存在单位元e,对于任意aeG,满足=(逆元)对于任意。，存在的逆元，尸，满足a-1=a-a=e则称G为群，记为(G,).如果群(G,)满足交换律，即对于任意“/eG,满足为=则称群为交换群或阿贝尔群.3.2环和域定义设斤是一个非空集合，斤上有两个二元运算+和，分别成为加法和乘法，如果斤满足下列条件a)(2+)为加法阿贝尔群(结合律)对于任意有(ab)c=a-(bc)(分配律)对于任意有:称万为环，记为(凡十),如果他对乘法满足交换律，即对任何(b+c)-a=ba+c-aa,beRah=ba称环(R,+,)为交换

28、环定义设(凡+,)为交换环，之表示A中所有非零元的集合，如果*在乘法运算下构成交换群，则称(凡+,)为域。3.3有限域定义设尸为一个域，如果尸只含有有限个元素，称尸为有限域，含有。个元素的有限域记为尸7,有限域也成为伽罗华域(Galoisfield),用Yq)或表示q阶有限域。最简单的有限域是二元域GF(2)=0,1o定义对于小3上的每个非零元素?，存在最小整数上使加=1成立，则称为A阶元素。定义对于成上的每个非零元素夕，如果其阶数是Q-1,则称仅为本原元素。定义Gb(2)上的一个卬次多项式双x),如果他的所有根都是6/(2)中的本原元素，则称；r(x)是加次本原多项式。例如，对于m=8时G尸

29、(2小)=6/(2,上的m次本原多项式为%(x)=1+/+/+/+/对于m=7时GFQ、=6/(2，)上的m次本原多项式为产(x)=1+1+x7定义设夕为G尸(2中的元素，多项式口)是GE(2)上使m(0)=0的最低次多项式，则称，)为最小多项式。具有相同最小多项式的元素，构成同一共桅系。1.1欧几里得算法欧儿里得算法给定两个正整数a,b,可以用欧儿里得除法得到其最大公约数(a,b),并求得A,B,满足(a,b);Aa+Bb。用欧儿里得除法求勿的步骤如下：第一步：不失一般性,假设a6,且令二2=。，二1=，4=-2第二步：用除以乙得到其商数怎+2和余数加2,亦即=%2+1+2第三步：如果4+2

30、=。，停止运算，并记=4+2；否则，k=+1转第二步。欧儿里得算法乂被称为辗转相除法，这里是单调下降序列。用欧儿里得算法可以求得儿B,沿用上述除法得到/的和力其方法如下：第一步：令2=0立1=1*=1第二步：计算瓦_1=4仄+bk+第三步：如果k=0,停止运算，此时A=%,8=%，否则攵=左-1转第二步事实上，9,(=44+心m_1，04,8)只是其中的一个特例。2BCH码、RS码及其编码2.1BCH码、RS码简介如前所述，BCH码是纠错能力可能的循环码，illBose、Chandhari和Hocquenghem在19501960年间分别独立地提出。最初的BCH码定义在二元域上，成为二元BCH

31、码，后来推广到多源于上。对于设计纠错能力为t的循环码，器生成多项式含有2t个连续幕次的根，这样的循环码称为BCH码。如果BCH码的根是本原元，成为本原BCH码。如果BCH码的根是非本原元，称为非本原BCH码。如果定义在G/(2)上的本原元。以及a?、。”共2t个连续幕次都是定义在GE(2)上的生成多项式g(x)的根，那么该BCH码成为设计纠错能力为t的二元本原BCH码。对于任意的证书卬和纠错数t,都可以构造出最小距离为，的二元本原BCH码，%,刃，n=2n-,kn-mt=2n,-1-mt,d2t+o另外，实际的纠错能力t,可能会大于设计纠错能力的t.同理，如果定义在G/(21上的非本原元月以及

32、犷、夕、夕”共2t个连续幕次都是定义在GE(2)上的生成多项式g(x)的根，那么该BCH码成为设计纠错能力为匕的二元非本原BCH码。进一步假设非本原元月和本原元。满足关系夕=优，其中lvcv2”-l,如果衣=2桁-1成立，那么/T=l,也就是说夕是n阶非本原元。如果c=2-l成立，那么可以构造出最小距离为，的二元非本原BCH码，6,2司，满足nc=2n-,kn-mt=2-1-mt,J2r+1o另外，实际的纠错能力力可能会大于设计纠错能力的士.BCH码的编码是在二元域完成的，对比特进行编码，与普通的二进制循环码并无不同。而RS的编码是在多元域GF(p，)上完成的(p是质数)，对符号进行编码，因为

33、RS码又被挈为多元域上的本原BCH码。如果定义在G/p)上的生成多项式g(x)=n(x-a),其中a是定义在W(p)上的本原元，那么该BCH码被称为纠错能力为t的诙码。1.1RS码的构造方法第一步，由关系式=2，”-1算出小查本原多项式表得到一个m次的本原多项式P(x),从而产生一个G/(2”)的扩域，使域元素(符号)优与m重向量建立起一一对应的关系本原多项式表mM本原多项式21+X+A23+x+x341+x+x45l+x2+x56+x+x67l+x3+x78+x2+x3+x4+x第三步：根据设计纠错能力t,直接计算定义在Gf)上的生成专项式g(x)=n(x-a,)o利用a”=ld+=0和P(

34、a)等运算规则，可以将*-优)展开并化简为软幻=/改。第三步：代知生成多项式g(x),根据关系式C(x)=M(x)g(x),对信息位M多项式9/32纠错编码的MATLAB仿真课程设计编码得到码字多项式C(x),这就完成了RS码的编码过程。这里的C(x)、M(x)和gj)23 / 32都是GF(2川)上的多项式。而对于长度为mk的二进制的输入序列，以m个比特位一组划分可以得到k个m重向量，再将每个m重向量映射为GF(2“l上的元素，从而得到长度为k的多元序列M(x)o得到长度为n的多元序列C*)后，对于每一个GF(2。上的元素，再映射为m重向量，从而得到长度为nm的二进制编码序列。例如，对于信息

35、输入比特序列100,101,010，首先根据表格。的各次罂将序列映射为GF(23)上的序列a?,/，,。,则其信息位多项式加(工)=&-2+261+2。那么可以求得G&j上的码字多项式。C(x)=M(x)g(x)=(a2x2+abx+a)(x4+x2+ax+a)=a2x6+ad+a/+-从而得到G42，)上的编码序列aaao,/,。,/。再根据表格。的各次暴将其映射为二进制编码序列即可得到RS码100,010,010,000,100,000,110)o表格。的各次事即约多项式3重向量00001001a010a2100a3=a+Oil42.a=a+a110a、=a2+a+1111a=a+1101

36、RS码是纠正短突发差错的首选纠错码，广泛应用于无线通信的存储系统中。例如，美国宇航局(NASA)在探险者号(Voyager)上用了256进制的255,223,33RS码，其生成扩域的本原多项式是尸(幻=1+/+/+/+/,相=8,生成多项式是g(x)=(x-a)(x-a2)(x-a32)oa是本原多项式P(x)的根,因为g(x)含有32个连续幕次的根，因而改码的纠错能力为符号1=32/2=16个符号(256进制)或者等效长度是(-1)帆+1E21的二进制特发差错。4RS码的译码由于BCH码和R-S码都是循环码，所以可以采用一般的梅杰特解码器，但是BCH码和R-S码的设计纠错能力都比较高，从而使

37、得梅杰特解码器的实现复杂度BCH码和RS码的解码原理是一样的，其高效解码算法的基础在于一个关键方程的引入和基于多项式的欧儿里德算法。在BCH/RS码的解码算法的发展历史上，彼得森(Peterson)于1960年提出了第一个BCH的解码算法。之后,钱(Chien)、福尼(Formey)梅西(Massey)和巴勒坎普(Berlekamp)相继提出了更高效的BCH解码算法。到了1975年，Sugiyama、KasaharaHirasawa和Namekawa发现也可以采用欧儿里德(Euclid)算法对BCH/RS码解码，并发现巴勒坎普(Berlekamp)解码算法与欧儿里德(Euclid)算法相比仅差

38、一个很小的常数因子。而欧凡里德(Euclid)算法更容易理解些，所以得到了更广泛的应用。具体解码又可以分为时域解码和频域解码。1.1关键方程的引入一】令尸是一个含有a阶单元本原元。的域，那么根据定义有l-x=n(l-ax)，再令/是尸上的一个A维向量，V称为时域向量。又令V=,；Q,辱V的离散傅里叶变换(DFT),成为频域向量；DFT(离散傅里叶变换)：)=匕，,小0,-1那么，可以证明，从频域到时域的IDFT(逆离散傅里叶变换)也成立；1AIDFT(逆离散傅里叶变换)：,二上2以/，/。，“设尸是GF(pD，是质数，=p5二f,那么特征是外IDFT中的是以特征为模In的同余类。易知=(-l)

39、mod，所以一=Imodp,根据欧几里得算法有11n-=(/?-l)modpo对于GF(2,”)，一=1在定义/和V的生成多项式：V(x)=%+匕x+匕和(、)历邛4M7(.才尸婷。那么，可以将上述的离散傅里叶变换写为：人对于V，定义他的支持集/,/=，：匕。0,，0,-1,亦即/是V中非缘品羞肺帮窿r桂定义/的位置多项式(x)R(x)=q(i-优幻。对于运/,再定义阶穿孔位置多项式b，a),b?(x)=口(1-0公)/(1行：最后，定义/的数值多项式程.(x),q(x)=%b，(x)。那么，可照正明GCD(5(x)，5(x)=1。定理为键方程/对于固定的向量匕多项式4，q(x)和V(x)满足

40、一下关键方程%(x)V(x)=4*)(l-x”)有了上述的数学基础，就可以引入BCH/RS码的关键方程了。设编码向量为C=c,信道错误图案为向量石=52,j_J,那么接收向量R=C+E,解码的第一步是计算伴随式向量S=%,S,S的定义如下/r-1一I一13=小。那么，=ZW=ZW令时域向量丫。)=4，60,易知，祥随式向量S与频域向量丫满足关系;=%/。,力-1,亦即，伴随式向量S是V的钱2匕个分量，这是可以A一直接观测到的，而V的后(n-2t)个分量不能直接观测到。记伴随式多项式S(x)=M.解码算法的目的是已知伴随式到量S求错误图案向量凡从而得到解码向量C=R-E,由于只是知道频域向量V(

41、x)的前2t个分量，需要用mod.一对关键方程降次A5.(x)V(x)modx2!=yy(x)(l-x)modx。所以得到BCH/RS的关键方程(x)SCt)=.(A)mod.r,由于V的支持集是发生误码的标号集合，所以b(x)乂被成为错误位置多项式，b(x)=b、(x),而以x)乂被成为错误数值多项式，其中以幻=%(%),deg(o-(x)r,deg()deg(6(x)且令匚i=a(x),“=匕),女=一1第二步：用修除以，得到其商数%2。)和余数仁21)，亦即4(X)=%2(X)+l(X)+4+2(X)第三步:如果+20)=0，停止运算，d(x)=gcd(a,。)=+i(x),并记=k+1

42、；否则k=k+1,转第二步。欧儿里得处理乂被成为辗转相除法，这里deg)是单调下降序列。用欧儿里得算法可以求得(x),i，(x)。沿用上述除法得到外和“，其方法如下：第一步：M_iW=1,M()(A)=O；V(X)=O,VO(X)=1；=1第二步：计算一(x)=%式幻-%(X)；吊(X)=%(X)-%(x)k(x)；第三步:如果k=,停止运算,此时u(x)=ii(x),v(x)=v(x)；否则k=k+1,转第二步。这里，deg(式x)是单调递增函数，而deg0(x)也是单调递增函数。容易得到以下两条性质：/(幻心)+”3)=(x”k+从而推出以下性质:(2)deg(唳+deg(_()=deg(

43、a(x),V攵e0,n+l(l)/(x)(x)=(工)moda(x),e-1,71+1进一步有如下.)加8(匕)+deg)deg(/?(x)满足：v(x)b(x)=r(x)moda(x)deg-mdeg(r(x)nm+n=deg(a(x)-1进一步假设vA(X)和“(%)伏eji+1)是对(a),/?(%)应用欧儿里得算法得到的多项式序列。那么存在且唯一存在标号力+使得V.(a)/?(A-)=o(x)moda(x)用一个欧儿里得抽象函数Vj(x),7)(x)=Euclid(x),/?(x),m9n表示上述结果。进加存在一个常数多项式X(x),使得：v(x)=A(x)v(x)这个定理表明完全可以

44、用欧几里得算法解决BCH/RS码的关键方程。r(x)=A(x)r.(x)1.1BCH/RS码的解码步骤有了关键方程和欧儿里得抽象函数，讨论BCH/RS解码的步骤就水到渠成了。假设已经求得了错误位置多项式b(x)和错误数值多项式次x),为工求差错图案多项式七(幻，有时域和频域处理两种方法。求出E(x)后，解码码字向量Z=R-E时域算法的本质就是对错误位置多项式b(x)进行验根。由于b(x)=n(l-/)，那么b(a-i)=0；反之，如果7(。-)=0,那么含有因子(1一x)。所以，揖臬b(a-，)=0,说明第i个位置上的接收向量小存在误码，否则第i个位置上的接收向量是正确的。对于二元域BCH码，

45、e,e0,l比较简单，如果6。7)=0,那么巧=1,否则4=0。而对于多元域上的RS码，4号多元域元素，还需零进一步求出。对于RS码，如果b(2Tj=0,那么匕丝0,亦即e产一丝?，否则=0。首先用C语言由脩马明BCH码的品输4马算法，如下所示：/*二元域BCH码的属于解码算法*/“/*码长n,设计纠错能力t,接收向量R,错误图案向量E,解码码字向量2*/(for(j=lto2t)n1，；卜u，2s)=；if(SM-o)printf(接收码字正确，无误码“)；else(用欧儿里得算法解关键方程vy(x),.(x)=Euclid1%2,S(x)JJ-1;if(v.(O)=O)printf(误码超出了纠错能力t,不可解码)；else(o-(A)=v/x)/vy(O);for(i=Oton-l)if(cr(a-,)=0)4=1elseq=0for(i=0ton-l)RCi=ri-ei,aapr