BCH码与汉明码的分析与仿真--毕业论文.doc

xx大学本科毕业论文（设计） 本科毕业论文（设计）论文（设计）题目： BCH码与汉明码的分析与仿真 学 院： 大数据与信息工程学院 专 业： 电子信息工程 班 级： 电信 学 号： 学生姓名： xx 指导教师： xx 年 月 日xx大学本科毕业论文（设计） xx大学本科毕业论文（设计）诚信责任书本人郑重声明：本人所呈交的毕业论文（设计），是在导师的指导下独立进行研究所完成。毕业论文（设计）中凡引用他人已经发表或未发表的成果、数据、观点等，均已明确注明出处。特此声明。论文（设计）作者签名： 日 期： xx大学本科毕业论文（设计） BCH码与汉明码的分析与仿真Analysis and simulation of the BCH code and Hamming codexxQi-yangxin目录摘要IAbstractII第一章 绪论1第二章 纠错编码简介32.1 差错控制技术32.2 纠错编码相关术语简介42.3 纠错编码基本原理52.4 纠错编码的性能及简单的纠错码讨论52.4.1 纠错编码的性能52.4.2 奇偶监督码62.4.3 二维奇偶监督码62.4.4线性分组码6第三章 汉明码73.1 汉明码构造原理73.2 汉明码解码原理103.3 汉明码的Matlab仿真163.3.1 Matlab简介163.3.2 汉明码仿真的思路163.3.3 汉明码的仿真模块分析173.3.4汉明码仿真的结果与分析20第四章 BCH码244.1 BCH码的构造原理244.1.1循环码的运算244.1.2本原BCH码构造原理254.2 BCH码的解码原理264.3 BCH码的仿真294.4 BCH码的仿真结果与分析34第五章 总结与体会355.1总结355.2体会35致谢37参考文献38附录一 仿真程序代码39第 43 页xx大学本科毕业论文（设计） BCH码与汉明码的分析与仿真摘要汉明码的功能是纠正单个错误或检测两个错误。在大的分类中，纠错编码被分为分组码和非分组码，分组码中的线性分组码是我们主要的研究对象，汉明码就是属于线性分组码。它具备适用性质强，编译电路十分简略，且相比同时期其他线性分组码的分支更易于实现的特点。BCH 码的功能是纠正多个错码，目前在通信领域仍然得到了广泛的运用。属于循环码的一种，而循环码又隶属于线性分组码。 本论文针对用途广泛的BCH码和汉明码检错纠错原理以及检错纠错性能进行了分析与仿真，主要完成了三个项目的学习：1. 了解BCH码和汉明码的来由、用途、性质及其性能，掌握通信传输相关基础知识2. 深入了解BCH码和汉明码的编码原理、解码原理，加深理解相关算法和相关思想。最终实现对任意（n,k）值的BCH码和汉明码所具备的纠错性能进行有效地分析。 3.利用MATLAB软件中内嵌的通信相关仿真模型库绘出模块图，从而进行BCH码和汉明码的建模仿真，分别对两种码进行分析讨论。关键字：BCH码,汉明码,编码,译码,检纠错Analysis and simulation of BCH code and Hamming codeAbstract Hamming code is a way to correct an error and automatically detect code of linear error correcting code, the increase in anti-jamming ability of the communication system . Hamming code is the excellent performance of error-correcting code , its coding efficiency is the highest linear block codes can correct random errors .BCH code is a way to correct same errors and belongs to Cyclic code,also belong to linear block code.BCH code has many special algebraic properties, these properties contribute to the error correction ability of the system as required to construct.This thesis focuses on the different parameters under the conditions of the BCH code and the Hamming code error detection and correction capability analysis, almost complete the following three aspects :1. An understanding of the source, use of the BCH code and Hamming code , classification and correction ability by learning the basics of how it works,and pay attention to how the communication system works.2. An deep understanding of the BCH code and the Hamming code ,about coding , error correction decoding algorithm . Can implement any （n,k）value of the BCH code and the Hamming code error correction capability for theoretical analysis .3. Using MATLAB simulation model library of communication systems the BCH code and the hamming modeling and simulation , to analyze the performance of the BCH code and the Hamming code separately.Key words: BCH code , Hamming code,encoding and decoding ,error detection and correction 第一章 绪论 通信过程中，数字信号在信道中传输会受到不可避免的干扰的影响，导致所发送的信息波形被破坏，从而使接收端接收到可能已经生成错误的信息。出现的干扰通常有两种：一种是乘性干扰，一种是加性干扰：乘性干扰由衰落引起，由乘性干扰引起的多径干扰可以用均衡的方法予以纠正：而加性干扰与乘性干扰完全不同，是由白噪声引起的，无法用均衡的方法排除，减小加性干扰的影响首先应该选择合理的调制制度，合理的解调方法，合理的发送功率，如果以上方法还不能达到相应的误码率的要求，就需要我们考虑用差错控制编码来控制了，差错控制编码也就是包括了汉明码和BCH码在内的多种编码。差错控制编码，本论文中以下均简称为纠错编码。纠错编码从问世算起的话已经有了近六十年的发展历史。1948年，克劳德艾尔伍德香农在自己发表的通信的数学理论中提出了信道编码定理，为纠错编码奠定了理论的基础，早期有线性分组码（包括汉明码、BCH码在内），后来出现了BCH码演化的的RS码、卷积码，级联码、Turbo码、网格码；从代数关系相关的理论研究，到注重纠错编码设备、码率要求的应用问题，更进一步经由计算机仿真来完善。从编码方法、译码方法、研究方法、应用范围等多个方面来看，关于纠错编码的研究都取得了难以估量的进步，对各种通信系统生成了深远的影响，比如移动通信和计算机通信，可以预见，纠错编码在今后的信息技术发展中还将扮演重要的角色。 本文主要研究的是其中的汉明码和BCH码。汉明码由理查德卫斯理汉明于1950年发明，所以命名为汉明码，汉明码的功能是纠正单个错误或检测两个错误。在大的分类中，纠错编码分为分组码和非分组码，分组码中的线性分组码使我们主要的研究对象，汉明码就是属于线性分组码的。它具备适用性质强，编译电路十分简略，且相比同时期其他线性分组码的分支更易于实现的特点，所以很快得到了通信纠错的亲睐。汉明码60年代以前用于磁芯,60年代期间用于大型计算机，70年代常见于MOS存储器，80年代以后用于小型计算机，目前常用于RFID系统。汉明码是在原编码的码组信息上根据某个代数关系再附加一些码组，也就是后面我们会详细介绍的监督位。汉明码的最小码距d=3，因而只可以够检测出两个错码或纠正一个错码，由于码率k/n=(n-r)/n=1-r/n，由数学原理知道，当n无限大r无限小的时候，码率接近于1，所以汉明码是一种高效率的编码。由于汉明码简单实用的特点，问世至今仍被广泛实用。BCH码于1960年左右被发明，名称由来和汉明码一样，是由三位发明者（Bose, Chaudhuri , Hocguenghem）的名字首个字母合在一起组成，第一位和其他两位其实是各自独立完成，Bose独立完成时间较早。BCH码是目前极为优秀的线性纠错码，它创造性地解决了循环码生成的多项式和其编码相对应的能力的关系问题.1960年科学家Peterson通过研究找出了二元BCH码算法及译码问题，率先奠定了BCH码相关译码理论的根底。1966年美国数学家波利坎普提出了BCH码的迭代算法，又提升了译码速度，奠定了BCH码译码实践、应用实现的基础。第二章 纠错编码简介2.1 差错控制技术我们把由加性干扰引起的差错因其性质不同分为以下三个小类：(1） 随机信道：错码出现是相互独立的，比如正态分布的白噪声引起的干扰；(2） 突发信道: 错码出现是集中的、成串的，比如脉冲干扰，信道衰落等原因；(3） 混合信道：同时具有以上两种信道的特点的信道。 针对不同的信道差错，我们选用了特点性能各有不同的四种差错控制技术并列举如下：（1）检错重发（error detection retransmission）：通信发送端码元中加入了差错控制码元，接收端利用这些码元来检测有错码，检测到不同时，则反馈要求发送端重新发送，一直反馈到所有码元都被正确接受后停止.在见的二进制中，知道了错误的位置便可以纠正（0纠正为1,1纠正为0如果并不能知道一组接收到的哪一个码元错了，便不能纠正。而且通信设备中必须具备双向信道传送重发指令才能实现，也就是需要双传送信道，这种通信系统称为自动要求重发（Automatic Repeat reQuest，简称ARQ）系统。 ARQ 系统原理方框图如下：图2.1 ARQ系统原理方框图（2） 前向（Forward） 纠错(Error Correction）：简称F E C：通信发送端码元中加入了差错控制码元，接收端利用码元检测到有错码，同时定位有错码，将把有错码恢复。并且在二进制中只要知道了错误位置即可进行恢复。 FEC系统与ARQ系统相比，优点是时效性强。没有反向信道传送指令，也没有重复反向造成的时延。缺点是必须增加比ARQ系统更多的差错控制码元，相应设备也较为复杂。（3）反馈校验 (feedback checkout):通信发送端码元不需要加入差错控制码元。接收端接收到的码元后，直接再次转发回去。之后通信发送端将收到的接收端返回的码元和原发送码元逐一比较，比较出不同，则确定接收端收到了有错码，发送端立即进行重发。 反馈校验与ARQ系统相比，优点是原理和设备都比较简单缺点使需要双向信道，每个码元占用两次传输时间，传输效率很低。（4）检 错 删 除 （deletion):只适用于少数特定系统，因为它和检错重发原理类似，一旦在接收端发现错码，直接将错码删除，不再要求发送端重新发送。 2.2 纠错编码相关术语简介（1） 检错能力：评价不同编码方法检出有错的能力（2） 纠错能力：评价不同编码方法检出有错码位置并恢复成正确码的能力（3） 监督（check）码元：通信发送端码元加入的差错控制码元（4） 多余度：如某码组中平均每三个信息码元有两个监督码元，则该编码多余度为五分之二（5） 编码效率（code rate）：简称码率。和多余度构成百分之百，例如上个序列多余度为五分之二，则码率为五分之三（6） 冗余度：监督码元和信息码元之比，例如上个序列冗余度为1/3（7） 信息位：传输不同信息所用的码位（8） 监督位：信息位之外增加的码位（9） 码重：二进制分组码中“1”的数目，以下讨论均为二进制编码（10） 码距：又叫汉明距离，两码组对应位置数字不同的位数数目（11） 分组码：将信息码分组并为每组信息码加上相应编码方式所需的监督码的编码2.3 纠错编码基本原理 以三位码组为例，三位码共有八种可能组合： 若将三位均用作信息位，则有八种信息，若任一码组发生错误将会直接变为另一码组，接收端没有任何方法来检错纠错。 若将三位均用信息位，规定000,011,101,110四种为许用码组，其他为禁用码组，则当任一码组发生一位或者三位错误时，系统可以检测出来，因为许用码组都变成了禁用码组，但该方法无法检测二位错误。若将将三位均用信息位，规定000,111两种为许用码组，其他为禁用码组，则系统功能变为可以检测两个以下错码和纠正一位错码。 由此可见，若想具有检错，纠错能力，必须增加多余度，不可避免地减小了码率。实用编码的研究就是研究在分组码中加入何种算法来尽量提高通信系统的检错纠错能力同时尽量小地减小码率。而汉明码和BCH码就是其中的佼佼者。评价一个编码检错和纠错能力是否强大的主要指标之一就是该编码的最小码距检错：可以检测出n个错码，须满足条件：dminn+1纠错：可以纠正m个错码，须满足条件：dmin2m+1纠检结合（转换式工作方式）：可以检测出n个错码,并纠正m个错码（nm）, 须满足条件:dminn+m+12.4 纠错编码的性能及简单的纠错码讨论2.4.1 纠错编码的性能 由上述原理可知，为了尽量让接收端接收到来自发送端的正确代码，我们使用了差错控制技术，在通信发送端码元中加入了差错控制码元，这样势必会让通信序列增长，冗余度增大，若又要保持通信发送端发送信息码元的速率不变，则序列传输段的速率必须变大，这样就造成通信系统的带宽也随之增大，这样将招致通信系统中噪声功率也随之增大，信噪比随之下降。信噪比下降之后又反过来使接收端码元序列中的错码再次增多，这样就形成了一种此消彼长、不可调和的矛盾。所以在某些时候，加入纠错编码后误码率反而会升高，但是一般说来，在大部分区间里，加入纠错编码后的编码误码率会大大降低，不同的纠错编码也会带来不同程度的效果。 所以针对不同的信道选用不同的纠错编码来解决误码率问题是很值得研究的，本文主要分析的是使用汉明码和BCH码来解决相应问题的方法。 在分析汉明码和BCH码之前，我们先分析几个简单的编码作为知识储备。2.4.2 奇偶监督码 奇偶监督码（parity check）是线性分组码也包括本文分析的汉明码原理的基础。它分为奇数监督码和偶数监督码，它们原理是一样的。以奇数监督码为例，它只有一位监督位（a0），其余均为信息位，监督位来使码组中值为0的数目为偶数，这样可以表示为： an-1+ an-2 +.+a0=0 (注：式中加号代表模2运算，以下均相同)这种编码方式可以检测到所有奇数个的错码，偶数个的错码由于异或结果依然为1，所以无法检测出来。同理偶数监督码是使码组中值为1的数目为偶数，故检错能力和奇数监督码相同。2.4.3 二维奇偶监督码 二维奇偶监督码的思路来源于奇偶监督码而又是它的性能增强版本。它将若干组带奇偶监督码的码组排成行列的方阵形式，并在每一列之后加上一个监督位，这样就构成了第二维。这种行列都有奇偶监督码的方式就有一定的能力检测偶数个的错码了，只有构成行列式矩形四个角上的偶数个错码无法被检测出来。二维奇偶监督码的检错能力可以说是很强，试验证明，二维形式的奇偶监督码可以使误码率降到之前的万分之一。二维奇偶监督码的能力强在几乎可以检测出任意偶数个的错码，还可以通过行列的交叉定位来确定奇数个错码的具体位置并予以纠正。2.4.4线性分组码 从以上的编码可以看出，奇偶监督码的编码原理是利用代数式生成监督位。“这类建立在代数学理论基础上的编码通常被称为代数码，而如果代数码中的信息码和监督码是由一些线性代数方程相关的话，就成为线性代数码。”线性码中的一个代表就是汉明码。第3章 汉明码3.1 汉明码构造原理汉明码由贝尔实验室的理查德卫斯理汉明发明，因此定名为汉明码。“汉明码是线性分组码的一种，具有纠正一位错码的能力和编码效率较高的优点。为了纠正一位错码，在简易正反码中，信息位和监督位需要一样多的位数，那么编码效率就是百分之五十”1 这显然太低了，而为了进一步提高编码效率，人们将研究方向投向怎样减少监督位位数，同时还有纠正一位错码的能力，汉明码就在这样的思路下应运而生了。介绍汉明码构造原理也要用到上面提到的奇偶监督码的思路。本文以下将异或算法称为模2算法，并用“+”号来代替。奇偶监督码在解码的时候将一位监督位和所有信息位放在一起进行模2运算，结果用S表示，S被称为校正子，S只有0和1两种可能，表示无措和有错两种情况，但是无法指出具体错误的位置。我们如果再增加一位监督位，并将这个监督位也和所有信息位一起进行模2运算，又可以获得一个校正子，这样校正信息就有两位，并且出现了00，01,10,11四种情况，这样00表示无错，其他三种情况就可能有能力指出一个错误出现的三个不同位置，这样的思路进行下去，n个监督关系式下的监督位便能指示出（2n-1）个可能出错的位置。根据这样的思路，我们便可以构造出汉明码：（1）每个信息码组由k个信息位组成；（2）根据确定的代数关系，把信息码组编成一个n位（nk）二进制数字的较长组（2n）。由于每个信息码组都有k位二进制数字，故共有个可能的码字。下面举常用的典型汉明码为例进行说明：根据前面介绍的原理，若想用r个监督位来确定一位错码的n种可能位置，则需满足条件： 2r-1n 或者 2rk+r+1 （3-1） 设有（n，k）汉明码其中信息位k=4，为了纠正一位错码，那么从（3-1）右边的式子可以算出，监督位数r至少为3。我们就代入r=3的至少情况，依照等式算出汉明码长n=k+r=7，取字母来代指这7个码元，取的值代指3个符合关系式的校正子，最后和错误码元所在的位置的对应关系可以一一排写出来，如下所列：错码位置错码位置 001101 010 110 100 111 011000无错码表3.1 校正子和错误码元的对应关系由表3-1可推出校正子与信息位的监督关系式： （3-2） （3-3） （3-4）“在发送端编码时，的值由输入信号的信息码来决定，因此它们是随机的。监督位、则还要根据编码中信息码的监督关系来算出，即监督位的功能是要保证、的值为0（也就是保证所编汉明码组无错码） 1。” （3-5）上式经过左右移项求出了监督位： （3-6） 之后接收端按照（3-2）（3-3）（3-4）计算出的方式来处理收到的码组信息，再按照列表所示来判断错码具体位置的情况。这样的构造检错方法就是汉明码，例子中的（7,4）汉明码最小码距为3。 （3-7） 由线性代数知识，上式可以简记为 或者是形式 （3-8）其中的， 如H一样形式的矩阵通常叫做监督矩阵，只要我们知道了监督矩阵H，那么汉明码编码中的信息位和监督位的关系就被确定下来了。推出： （3-9）式（3-7）等价于 （3-10）Q和P互为转置，即 （3-11）上式表明，只要我们知道了信息位，按照公式，用它的行矩阵去乘可以当做是已知的矩阵Q即可求出相应监督位。 在Q的左边加上一个所用汉明码对应的k阶单位方阵（本例中为4阶），就构成了一个新的矩阵G： （3-12）我们称G为生成矩阵，生成矩阵可以生成所有该码组信息，包括，即有 （3-13） 以上即是汉明码的编码原理。3.2 汉明码解码原理 根据3.1中介绍的公式，我们只要确定了某个编码的生成矩阵G，则该编码的具体的信息码与监督码的关系就可以马上根据汉明码的编码原理推导，从而确定下来。具有这种功能的生成矩阵G叫做典型生成矩阵，G所生成的信息码组中，信息位不会改变，而监督位总是在信息位后面。 当数字信号运用汉明码编码方式编码后进入传输信道，不可避免地受到传输信道中噪声的干扰，从而生成差错，使得接收端收到错码而往往不是A码组而是差错成了某个B码组，加入汉明码作为纠错编码可以有效地降低误码率。设接收端接受到已发生错误的信息码组为n列的行矩阵码组B，即 （3-14） 那么发送码组A和接收码组B之差为（进行模2运算，即整除2留余数的运算） （3-15） E即传输过程中受干扰出现的，通常称为错码矩阵： （3-16） 例如发送信息码组A=1100001，错码矩阵E=0000001,则表明最后一位码元接受错误，接受码组B=1100000（错误矩阵又称错误图样）若用ei字母表示AB两组码组在第i位比对后的结果,即是说，若第i位的ai=bi，接受完全正确，那么ei=0，否则ei=1，表示接受出错了。将（3-15）改写成 （3-18） 考虑极端情况下,E=0的时候，表明接收码组B每个位置都没有出现错误,即完全等同于A时，仍然有存在，代入（2-8），仍然能够成立： （3-19） 接收码组B任意个位置出错，则E不为0时，将接受码组B带入（2-8）后，该式不一定成立。再次考虑极端情况，错码出现的非常多，远远大于汉明码编码所具有的检错能力的极限的时候，B可能变为另一个可用仍满足（2-8）式的码组A以致（2-19）因为错上加错而恰好成立。一般情况下，在未超过汉明码编码具有的检错极限时，（2-19）不可能成立。 在式（2-19）不成立的情况下，左右端不相等，将右端设为S,即将 （2-18）代入（2-20），推出： （3-21） 代到（2-8），推出： （3-22）推出的S与前面的S1S2S3完全对应，也就是之前介绍的校正子，通过它我们就可以确定错码出现的具体位置。汉明码的编码过程：输入一个4位的信息码，如0101的四位信息码，编码后弹出一个汉明码的编码脉冲图，编码后为0101010的典型七位（7,4）汉明码，如图2-4所示图3-1汉明码编码图汉明码解码程序：汉明码译码过程：汉明码的译码功能启用后，由于信道环境中噪声因素的不同，可能造成表中所列的三种情况的发生：信道中无噪声汉明码解码恢复了源信息码信道出现噪声干扰噪声使信息码出现误码，但误码只有一个汉明码纠正了该位误码并恢复了源信息码当信道出现噪声干扰噪声使信息码出现两个及两个以上的误码汉明码能力已经不足以纠正，所以解码后的码组依然存在错码表3.2 汉明码解码情况对应表我们选择测试汉明码译码，根据系统提示键入长度为7的汉明码0101010：第一种情形：信道不加噪的环境下，输入的信息码与经过汉明码编码后的信息码是一样的，输出结果及波形如下所示：图3.2 未加噪声解码生成的脉冲图形 第二种情形：信道出现噪声干扰的环境里，键入0101011码组（有意键入一个错码，错码在第七位），2-9为接收后最终解码的结果，我们可以看出由于信息码0101010 受到噪声干扰出现了一个误码，并且汉明码已经指出了误码位置在第7位，正是因为汉明码能够纠正一位误码，因而从解码后的接受码中顺利恢复出了原码组。图3.3 加噪声解码生成的脉冲图形 由波形得出经过汉明译码后为0101010； 第三种情形：信道出现噪声干扰的环境里，当输入0101111码组（有意键入两个错码，错码在第五位和第七位），2-10为接收后最终解码的结果：图3.4加另一噪声解码生成的脉冲图形 由波形得出经过汉明译码后为0001111； 结合图2-11我们发现解码后的汉明码码组与原码组不完全相同，原因是错码的数量已达到两位，而我们前面提到汉明码的能力是纠错一位误码和检测两位误码，已经超过此范围，汉明码对纠错失去控制，编码会自动默认为只有一个错码的，并进行纠正，导致纠错的结果依然是错码。为了达到系统能对任意给出满足条件的n,k数值的汉明码进行Matlab的仿真的效果，我们改良了程序，使它适用性更强，实现任意汉明码的编码解码，并能生成图表完成相关性能的分析（程序见附录）。Matlab中用于展示汉明码检错、纠错能力的程序结果如下所示：键入参数N=31，K=26，系统即按指令自动生成相应形式的汉明码：信息码msg = 0 1 0 1 1 1 1 0 0 0 0 0 1 1 0 0 1 0 0 1 1 1汉明码编码code = 1 0 1 0 0 1 0 1 1 1 1 0 0 0 0 1 1 0 1 0 1 1 0 0 1 0 0 1 1 1噪声码rand1 = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1噪声码和汉明码进行模二运算产生被噪声干扰的汉明码codenoise = 1 0 1 0 0 1 0 1 1 1 1 0 0 0 01 1 0 1 0 1 1 0 0 1 0 0 0 1 0汉明码解码rcv = 0 1 0 1 1 1 1 0 0 0 00 0 1 0 0 1 0 0 0 1 0程序仿真结果：图3.5 （15,11）汉明码的仿真结果由上图读出初始发送端信息码为0101111000001100100111。之后经过汉明编码加入监督位的码组变为101001011110000110101100100111。受到噪声后干扰出现差错的码组变为101001011110000110101100100010。最后通过汉明码译码后成功接受的发送端信息码是0101111000000100100010。我们由以上程序运行产生的四组坐标对比可知，前面共计15个信息码的传输排除了信道噪声的干扰，所以依然是原信息码；而后面共计11个信息码由于噪声带来的干扰出现两个错码，具体影响是两个信息位上的0差错成了1。汉明码纠正一个误码的局限，造成不能恢复回正确的源信息码的结果。键入参数N=31，K=26，系统即按指令自动生成相应形式的汉明码：msg = 0 1 1 0 1 0 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 1 0 1 11 0 1 0 1 1 0 0 0 0 1 0 0 0 1 1 0 1 1 1 0 1 0 0 1汉明码编码code =1 1 0 0 0 0 1 1 0 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 1 0 1 10 1 1 1 1 1 0 1 0 1 1 0 0 0 0 1 0 0 0 1 1 0 0 1 1 1 0 1 0 0 1噪声码rand1 = 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 00 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0噪声码和汉明码进行模二运算产生被噪声干扰的汉明码codenoise =1 1 0 0 0 0 1 1 0 1 1 0 0 1 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 1 10 1 1 1 0 1 0 1 0 1 1 0 0 0 0 1 0 0 0 1 1 0 0 1 1 1 0 1 0 0 1 汉明码解码rcv =0 1 1 0 1 1 0 0 1 1 0 1 0 1 0 1 1 0 0 0 0 0 0 0 1 11 0 1 0 1 1 0 0 0 0 1 0 0 0 1 1 0 0 1 1 1 0 1 0 0 1图3.6 参数N=31，K=26时的汉明码从图2-14中我们可以看到信息码是0 1 1 0 1 0 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 1 0 1 1 1 0 1 0 1 1 0 0 0 0 1 0 0 0 1 1 0 1 1 1 0 1 0 0 1, 然后对信息码进行汉明编码，经过汉明编码后的信息码是1 1 0 0 0 0 1 1 0 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 1 1 1 1 0 1 0 1 1 0 0 0 0 1 0 0 0 1 1 0 0 1 1 1 0 1 0 0 1 ,加入噪声后的信息码是1 1 0 0 0 0 1 1 0 1 1 0 0 1 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 1 0 1 0 1 1 0 0 0 0 1 0 0 0 1 1 0 0 1 1 1 0 1 0 0 1, 经过汉明译码后信息码是0 1 1 0 1 1 0 0 1 1 0 1 0 1 0 1 1 0 0 0 0 0 0 0 1 1 1 0 1 0 1 1 0 0 0 0 1 0 0 0 1 1 0 0 1 1 1 0 1 0 0 1。同理，我们由以上程序运行产生的四组坐标对比可知，前半部分的31个信息码遭受噪声干扰发生差错，出现了4个误码，具体错误是四个位置上信息码两个0差错成1，两个1差错成0，汉明码只能纠正一位误码的局限，造成不能恢复回正确的源信息码的结果，后半部分的31个信息码由于噪声的干扰出现了一位误码，其中的一个1差错成了0，而汉明码有纠正一位错码的能力，因此汉明码译码完成后，错码顺利恢复成了源信息码。3.3 汉明码的Matlab仿真3.3.1 Matlab简介Matlab由位于美国的数学工厂公司研发出品。该软件取名由来是英文的matrix（矩阵） 和 laboratory（工厂）两个单词各取一部分组合的合成词。中文翻译为矩阵工厂。MATLAB是一款带有商业色彩的数学功能强大软件。主要功能有：算法的开发、数据可视化、结果分析、数值运算、数学语言的交互式环境，结构上分为Matlab和Simulink两大模块，各自可独立运行而又相辅相成。3.3.2 汉明码仿真的思路 首先用随机生成的方法生成若干组作为信息码组A的二进制码,对这些数据进行汉明码编码,编码后再加入一些噪声,人为地使编码生成一定量的错误,然后再对这组有错的信息码组B进行汉明译码,最后把最先生成的数据与最后汉明码译码出的数据进行比较、分析，观察结果，考察汉明码检错纠错的能力如何。参数设置信号源采样时间传输环境仿真系统结构伯努利随机二进制生成器视情况而定差错率为5%的二进制平衡信道信号源、汉明码编码器、对称信道、汉明码译码器、输出模块表3.3 汉明码仿真参数设置 图3.7 仿真结构图3.3.3 汉明码的仿真模块分析 （1）Bernoulli Binary Generator（伯努利二进制随机数生成器）模块参数:图3.8 伯努利二进制随机数生成器模块 模块描述 模块参数名称 模块参数简介如名称所示该模块用来生成服从伯努利分布的随机二进制信息码序列模块的输出可以选择是信息矩阵亦或是选择行或列向量形式的一维数组。Probability of a zero0出现的可能性信息序列中出现0的概率Initial seed随机数产生种子各种随机数种能生成各种随机信息。Sample time抽样时间输出信息序列中每个符号持续所花费的时间。图中的模块参数表示0.02秒内生成了4个bit字节。Frame-based outputs帧格式输出勾选则输出为帧格式不勾选则只输出数据流。Samples per frame每帧抽样勾选Frame-based outputs后之后为可编辑啊否则为灰色控制输出帧中所有的抽样点数，以一帧为单位。此处表示1帧由4个bit组成。表3.4 伯努利二进制随机数生成器模块参数设置表（2）Hamming Encode（汉明码编码器）模块功能：用汉明码的编码方式对输入的信息码组进行处理。模块参数：图3.9 汉明码编码器模块（3）Binary Symmetric Channel（二进制对称信道）图3.10 二进制对称信道模块 模块描述 模块参数名称 模块参数简介仿真分析二进抽制信号的误码率添加信道噪声对输入信号进行干扰Error probability增加噪声出现的概率。表3.5 二进制对称信道模块参数设置表（4）Hamming Decode（汉明码译码器）模块描述：创建一个（n,k）汉明码码组序列。模块参数：与Hamming Encode参数保持一致即可。图3.11汉明码译码器模块（5）Error Rate Calculation（误码率计算） 图3.12 误码率计算模块 模块描述 模块参数名称 模块参数简介通过比较最初传出的信息和最后接受的信息来计算误码率模块的输出数据是码长三的向量，其中每个部分分别控制：误码率、所有错误个数、所有参加比较的位数。Computation delay控制最初比较时直接忽略抽样点数的数量Computation mode控制模块是比较全部还是输入数据Output data控制运算结果输出到工作区或者端口Receive delay控制接收后发送抽样点数为接收的第几个值表3.6 误码率计算模块参数设置表3.3.4汉明码仿真的结果与分析(1) 误码率参数设置为0.05。工作空间主要项目项目功能Simout1伯努利二进制随机数生成器1s生成2004个bit，每4个bit组成一帧数据为0的概率为0.5。Simout2进行汉明编码的模块我们采用典型的（7,4）汉明编码，编码之后，2004位信息码组经编码后变为3507位的汉明码码组。Simout3Hamming Decoder 汉明译码对通过误码率为0.05的信道的信息进行汉明译码Simout4 Error Rate Calculation 错码统计对原码和译码进行比较每帧统计一次,每次统计将前面传输的bit合在一起进行统计 如下图3-14所示：参与实验的输入信息码组共计2004位,传输错误的信息位共计38位,由此得出误码率=0.018962。表3.7 工作模块表 图3.13 伯努利随机数生成器生成的随机二进制码图3.14 汉明码编码器对伯努利随机数生成器生成码进行汉明编码图3.15 汉明码解码器模块进行解码图3.16 原码和汉明码译码对比 图3.17 Display(2) 把误码率参数再分别调整为0.0001 、0.001 、0.005 、0.01 、0.02 、0.03、 0.04 、0.06、 0.07 、0.08、 0.09 、0.1得出如表3-1所示：信道误码率0.00010.0010.0050.01比较结果信道误码率0.020.030.040.06比较结果信道误码率0.070.080.090.1比较结果表3.8 误码率参数比较结果结合(1)信道误码率为0.05的结果，可得出下图图3.18实际误码率与信道误码率之比通过以上的仿真我们可以对汉明码的检纠错能力有一个大概了解。汉明码能强效地解决信息在信道的传输过程中不可避免地受到噪声等引起的差错。仿真结果显示，当信道误码率为0.0001 、0.001 、0.005 、0.01 的时候，我们可以近似地认为汉明码完成了信息的无错传输，即汉明码的纠错能力在此范围达到最佳，为100%。随着信道误码率的增大，汉明码能力开始下降，大体实验结果列表如下：信道的误码率汉明码的检错纠错比率0.01100%0.0275%0.150%两者关系：呈明显的反比关系表3.9 信道误码率与汉明码对应关系第四章 BCH码4.1 BCH码的构造原理4.1.1循环码的运算循环码在线性分组码分支中扮演重要的角色，循环码编码设备简单，同时解码设备不复杂，满足方便实用的优点。循环码自然具有线性分组码的共同特性同时还多了循环性；循环性指的是任一码组将最左端的码元移至最右端亦或将最右端的码元移至最左端之后，变化后的码组依然是原码组中的一个。和汉明码一样，我们用典型的（7,3）循环码为例进行简单介绍。码组编号信息位监督位码组编号信息位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a01000000051001011200101116101110030101110711001014011100181110010表4.1 一种（7,3）循环码的全部码组出于简化计算的考量，我们在代数编码理论中常常把诸如此类的循环码看作是系数，放在一个一元多项式中。即：拿以上的例子来说，这种（7,3）循环码中的