RS255,223纠错编码的MATLAB仿真课程设计报告书

1、. . . . 编号：课程设计说明书题 目： RS(255,223)纠错编码的 MATLAB仿真 院 （系）：专 业：学生：学 号：指导教师：2013 年 12月10日目 录1 引言21.1信道编码理论与技术的发展历程与应用21.2纠错编码简介42Reed Solomon编码概述53Reed Solomon编码抽象代数基础63.1 群63.2环和域73.3有限域73.4欧几里得算法84BCH码、RS码与其编码94.1BCH码、RS码简介94.2RS码的构造方法105RS码的译码115.1关键方程的引入125.2多项式的欧几里得算法135.3BCH/RS码的解码步骤156MATLAB主要程序与其

2、仿真结果187总结19致20参考文献21附 录2222 / 25摘 要在纠错码领域中Reed-Solomon码是一类具有严格代数结构的线性分组码。由于它突出的纠错能力(特别是纠突发错误的能力),常被应用于数据存储以与现代数字通信系统中。在卫星通讯中，差错控制编码技术对降低误码率、提高通信的可靠性具有非常重要的作用。RS(Reed-Solomon)码是差错控制领域中一种性能优异的线性分组循环码，由于其具有很强的随机错误和突发错误的纠错能力，所以被CCSDS、NASA、ESA 等空间组织接受，广泛用于深空探测中。目前我国还没有高码速率的 RS 硬件译码器，虽然“双星计划”已经采用 RS纠错编码技术

3、，在卫星上使用 RS(255,223)硬件编码器进行编码，但是由于硬件译码器的复杂性，地面接收系统采用的是软件译码，无法保证通信的实时性。为此，本文在详细介绍RS(255,223)编码译码的基础上，利用MATLAB软件对该理论进行仿真。关键词：Reed-Solomon编码；抽象代数；RS码编码；RS码译码算法；RS(255,223)仿真；MATLAB1 引言1.1 信道编码理论与技术的发展历程与应用Shannon 的信道编码定理给出了有噪信道通信的最大速率，证明了好码的存在性，但对该定理证明是非构造性的，它没有告诉我们怎么构造好码。如何通过不可靠信道进行可靠的通信，是编码理论所要研究的问题。半

4、个多世纪以来，众多的学者为构造逼近容量限的纠错码做了大量的工作，但这一问题直到 45 年后才基本得到解决。但是，“过程比目标更重要”，在应对这一挑战的过程中，编码理论家和工程师们应用组合数学、线性代数、概率论、有限域理论等数学工具，建立了纠错码的性能参数限，发现了许多构造纠错码的方法，并设计了有效的编译码算法，为信息技术的蓬勃发展建立了不朽的功勋！在 Shannon 的论文发表之前，Richard Hamming 就已经为早期的计算机设计了一种纠单个错误的码，迈出了信道编码理论与技术研究的第一步。之后，信道编码理论与与技术的大致经历了以下几个发展阶段：1. 50 年代至 60 年代初这是编码理

5、论从无到有并得到迅速发展的年代，现代编码理论的许多思想都起源于这一时期。1）发现了几种线性分组码，如 Golay 码、Reed-Muller 码（RM 码）、Reed-Solomon 码（RS 码）、Bose-Chaudhuri-Hocquengham 码（BCH 码）、低密度校验码（LDPC 码）等，以与卷积码；2）为这些码设计了有效的译码算法，如用于 RS 码和 BCH 码译码的 PGZ 算法、用于卷积码译码的 Fano 译码算法；3）证明了纠错码的几个最小码距限，如 Hamming 限（H 限）、Singleton限、Plotkin 限（P 限）、Gilbert-Varshamove 限

6、（GV 限），其证明可以在编码理论的基础教材中找到；4）1957 年，Elias 提出了一种概念译码器表单译码器（List Decoder），以突破传统的限定距离译码（BDD）的半最小码距的纠错半径；5）1961 年，W. W. Peterson 编写了第一本关于纠错码理论的专著，系统地阐述了纠错码的基本理论。2. 60 年代至 70 年代初这是纠错码发展最为活跃的时期之一。在此期间，以代数方法特别是以有限域理论为基础的线性分组码理论已趋成熟。1）提出了许多有效的编、译码方法。1965年，E. R. Berlekamp提出了一种实用分组码的代数译码算法，1969年, J.L. Massey从序

