《课设_RS纠错编码仿真.》由会员分享，可在线阅读，更多相关《课设_RS纠错编码仿真.（27页珍藏版）》请在金锄头文库上搜索。
1、编号： 课程设计说明书题 目： RS(255,223)纠错编码的 MATLAB仿真 院 （系）： 专 业： 学生姓名： 学 号： 指导教师： 2013 年 12月10日目 录1 引言21.1信道编码理论与技术的发展历程及应用21.2 纠错编码简介42 Reed Solomon编码概述53 Reed Solomon编码抽象代数基础63.1 群63.2 环和域73.3 有限域73.4 欧几里得算法84 BCH码、RS码及其编码94.1 BCH码、RS码简介94.2 RS码的构造方法105 RS码的译码115.1 关键方程的引入125.2 多项式的欧几里得算法135.3 BCH/RS码的解码步骤15
2、6 MATLAB主要程序及其仿真结果187 总结19致谢20参考文献21附 录22摘 要在纠错码领域中Reed-Solomon码是一类具有严格代数结构的线性分组码。由于它突出的纠错能力(特别是纠突发错误的能力),常被应用于数据存储以及现代数字通信系统中。在卫星通讯中，差错控制编码技术对降低误码率、提高通信的可靠性具有非常重要的作用。RS(Reed-Solomon)码是差错控制领域中一种性能优异的线性分组循环码，由于其具有很强的随机错误和突发错误的纠错能力，所以被CCSDS、NASA、ESA 等空间组织接受，广泛用于深空探测中。目前我国还没有高码速率的 RS 硬件译码器，虽然“双星计划”已经采用
3、 RS纠错编码技术，在卫星上使用 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-Var
6、shamove 限（GV 限），其证明可以在编码理论的基础教材中找到；4）1957 年，Elias 提出了一种概念译码器表单译码器（List Decoder），以突破传统的限定距离译码（BDD）的半最小码距的纠错半径；5）1961 年，W. W. Peterson 编写了第一本关于纠错码理论的专著，系统地阐述了纠错码的基本理论。2. 60 年代至 70 年代初这是纠错码发展最为活跃的时期之一。在此期间，以代数方法特别是以有限域理论为基础的线性分组码理论已趋成熟。1）提出了许多有效的编、译码方法。1965年，E. R. Berlekamp提出了一种实用分组码的代数译码算法，1969年, J.L.
7、 Massey从序列综合的角度重新推导了这一算法，后人称之为Berlekamp-Massey算法（BM算法）。BM算法的提出，是分组码走向实用的一个重要里程碑。1966年，G. D. Forney第一次采用简单的分量码构造级联码，以提高码的性能。第一个成功的级联码是采用卷积码作内码、RS码作外码的串行级联码，其典型应用是在卫星通信、深空探测等领域，如Voyager、Galileo、Cassini等任务，这种编码方式还被应用于美国的数字电视（ATSC）、欧洲的数字视频广播（DVB）和数字音频广播（DAB）等系统中；另一种典型的级联码是C. Berrou于1993年发现的并行级联卷积码（PCCC）
8、，即我们通常所称的Turbo码，这是一种逼近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码是一种利用伪随机交织器构造的具有随机码行为的长码，它采用并行级联卷积码的方式进行编码，用最
13、大后验概率（MAP）译码器进行迭代译码，分量译码器之间通过传递所谓的外信息来减少信息损失，其性能非常接近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年提出的Guruswami-Sudan算法则可适用于任意码率的RS码和代数几何码。另一方面，Koetter和Vardy基于G
