BCH码与汉明码的分析与仿真要点.docx

BCH码与汉明码的分析与仿真要点.docx

《BCH码与汉明码的分析与仿真要点.docx》由会员分享，可在线阅读，更多相关《BCH码与汉明码的分析与仿真要点.docx（54页珍藏版）》请在冰点文库上搜索。

BCH码与汉明码的分析与仿真要点

本科毕业论文（设计）

论文（设计）题目：

BCH码与汉明码的分析与仿真

学院：

大数据与信息工程学院

专业：

电子信息工程

班级：

电信111班

学号：

1108040212

学生姓名：

齐杨鑫

指导教师：

张盛耀

2015年06月05日

贵州大学本科毕业论文（设计）

诚信责任书

本人郑重声明：

本人所呈交的毕业论文（设计），是在导师的指导下独立进行研究所完成。

毕业论文（设计）中凡引用他人已经发表或未发表的成果、数据、观点等，均已明确注明出处。

特此声明。

论文（设计）作者签名：

日期：

BCH码与汉明码的分析与仿真

AnalysisandsimulationoftheBCHcodeandHammingcode

齐杨鑫

Qi-yangxin

目录

摘要I

AbstractII

第一章绪论1

第二章纠错编码简介3

2.1差错控制技术3

2.2纠错编码相关术语简介4

2.3纠错编码基本原理5

2.4纠错编码的性能及简单的纠错码讨论5

2.4.1纠错编码的性能5

2.4.2奇偶监督码6

2.4.3二维奇偶监督码6

2.4.4线性分组码6

第三章汉明码7

3.1汉明码构造原理7

3.2汉明码解码原理10

3.3汉明码的Matlab仿真16

3.3.1Matlab简介16

3.3.2汉明码仿真的思路16

3.3.3汉明码的仿真模块分析17

3.3.4汉明码仿真的结果与分析20

第四章BCH码24

4.1BCH码的构造原理24

4.1.1循环码的运算24

4.1.2本原BCH码构造原理25

4.2BCH码的解码原理26

4.3BCH码的仿真29

4.4BCH码的仿真结果与分析34

第五章总结与体会35

5.1总结35

5.2体会35

致谢37

参考文献38

附录一仿真程序代码39

BCH码与汉明码的分析与仿真

摘要

汉明码的功能是纠正单个错误或检测两个错误。

在大的分类中，纠错编码被分为分组码和非分组码，分组码中的线性分组码是我们主要的研究对象，汉明码就是属于线性分组码。

它具备适用性质强，编译电路十分简略，且相比同时期其他线性分组码的分支更易于实现的特点。

BCH码的功能是纠正多个错码，目前在通信领域仍然得到了广泛的运用。

属于循环码的一种，而循环码又隶属于线性分组码。

本论文针对用途广泛的BCH码和汉明码检错纠错原理以及检错纠错性能进行了分析与仿真，主要完成了三个项目的学习：

1.了解BCH码和汉明码的来由、用途、性质及其性能，掌握通信传输相关基础知识

2.深入了解BCH码和汉明码的编码原理、解码原理，加深理解相关算法和相关思想。

最终实现对任意（n,k）值的BCH码和汉明码所具备的纠错性能进行有效地分析。

3.利用MATLAB软件中内嵌的通信相关仿真模型库绘出模块图，从而进行BCH码和汉明码的建模仿真，分别对两种码进行分析讨论。

关键字：

BCH码,汉明码,编码,译码,检纠错

AnalysisandsimulationofBCHcodeandHammingcode

Abstract

Hammingcodeisawaytocorrectanerrorandautomaticallydetectcodeoflinearerrorcorrectingcode,theincreaseinanti-jammingabilityofthecommunicationsystem.Hammingcodeistheexcellentperformanceoferror-correctingcode,itscodingefficiencyisthehighestlinearblockcodescancorrectrandomerrors.BCHcodeisawaytocorrectsameerrorsandbelongstoCycliccode,alsobelongtolinearblockcode..BCHcodehasmanyspecialalgebraicproperties,thesepropertiescontributetotheerrorcorrectionabilityofthesystemasrequiredtoconstruct.