7、列综合的角度重新推导了这一算法，后人称之为Berlekamp-Massey算法（BM算法）。BM算法的提出，是分组码走向实用的一个重要里程碑。1966年，G. D. Forney第一次采用简单的分量码构造级联码，以提高码的性能。第一个成功的级联码是采用卷积码作码、RS码作外码的串行级联码，其典型应用是在卫星通信、深空探测等领域，如Voyager、Galileo、Cassini等任务，这种编码方式还被应用于美国的数字电视（ATSC）、欧洲的数字视频广播（DVB）和数字音频广播（DAB）等系统中；另一种典型的级联码是C. Berrou于1993年发现的并行级联卷积码（PCCC），即我们通常所称的T

8、urbo码，这是一种逼近Shannon限的码。1967年，A. J. Viterbi提出了卷积码的最大似然译码算法，实现了数字通信道编码技术的一次实质性突破。Viterbi算法还在其它领域得到了广泛应用。1974年，Bahl等提出了一种最大后验概率（MAP）译码算法（也称为BCJR算法），其误比特率（BER）性能优于Viterbi算法。但由于计算复杂度大大增加，MAP算法直到1993年Berrou发现Turbo码之后才得到广泛应用。由于硬判决译码通常较软判决译码损失23dB，对分组码的软判决译码算法的研究也逐渐成为一个重要的课题。对于卷积码，硬判决译码和软判决译码通过一样的格图进行译码，其复杂

9、度大体一样。而对于分组码，基于格图的译码与代数译码相比，复杂度会大大增加，因此次优的译码算法成为首选。在这方面，著名的有广义最小距离（GMD）译码算法、Chase算法等。2）研究了与码的性能有关的各种问题，如码的重量分布、译码错误概率和不可检错误概率的计算、信道的模型化等，所有这些问题的研究为信道编码技术的实用化打下了坚实的基础。3. 70 年代初至 80 年代这是信道编码发展史中最具重要意义的时期，信道编码在理论和实践方面都取得了丰硕的成果。1）在理论上，以 Goppa 为首的一批学者在 70 年代初较系统地构造了一类逼近 Shannon 限的有理多项式码Goppa 码，这在纠错码的历史上具

10、有划时代的意义。80 年代初，Goppa 等将代数几何的理论与方法系统地应用于编码理论中，由 Goppa 码引出了代数几何码，使得 Goppa 码日益引起了人们的极大兴趣。1987 年，G. Ungerboeck 提出了著名的格图编码调制（TCM）技术，展示了如何将编码和调制结合起来，改善系统的整体性能，这是编码理论的又一重要里程碑。之后，众多研究者开始对 TCM 进行了深入研究，并将这一概念推广到分组编码调制（BCM）。2）这期间微电子技术的迅速发展，为编码技术的实用化打下了坚实的物质基础；各种实际应用也带动了信道编码技术的发展，编码技术的实用化得到了极大关注，并取得了巨大的进展。例如，用于

11、 RS 码译码的 BM 算法进一步发展成熟，出现了无求逆的 BM（iBM）算法、Euclid 算法、Welch-Berlekamp 算法（WB 算法）等，其超大规模集成电路（VLSI）实现也得到了充分的发展。信道编码技术最成功的应用在于卫星通信和深空探测领域，这使得宇宙飞船从遥远的太空传回了许多极其宝贵的天文学资料。特别值得一提的是，在 1989年的 Galileo 任务中，由于主天线的故障，数据传输的速率比原设计指标大大下降，喷气式推进实验室（JPL）的科学家们从地面发送指令，重新配置板上计算机，在数据传输之前进行了更多的编码处理，使得由于硬件故障引起的数据传输速率下降得以部分恢复，从而挽救

12、了整个探测计划。若不应用信道编码技术，这些成就的取得是不可企与的。此外，信道编码技术还用于数据存储系统，提高数据存储密度；用于数据传输系统，提高数据传输速率；用于各种数字通信系统，提高通信质量；用于数字音频/视频传输系统以与视听娱乐设备，为我们的生活带来美妙的音乐和完美的视觉享受；而且纠错码技术还应用于超大规模集成电路设计中，以提高集成电路芯片的成品率，降低芯片的生产成本。4. 90 年代以后这一时期，编码理论的重大发现当首推1993年Berrou等发现的Turbo码。Turbo码是一种利用伪随机交织器构造的具有随机码行为的长码，它采用并行级联卷积码的方式进行编码，用最大后验概率（MAP）译码

13、器进行迭代译码，分量译码器之间通过传递所谓的外信息来减少信息损失，其性能非常接近Shannon限，这一惊人的性能打破了长期以来的猜想：利用二元卷积码和序列译码是达到截止速率R （即所谓的“实际容量”）的一种可实现的方法。在迭代译码器中，所采用的分量码MAP译码器可以用软入输出Viterbi算法（SOVA）代替，这会使Turbo码译码性能略有下降，但大大降低了计算复杂度和存储量要求。更为实用的分量码译码器是Koch等提出的Max-Log-MAP译码算法和Robertson等提出的Log-MAP译码算法。后来，Hagenauer、Pyndiah又分别将Turbo码迭代译码的思想用于级联二元分组码和

