课设RS纠错编码仿真

1、编号:课程设计说明书题 目 RS(255,223)纠错编码的MATLAB 仿真院(系)：专 业：学生姓名：学 号：指导教师：2013年12月10日目录1 引言 01.1 信道编码理论与技术的发展历程及应用 01.2 纠错编码简介 32Reed -Solomon 编码概述 53Reed -Solomon编码抽象代数基础63.1 群 63.2 环和域 63.3 有限域 73.4 欧几里得算法 74BCH码、RS码及其编码84.1BCH码、RS码简介84.2RS码的构造方法85RS码的译码105.1 关键方程的引入 105.2多项式的欧几里得算法 115.3BCH/RS 码的解码步骤 126MATL

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

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

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

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

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

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

8、AB 等系统中； 另一种典型的级联码是 C. Berrou 于 1993年发现的并行级联卷积码 （PCCC， 即我们通常所称的Turbo码，这是一种逼近Shannon限的码。1967 年， A. J. Viterbi 提出了卷积码的最大似然译码算法，实现了数字通信中信道编码技术的一次实质性突破。 Viterbi 算法还在其它领域得到了广泛应用。 1974年， Bahl等提出了一种最大后验概率（MAP译码算法（也称为BCJR算法），其误比特率（BER 性能优于Viterbi算法。但由于计算复杂度大大增加，MAP算法直到1993年Berrou发现 Turbo 码之后才得到广泛应用。由于硬判决译码通

9、常较软判决译码损失23dB,对分组码的软判决译码算法的研究也逐渐成为一个重要的课题。对于卷积码，硬判决译码和软判决译码通过相同的格图进 行译码，其复杂度大体相同。而对于分组码，基于格图的译码与代数译码相比，复杂度 会大大增加，因此次优的译码算法成为首选。在这方面，著名的有广义最小距离（ GMD 译码算法、Chase算法等。2）研究了与码的性能有关的各种问题， 如码的重量分布、 译码错误概率和不可检错 误概率的计算、信道的模型化等，所有这些问题的研究为信道编码技术的实用化打下了 坚实的基础。3. 70 年代初至 80 年代 这是信道编码发展史中最具重要意义的时期，信道编码在理论和实践方面都取得了

10、 丰硕的成果。1）在理论上，以 Goppa 为首的一批学者在 70 年代初较系统地构造了一类逼近Shannon 限的有理多项式码 Goppa 码，这在纠错码的历史上具有划时代的意义。80年代初， Goppa 等将代数几何的理论与方法系统地应用于编码理论中，由 Goppa 码引 出了代数几何码，使得Goppa码日益引起了人们的极大兴趣。1987年，G. Ungerboeck 提出了著名的格图编码调制（TCM技术，展示了如何将编码和调制结合起来，改善系 统的整体性能，这是编码理论的又一重要里程碑。之后，众多研究者开始对 TCM 进行 了深入研究，并将这一概念推广到分组编码调制（ BCM。2）这期间

11、微电子技术的迅速发展， 为编码技术的实用化打下了坚实的物质基础； 各 种实际应用也带动了信道编码技术的发展，编码技术的实用化得到了极大关注，并取得 了巨大的进展。 例如，用于 RS 码译码的 BM 算法进一步发展成熟， 出现了无求逆的 BM（iBM）算法、Euclid 算法、Welch-Berlekamp算法（WB算法）等，其超大规模集成 电路（VLSI）实现也得到了充分的发展。信道编码技术最成功的应用在于卫星通信和深空探测领域，这使得宇宙飞船从遥远 的太空传回了许多极其宝贵的天文学资料。特别值得一提的是，在 1989 年的 Galileo 任务中，由于主天线的故障，数据传输的速率比原设计指标

12、大大下降，喷气式推进实验 室（JPL）的科学家们从地面发送指令，重新配置板上计算机，在数据传输之前进行了 更多的编码处理，使得由于硬件故障引起的数据传输速率下降得以部分恢复，从而挽救 了整个探测计划。若不应用信道编码技术，这些成就的取得是不可企及的。此外， 信道编码技术还用于数据存储系统， 提高数据存储密度； 用于数据传输系统， 提高数据传输速率；用于各种数字通信系统，提高通信质量；用于数字音频 / 视频传输 系统以及视听娱乐设备，为我们的生活带来美妙的音乐和完美的视觉享受；而且纠错码 技术还应用于超大规模集成电路设计中，以提高集成电路芯片的成品率，降低芯片的生 产成本。4. 90 年代以后这