ThisthesisfocusesonthedifferentparametersundertheconditionsoftheBCHcodeandtheHammingcodeerrordetectionandcorrectioncapabilityanalysis,almostcompletethefollowingthreeaspects:

1.Anunderstandingofthesource,useoftheBCHcodeandHammingcode,classificationandcorrectionabilitybylearningthebasicsofhowitworks,,andpayattentiontohowthecommunicationsystemworks..

2.AndeepunderstandingoftheBCHcodeandtheHammingcode,aboutcoding,errorcorrectiondecodingalgorithm.Canimplementany（n,k）valueoftheBCHcodeandtheHammingcodeerrorcorrectioncapabilityfortheoreticalanalysis.

3.UsingMATLABsimulationmodellibraryofcommunicationsystemstheBCHcodeandthehammingmodelingandsimulation,toanalyzetheperformanceoftheBCHcodeandtheHammingcodeseparately.

Keywords:

BCHcode,Hammingcode,encodinganddecoding,errordetectionandcorrection

第一章绪论

通信过程中，数字信号在信道中传输会受到不可避免的干扰的影响，导致所发送的信息波形被破坏，从而使接收端接收到可能已经生成错误的信息。

出现的干扰通常有两种：

一种是乘性干扰，一种是加性干扰：

乘性干扰由衰落引起，由乘性干扰引起的多径干扰可以用均衡的方法予以纠正：

而加性干扰与乘性干扰完全不同，是由白噪声引起的，无法用均衡的方法排除，减小加性干扰的影响首先应该选择合理的调制制度，合理的解调方法，合理的发送功率，如果以上方法还不能达到相应的误码率的要求，就需要我们考虑用差错控制编码来控制了，差错控制编码也就是包括了汉明码和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）检错重发（errordetectionretransmission）：

通信发送端码元中加入了差错控制码元，接收端利用这些码元来检测有错码，检测到不同时，则反馈要求发送端重新发送，一直反馈到所有码元都被正确接受后停止.在见的二进制中，知道了错误的位置便可以纠正（0纠正为1,1纠正为0如果并不能知道一组接收到的哪一个码元错了，便不能纠正。

而且通信设备中必须具备双向信道传送重发指令才能实现，也就是需要双传送信道，这种通信系统称为自动要求重发（AutomaticRepeatreQuest，简称ARQ）系统。

ARQ系统原理方框图如下：

图2.1ARQ系统原理方框图

（2）前向（Forward）纠错（ErrorCorrection）：

简称FEC：

通信发送端码元中加入了差错控制码元，接收端利用码元检测到有错码，同时定位有错码，将把有错码恢复。

并且在二进制中只要知道了错误位置即可进行恢复。

FEC系统与ARQ系统相比，优点是时效性强。

没有反向信道传送指令，也没有重复反向造成的时延。

缺点是必须增加比ARQ系统更多的差错控制码元，相应设备也较为复杂。

（3）反馈校验（feedbackcheckout）:

通信发送端码元不需要加入差错控制码元。

接收端接收到的码元后，直接再次转发回去。

之后通信发送端将收到的接收端返回的码元和原发送码元逐一比较，比较出不同，则确定接收端收到了有错码，发送端立即进行重发。

反馈校验与ARQ系统相比，优点是原理和设备都比较简单缺点使需要双向信道，每个码元占用两次传输时间，传输效率很低。

（4）检错删除（deletion）:

只适用于少数特定系统，因为它和检错重发原理类似，一旦在接收端发现错码，直接将错码删除，不再要求发送端重新发送。

2.2纠错编码相关术语简介

（1）检错能力：

评价不同编码方法检出有错的能力

（2）纠错能力：

评价不同编码方法检出有错码位置并恢复成正确码的能力

（3）监督（check）码元：

通信发送端码元加入的差错控制码元

（4）多余度：

如某码组中平均每三个信息码元有两个监督码元，则该编码多余度为五分之二

（5）编码效率（coderate）：