14、乘积码。现在，Turbo码的迭代算法已经成为“Turbo原理”，广泛应用于各种级联系统，如均衡、编码调制、信源压缩、信源信道联合编码以与信号检测等。另一方面，在探究Turbo码迭代算法的过程中，Mackay和Neal于1996年重新发现了Gallager于60年代提出的具有稀疏校验矩阵的线性分组码LDPC码，基于Tanner图进行迭代译码，其性能与Turbo码差不多。最近，采用BCH码作外码、LDPC码作码的级联码已经被DVB-S2采纳。1998年，Tarokh、Seshadri和Calderbank提出的格图空时码，在时间和空间上都引入了编码，集前向纠错（FEC）、发送分集和接收分集于一体，

15、能获得较大的编码增益和分集增益，实现数据的高速传输。几个月后，Alamouti发明了低复杂度的分组空时码。空时码的基本思想是采用多个发射天线和多个接收天线来提高系统容量，关于空时码已有许多研究文献。由于RS码在众多数字通信系统、数据存储系统中的成功应用，以与其软判决译码性能的巨大潜力，RS码的软判决译码问题也得到了很大的关注。其中，Sudan于1997年提出了多项式复杂度的表单译码（List Decoding）算法，将RS译码问题转化成有限域上的曲线拟合问题，给出并证明了几个重要的定理，奠定了RS码表单译码的基础。但Sudan算法只适用于码率不大于1/3的RS码，而1999年提出的Gurusw

16、ami-Sudan算法则可适用于任意码率的RS码和代数几何码。另一方面，Koetter和Vardy基于Guruswami-Sudan算法，将接收符号的软信息转化为一系列的代数条件，用代数方法实现了RS码的软判决译码。1.2 纠错编码简介我们知道,在计算机和数据通信中,经常需要将二进制数字信号进行传递,这种传递的距离近则数米!数毫米,远则超过数千公里。在传递信息过程中,由于存在着各种干扰,可能会使二进制信号产生失真现象,即在传递过程中二进制信号O可能会变成1,1可能会变成0。试想一个二进制信号传递的简单模型,它有一个发送端和一个接收端,二进制信号串从发送端发出经传输介质而至接收端。由于存在着干扰

17、,因而接收端接收到的二进制信号串可能与原来的二进制信号串不相等,从而产生了二进制信号的错误传递。由于在计算机和数据通信系统中的信号传递是非常的频繁与广泛,因此,如何防止传输错误就变得相当重要了,当然,要解决这个问题可以有不同的途径。人们所想到的第一个途径是提高设备的抗干扰能力和信号的抗干扰能力。但是,大家都知道,这种从物理角度去提高抗干扰能力并不能完全消除错误的出现。第二个途径就是我们所要谈到的采用纠错码(Errorcorrectingcode)的方法以提高抗干扰能力。这种纠错码的方法是从编码上下功夫,使得二进制数码在传递过程中一旦出错,在接收端的纠错码装置就能立刻发现错误,并将其纠正。由于这

18、种方法简单易行,因此目前在计算机和数据通信系统中被广泛采用"采用这种方法后,二进制信号传递模型就可以变为纠错码模型了。由纠错码模型可以想到,当二进制信号串从发送端发送时,需按规定转换成具有抗干扰能力的纠错码,然后才发送出去。在接收端,当接收到二进制信号串后立即对接收到的纠错码进行检查,查对在途中是否失真,如失真则负责纠正。该模型的一个典型实现,就是在远程数据传输系统中具有纠错能力的数据传输装置,该装置的纠错过程是二进制信号发生器发出信号(二进制信号发生器可以是计算机,或者是由人控制的某些装置如终端),经差错控制器形成纠错码,然后经调制器使二进制信号变成为适宜于信道传播的电信号,这种信

19、号通过信道传输至接收端,首先通过解调器将其还原为原来的二进制信号,再经差错控制器检验经信道传输后是否产生失真,并采取措施进行纠正。经纠正后的二进制信号送入二进制信号接收器,从而完成整个传输过程"二进制信号接收器可以是计算机,或其他接收装置如终端等。但是,为什么纠错码具有发现错误!纠正错误的能力呢?纠错码又是按什么样的原理去编的呢?为了说明这些问题,我们首先介绍一些基本概念:由0和1组成的串称为字(Word),一些字的集合称为码(Code)。码中的字称为码字(CodeWord)。不在码中的字称为废码(InvalidCode)。码中的每个二进制信号0或1称为码元(Code Letter)