13、一时期，编码理论的重大发现当首推 1993年 Berrou 等发现的 Turbo 码。 Turbo 码是一种利用伪随机交织器构造的具有随机码行为的长码， 它采用并行级联卷积码的方 式进行编码，用最大后验概率（MAP译码器进行迭代译码，分量译码器之间通过传递 所谓的外信息来减少信息损失，其性能非常接近 Sha nnon限，这一惊人的性能打破了长期以来的猜想： 利用二元卷积码和序列译码是达到截止速率 R （即所谓的“实际容量”） 的一种可实现的方法。在迭代译码器中，所采用的分量码MAP译码器可以用软入输出Viterbi算法（SOVA代替，这会使Turbo码译码性能略有下降，但大大降低了计算复 杂度

14、和存储量要求。更为实用的分量码译码器是Koch等提出的Max-Log-MAP译码算法和Robertson等提出的Log-MAP译码算法。后来，Hagenauer、Pyndiah又分别将Turbo 码迭代译码的思想用于级联二元分组码和乘积码。现在， Turbo 码的迭代算法已经成为 “Turbo 原理”，广泛应用于各种级联系统，如均衡、编码调制、信源压缩、信源信道联 合编码以及信号检测等。另一方面，在探究Turbo码迭代算法的过程中，Mackay和Neal于1996年重新发现 了 Gallager于60年代提出的具有稀疏校验矩阵的线性分组码 LDPC码，基于Tanner 图进行迭代译码，其性能与

15、Turbo码差不多。最近，采用BCH码作外码、LDPC码作内码 的级联码已经被DVB-S2采纳。1998年， Tarokh、 Seshadri 和 Calderbank 提出的格图空时码，在时间和空间上都 引入了编码，集前向纠错（FEQ、发送分集和接收分集于一体，能获得较大的编码增益 和分集增益，实现数据的高速传输。 几个月后， Alamouti 发明了低复杂度的分组空时码。 空时码的基本思想是采用多个发射天线和多个接收天线来提高系统容量， 关于空时码已 有许多研究文献。由于RS码在众多数字通信系统、数据存储系统中的成功应用，以及其软判决译码性 能的巨大潜力，RS码的软判决译码问题也得到了很大

16、的关注。其中，Sudan于1997年提出了多项式复杂度的表单译码（List Decoding）算法，将RS译码问题转化成有限域 上的曲线拟合问题，给出并证明了几个重要的定理，奠定了RS码表单译码的基础。但Sudan算法只适用于码率不大于 1/3的RS码，而1999年提出的Guruswami-Sudan算法 则可适用于任意码率的 RS 码和代数几何码。另一方面， Koetter 和 Vardy 基于 Guruswami-Sudan算法，将接收符号的软信息转化为一系列的代数条件，用代数方法实 现了 RS码的软判决译码。1.2 纠错编码简介我们知道 ,在计算机和数据通信中 ,经常需要将二进制数字信号

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

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

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

20、正。经纠正后的二进制信号送入二进制信号接收器 , 从而完成整个传输过 程"二进制信号接收器可以是计算机 , 或其他接收装置如终端等。但是, 为什么纠错码具有发现错误 !纠正错误的能力呢 ?纠错码又是按什么样的原理 去编的呢 ?为了说明这些问题 ,我们首先介绍一些基本概念 : 由 0 和 1 组成的串称为字 (Word), 一些字的集合称为码(Code)。码中的字称为码字(Codeword)。不在码中的字称 为废码(InvalidCode)。码中的每个二进制信号 0或1称为码元(Code Letter)。我们下面举出几个关于纠错码的例子。设有长度为2的字,它们一共可有2x2=4个,创门