简称码率。

和多余度构成百分之百，例如上个序列多余度为五分之二，则码率为五分之三

（6）冗余度：

监督码元和信息码元之比，例如上个序列冗余度为1/3

（7）信息位：

传输不同信息所用的码位

（8）监督位：

信息位之外增加的码位

（9）码重：

二进制分组码中“1”的数目，以下讨论均为二进制编码

（10）码距：

又叫汉明距离，两码组对应位置数字不同的位数数目

（11）分组码：

将信息码分组并为每组信息码加上相应编码方式所需的监督码的编码

2.3纠错编码基本原理

以三位码组为例，三位码共有八种可能组合：

若将三位均用作信息位，则有八种信息，若任一码组发生错误将会直接变为另一码组，接收端没有任何方法来检错纠错。

若将三位均用信息位，规定000,011,101,110四种为许用码组，其他为禁用码组，则当任一码组发生一位或者三位错误时，系统可以检测出来，因为许用码组都变成了禁用码组，但该方法无法检测二位错误。

若将将三位均用信息位，规定000,111两种为许用码组，其他为禁用码组，则系统功能变为可以检测两个以下错码和纠正一位错码。

由此可见，若想具有检错，纠错能力，必须增加多余度，不可避免地减小了码率。

实用编码的研究就是研究在分组码中加入何种算法来尽量提高通信系统的检错纠错能力同时尽量小地减小码率。

而汉明码和BCH码就是其中的佼佼者。

评价一个编码检错和纠错能力是否强大的主要指标之一就是该编码的最小码距

检错：

可以检测出n个错码，须满足条件：

dmin≥n+1

纠错：

可以纠正m个错码，须满足条件：

dmin≥2m+1

纠检结合（转换式工作方式）：

可以检测出n个错码,并纠正m个错码（n＞m）,须满足条件:

dmin≥n+m+1

2.4纠错编码的性能及简单的纠错码讨论

2.4.1纠错编码的性能

由上述原理可知，为了尽量让接收端接收到来自发送端的正确代码，我们使用了差错控制技术，在通信发送端码元中加入了差错控制码元，这样势必会让通信序列增长，冗余度增大，若又要保持通信发送端发送信息码元的速率不变，则序列传输段的速率必须变大，这样就造成通信系统的带宽也随之增大，这样将招致通信系统中噪声功率也随之增大，信噪比随之下降。

信噪比下降之后又反过来使接收端码元序列中的错码再次增多，这样就形成了一种此消彼长、不可调和的矛盾。

所以在某些时候，加入纠错编码后误码率反而会升高，但是一般说来，在大部分区间里，加入纠错编码后的编码误码率会大大降低，不同的纠错编码也会带来不同程度的效果。

所以针对不同的信道选用不同的纠错编码来解决误码率问题是很值得研究的，本文主要分析的是使用汉明码和BCH码来解决相应问题的方法。

在分析汉明码和BCH码之前，我们先分析几个简单的编码作为知识储备。

2.4.2奇偶监督码

奇偶监督码（paritycheck）是线性分组码也包括本文分析的汉明码原理的基础。

它分为奇数监督码和偶数监督码，它们原理是一样的。

以奇数监督码为例，它只有一位监督位（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位（n>k）二进制数字的较长组（2n）。

由于每个信息码组都有k位二进制数字，故共有

个可能的码字。

下面举常用的典型汉明码为例进行说明：

根据前面介绍的原理，若想用r个监督位来确定一位错码的n种可能位置，则需满足条件：

2r-1≥n或者2r≥k+r+1（3-1）

设有（n，k）汉明码其中信息位k=4，为了纠正一位错码，那么从（3-1）右边的式子可以算出，监督位数r至少为3。

我们就代入r=3的至少情况，依照等式算出汉明码长n=k+r=7，取字母

来代指这7个码元，取

的值代指3个符合关系式的校正子，最后

和错误码元所在的位置的对应关系可以一一排写出来，如下所列：

错码位置

错码位置

001

101

010

110

100

111

011

000

无错码

表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汉明码编码图