20、。我们下面举出几个关于纠错码的例子。设有长度为2的字,它们一共可有2x2=4个,创门所组成的字集S,=00,01,10,11。当选取编码为52时,这种编码不具有抗干扰能力。因为当52中的一个字如10,在传递过程中其第一个码元1变为0,因而整个字成为00时,由于00也是52中的字,故我们不能发现传递中是否出错。但是,当我们选取52的一个子集如C2二00,川作为编码时就会发生另一种完全不同的情况。因为此时01和10均为废码,而当H在传递过程中第一个码元由1变为O,即整个字成为01时,由于01是废码,因而我们发现传递过程中出现了错误。对00也有同样的情况。但是,这种编码有一个缺点,即它只能发现错误而

21、不能纠正错误,因此我们还需要选择另一种能纠错的编码"现在我们考虑长度为3的字,它们一共可有2!3=8个,它们所组成的字集凡000,001,010,011,100,101,110,111中我们选取编码q二001,110。利用此编码我们不仅能发现错误而且能纠正错误。因为码字001出现错误后将变为:000,011,101,而码字110出现错误后将变为:111,100,010。故如码字001在传递过程中任何一个码元出现了错误,整个码字只会变为101!011或000,但是都可知其原码为001。对于码字110也有类似的情况"故对编码q,我们不仅能发现错误而且能纠正错误"当然,

22、上述编码还有一个缺点,就是它只能发现并纠正单个错误。当错误超过两个码元时,它就既不能发现错误,更无法纠正了。2 Reed Solomon编码概述Reed-Solomon 码（RS 码）是 Reed和 Solomon于 1960 年发现的一类多元最大距离可分（MDS）码，其最小距离达到了 Singleton 限mind = n k+ 1，从这个意义上讲，RS 码是最佳的。之后几十年里，RS 码的硬判决译码得到了深入的研究，其理论和技术都已经非常成熟。因而，RS码在现代数字通信、数据存储系统中得到了广泛的应用，见下表应用领域编码方案硬盘驱动器RS(32, 28, 5)码CD交叉交织 RS 码（CI

23、RC）DVDRS(208, 192, 17)码、RS(182, 172, 11)码乘积码DAB、DVB码为卷积码、外码为 RS(204, 188, 17)码的级联码ATSC码为卷积码、外码为 RS(207, 187, 21)码的级联码深空通信码为卷积码、外码为 RS(255, 223, 33)码的级联码光纤通信RS(255, 239, 17)码有限域算术是 RS 码的基础，并行通用有限域乘法器的时延决定了 RS 码译码器的工作频率。如何用现场可编程门阵列（FPGA）实现通用有限域乘法器，降低其运算时延，是软件无线电中 RS 码译码子系统设计过程中要考虑的一个关键的问题。在工程实践常采用的“直接

24、二级逻辑设计”仅仅依靠综合工具对所设计的电路进行优化，不能有效地利用 FPGA 所提供的资源，降低有限域乘法器的时延。就作者所知，目前还没有一种系统的方法，可以用来设计高速并行有限域乘法器。RS 码的硬判决译码器不能充分地利用接收信息，造成了一定的性能损失。众所周知，从最小化不正确译码概率的意义上讲，最大似然译码（MLD）是最好的方法。在 AWGN 信道条件下，RS 码的最大似然译码与硬判决距离译码相比，会有 2.53.2dB 的软判决译码增益；在衰落信道条件下，其软判决译码增益会更大。2005 年，Guruswami 和 Vardy90在 IEEE 信息论会刊上撰文指出，RS 码的最大似然译

25、码是 NP-Hard 问题。因此，低复杂度的次优译码算法成为人们研究的热点。现有的 RS 码软判决译码算法主要有以下四类：l 基于代数译码器的软判决译码：主要有纠错纠删译码、广义最小距离（GMD）译码算法、Chase 算法、Lacan 算法、有序统计量译码（OSD）算法等；l 基于格图的译码：主要有 Vardy 和 Beery提出的比特级软判决译码算法、Ponnampalam 和 Vucetic提出的简化的比特级软判决译码算法等；l 基于 Tanner 图的译码：基于自适应校验矩阵的软判决译码算法、基于临界抽取滤波器组表示的软判决译码算法等；l 表单译码：主要有 Koetter-Vardy 算