21、所组成的字集 S,=00,01,10,11 。当选取编码为 52 时,这种编码不具有抗干扰能 力。因为当 52中的一个字如 10,在传递过程中其第一个码元 1变为0,因而整个字成为 00 时,由于 00也是 52 中的字,故我们不能发现传递中是否出错。但是 ,当我们选取 52 的一个子集如C2二00,川作为编码时就会发生另一种完全不同的情况。因为此时01和10均为废码,而当H在传递过程中第一个码元由1变为0,即整个字成为01时，由于01 是废码,因而我们发现传递过程中出现了错误。对 00也有同样的情况。但是 ,这种编码 有一个缺点 , 即它只能发现错误而不能纠正错误 , 因此我们还需要选择另一

22、种能纠错的 编码 " 现在我们考虑长度为 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, 我们不仅能发现错误而且能纠

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

24、码CD交叉交织RS码（CIRCDVDRS(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码译码子系统设计过程中要考虑的一个关键的问题。

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

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

27、些译码算法各有千秋，就实用性而言，GMDT法、Chase-ll算法和Koetter-Vardy 算法略胜一筹。3 Reed - Solo mon编码抽象代数基础3.1 群定义 设G是一个非空集合，称映射 :G G G为G上的一个二元运算，即对于 G 中仍以两个元a和b，唯一确定c (a,b).记为c a b,为了方便起见，可写成c=ab.定义 设G是一个非空集合，是G上的一个二元运算，如果G满足下列条件：a) (结合律)对于任意a,b,c G,有(a b) c a (b c)b) (单位元)G中存在单位元e,对于任意a G ,满足e a a e ac) (逆元)对于任意 a ，存在的逆元 a

28、1，满足a a 1 a 1 a e则称G为群，记为(G,?).如果群(G,?)满足交换律，即对于任意a,b G,满足ab ba则称群 为交换群或阿贝尔群 .3.2 环和域定义 设R是一个非空集合，R上有两个二元运算和？，分别成为加法和乘法，如果R满足下列条件a) (R, ) 为加法阿贝尔群b) (结合律)对于任意 a,b,c R, 有(a b) c a (b c)c) (分配律)对于任意 a,b,c R, 有a (b c) a b a c(b c) a b a c a称R为环，记为(R, ,?)，如果他对乘法满足交换律，即对任何a,b Rab b a称环 (R, ,?) 为交换环定义设(R,

29、,?)为交换环，R*表示R中所有非零元的集合，如果 R*在乘法运算下构成 交换群，则称 (R, ,?)为域。3.3 有限域定义 设F为一个域，如果F只含有有限个元素，称F为有限域，含有q个元素的有 限域记为Fq，有限域也成为伽罗华域(Galois field)，用GF(q)或Fq表示q阶有限域。最简单的有限域是二元域 GF(2)=0,1 。定义对于GF(q)上的每个非零元素，存在最小整数k,使k 1成立，则称为k阶定义 对于GF(q)上的每个非零元素，如果其阶数是q-1 ,则称 为本原元素。定义GF 2上的一个m次多项式(x)，如果他的所有根都是GF 2m中的本原元素, 则称(x)是m次本原多

30、项式。例如，对于m = 8时GF(2m) GF(28)上的m次本原多项式为(x)1 x2 x3 x4 x8对于m = 7时GF(2m) GF(27)上的m次本原多项式为(x)1 x3 x7定义设 为GF 2m中的元素，多项式m(x)是GF 2上使m( )0的最低次多项式，则称m(x)为最小多项式。具有相同最小多项式的元素，构成同一共轭系。3.4 欧几里得算法欧几里得算法给定两个正整数 a,b ，可以用欧几里得除法得到其最大公约数 (a,b) ， 并求得 A，B，满足(a,b)=Aa+Bb。用欧几里得除法求 (a,b) 的步骤如下：第一步：不失一般性，假设 a>b，且令r 2 a,r i

31、b,k 2 第二步：用rk i除以rk得到其商数ak 2和余数m 2，亦即rk ak 2rk 1 rk 2第三步：如果rk 2 0,停止运算，(a,b) rki并记n k 2;否则，k k 1转第二 步。欧几里得算法又被称为辗转相除法，这里 rk 是单调下降序列。用欧几里得算法可以求得 A B,沿用上述除法得到ak的和n,其方法如下： 第一步：令 bn 0,bn i i,k n i第二步：计算 bk 1 akbk bk 1第三步：如果k 0,停止运算，此时A b0, B b1,否则k k 1转第二步事实上， k,(a,b) bkrk bk 1rk 1 , ( A, B )只是其中的一个特例。4

