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

编号： 课程设计说明书 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 目： RS(255,223)纠错编码的 MATLAB仿真 院 （系）： 专 业： 学生姓名： 学 号： 指导教师： 2013 年 12月10日 目 录 21 引言 21.1信道编码理论与技术的发展历程及应用 41.2 纠错编码简介 52 Reed – Solomon编码概述 63 Reed – Solomon编码抽象代数基础 63.1 群 73.2 环和域 73.3 有限域 83.4 欧几里得算法 94 BCH码、RS码及其编码 94.1 BCH码、RS码简介 104.2 RS码的构造方法 115 RS码的译码 125.1 关键方程的引入 135.2 多项式的欧几里得算法 155.3 BCH/RS码的解码步骤 186 MATLAB主要程序及其仿真结果 197 总结 20致谢 21参考文献 22附 录 摘 要 在纠错码领域中Reed-Solomon码是一类具有严格代数结构的线性分组码。由于它突出的纠错能力(特别是纠突发错误的能力),常被应用于数据存储以及现代数字通信系统中。在卫星通讯中，差错控制编码技术对降低误码率、提高通信的可靠性具有非常重要的作用。RS(Reed-Solomon)码是差错控制领域中一种性能优异的线性分组循环码，由于其具有很强的随机错误和突发错误的纠错能力，所以被CCSDS、NASA、ESA 等空间组织接受，广泛用于深空探测中。目前我国还没有高码速率的 RS 硬件译码器，虽然“双星 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 ”已经采用 RS纠错编码技术，在卫星上使用 RS(255,223)硬件编码器进行编码，但是由于硬件译码器的复杂性，地面接收系统采用的是软件译码，无法保证通信的实时性。为此，本文在详细介绍RS(255,223)编码译码的基础上，利用MATLAB软件对该理论进行仿真。 关键词：Reed-Solomon编码；抽象代数；RS码编码；RS码译码算法；RS(255,223)仿真；MATLAB 引言 信道编码理论与技术的发展历程及应用 Shannon 的信道编码定理给出了有噪信道通信的最大速率，证明了好码的存在性，但对该定理证明是非构造性的，它没有告诉我们怎么构造好码。如何通过不可靠信道进行可靠的通信，是编码理论所要研究的问题。半个多世纪以来，众多的学者为构造逼近容量限的纠错码做了大量的工作，但这一问题直到 45 年后才基本得到解决。 但是，“过程比目标更重要”，在应对这一挑战的过程中，编码理论家和工程师们应用组合数学、线性代数、概率论、有限域理论等数学工具，建立了纠错码的性能参数限，发现了许多构造纠错码的方法，并设计了有效的编译码算法，为信息技术的蓬勃发展建立了不朽的功勋！ 在 Shannon 的论文发 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 之前，Richard Hamming 就已经为早期的计算机设计了一种纠单个错误的码，迈出了信道编码理论与技术研究的第一步。之后，信道编码理论与与技术的大致经历了以下几个发展阶段： 50 年代至 60 年代初 这是编码理论从无到有并得到迅速发展的年代，现代编码理论的许多思想都起源于这一时期。 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 限（GV 限），其证明可以在编码理论的基础教材中找到； 4）1957 年，Elias 提出了一种概念译码器——表单译码器（List Decoder），以突破传统的限定距离译码（BDD）的半最小码距的纠错半径； 5）1961 年，W. W. Peterson 编写了第一本关于纠错码理论的专著，系统地阐述了纠错码的基本理论。 60 年代至 70 年代初 这是纠错码发展最为活跃的时期之一。在此期间，以代数方法特别是以有限域理论为基础的线性分组码理论已趋成熟。 1）提出了许多有效的编、译码方法。1965年，E. R. Berlekamp提出了一种实用分组码的代数译码算法，1969年, J.L. Massey从序列综合的角度重新推导了这一算法，后人称之为Berlekamp-Massey算法（BM算法）。BM算法的提出，是分组码走向实用的一个重要里程碑。 1966年，G. D. Forney第一次采用简单的分量码构造级联码，以提高码的性能。第一个成功的级联码是采用卷积码作内码、RS码作外码的串行级联码，其典型应用是在卫星通信、深空探测等领域，如Voyager、Galileo、Cassini等任务，这种编码方式还被应用于美国的数字电视（ATSC）、欧洲的数字视频广播（DVB）和数字音频广播（DAB）等系统中；另一种典型的级联码是C. Berrou于1993年发现的并行级联卷积码（PCCC），即我们通常所称的Turbo码，这是一种逼近Shannon限的码。 1967年，A. J. Viterbi提出了卷积码的最大似然译码算法，实现了数字通信中信道编码技术的一次实质性突破。Viterbi算法还在其它领域得到了广泛应用。1974年，Bahl等提出了一种最大后验概率（MAP）译码算法（也称为BCJR算法），其误比特率（BER）性能优于Viterbi算法。但由于计算复杂度大大增加，MAP算法直到1993年Berrou发现Turbo码之后才得到广泛应用。 由于硬判决译码通常较软判决译码损失2~3dB，对分组码的软判决译码算法的研究也逐渐成为一个重要的课题。对于卷积码，硬判决译码和软判决译码通过相同的格图进行译码，其复杂度大体相同。而对于分组码，基于格图的译码与代数译码相比，复杂度会大大增加，因此次优的译码算法成为首选。在这方面，著名的有广义最小距离（GMD）译码算法、Chase算法等。 2）研究了与码的性能有关的各种问题，如码的重量分布、译码错误概率和不可检错误概率的计算、信道的模型化等，所有这些问题的研究为信道编码技术的实用化打下了坚实的基础。 70 年代初至 80 年代 这是信道编码发展史中最具重要意义的时期，信道编码在理论和实践方面都取得了丰硕的成果。 1）在理论上，以 Goppa 为首的一批学者在 70 年代初较系统地构造了一类逼近 Shannon 限的有理多项式码——Goppa 码，这在纠错码的历史上具有划时代的意义。80 年代初，Goppa 等将代数几何的理论与方法系统地应用于编码理论中，由 Goppa 码引出了代数几何码，使得 Goppa 码日益引起了人们的极大兴趣。1987 年，G. Ungerboeck 提出了著名的格图编码调制（TCM）技术，展示了如何将编码和调制结合起来，改善系统的整体性能，这是编码理论的又一重要里程碑。之后，众多研究者开始对 TCM 进行了深入研究，并将这一概念推广到分组编码调制（BCM）。 2）这期间微电子技术的迅速发展，为编码技术的实用化打下了坚实的物质基础；各种实际应用也带动了信道编码技术的发展，编码技术的实用化得到了极大关注，并取得了巨大的进展。例如，用于 RS 码译码的 BM 算法进一步发展成熟，出现了无求逆的 BM（iBM）算法、Euclid 算法、Welch-Berlekamp 算法（WB 算法）等，其超大规模集成电路（VLSI）实现也得到了充分的发展。 信道编码技术最成功的应用在于卫星通信和深空探测领域，这使得宇宙飞船从遥远的太空传回了许多极其宝贵的天文学资料。特别值得一提的是，在 1989年的 Galileo 任务中，由于主天线的故障，数据传输的速率比原设计指标大大下降，喷气式推进 实验室 17025实验室iso17025实验室认可实验室检查项目微生物实验室标识重点实验室计划 （JPL）的科学家们从地面发送指令，重新配置板上计算机，在数据传输之前进行了更多的编码处理，使得由于硬件故障引起的数据传输速率下降得以部分恢复，从而挽救了整个探测计划。若不应用信道编码技术，这些成就的取得是不可企及的。 此外，信道编码技术还用于数据存储系统，提高数据存储密度；用于数据传输系统，提高数据传输速率；用于各种数字通信系统，提高通信质量；用于数字音频/视频传输系统以及视听娱乐设备，为我们的生活带来美妙的音乐和完美的视觉享受；而且纠错码技术还应用于超大规模集成电路设计中，以提高集成电路芯片的成品率，降低芯片的生产成本。 90 年代以后 这一时期，编码理论的重大发现当首推1993年Berrou等发现的Turbo码。Turbo码是一种利用伪随机交织器构造的具有随机码行为的长码，它采用并行级联卷积码的方式进行编码，用最大后验概率（MAP）译码器进行迭代译码，分量译码器之间通过传递所谓的外信息来减少信息损失，其性能非常接近Shannon限，这一惊人的性能打破了长期以来的猜想：利用二元卷积码和序列译码是达到截止速率R （即所谓的“实际容量”）的一种可实现的方法。在迭代译码器中，所采用的分量码MAP译码器可以用软入输出Viterbi算法（SOVA）代替，这会使Turbo码译码性能略有下降，但大大降低了计算复杂度和存储量要求。更为实用的分量码译码器是Koch等提出的Max-Log-MAP译码算法和Robertson等提出的Log-MAP译码算法。后来，Hagenauer、Pyndiah又分别将Turbo码迭代译码的思想用于级联二元分组码和乘积码。现在，Turbo码的迭代算法已经成为“Turbo原理”，广泛应用于各种级联系统，如均衡、编码调制、信源压缩、信源信道联合编码以及信号检测等。 另一方面，在探究Turbo码迭代算法的过程中，Mackay和Neal于1996年重新发现了Gallager于60年代提出的具有稀疏校验矩阵的线性分组码——LDPC码，基于Tanner图进行迭代译码，其性能与Turbo码差不多。最近，采用BCH码作外码、LDPC码作内码的级联码已经被DVB-S2采纳。 1998年，Tarokh、Seshadri和Calderbank提出的格图空时码，在时间和空间上都引入了编码，集前向纠错（FEC）、发送分集和接收分集于一体，能获得较大的编码增益和分集增益，实现数据的高速传输。几个月后，Alamouti发明了低复杂度的分组空时码。空时码的基本思想是采用多个发射天线和多个接收天线来提高系统容量，关于空时码已有许多研究文献。 由于RS码在众多数字通信系统、数据存储系统中的成功应用，以及其软判决译码性能的巨大潜力，RS码的软判决译码问题也得到了很大的关注。其中，Sudan于1997年提出了多项式复杂度的表单译码（List Decoding）算法，将RS译码问题转化成有限域上的曲线拟合问题，给出并证明了几个重要的定理，奠定了RS码表单译码的基础。但Sudan算法只适用于码率不大于1/3的RS码，而1999年提出的Guruswami-Sudan算法则可适用于任意码率的RS码和代数几何码。另一方面，Koetter和Vardy基于Guruswami-Sudan算法，将接收符号的软信息转化为一系列的代数条件，用代数方法实现了RS码的软判决译码。 纠错编码简介 我们知道,在计算机和数据通信中,经常需要将二进制数字信号进行传递,这种传递的距离近则数米!数毫米,远则超过数千公里。在传递信息过程中,由于存在着各种干扰,可能会使二进制信号产生失真现象,即在传递过程中二进制信号O可能会变成1,1可能会变成0。试想一个二进制信号传递的简单模型,它有一个发送端和一个接收端,二进制信号串从发送端发出经传输介质而至接收端。由于存在着干扰,因而接收端接收到的二进制信号串可能与原来的二进制信号串不相等,从而产生了二进制信号的错误传递。 由于在计算机和数据通信系统中的信号传递是非常的频繁与广泛,因此,如何防止传输错误就变得相当重要了,当然,要解决这个问题可以有不同的途径。人们所想到的第一个途径是提高设备的抗干扰能力和信号的抗干扰能力。但是,大家都知道,这种从物理角度去提高抗干扰能力并不能完全消除错误的出现。第二个途径就是我们所要谈到的采用纠错码(Error correcting code)的方法以提高抗干扰能力。这种纠错码的方法是从编码上下功夫,使得二进制数码在传递过程中一旦出错,在接收端的纠错码装置就能立刻发现错误,并将其纠正。由于这种方法简单易行,因此目前在计算机和数据通信系统中被广泛采用"采用这种方法后,二进制信号传递模型就可以变为纠错码模型了。 由纠错码模型可以想到,当二进制信号串从发送端发送时,需按规定转换成具有抗干扰能力的纠错码,然后才发送出去。在接收端,当接收到二进制信号串后立即对接收到的纠错码进行检查,查对在途中是否失真,如失真则负责纠正。 该模型的一个典型实现,就是在远程数据传输系统中具有纠错能力的数据传输装置,该装置的纠错过程是二进制信号发生器发出信号(二进制信号发生器可以是计算机,或者是由人控制的某些装置如终端),经差错控制器形成纠错码,然后经调制器使二进制信号变成为适宜于信道传播的电信号,这种信号通过信道传输至接收端,首先通过解调器将其还原为原来的二进制信号,再经差错控制器检验经信道传输后是否产生失真,并采取措施进行纠正。经纠正后的二进制信号送入二进制信号接收器,从而完成整个传输过程"二进制信号接收器可以是计算机,或其他接收装置如终端等。 但是,为什么纠错码具有发现错误!纠正错误的能力呢?纠错码又是按什么样的原理去编的呢?为了说明这些问题,我们首先介绍一些基本概念:由0和1组成的串称为字(Word),一些字的集合称为码(Code)。码中的字称为码字(Code Word)。不在码中的字称为废码(Invalid Code)。码中的每个二进制信号0或1称为码元(Code Letter)。 我们下面举出几个关于纠错码的例子。设有长度为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也有同样的情况。但是,这种编码有一个缺点,即它只能发现错误而不能纠正错误,因此我们还需要选择另一种能纠错的编码"现在我们考虑长度为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,我们不仅能发现错误而且能纠正错误"当然,上述编码还有一个缺点,就是它只能发现并纠正单个错误。当错误超过两个码元时,它就既不能发现错误,更无法纠正了。 Reed – Solomon编码概述 Reed-Solomon 码（RS 码）是 Reed和 Solomon于 1960 年发现的一类多元最大距离可分（MDS）码，其最小距离达到了 Singleton 限mind = n − k+ 1，从这个意义上讲，RS 码是最佳的。之后几十年里，RS 码的硬判决译码得到了深入的研究，其理论和技术都已经非常成熟。因而，RS码在现代数字通信、数据存储系统中得到了广泛的应用，见下表 应用领域 编码 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 硬盘驱动器 RS(32, 28, 5)码 CD 交叉交织 RS 码（CIRC） DVD RS(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 码译码子系统设计过程中要考虑的一个关键的问题。在工程实践中通常采用的“直接二级逻辑设计”仅仅依靠综合工具对所设计的电路进行优化，不能有效地利用 FPGA 所提供的资源，降低有限域乘法器的时延。就作者所知，目前还没有一种系统的方法，可以用来设计高速并行有限域乘法器。 RS 码的硬判决译码器不能充分地利用接收信息，造成了一定的性能损失。众所周知，从最小化不正确译码概率的意义上讲，最大似然译码（MLD）是最好的方法。在 AWGN 信道条件下，RS 码的最大似然译码与硬判决距离译码相比，会有 2.5~3.2dB 的软判决译码增益；在衰落信道条件下，其软判决译码增益会更大。2005 年，Guruswami 和 Vardy[90]在 IEEE 信息论会刊上撰文指出，RS 码的最大似然译码是 NP-Hard 问题。因此，低复杂度的次优译码算法成为人们研究的热点。 现有的 RS 码软判决译码算法主要有以下四类： 基于代数译码器的软判决译码：主要有纠错纠删译码、广义最小距离（GMD）译码算法、Chase 算法、Lacan 算法、有序统计量译码（OSD）算法等； 基于格图的译码：主要有 Vardy 和 Be’ery提出的比特级软判决译码算法、Ponnampalam 和 Vucetic提出的简化的比特级软判决译码算法等； 基于 Tanner 图的译码：基于自适应校验矩阵的软判决译码算法、基于临界抽取滤波器组表示的软判决译码算法等； 表单译码：主要有 Koetter-Vardy 算法等。 这些译码算法各有千秋，就实用性而言，GMD算法、Chase-II算法和Koetter-Vardy算法略胜一筹。 Reed – Solomon编码抽象代数基础 群 定义 设G是一个非空集合，称映射 为G上的一个二元运算，即对于G中仍以两个元a和b，唯一确定 (a,b).记为 ,为了方便起见，可写成c=ab. 定义 设G是一个非空集合，是G上的一个二元运算，如果G满足下列条件： （结合律）对于任意 ,有 （单位元）G中存在单位元 ，对于任意 ，满足 （逆元）对于任意 ，存在的逆元 ，满足 则称G为群，记为 . 如果群 满足交换律，即对于任意 ，满足 则称群 为交换群或阿贝尔群. 环和域 定义 设R是一个非空集合，R上有两个二元运算 和 ，分别成为加法和乘法，如果R满足下列条件 为加法阿贝尔群 （结合律）对于任意 ,有 （分配律）对于任意 ,有 称R为环，记为 ，如果他对乘法满足交换律，即对任何 称环 为交换环 定义 设 为交换环， 表示R中所有非零元的集合，如果 在乘法运算下构成交换群，则称 为域。 有限域 定义 设F为一个域，如果F只含有有限个元素，称F为有限域，含有q个元素的有限域记为 ，有限域也成为伽罗华域(Galois field)，用GF(q)或 表示q阶有限域。 最简单的有限域是二元域GF(2)={0,1}。 定义 对于GF(q)上的每个非零元素 ，存在最小整数k,使 成立，则称为k阶元素。 定义 对于GF(q)上的每个非零元素 ，如果其阶数是q-1,则称 为本原元素。 定义 上的一个m次多项式 ，如果他的所有根都是 中的本原元素，则称 是m次本原多项式。 例如，对于m = 8时 上的m次本原多项式为 对于m = 7时 上的m次本原多项式为 定义 设 为 中的元素，多项式 是 上使 的最低次多项式，则称 为最小多项式。具有相同最小多项式的元素，构成同一共轭系。 欧几里得算法 欧几里得算法给定两个正整数a,b，可以用欧几里得除法得到其最大公约数(a,b)，并求得A，B，满足(a,b)=Aa+Bb。 用欧几里得除法求(a,b)的步骤如下： 第一步：不失一般性，假设a>b，且令 第二步：用 除以 得到其商数 和余数 ，亦即 第三步：如果 ，停止运算， 并记 ；否则， 转第二步。 欧几里得算法又被称为辗转相除法，这里 是单调下降序列。 用欧几里得算法可以求得A、B，沿用上述除法得到 的和n，其方法如下： 第一步：令 第二步：计算 第三步：如果 ，停止运算，此时 ,否则 转第二步 事实上， 只是其中的一个特例。 BCH码、RS码及其编码 BCH码、RS码简介 如前所述，BCH码是纠错能力可能的循环码，由Bose、Chandhari和Hocquenghem在1950~1960年间分别独立地提出。最初的BCH码定义在二元域上，成为二元BCH码，后来推广到多源于上。对于设计纠错能力为t的循环码，器生成多项式含有2t个连续幂次的根，这样的循环码称为BCH码。如果BCH码的根是本原元，成为本原BCH码。如果BCH码的根是非本原元，称为非本原BCH码。 如果定义在 上的本原元 以及 共2t个连续幂次都是定义在 上的生成多项式 的根，那么该BCH码成为设计纠错能力为t的二元本原BCH码。对于任意的证书m和纠错数t，都可以构造出最小距离为d的二元本原BCH码，[n, k, d]，满足 。另外，实际的纠错能力t，可能会大于设计纠错能力的t. 同理，如果定义在 上的非本原元 以及 共2t个连续幂次都是定义在 上的生成多项式 的根，那么该BCH码成为设计纠错能力为t的二元非本原BCH码。进一步假设非本原元 和本原元 满足关系 ，其中 ，如果 成立，那么 ，也就是说 是n阶非本原元。如果 成立，那么可以构造出最小距离为d的二元非本原BCH码，[n, k, d]，满足 。另外，实际的纠错能力t，可能会大于设计纠错能力的t. BCH码的编码是在二元域完成的，对比特进行编码，与普通的二进制循环码并无不同。而RS的编码是在多元域 上完成的（p是质数），对符号进行编码，因为RS码又被视为多元域上的本原BCH码。如果定义在 上的生成多项式 ，其中 是定义在 上的本原元，那么该BCH码被称为纠错能力为t的RS码。 RS码的构造方法 第一步，由关系式 算出m，查本原多项式表得到一个m次的本原多项式 ，从而产生一个 的扩域，使域元素（符号） 与m重向量建立起一一对应的关系 本原多项式表 m M本原多项式 2 3 4 5 6 7 8 第二步：根据设计纠错能力t，直接计算定义在 上的生成多项式 。利用 和 等运算规则，可以将 展开并化简为 。 第三步：已知生成多项式 ，根据关系式 ，对信息位 多项式编码得到码字多项式 ，这就完成了RS码的编码过程。这里的 、 和 都是 上的多项式。而对于长度为mk的二进制的输入序列，以m个比特位一组划分可以得到k个m重向量，再将每个m重向量映射为 上的元素 ，从而得到长度为k的多元序列 。得到长度为n的多元序列 后，对于每一个 上的元素，再映射为m重向量，从而得到长度为nm的二进制编码序列。 例如，对于信息输入比特序列{100,101,010}，首先根据表格 的各次幂将序列映射为 上的序列{ }，则其信息位多项式 。那么可以求得 上的码字多项式。 EMBED Equation.DSMT4 从而得到 上的编码序列 。再根据表格 的各次幂将其映射为二进制编码序列即可得到RS码 。 表格 的各次幂 即约多项式 3重向量 0 000 1 001 010 100 011 110 111 101 RS码是纠正短突发差错的首选纠错码，广泛应用于无线通信的存储系统中。例如，美国宇航局（NASA）在探险者号（Voyager）上用了256进制的[255,223,33]RS码，其生成扩域的本原多项式是 ，生成多项式是 。 是本原多项式 的根，因为 含有32个连续幂次的根，因而改码的纠错能力为符号 个符号（256进制）或者等效长度是 的二进制特发差错。 RS码的译码 由于BCH码和R-S码都是循环码，所以可以采用一般的梅杰特解码器，但是 BCH码和R-S码的设计纠错能力都比较髙，从而使得梅杰特解码器的实现复杂度 BCH码和RS码的解码原理是一样的，其髙效解码算法的基础在于一个关键方程 的引入和基于多项式的欧几里德算法。在BCH/RS码的解码算法的发展历史上， 彼得森（Peterson)于1960年提出了第一个BCH的解码算法。之后，钱（Chien)、 福尼（Formey)、梅西（Massey)和巴勒坎普（Berlekamp)相继提出了更高效的 BCH解码算法。到了 1975 年，Sugiyama、Kasahara、Hirasawa和Namekawa发现 也可以采用欧几里德(Euclid)算法对BCH/RS码解码，并发现巴勒坎普（Berlekamp) 解码算法与欧几里德（Euclid)算法相比仅差一个很小的常数因子。而欧几里德（Euclid)算法更容易理解些，所以得到了更广泛的应用。具体解码又可以分为时域解码和频域解码。 关键方程的引入 令F是一个含有n阶单元本原元 的域，那么根据定义有 ，再令V是F上的一个n维向量， 称为时域向量。 又令 ，是V的离散傅里叶变换（DFT），成为频域向量； DFT（离散傅里叶变换）： 那么，可以证明，从频域到时域的IDFT（逆离散傅里叶变换）也成立； IDFT（逆离散傅里叶变换）： 设F是 ，p是质数， ，那么特征是p。IDFT中的 是以特征p为模的同余类。易知 ，所以 ，根据欧几里得算法有 。对于 , 在定义V和 的生成多项式： 和 。那么，可以将上述的离散傅里叶变换写为： 对于V，定义他的支持集 ，亦即I是V中非零元素的索引集。在定义V的位置多项式 。对于 ，再定义i阶穿孔位置多项式 。最后，定义V的数值多项式 。那么，可以证明 。 定理 关键方程：对于固定的向量V，多项式 ， 和 满足一下关键方程 有了上述的数学基础，就可以引入BCH/RS码的关键方程了。设编码向量为 ，信道错误图案为向量 ，那么接收向量 ，解码的第一步是计算伴随式向量 , 的定义如下 那么， 令时域向量 ，那么易知，伴随式向量S与频域向量 满足关系 ，亦即，伴随式向量S是 的钱2t个分量，这是可以直接观测到的，而 的后（n-2t）个分量不能直接观测到。记伴随式多项式 解码算法的目的是已知伴随式向量S求错误图案向量E，从而得到解码向量 ，由于只是知道频域向量 的前2t个分量，需要用 对关键方程降次 。 所以得到BCH/RS的关键方程 由于V的支持集是发生误码的标号集合，所以 又被成为错误位置多项式， ，而 又被成为错误数值多项式，其中 ， ，t是最高次的数字。t是BCH/RS码的设计纠错能力。 多项式的欧几里得算法 BCH解码的目标是已知 ，通过求解关键方程 ，得到 和 ，进而求出 。求解的关键算法是欧几里得算法。在抽象代数基础已经介绍了欧几里得算法，这里将其推广到多项式上。 多项式上的欧几里得算法 给定两个有限域F上的两个多项式 可以用欧几里得除法得到其最大公约数 ，并求得 ，满足 欧几里得除法求 的步骤如下： 第一步：不失一般性，假设 且令 第二步：用 除以 ，得到其商数 和余数 ，亦即 第三步：如果 ，停止运算， ，并记 ；否则 ，转第二步。 欧几里得处理又被成为辗转相除法，这里 是单调下降序列。 用欧几里得算法可以求得 。沿用上述除法得到 和 ，其方法如下： 第一步： 第二步：计算 EMBED Equation.DSMT4 第三步：如果 ，停止运算，此时 ， ；否则 ，转第二步。 这里， 是单调递增函数，而 也是单调递增函数。容易得到以下两条性质： 从而推出以下性质： 进一步有如下定理： 定理 设 EMBED Equation.DSMT4 和 是非零多项式， 是非零负整数， 满足： 进一步假设 和 是对 应用欧几里得算法得到的多项式序列。那么存在且唯一存在标号 使得 用一个欧几里得抽象函数 表示上述结果。 进而存在一个常数多项式 ，使得： 这个定理表明完全可以用欧几里得算法解决BCH/RS码的关键方程。 BCH/RS码的解码步骤 有了关键方程和欧几里得抽象函数，讨论BCH/RS解码的步骤就水到渠成了。假设已经求得了错误位置多项式 和错误数值多项式 ，为了求差错图案多项式 ，有时域和频域处理两种方法。求出 后，解码码字向量 时域算法的本质就是对错误位置多项式 进行验根。由于 ，那么 ；反之，如果 ，那么含有因子 。所以，如果 ，说明第 个位置上的接收向量 ，存在误码，否则第 个位置上的接收向量 是正确的。对于二元域BCH码， 比较简单，如果 ，那么 ，否则 。而对于多元域上的RS码， 是多元域元素，还需要进一步求出。对于RS码，如果 ，那么 ，亦即 ，否则 。 首先用C语言伪代码说明BCH码的时域解码算法，如下所示： /*二元域BCH码的属于解码算法*/ /*码长n，设计纠错能力t，接收向量R，错误图案向量E，解码码字向量 */ { for(j = 1 to 2t) ;// ; if( ) printf("接收码字正确，无误码"); else { //用欧几里得算法解关键方程 ; if( ) printf("误码超出了纠错能力t，不可解码"); else { ; for(i = 0 to n-1) if( ) else for(i = 0 to n-1) printf("接收到的码字为： "); } } } 解码中需要归一化 。因为 ，所以 ，从而归一化是必须的。如果 ，那么无法归一化，这通常是因为误码超过了纠错能力t，从而不可解码。由于BCH码的简单性，无需用到 。下面说明RS码的解码算法，如下所示： /*RS解码算法*/ /*码长n，设计纠错能力t，接收向量R，错误图案向量E，解码码字向量 */ { for(j = 1 to 2t) ;// ; if( ) printf("接收码字正确，无误码"); else { //用欧几里得算法解关键方程 ; if( ) printf("误码超出了纠错能力t，不可解码"); else { for(i = 0 to n-1) if( ) else for(i = 0 to n-1) printf("接收到的码字为： "); } } } 至此，RS编码解码的代数基础、编码理论及方法，解码理论及方法均已介绍完毕，下面利用MATLAB进行仿真。 MATLAB主要程序及其仿真结果 利用MATLAB编写仿真程序如下所示： %% 信源编码 clc; clear; m = 8; % GF(2^m) = GF(2^8)伽罗瓦域 n = 2^m-1; k = 223; %定义编码长度RS(n, k) = RS(2^m - 1, k) = RS(255, 223) data = ceil(255*rand(1, 223)); % 构建1个随机生成的数据包数据范围0~255，共223个数据 msg = gf(data,m); % 生成伽罗华域，限定msg信息的运算范围，所有关于msg的运算都将进行mod(2^m)运算、 Code = rsenc(msg,n,k); % 在伽罗瓦域内对msg进行编码。使用RS(255, 223)编码 %code = GF(2^8) array. 特征多项式Primitive polynomial = D^8+D^4+D^3+D^2+1 %% 构建0~18个随机生成的随机信道误码，RS(255,223)可以纠正(n-k)/2=16个随机位置错误 Err_cut_t = round(18 * rand(1));%随机构建0~18个随机生成的错误，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); %信道噪声加入完毕，下面进行解码 %% Recv为接收到的信号。rsdec函数进行解码 Recv = Code + Errors; % 二进制模2^m加，在伽罗华域中运算，所有大于255的数都将进行模运算 R = E + C [dec,cnumerr] = rsdec(Recv,n,k); % 解码use RS decoder cnumerr是一个列向量，记载了每一行纠正的错误数，-1表示纠错失败 %% 验证正确性。 %画信源图 程序代码运行结果如下： 由MATLAB仿真结果可以看到，只要信道噪声小于16个随机突发错误，利用RS（255，223）编码后的信号通过随机信道噪声加成后再利用解码算法可以完美的还原信源。 总结 我国的航天事业正处于蓬勃发展的阶段，月球探测等今后的重大项目都对数据的传输提出了越来越高的要求，高速的数据传输系统必将得到更多的推广。本课题中 RS(255,223)译码器仿真对以后的航天项目中的地面高速接收系统的设计和星上数据接收系统的设计均有着很大的意义。 本文详细介绍了纠错码的相关理论，包括编码定理、有限域运算法则、BCH 码、RS 码的基础知识，还介绍了RS码的译码，为后续MATLAB仿真奠定了本论文的理论基础。RS码一直是国际通信领域研究的热点,由于其良好的对随机错误和突发错误的纠错能力,尤其是对突发错误的纠错,已经广泛被应用于各种数字通信系统中，本论文采用的是时域译码算法，另外频域算法也是比较常用的一种算法。随着对 RS 码研究的深入，新算法也层出不穷，设计高效的算法必将大幅度提升系统的性能、提高处理速度和减少对软硬件资源的占用。，因此如何设计高效的算法将是以后的努力方向。 还有从功能实现和性能的角度来看，本设计还有较大的改进空间。通过采用高效的算法及优秀的代码将会大幅度提高性能。 可以预见，随着科学技术的进步和研究的深入，纠错码理论将进一步地发展，必将得到更广泛的应用。 致 谢 在本次课设中，自己复习了有关MATLAB程序和信息论相关理论知识，在之前《信号与系统》与《数字信号处理》的实验课程中初步学习了有关MATLAB软件对于信号仿真与分析中的应用，RS码作为现代通信领域的热点，首先自己有一定的兴趣去学习，在所翻阅的资料中，有了关于RS码的较为详尽的介绍与应用举例，在此对这些论著与文献的作者表示感谢，接着感谢在此次课设中给予我帮助的同学们，对于MATLAB软件操作自己开始有一些的生疏给予了指导，最后感谢此次的指导老师熬珺老师在自己学习过程中所遇困惑给予的解答与帮助，作为通信专业的毕业生，在大四的课设中接触到一些应用性较强的前沿知识，自己得到了锻炼，对于以后走向工作岗位有很大的帮助，老师严谨的学术态度与本着对学生负责的想法令人敬佩，本次课设自己以认真的态度和花费较多的时间与精力完成，如有不足之处，望老师给予指教与包涵，谢谢！ 参考文献 [1] [美] Robert J.McEliece,李斗 等译《信息论与编码理论》第二版 [2] 沈世镒、陈鲁生《信息论与编码理论》 [3] [美]Ranjan Bose 武传坤译《信息论、编码与密码学》 [4] [美]Robert H.Morelos-Zaragoza著 张立军译《纠错编码的艺术》 [5] 吴湛击 著 王文博 审《现代纠错编码与调制理论及应用》 [6] 宋文俊 华东师范大学硕士学位论文《RS码的译码研究》 [7] 石俊峰 中国科学院研究生院硕士学位论文《RS(255,223)译码器的FPGA实现及其性能测试》 [8] 徐朝军 西安电子科技大学博士学位论文《RS码译码算法及其实现的研究》 附 录 MATLAB仿真程序： %% 信源编码 clc; clear; m = 8; % GF(2^m) = GF(2^8)伽罗瓦域 n = 2^m-1; k = 223; %定义编码长度RS(n, k) = RS(2^m - 1, k) = RS(255, 223) data = ceil(255*rand(1, 223)); % 构建1个随机生成的数据包数据范围0~255，共223个数据 msg = gf(data,m); % 生成伽罗华域，限定msg信息的运算范围，所有关于msg的运算都将进行mod(2^m)运算、 Code = rsenc(msg,n,k); % 在伽罗瓦域内对msg进行编码。使用RS(255, 223)编码 %code = GF(2^8) array. 特征多项式Primitive polynomial = D^8+D^4+D^3+D^2+1 x = input('手动输入随机信道误码则请输入非零数，随机输入随机信道误码则请输入0:'); if(x == 0) %% 构建0~18个随机生成的随机信道误码，RS(255,223)可以纠正(n-k)/2=16个随机位置错误 Err_cut_t = round(16 * rand(1));%随机构建0~18个随机生成的错误，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 %% 数据输入 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_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('超出数据范围,请重新输入，请重新运行程序') return; else for j = 1 : length(Errs) Error(Err_pos(j)) = Errs(j);%给出现突发数据错误的位置赋予突发数据错误 end break; end end end Errors = gf(Error,m); end %信道噪声加入完毕，下面进行解码 %% Recv为接收到的信号。rsdec函数进行解码 Recv = Code + Errors; % 二进制模2^m加，在伽罗华域中运算，所有大于255的数都将进行模运算 R = E + C [dec,cnumerr] = rsdec(Recv,n,k); % 解码use RS decoder cnumerr是一个列向量，记载了每一行纠正的错误数，-1表示纠错失败 %% 验证正确性。 %画信源图 subplot(2,3,1); stem(data);%信源编码图 axis([-2 225 -2 257]);%规定范围 title('信源，223个符号');xlabel('码序↓↓↓↓');ylabel('码元');%示意 %画RS编码后的编码图 subplot(2,3,4); Disp_RS_Code = gf_double(Code);%伽罗华域到实数域转换。数据域的转换 stem(Disp_RS_Code);%信源编码图 axis([-2 257 -2 257]);%规定范围 title('RS(255,223)编码完成，编码待发送');xlabel('码序');ylabel('码元');%示意 %画信道噪声图 subplot(2,3,5); Disp_RS_Errors = gf_double(Errors); stem(Disp_RS_Errors,':diamondr');%信源编码图 axis([-2 257 -2 257]);%规定范围 title([num2str(Err_cut_t),'个随机信道噪声']);xlabel('码序');ylabel('随机信道噪声↓↓↓↓');%示意 %画RS编码经过信道噪声加成后接收到的信息图 subplot(2,3,6); Disp_RS_Recv = gf_double(Recv); stem(Disp_RS_Recv);%信源编码图 axis([-2 257 -2 257]);%规定范围 title('RS编码经过信道噪声加成后接收到的信息');xlabel('码序');ylabel('码元↓↓↓↓');%示意 %将错误信息也画到此图上， hold on for j = 1 : Err_cut_t stem(Err_pos(j),Disp_RS_Recv(Err_pos(j)),':diamondr');%给出现突发数据错误的位置赋予突发数据错误 end hold off %画RS(255,223)解码后的波形图 subplot(2,3,3); Disp_RS_dec = gf_double(dec); stem(Disp_RS_dec);%信源编码图 axis([-2 225 -2 257]);%规定范围 title('RS(255,223)解码后的信息');xlabel('码序↑↑↑↑');ylabel('码元');%示意 %画比较图 subplot(2,3,2); stem(Disp_RS_dec - data); axis([-2 225 -2 257]);%规定范围 title('信源和接收信息的差值');xlabel('码序');ylabel('差值');%示意 %% 方法 for i = 1 : Err_cut_t if data(Err_pos(i)) == dec(Err_pos(i)) disp([num2str(Err_pos(i)),' th message is decoded right']); else disp([num2str(Err_pos(i)),' th message is decoded wrong']); end end _1234568017.unknown _1234568081.unknown _1234568113.unknown _1234568145.unknown _1234568161.unknown _1234568177.unknown _1234568185.unknown _1234568189.unknown _1234568191.unknown _1234568193.unknown _1234568195.unknown _1234568196.unknown _1234568194.unknown _1234568192.unknown _1234568190.unknown _1234568187.unknown _1234568188.unknown _1234568186.unknown _1234568181.unknown _1234568183.unknown _1234568184.unknown _1234568182.unknown _1234568179.unknown _1234568180.unknown _1234568178.unknown _1234568169.unknown _1234568173.unknown _1234568175.unknown _1234568176.unknown _1234568174.unknown _1234568171.unknown _1234568172.unknown _1234568170.unknown _1234568165.unknown _1234568167.unknown _1234568168.unknown _1234568166.unknown _1234568163.unknown _1234568164.unknown _1234568162.unknown _1234568153.unknown _1234568157.unknown _1234568159.unknown _1234568160.unknown _1234568158.unknown _1234568155.unknown _1234568156.unknown _1234568154.unknown _1234568149.unknown _1234568151.unknown _1234568152.unknown _1234568150.unknown _1234568147.unknown _1234568148.unknown _1234568146.unknown _1234568129.unknown _1234568137.unknown _1234568141.unknown _1234568143.unknown _1234568144.unknown _1234568142.unknown _1234568139.unknown _1234568140.unknown _1234568138.unknown _1234568133.unknown _1234568135.unknown _1234568136.unknown _1234568134.unknown _1234568131.unknown _1234568132.unknown _1234568130.unknown _1234568121.unknown _1234568125.unknown _1234568127.unknown _1234568128.unknown _1234568126.unknown _1234568123.unknown _1234568124.unknown _1234568122.unknown _1234568117.unknown _1234568119.unknown _1234568120.unknown _1234568118.unknown _1234568115.unknown _1234568116.unknown _1234568114.unknown _1234568097.unknown _1234568105.unknown _1234568109.unknown _1234568111.unknown _1234568112.unknown _1234568110.unknown _1234568107.unknown _1234568108.unknown _1234568106.unknown _1234568101.unknown _1234568103.unknown _1234568104.unknown _1234568102.unknown _1234568099.unknown _1234568100.unknown _1234568098.unknown _1234568089.unknown _1234568093.unknown _1234568095.unknown _1234568096.unknown _1234568094.unknown _1234568091.unknown _1234568092.unknown _1234568090.unknown _1234568085.unknown _1234568087.unknown _1234568088.unknown _1234568086.unknown _1234568083.unknown _1234568084.unknown _1234568082.unknown _1234568049.unknown _1234568065.unknown _1234568073.unknown _1234568077.unknown _1234568079.unknown _1234568080.unknown _1234568078.unknown _1234568075.unknown _1234568076.unknown _1234568074.unknown _1234568069.unknown _1234568071.unknown _1234568072.unknown _1234568070.unknown _1234568067.unknown _1234568068.unknown _1234568066.unknown _1234568057.unknown _1234568061.unknown _1234568063.unknown _1234568064.unknown _1234568062.unknown _1234568059.unknown _1234568060.unknown _1234568058.unknown _1234568053.unknown _1234568055.unknown _1234568056.unknown _1234568054.unknown _1234568051.unknown _1234568052.unknown _1234568050.unknown _1234568033.unknown _1234568041.unknown _1234568045.unknown _1234568047.unknown _1234568048.unknown _1234568046.unknown _1234568043.unknown _1234568044.unknown _1234568042.unknown _1234568037.unknown _1234568039.unknown _1234568040.unknown _1234568038.unknown _1234568035.unknown _1234568036.unknown _1234568034.unknown _1234568025.unknown _1234568029.unknown _1234568031.unknown _1234568032.unknown _1234568030.unknown _1234568027.unknown _1234568028.unknown _1234568026.unknown _1234568021.unknown _1234568023.unknown _1234568024.unknown _1234568022.unknown _1234568019.unknown _1234568020.unknown _1234568018.unknown _1234567953.unknown _1234567985.unknown _1234568001.unknown _1234568009.unknown _1234568013.unknown _1234568015.unknown _1234568016.unknown _1234568014.unknown _1234568011.unknown _1234568012.unknown _1234568010.unknown _1234568005.unknown _1234568007.unknown _1234568008.unknown _1234568006.unknown _1234568003.unknown _1234568004.unknown _1234568002.unknown _1234567993.unknown _1234567997.unknown _1234567999.unknown _1234568000.unknown _1234567998.unknown _1234567995.unknown _1234567996.unknown _1234567994.unknown _1234567989.unknown _1234567991.unknown _1234567992.unknown _1234567990.unknown _1234567987.unknown _1234567988.unknown _1234567986.unknown _1234567969.unknown _1234567977.unknown _1234567981.unknown _1234567983.unknown _1234567984.unknown _1234567982.unknown _1234567979.unknown _1234567980.unknown _1234567978.unknown _1234567973.unknown _1234567975.unknown _1234567976.unknown _1234567974.unknown _1234567971.unknown _1234567972.unknown _1234567970.unknown _1234567961.unknown _1234567965.unknown _1234567967.unknown _1234567968.unknown _1234567966.unknown _1234567963.unknown _1234567964.unknown _1234567962.unknown _1234567957.unknown _1234567959.unknown _1234567960.unknown _1234567958.unknown _1234567955.unknown _1234567956.unknown _1234567954.unknown _1234567921.unknown _1234567937.unknown _1234567945.unknown _1234567949.unknown _1234567951.unknown _1234567952.unknown _1234567950.unknown _1234567947.unknown _1234567948.unknown _1234567946.unknown _1234567941.unknown _1234567943.unknown _1234567944.unknown _1234567942.unknown _1234567939.unknown _1234567940.unknown _1234567938.unknown _1234567929.unknown _1234567933.unknown _1234567935.unknown _1234567936.unknown _1234567934.unknown _1234567931.unknown _1234567932.unknown _1234567930.unknown _1234567925.unknown _1234567927.unknown _1234567928.unknown _1234567926.unknown _1234567923.unknown _1234567924.unknown _1234567922.unknown _1234567905.unknown _1234567913.unknown _1234567917.unknown _1234567919.unknown _1234567920.unknown _1234567918.unknown _1234567915.unknown _1234567916.unknown _1234567914.unknown _1234567909.unknown _1234567911.unknown _1234567912.unknown _1234567910.unknown _1234567907.unknown _1234567908.unknown _1234567906.unknown _1234567897.unknown _1234567901.unknown _1234567903.unknown _1234567904.unknown _1234567902.unknown _1234567899.unknown _1234567900.unknown _1234567898.unknown _1234567893.unknown _1234567895.unknown _1234567896.unknown _1234567894.unknown _1234567891.unknown _1234567892.unknown _1234567890.unknown