26、法等。这些译码算法各有千秋，就实用性而言，GMD算法、Chase-II算法和Koetter-Vardy算法略胜一筹。3 Reed Solomon编码抽象代数基础3.1 群定义 设G是一个非空集合，称映射为G上的一个二元运算，即对于G中仍以两个元a和b，唯一确定(a,b).记为,为了方便起见，可写成c=ab.定义 设G是一个非空集合，是G上的一个二元运算，如果G满足下列条件：a) （结合律）对于任意,有b) （单位元）G中存在单位元，对于任意，满足c) （逆元）对于任意，存在的逆元，满足则称G为群，记为.如果群满足交换律，即对于任意，满足则称群 为交换群或阿贝尔群.3.2 环和域定义 设R是一个

27、非空集合，R上有两个二元运算和，分别成为加法和乘法，如果R满足下列条件a) 为加法阿贝尔群b) （结合律）对于任意,有c) （分配律）对于任意,有称R为环，记为，如果他对乘法满足交换律，即对任何称环为交换环定义 设为交换环，表示R中所有非零元的集合，如果在乘法运算下构成交换群，则称为域。3.3 有限域定义 设F为一个域，如果F只含有有限个元素，称F为有限域，含有q个元素的有限域记为，有限域也成为伽罗华域(Galois field)，用GF(q)或表示q阶有限域。最简单的有限域是二元域GF(2)=0,1。定义 对于GF(q)上的每个非零元素，存在最小整数k,使成立，则称为k阶元素。定义 对于GF

28、(q)上的每个非零元素，如果其阶数是q-1,则称为本原元素。定义上的一个m次多项式，如果他的所有根都是中的本原元素，则称是m次本原多项式。例如，对于m = 8时上的m次本原多项式为对于m = 7时上的m次本原多项式为定义 设为中的元素，多项式是上使的最低次多项式，则称为最小多项式。具有一样最小多项式的元素，构成同一共轭系。3.4 欧几里得算法欧几里得算法给定两个正整数a,b，可以用欧几里得除法得到其最大公约数(a,b)，并求得A，B，满足(a,b)=Aa+Bb。用欧几里得除法求(a,b)的步骤如下：第一步：不失一般性，假设a>b，且令第二步：用除以得到其商数和余数，亦即第三步：如果，停止

29、运算，并记；否则，转第二步。欧几里得算法又被称为辗转相除法，这里是单调下降序列。用欧几里得算法可以求得A、B，沿用上述除法得到的和n，其方法如下：第一步：令第二步：计算第三步：如果，停止运算，此时,否则转第二步事实上，只是其中的一个特例。4 BCH码、RS码与其编码4.1 BCH码、RS码简介如前所述，BCH码是纠错能力可能的循环码，由Bose、Chandhari和Hocquenghem在19501960年间分别独立地提出。最初的BCH码定义在二元域上，成为二元BCH码，后来推广到多源于上。对于设计纠错能力为t的循环码，器生成多项式含有2t个连续幂次的根，这样的循环码称为BCH码。如果BCH码

30、的根是本原元，成为本原BCH码。如果BCH码的根是非本原元，称为非本原BCH码。如果定义在上的本原元以与共2t个连续幂次都是定义在上的生成多项式的根，那么该BCH码成为设计纠错能力为t的二元本原BCH码。对于任意的证书m和纠错数t，都可以构造出最小距离为d的二元本原BCH码，n, k, d，满足。另外，实际的纠错能力t，可能会大于设计纠错能力的t.同理，如果定义在上的非本原元以与共2t个连续幂次都是定义在上的生成多项式的根，那么该BCH码成为设计纠错能力为t的二元非本原BCH码。进一步假设非本原元和本原元满足关系，其中，如果成立，那么，也就是说是n阶非本原元。如果成立，那么可以构造出最小距离为

31、d的二元非本原BCH码，n, k, d，满足。另外，实际的纠错能力t，可能会大于设计纠错能力的t.BCH码的编码是在二元域完成的，对比特进行编码，与普通的二进制循环码并无不同。而RS的编码是在多元域上完成的（p是质数），对符号进行编码，因为RS码又被视为多元域上的本原BCH码。如果定义在上的生成多项式，其中是定义在上的本原元，那么该BCH码被称为纠错能力为t的RS码。4.2 RS码的构造方法第一步，由关系式算出m，查本原多项式表得到一个m次的本原多项式，从而产生一个的扩域，使域元素（符号）与m重向量建立起一一对应的关系本原多项式表mM本原多项式2345678第二步：根据设计纠错能力t，直接计算

32、定义在上的生成多项式。利用和等运算规则，可以将展开并化简为。第三步：已知生成多项式，根据关系式，对信息位多项式编码得到码字多项式，这就完成了RS码的编码过程。这里的、和都是上的多项式。而对于长度为mk的二进制的输入序列，以m个比特位一组划分可以得到k个m重向量，再将每个m重向量映射为上的元素，从而得到长度为k的多元序列。得到长度为n的多元序列后，对于每一个上的元素，再映射为m重向量，从而得到长度为nm的二进制编码序列。例如，对于信息输入比特序列100,101,010，首先根据表格的各次幂将序列映射为上的序列，则其信息位多项式。那么可以求得上的码字多项式。从而得到上的编码序列。再根据表格的各次幂