32、 BCH码、RS码及其编码4.1 BCH码、RS码简介如前所述，BCH码是纠错能力可能的循环码，由 Bose、Chandhari和Hocquenghem 在19501960年间分别独立地提出。最初的 BCH码定义在二元域上，成为二元 BCH码， 后来推广到多源于上。对于设计纠错能力为 t 的循环码，器生成多项式含有 2t 个连续 幕次的根，这样的循环码称为 BCH码。如果BCH码的根是本原元，成为本原 BCH码。如 果BCH码的根是非本原元，称为非本原 BCH码。如果定义在GF 2m上的本原元以及2、 3、2t共2t个连续幕次都是定义 在GF 2上的生成多项式g(x)的根，那么该BCH码成为设

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

34、造出最小距离为d的二元非本原BCH码，n, k, d ，满足 nc 2m 1,k n mt 2m 1 mt,d 2t 1。另外，实际的纠错能力t，可能会大于设计 纠错能力的 t.BCH码的编码是在二元域完成的，对比特进行编码，与普通的二进制循环码并无不 同。而RS的编码是在多元域GF pm上完成的(p是质数)，对符号进行编码，因为RS 码又被视为多元域上的本原 BCH码。如果定义在GF pm上的生成多项式2tg(x) (x i)，其中 是定义在GF pm上的本原元，那么该BCH码被称为纠错能力i1为t的RS码。4.2 RS码的构造方法第一步，由关系式n 2m 1算出m查本原多项式表得到一个 m

35、次的本原多项式 P(x)，从而产生一个GF 2m的扩域，使域元素(符号)i与m重向量建立起一一对应第二步：2tg(x) (xi 1化简为g(x)第三步：根据设计纠错能力 i)。利用n 2tk(i) ix。i 0已知生成多项式1,的关系本原多项式表mM本原多项式2彳 21 x x3d31 x x41 x x51 x2 x561 xx67“371 x x823481 x x x xt，直接计算定义在GF 2m上的生成多项式2ti i 0和P()等运算规则，可以将 (x i)展开并g(x)，根据关系式C(x) M(x)g(x)，对信息位M(x)多项式 g(x)都i 1编码得到码字多项式C(x)，这就