33、将其映射为二进制编码序列即可得到RS码。表格 的各次幂即约多项式3重向量00001001010100011110111101RS码是纠正短突发差错的首选纠错码，广泛应用于无线通信的存储系统中。例如，美国宇航局（NASA）在探险者号（Voyager）上用了256进制的255,223,33RS码，其生成扩域的本原多项式是，生成多项式是。是本原多项式的根，因为含有32个连续幂次的根，因而改码的纠错能力为符号个符号（256进制）或者等效长度是的二进制特发差错。5 RS码的译码由于BCH码和R-S码都是循环码，所以可以采用一般的梅杰特解码器，但是BCH码和R-S码的设计纠错能力都比较髙，从而使得梅杰特解

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

35、一个很小的常数因子。而欧几里德（Euclid)算法更容易理解些，所以得到了更广泛的应用。具体解码又可以分为时域解码和频域解码。5.1 关键方程的引入令F是一个含有n阶单元本原元的域，那么根据定义有，再令V是F上的一个n维向量，称为时域向量。又令，是V的离散傅里叶变换（DFT），成为频域向量；DFT（离散傅里叶变换）：那么，可以证明，从频域到时域的IDFT（逆离散傅里叶变换）也成立；IDFT（逆离散傅里叶变换）：设F是，p是质数，那么特征是p。IDFT中的是以特征p为模的同余类。易知，所以，根据欧几里得算法有。对于,在定义V和的生成多项式：和。那么，可以将上述的离散傅里叶变换写为：对于V，定义他

36、的支持集，亦即I是V中非零元素的索引集。在定义V的位置多项式。对于，再定义i阶穿孔位置多项式。最后，定义V的数值多项式。那么，可以证明。定理 关键方程：对于固定的向量V，多项式，和满足一下关键方程有了上述的数学基础，就可以引入BCH/RS码的关键方程了。设编码向量为，信道错误图案为向量，那么接收向量，解码的第一步是计算伴随式向量 ,的定义如下那么，令时域向量，那么易知，伴随式向量S与频域向量满足关系，亦即，伴随式向量S是的钱2t个分量，这是可以直接观测到的，而的后（n-2t）个分量不能直接观测到。记伴随式多项式解码算法的目的是已知伴随式向量S求错误图案向量E，从而得到解码向量，由于只是知道频域

37、向量的前2t个分量，需要用对关键方程降次。所以得到BCH/RS的关键方程由于V的支持集是发生误码的标号集合，所以又被成为错误位置多项式，而又被成为错误数值多项式，其中，t是最高次的数字。t是BCH/RS码的设计纠错能力。5.2 多项式的欧几里得算法BCH解码的目标是已知，通过求解关键方程，得到和，进而求出。求解的关键算法是欧几里得算法。在抽象代数基础已经介绍了欧几里得算法，这里将其推广到多项式上。多项式上的欧几里得算法给定两个有限域F上的两个多项式可以用欧几里得除法得到其最大公约数，并求得，满足欧几里得除法求的步骤如下：第一步：不失一般性，假设且令第二步：用除以，得到其商数和余数，亦即第三步：

38、如果，停止运算，并记；否则，转第二步。欧几里得处理又被成为辗转相除法，这里是单调下降序列。用欧几里得算法可以求得。沿用上述除法得到和，其方法如下：第一步：第二步：计算第三步：如果，停止运算，此时，；否则，转第二步。这里，是单调递增函数，而也是单调递增函数。容易得到以下两条性质：从而推出以下性质：进一步有如下定理：定理 设和是非零多项式，是非零负整数，满足：进一步假设和是对应用欧几里得算法得到的多项式序列。那么存在且唯一存在标号使得用一个欧几里得抽象函数表示上述结果。进而存在一个常数多项式，使得：这个定理表明完全可以用欧几里得算法解决BCH/RS码的关键方程。5.3 BCH/RS码的解码步骤有了

39、关键方程和欧几里得抽象函数，讨论BCH/RS解码的步骤就水到渠成了。假设已经求得了错误位置多项式和错误数值多项式，为了求差错图案多项式，有时域和频域处理两种方法。求出后，解码码字向量时域算法的本质就是对错误位置多项式进行验根。由于，那么；反之，如果，那么含有因子。所以，如果，说明第个位置上的接收向量，存在误码，否则第个位置上的接收向量是正确的。对于二元域BCH码，比较简单，如果，那么，否则。而对于多元域上的RS码，是多元域元素，还需要进一步求出。对于RS码，如果，那么，亦即，否则。首先用C语言伪代码说明BCH码的时域解码算法，如下所示：/*二元域BCH码的属于解码算法*/*码长n，设计纠错能力

40、t，接收向量R，错误图案向量E，解码码字向量*/for(j = 1 to 2t);/;if()printf("接收码字正确，无误码");else/用欧几里得算法解关键方程;if()printf("误码超出了纠错能力t，不可解码");else;for(i = 0 to n-1)if()elsefor(i = 0 to n-1)printf("接收到的码字为：");解码中需要归一化。因为，所以，从而归一化是必须的。如果，那么无法归一化，这通常是因为误码超过了纠错能力t，从而不可解码。由于BCH码的简单性，无需用到。下面说明RS码的解码算法

41、，如下所示：/*RS解码算法*/*码长n，设计纠错能力t，接收向量R，错误图案向量E，解码码字向量*/for(j = 1 to 2t);/;if()printf("接收码字正确，无误码");else/用欧几里得算法解关键方程;if()printf("误码超出了纠错能力t，不可解码");elsefor(i = 0 to n-1)if()elsefor(i = 0 to n-1)printf("接收到的码字为：");至此，RS编码解码的代数基础、编码理论与方法，解码理论与方法均已介绍完毕，下面利用MATLAB进行仿真。6 MATLAB主要

42、程序与其仿真结果利用MATLAB编写仿真程序如下所示：% 信源编码clc; clear;m = 8; % GF(2m) = GF(28)伽罗瓦域n = 2m-1; k = 223; %定义编码长度RS(n, k) = RS(2m - 1, k) = RS(255, 223)data = ceil(255*rand(1, 223); % 构建1个随机生成的数据包数据围0255，共223个数据msg = gf(data,m); % 生成伽罗华域，限定msg信息的运算围，所有关于msg的运算都将进行mod(2m)运算、Code = rsenc(msg,n,k); % 在伽罗瓦域对msg进行编码。使用

43、RS(255, 223)编码 %code = GF(28) array. 特征多项式Primitive polynomial = D8+D4+D3+D2+1 % 构建018个随机生成的随机信道误码，RS(255,223)可以纠正(n-k)/2=16个随机位置错误Err_cut_t = round(18 * rand(1);%随机构建018个随机生成的错误，RS(255,223)可以纠正(n-k)/2=16个随机位置错误Err_pos = randperm(223,Err_cut_t); %随机生成Err_cut_t个不重复位置错误Errs = ceil(255*rand(1, Err_cut_

44、t);%随机构建Err_cut_t个数据突发错误，Error = zeros(1,255);%全零信道误码，即无信道误码。for j = 1 : Err_cut_t Error(Err_pos(j) = Errs(j);%给出现突发数据错误的位置赋予突发数据错误endErrors = gf(Error,m);%信道噪声加入完毕，下面进行解码% Recv为接收到的信号。rsdec函数进行解码Recv = Code + Errors; % 二进制模2m加，在伽罗华域中运算，所有大于255的数都将进行模运算 R = E + Cdec,cnumerr = rsdec(Recv,n,k); % 解码us

45、e RS decoder umerr是一个列向量，记载了每一行纠正的错误数，-1表示纠错失败 % 验证正确性。%画信源图程序代码运行结果如下：由MATLAB仿真结果可以看到，只要信道噪声小于16个随机突发错误，利用RS（255，223）编码后的信号通过随机信道噪声加成后再利用解码算法可以完美的还原信源。7 总结我国的航天事业正处于蓬勃发展的阶段，月球探测等今后的重大项目都对数据的传输提出了越来越高的要求，高速的数据传输系统必将得到更多的推广。本课题中 RS(255,223)译码器仿真对以后的航天项目中的地面高速接收系统的设计和星上数据接收系统的设计均有着很大的意义。本文详细介绍了纠错码的相关理

46、论，包括编码定理、有限域运算法则、BCH 码、RS 码的基础知识，还介绍了RS码的译码，为后续MATLAB仿真奠定了本论文的理论基础。RS码一直是国际通信领域研究的热点,由于其良好的对随机错误和突发错误的纠错能力,尤其是对突发错误的纠错,已经广泛被应用于各种数字通信系统中，本论文采用的是时域译码算法，另外频域算法也是比较常用的一种算法。随着对 RS 码研究的深入，新算法也层出不穷，设计高效的算法必将大幅度提升系统的性能、提高处理速度和减少对软硬件资源的占用。，因此如何设计高效的算法将是以后的努力方向。还有从功能实现和性能的角度来看，本设计还有较大的改进空间。通过采用高效的算法与优秀的代码将会大

47、幅度提高性能。可以预见，随着科学技术的进步和研究的深入，纠错码理论将进一步地发展，必将得到更广泛的应用。致 在本次课设中，自己复习了有关MATLAB程序和信息论相关理论知识，在之前信号与系统与数字信号处理的实验课程中初步学习了有关MATLAB软件对于信号仿真与分析中的应用，RS码作为现代通信领域的热点，首先自己有一定的兴趣去学习，在所翻阅的资料中，有了关于RS码的较为详尽的介绍与应用举例，在此对这些论著与文献的作者表示感，接着感在此次课设中给予我帮助的同学们，对于MATLAB软件操作自己开始有一些的生疏给予了指导，最后感此次的指导老师熬珺老师在自己学习过程中所遇困惑给予的解答与帮助，作为通信专

48、业的毕业生，在大四的课设中接触到一些应用性较强的前沿知识，自己得到了锻炼，对于以后走向工作岗位有很大的帮助，老师严谨的学术态度与本着对学生负责的想法令人敬佩，本次课设自己以认真的态度和花费较多的时间与精力完成，如有不足之处，望老师给予指教与包涵，！参考文献1 美 Robert J.McEliece,斗 等译信息论与编码理论第二版2 世镒、鲁生信息论与编码理论3 美Ranjan Bose 武传坤译信息论、编码与密码学4 美Robert H.Morelos-Zaragoza著 立军译纠错编码的艺术5 吴湛击 著 王文博 审现代纠错编码与调制理论与应用6 宋文俊 华东师大学硕士学位论文RS码的译码研

49、究7 石俊峰 中国科学院研究生院硕士学位论文RS(255,223)译码器的FPGA实现与其性能测试8 徐朝军 电子科技大学博士学位论文RS码译码算法与其实现的研究附 录MATLAB仿真程序：% 信源编码clc; clear;m = 8; % GF(2m) = GF(28)伽罗瓦域n = 2m-1; k = 223; %定义编码长度RS(n, k) = RS(2m - 1, k) = RS(255, 223)data = ceil(255*rand(1, 223); % 构建1个随机生成的数据包数据围0255，共223个数据msg = gf(data,m); % 生成伽罗华域，限定msg信息的运

50、算围，所有关于msg的运算都将进行mod(2m)运算、Code = rsenc(msg,n,k); % 在伽罗瓦域对msg进行编码。使用RS(255, 223)编码 %code = GF(28) array. 特征多项式Primitive polynomial = D8+D4+D3+D2+1 x = input('手动输入随机信道误码则请输入非零数，随机输入随机信道误码则请输入0:');if(x = 0) % 构建018个随机生成的随机信道误码，RS(255,223)可以纠正(n-k)/2=16个随机位置错误 Err_cut_t = round(16 * rand(1);%随机

51、构建018个随机生成的错误，RS(255,223)可以纠正(n-k)/2=16个随机位置错误 Err_pos = randperm(223,Err_cut_t); %随机生成Err_cut_t个不重复位置错误 Errs = ceil(255*rand(1, Err_cut_t);%随机构建Err_cut_t个数据突发错误， Error = zeros(1,255);%全零信道误码，即无信道误码。 for j = 1 : Err_cut_t Error(Err_pos(j) = Errs(j);%给出现突发数据错误的位置赋予突发数据错误 end Errors = gf(Error,m);else

52、 % 数据输入 Err_cut_t = input('请输入Err_cut_t个突发随机错误个数，RS(255,223)只能纠错16个以的编码！:'); if(Err_cut_t > 16 | Err_cut_t < 0) display('不能正确纠错' num2str(Err_cut_t) '个错误，请重新运行程序'); return; else display(num2str(Err_cut_t) '个突发错误') end Err_pos = input('请输入' num2str(Err_cut

53、_t) '个不重复随机位置错误向量 Err_pos = :'); while(1) if(length(Err_pos) = Err_cut_t)%如果长度不相等 Err_pos = input('输入数据长度不匹配，请重新输入'); else if(sum(Err_pos > 255, 2) + sum(Err_pos < 0, 2)%如果超出围 display('超出数据围,请重新输入，请重新运行程序') return; else break; end end end Errs = input('请在对应错位位置输入错误Err_cut_t个的数据Errs = :'); Error = zeros(1,255);%全零信道误码，即无信道误码。 while(1) if(length(Errs) = Err_cut_t)%如果长度不相等 Errs = input('输入数据长度不匹配，请重新输入'); else if(sum(Errs > 255, 2) + sum(Errs < 0, 2)%如果超出围 display('超出