36、完成了 RS码的编码过程。这里的C(x)、M (x)和是GF 2m上的多项式。而对于长度为mk的二进制的输入序列，以m个比特位一组划分可以得到k个m重向量，再将每个m重向量映射为GF 2m上的元素i，从而得到长度为k的多元序列M(x)。得到长度为n的多元序列C(x)后，对于每一个GF 2m上的元素,再映射为m重向量，从而得到长度为nm的二进制编码序列。的各次幂将序列映射6x。那么可以求3x )的各次幕将其映射为例如，对于信息输入比特序列100,101,010，首先根据表格 为GF 23上的序列 2, 6, ，则其信息位多项式M(x) 2x2 得GF 23上的码字多项式。C(x) M (x)g(

37、x)( 2x26x )(x43x3 x22 654224x x x x从而得到GF 23上的编码序列 2, , ,0, 2,0, 4。再根据表格 二进制编码序列即可得到 RS码100,010,010,000,100,000,110。表格的各次幕即约多项式3重向量0000100101021003 1011421105 2 11116 2 1101RS码是纠正短突发差错的首选纠错码，广泛应用于无线通信的存储系统中。例如，美国宇航局(NASA在探险者号(Voyager)上用了 256进制的255,223,33RS 码，其 生成扩域的本原多项式是P(x) 1 x2 x3 x4 x8,m 8，生成多项式

38、是g(x) (x )(x2)(x 32)。是本原多项式P(x)的根，因为g(x)含有32个连续幕次的根，因而改码的纠错能力为符号t 32/2 16个符号(256进制)或者等效长度 是(t 1)m 1 121的二进制特发差错。5 RS码的译码由于BCH码和R-S码都是循环码，所以可以米用一般的梅杰特解码器，但是BCH码和R-S码的设计纠错能力都比较髙，从而使得梅杰特解码器的实现复杂度BCH码和RS码的解码原理是一样的，其髙效解码算法的基础在于一个关键方程的引入和基于多项式 的欧几里德算法。在 BCH/RS码的解码算法的发展历史上，彼得森(Peterson)于1960 年提出了第一个BCH勺解码算

39、法。之后，钱(Chien)、福尼(Formey)、梅西(Massey) 和巴勒坎普(Berlekamp)相继提出了更高效的BCH解码算法。到了 1975年，Sugiyama Kasahara、Hirasawa和Namekaw发现也可以采用欧几里德(Euclid)算法对BCH/RS3解 码，并发现巴勒坎普(Berlekamp)解码算法与欧几里德(Euclid)算法相比仅差一个很 小的常数因子。而欧几里德(Euclid)算法更容易理解些，所以得到了更广泛的应用。 具体解码又可以分为时域解码和频域解码。5.1关键方程的引入n 1令F是一个含有n阶单元本原元的域，那么根据定义有1 xn (1 ix)，

40、再令i 0V是F上的一个n维向量，V (v0,w，,vn1)称为时域向量。AAAA又令V (V0,V1,vn 1)，是V的离散傅里叶变换(DFT，成为频域向量；a n 1DFT(离散傅里叶变换)：vj vi ij,j 0,n 1那么，可以证明，从频域到时域的 IDFT (逆离散傅里叶变换)也成立；IDFT (逆离散傅里叶变换)：vj 1 vi u,j 0, n 1n i 01设F是GF(pm),p是质数，n pm 1，那么特征是p。IDFT中的丄是以特征p为模1n的同余类。易知n (p 1)mod p，所以(p 1)* - 1mod p，根据欧几里得算法有n1 1一 (p 1)mod p。对于

41、 GF(2m)，一 1 nAn在定义V和V的生成多项式：V(x) v0 wxvn 1xn 1和AAAAV(x) v0 v1 xvn 1 xn 1。那么df可以将上述的离散傅里叶变换写为:对于V,定义他的支持集I, I馆，亦即I是V中非零元素的索引集。在定义V的位置多项式v(x), v(x)(1 ix)。对于i I，再定义i阶穿孔位置XLXuo V1最后，疋义/、 j Iv(x), v(x)Vi V"(x)。那么，可以证明 GCD( v(x), v定理关键方程：对于固定的向量V,多项式v(x),Av(x)V(x)v(x)(1 xn)V的数值多项式(x)1。Av(x)和V(x)满足一下关

42、键方程有了上述的数学基础，就可以引入 BCH/RS码的关键方程了。设编码向量为C 5 5,cn 1，信道错误图案为向量E e。®,en解码的第一步是计算伴随式向量止日 步疋n 1 那E么，SjCii 0令时域向量V(x)A关系 vi si 1,i 0, 2tA1，那么接收向量R C E，S So,S!,Sn 1 , S的定义如下n 1Sjri ij,j 1,2tn 1 i 0ii ij0ei 0 n 1A,en1 ，那么易知，伴随式向量S与频域向量V满足An 1 ij e iji 0ge ,1，亦即，伴随式向量S是V的钱2t个分量，这是可以直接观测n 1到的，而V的后(n-2t )个

43、分量不能直接观测到。记伴随式多项式S(x)ri iji 0 A解码算法的目的是已知伴随式向量 S求错误图案向量E,从而得到解码向量C R E，A由于只是知道频域向量V(x)的前2t个分量，需要用modx2t对关键方程降次Av(x)V(x)mod x2tv(x)(1 xn )mod x2 0所以得到BCH/RS勺关键方程v(x)S(x)v(x) mod x2t由于V的支持集是发生误码的标号集合，所以(x)又被成为错误位置多项式，(x)v(x)，而(x)又被成为错误数值多项式，其中(X) v(x)，deg( (x) t,deg( (x) t 1，t是最高次的数字。t是BCH/RS的设计纠错能力。5

44、.2多项式的欧几里得算法BCH解码的目标是已知S(x)，通过求解关键方程 (x)S(x) (x)mod x2t，得到(x) 和(x)，进而求出E(x)。求解的关键算法是欧几里得算法。在抽象代数基础已经介绍 了欧几里得算法，这里将其推广到多项式上。多项式上的欧几里得算法 给定两个有限域F上的两个多项式a(x),b(x),可以用欧几 里得除法得到其最大公约数d(x) gcd(a(x),b(x)，并求得u(x), v(x)，满足 d (x) u(x)a(x) v(x)b(x)欧几里得除法求gcd(a(x), b(x)的步骤如下：第一步：不失一般性，假设 deg(a(x) deg(b(x)且令 r 1

45、a(x), r0 b(x),k 1第二步：用rk 1 (x)除以rk(x)，得到其商数qk 2(x)和余数rk 2(x)，亦即rk(x) qk 2(x)rk1(x) rk 2(x)第三步：如果个2(x) 0,停止运算，d(x) gcd(a,b)个i(x)，并记n k 1 ;否则 k k 1，转第二步。欧几里得处理又被成为辗转相除法,这里deg(rk) 是单调下降序列。用欧几里得算法可以求得u(x), v(x)。沿用上述除法得到2讣和n，其方法如下： 第一步： u 1(x) 1,u0(x) 0;v(x) 0,v0(x)1;k 1第二步：计算 uk(x) uk 2(x) qk(x)uk 1(x);

46、vk(x) vk 2(x) qk(x)vk1(x);第三步：如果k n，停止运算，此时U(x) Un(x)， v(x) Vn(x);否则k k 1，转 第二步。这里， deg(uk(x) 是单调递增函数，而 deg(vk(x) 也是单调递增函数。容易得到 以下两条性质：(1) uk(x)a(x) vk (x)b(x) rk(x), k 1,n 1(2) deg(vk(x) deg(rk 1(x) deg(a(x), k 0,n 1 从而推出以下性质：(1) vk(x)b(x) rk(x)moda(x), k 1,n 1(2) deg( vk ( x) deg(rk (x) deg(a( x),

47、 k 0,n 1 进一步有如下定理：定理 设a(x), b(x), v(x)和r(x)是非零多项式，m、n是非零负整数， deg(a(x) deg(b(x) 满足：v(x)b(x) r(x)mod a(x)deg( v( x) mdeg(r (x) nm n deg(a(x) 1 进一步假设vk(x)和rk(x)(k 1,n 1)是对(a(x), b(x)应用欧几里得算法得到的多 项式序列。那么存在且唯一存在标号 j, j 0, n 1使得vj(x)b(x) rj(x)moda(x)Euclid a(x),b(x),m, n表示上述结果。(x)vj (x)(BCH/Rs码的关键方程。用一个欧几

48、里得抽象函数 vj(x),rj(x) 进而存在一个常数多项式 (x) ，使得： v(x) r(x) 这个定理表明完全可以用欧几里得算法解决5.3 BCH/RS码的解码步骤有了关键方程和欧几里得抽象函数， 讨论BCH/RS军码的步骤就水到渠成了。假设已经求得了错误位置多项式（x）和错误数值多项式（x），为了求差错图案多项式E（x）,A有时域和频域处理两种方法。求出 E（x）后，解码码字向量C R E时域算法的本质就是对错误位置多项式（x）进行验根。由于（x）（1 ix），那么（i）0;反之，如果（i） 0，那么含有因子（1 ix）。所以，如果（i）0，说明第i个位置上的接收向量存在误码，否则第i

49、个位置上的接收向量ri是正确的。 对于二元域BCH码，e 0,1比较简单，如果（i） 0,那么e 1，否则e 0。而对 于多元域上的RS码，e是多元域元素，还需要进一步求出。对于RS码，如果（i） 0， 那么 viieii -V一，亦即 e-4一），否则 e 0。首先用C语言伪代代码说明BCH码的时域解码算法，如下所示:/*二元域BCH码的属于解码算法*/A/*码长n,设计纠错能力t，接收向量R,错误图案向量E,解码码字向量C*/for(j = 1 to 2t)n 1ri ij ；/ j 1,2t i 02t 1iS 1X ；SjS(x)i 0if( S(x) 0)printf("接

50、收码字正确，无误码");else/用欧几里得算法解关键方程Vj （x）jj （x）Euclidxjs（x）,t,t 1;if（ Vj（0）0）printf（"误码超出了纠错能力t，不可解码"）;else (X)Vj(x)/Vj (0);for(i = 0 to n-1)if( ( i)0)eielseeiACirifor(i = 0 to n-1)A AAprintf("接收到的码字为：6,g,G 1 ")；1解码中需要归一化(x) Vj(x)/Vj(O)。因为(X)(1 ix)，所以(0) 1，从而归一化是必须的。如果Vj(0)0，那么无法归

51、一化，这通常是因为误码超过了纠错能力t，从而不可解码。由于BCH码的简单性，无需用到(x)。下面说明RS码的解码算法，如下所示:/*RS解码算法*/A/*码长n,设计纠错能力t，接收向量R,错误图案向量E,解码码字向量C*/for(j = 1 to 2t)n 1Sjri ij ;/ j 1,2ti 02t 1iS(x) s 1X;i 0if( S(x) 0)printf("接收码字正确，无误码");else/用欧几里得算法解关键方程Vj (x)，r (x) Euclidx2t,S(x),t,t 1;if( Vj(0)0)printf("误码超出了纠错能力t，不可解

52、码");else(x) v(x)/Vj(0);(x) rj(x)/Vj(0); j fo+(i = 0 to n-1)if( ( i)0)厂()i)elseeifor(i = 0 to n-1)riCiprintf("接收到的码字为：sg,cn 1 ");至此，RS编码解码的代数基础、编码理论及方法，解码理论及方法均已介绍完毕, 下面利用MATLA进行仿真。6 MATLAB主要程序及其仿真结果利用MATLABS写仿真程序如下所示：%信源编码clc; clear;m = 8; % GF(2Am) = GF(2A8)伽罗瓦域n = 2Am-1; k = 223; %

53、定义编码长度 RS(n, k) = RS(2Am - 1, k) = RS(255,223)data = ceil(255*ra nd(1,223); %构建1个随机生成的数据包数据范围0255,共223个数据msg = gf(data,m); % 生成伽罗华域，限定 msg信息的运算范围，所有关于msg的运算都将进行mod(2Am运算、Code= rsenc(msg,n,k);%在伽罗瓦域内对 msg进行编码。使用 RS(255, 223)编码%code = GF(2A8) array. 特征多项式 Primitivepoly no mial=DA8+DA4+DA3+DA2+1%构建018个

54、随机生成的随机信道误码，RS(255,223)可以纠正(n-k)/2=16 个随机位置错误Err_cut_t = round(18 * rand(1);%随机构建 0T8个随机生成的错误，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_

55、tError(Err_pos(j) = Errs(j);%给出现突发数据错误的位置赋予突发数据错误endErrors = gf(Error,m);%言道噪声加入完毕，下面进行解码% Rec为接收到的信号。rsdec函数进行解码Recv = Code + Errors; % 二进制模2Am加，在伽罗华域中运算，所有大于255的数都将进行模运算R = E + Cdec,cnumerr = rsdec(Recv,n,k); % 解码 use RS decoder cnumerr 是个列向量，记载了每一行纠正的错误数，-1表示纠错失败%验证正确性。%画信源图程序代码运行结果如下:* LI 由MATLA仿真结果可以看到，只要信道噪声小于 16个随机突发错误，利用 RS(255, 223)编码后的信号通过随机信道噪声加成后再利用解码算法可以完美的还原信源。7总结我国的航天事业正处于蓬勃发展的阶段，月球探测等今后的重大项目都对数据的传 输提出了越来越高的要求，高速的数据传输系统必将得到更多的推广。本课题中 RS(255,223)译码器仿真对以后的航天项目中的地面高速接收系统的设计和星上数据接 收系统的设计均有着很大的意义。本文详细介绍了纠错码的相关理论， 包括编码定理、有限域运算法则、BCH码、RS码 的基础知识，还介绍