《BCH纠错码的性能分析与仿真实.docx》由会员分享，可在线阅读，更多相关《BCH纠错码的性能分析与仿真实.docx（58页珍藏版）》请在课桌文档上搜索。
1、毕业设计（论文）BCH纠错码的性能分析与仿真实现大学毕业设计（论文）任务书学号8学生姓名专业班级电子信息工程课题题目名称BCH纠错码的性能分析与仿真实现题目性质软件题目来源自选主要内容分析BCH码的编码和译码算法。设计该算法的软件实现方案给出BCH码的编码和译码的软件模块基木要求I.选择BCH码的迭代译码算法作为译码方法进行仿真2.选用高级语言实现算法参号资料1 .张宗橙，编著.纠错编码原理与应用.北京：电子工业出版社，2003.2 .张传生.数字通信原理.陕西：西安交通大学出版社，1995.3 .张力军，张宗橙，郑保玉，等译.美IJohnGProakis著数字通信（第四版）.北京：电子工业出
2、版社，2003.4 .王可定,计算机摸拟及其应用，东南大学出社，1997.5 .王新梅.纠错码与差错控制.北京：人民邮电出版社，1989.6 .袁东风.移动数字信道差错控制系统性能估计与计算机模拟.山东大学学报，1996,4.周次14周58周9一12周1316周1718周应完成的内容阅读材料熟悉内容设计软件实现方案软件编程软件调试总结写毕业论文指导教师：许成谦职称：教授2007年5月30日系级教学单位审批：年月曰学院:系级教学单位：通信工程系科技的发展给人们的生活带来了日新月异的变化，在这个信息时代，存储、恢复、恢复和传输数据不但对速度，而且对准确性有着越来越高的需求。通信技术的进步更是对社会
3、的文明发展与进步产生着深刻的影响。人们对高数据速率的要求推动了个人移动通信技术的迅速发展。众所周知的，在现代通信系统中，纠错码技术是实现可靠通信的基本方法；所以越来越快的传输速率要求更好的信道编码及相应的译码方式，极大改善无线通信环境下的通信效能。本文通过对信息论发展的介绍引出编码技术基础概念，重点介绍了BCH码的编码原理和译码算法。根据马尔可夫三状态模型来模拟移动通信信道长突发误码的概率模型，并根据此模型给出的参数模拟完成了BCH码的编码和译码过程。最后实现了BCH纠错码的性能分析与仿真，结果表明，用马尔可夫三状态模型表示移动信道具有较高的精度，BCH编码具有较好的纠错性能。关键词移动信道；
4、纠错码；BCH码；模拟仿真；乘同余法AbstractScientificdevelopmentbringsgreatchangetoourdailylife,inthisageofinformation,thereisincreasingneednotonlyforspeed,butalsoforaccuracyinthestorage,retrieval,andtransmissionofdate,andtheadvancementofcommunicationtechniquealsogiveprofoundinfluencetoourcivilization.Peoplesdemands
5、forthehigh-speeddatatransmissionpromotethedevelopmentofPCS.Asweallknown,inthemoderncommunicationsystem,error-correctioncodeisafundamentaltechniquewhichcanguaranteesreliablecommunication.Thelifetransformationrateisbecamemoreandmorefast,somorebetterchannelcodinganddecodingwaysareneeded,soastoimproveex
6、tremelycommunicationefficiencyandquality.InthispaperWeintroducedtheinformationtheorythendrawsoutthefundamentalconceptofthecodingtechnology,andintroducedtheBCHcodingprincipleandthedecodingalgorithmwithemphasis.TheMarkovmodelthreestatesareusedfortheprobabilitymodelinthedigitalmobilecommunicationchanne
7、lwithlongbursterror.Bymeansofasimplifiedmethodandbyuseoftheerror-codesgeneratebytheparametersofthemodel.Atlast,wecompletethesimulationandanalysisofBCHerrorcode,theanalogueresultindicatedthat,withtheMarkovmodelthreestatesexpressthemotionchannelhasahigherprecision,andtheBCHcodehasthebettererrorcorrect
8、ionperformance.KeywordsMobileradiochannelErrorcodeBCHcodeAnalogemulationMultiplicativeCongruentialmethod摘要IAbstractII第1章绪论11.1 课题背景11.2 信息理论的发展11.3 研究的内容和安排2第2章纠错码的基础理论32.1 编码技术的产生32.1.1 纠错码的分类32.1.2 信道错误种类42.1.3 差错控制系统分类42.1.4 差错控制编码的基本原理72.1.5 差错控制编码的分类82.2 纠错编码的基本原理与分析方法82.2.1 信道编码公式的研究82.2.2 纠错码
9、概念的分析102.3 常用检错码与纠错码112.3.1 等重码112.3.2 群计数和水平计数112.3.3 海明码112.3.4 卷积码122.4 检错码与纠错码122.4.1 纠错码122.4.2 检错码132.4.3 检错码与纠错码的关系142.5 本章小结14第3章BCH纠错码的编码和译码原理153.1 BCH码的特点153.1.1 BCH码的生成多项式153.1.2 BCH码的几种常见码153.2 BCH码的编码原理163.3 BCH码的结构及BCH码的一般编译方法163.3.1 BCH码的结构173.3.2 多元BCH码173.3.3 BCH码的一般编译方法173.3.4 BCH码
10、的新型译码方法183.3.5 BCH码的硬判决译码方法193.3.6 BCH码的Chase译码算法203.4 本章小结20第4章BCH纠错码的仿真实现214.1 伪随机数的选取214.1.1 引言214.2 产生随机数的一般方法234.2.1 利用随机数表234.2.2 利用数学方法244.2.3 利用物理随机数发生器254.2.4 乘同余法产生随机数254.2.5 混同余法产生随机数264.3 BCH码的仿真及分析274.4 本章小结29结论31参考文献33附录135附录239附录343附录451致谢63第1章绪论1.1 课题背景近些年，随着科学技术尤其是信息技术的飞速发展使人类跨入了高度发
11、达的信息化时代，在政治、军事、经济等各个领域，信息的重要性不言而喻，因而有关信息理论的研究将越来越受到关注。信息论理论基础的建立，一般来说开始于香农研究通信系统所取得的成就。信息在早期的定义由奈奎斯特和哈特利在20世纪20年代提出，1924年奈奎斯特解释了信号带宽和信息速率之间的关系；1928年哈特利最早研究了通信系统传输信息的能力，给出了信息度量的方法；香农在1941年至1944年对通信系统和密码进行深入研究，并用概率论的方法研究通信系统,揭示了通信系统传递的对象就是信息，并对信息给以科学的定量描述，提出了信息病的概念同时指出通信系统的主要问题是在噪声下如何有效而可靠地传送信息；而实现这一目
12、标的主要方法是编码。香农也因此成为信息论的奠基人。20世纪50年代信息论在学术界引起了巨大反响。20世纪60年代信道编码技术把代数方法引入到纠错码的研究，使分组码技术的发展到了高峰，找到了大量可纠正多个错误的码，提出了序列译码和Viterbi译码方法，并被美国卫星通信系统采用，这同时也使香农理论成为真正意义上的科学理论。1982年UngerboeckG.提出了将信道编码和调制结合在一起的网格编码调制方法，这种方法无需增大带宽和功率，以增加设备的复杂度换取编码增益，受到了广泛关注，在目前的通信系统中占据统治地位。香农在1948年提出了无失真信源编码定理，也给出了简单的编码方法。1.2 信息理论的
13、发展近30多年来，信息领域的研究日益活跃，大量的有关信息论文被发表，使多用户信息论的理论日趋完整。信息在传输中的误码率逐渐降低，甚至在某些领域已经达到了几乎可以忽略不计的程度。但是，在信息传输过程中，误差总是存在的，尽管是微乎其微的，在高科技领域内，信息起着关键性作用，差之毫厘，失之千里，不可有丝毫的忽视。因此，虽然信息传输过程中误码率很低，但是，为了保证信息的精确性，译码过程中的检错和纠错仍然是必不可少的一个部分。而且现代社会中无线通信更是对信道的可靠性提出了越来越高的要求；尤其在进入21世纪后，中国的无线移动通信事业正在以前所未有的速度向前发展，在国家“863”计划的大力支持下，以自主创新
14、为主要目标的“第四代”移动通信技术正在如火如荼地展开。下一代系统最主要的特征是高速带宽的传输系统。为此系统的设计应着眼于更大的容量、更高的传输效率、更可靠的传输质量和性能。因此，使用信道纠错编码来提高通信的可靠性越来越为人们所关注。信道模型的研究也将为纠错编码的计算机模型，纠错方案的选择及其优劣比较、性能估计提供重要的依据。1.3 研究的内容和安排随着电子技术和现代计算机技术的迅猛发展，移动通信已从原来的低容量、小区域、模拟式和单一功能向高容量、大区域、数字式和多功能的方向发展。由于通信业务的不断扩展，移动频带越来越拥挤，人为干扰和环境干扰越来越严重；另外人们对通信质量的要求也越来越高；但是移
15、动信道其本身的环境是极其恶劣的，多路径效应造成的快衰落和地形、阴影效应造成的慢衰落产生了移动信道的长突发误码形式。它的这种特性使通常使用的混合或随机模型不切实际。而且，对于移动通信来说，恶劣的信道特性是不可回避的问题，要在这样的传播条件下保持可以接收的传输质量，就必须采用各种技术措施来抵消衰落的不利影响，这就是各种抗衰落技术，它包括分集、扩频/跳频、均衡、交织和纠错编码等技术叫BeH纠错码是线性循环码的重要子类，由于其编码算法简单，译码速度快，硬件实现复杂度低、经济实惠等优点被广泛使用，经由BCH纠错码处理的器件多具有体积小，速度快，性能稳定并可以自动提高系统的抗干扰能力；因此BCH的出现为通
16、信系统设计者在纠错能力、码长和码率的选择和控制上提供了很大的灵活性，BCH纠错码的出现极大改善了通信效能。本文根据部分文献，提出建立在马尔可夫模型，它比其他的模型能更精确地反映出突发错误的特性”主要内容的安排将从以下几个方面展开：第1章从信息理论的发展及意义出发说明了BCH纠错码的主要优点并对论文进行了安排；第2章从编码技术的产生以及纠错码和差错控制系统的分类出发分析了纠错码的基础理论并了解纠错码的基本原理；第3章引出了BCH纠错码的基本概念并分析了BCH纠错码的编码原理和译码方法等；第4章从随机数的产生出发实现了纠错码编码，通过译码实现了BCH码的模拟仿真，并进行了性能分析。完成了本次设计。
17、第2章纠错码的基础理论2.1 编码技术的产生科学技术的突飞猛进使得现代社会不断地向信息化发展。因此，信息成为我们现实生活中重要的一部分，然而信息是一种微观的事物，它是一种抽象的内涵，必须依附某种有形的载体才能传输，这种载体就叫做信号。模拟信号的每一瞬间都包含无限信息量，无法使用“码”这种有限载体；数字信号则包含有限信息量，于是就产生了编码技术。信道编码是以信息在信道上的正确传输为目标的编码，可分为两个层次：一是如何正确接收载有信息的信号；二是如何避免少量差错信号对信息内容的影响。由此我们可以看出前一层次主要涉及通信，主要目标是为了消除直流分量，或是为了改造信号频谱，以适应信道特性，或是为了便于
18、在信号流中提取时钟频率，或是为了数字信号的透明传输。还有部分响应系统用来压缩占用带宽、抑制码间干扰等，这个层次的码，比如曼彻斯特码、AMI码、HDB3码、nBmB码和部分响应系统中的相关编码。而第二层次的编码即差错控制码包括各种形式的纠错码、检错码等2.1.1 纠错码的分类从不同角度，不同侧面看问题，可以对纠错码做出不同的归类。(1)从功能角度讲，差错码分为两类：一类用于发现差错，叫做检错码;另一类要求能自动纠正错误，叫纠错码。纠错码与检错码在理论上没有本质的区别只是应用场合不同，而侧重的性能参数也不同。(2)按照对信息序列的处理方法，有分组码和卷积码两种。分组码(blockCode)将信息序
19、列分割为k位成一组独立编解码，分组间无关。卷积码(convolutioncode)也先将信息序列分组，不同的是编解码运算不仅与本组信息有关，而且还与前面若干组有关。(3)按照码元与原始信息位的关系，分为线性码与非线性码。线性码的所有码元均是原始信息元的线性组合，编码器不带反馈电路。非线性码的码元，并不都是信息元的线性组合，可能还与前面已编的码元有关，编码器可能含反馈回路。由于非线性码的分析比较困难，早期实用的纠错码多为线性码，但当今发现的很多码恰恰是非线性码。(4)按照适用差错类型，分成纠随机差错码和纠突发差错码两种，也有介于中间的纠随机突发差错码。纠随机差错码用于随机差错信道，其纠错能力用码
20、组或码段内允许的独立差错的个数来衡量。纠突发差错码针对突发差错而设计，其纠错能力主要用可纠突发差错的最大长度来衡量。(5)按照构码理论来分，有代数码、几何码、算术码、组合码等代数码的理论基础是近世代数，几何码的理论基础是投影几何，算术码的理论基础是数论、高等算术，组合码的理论基础是排列组合和数论，用到同余、拉丁方阵、阿达玛矩阵等数学方法。除了上述分类外，有多少观察问题的角度，就有多少分类方法。比如,按每个码元的取值，可以分为二进制码与多进制码；按码字之间的关系有循环码和非循环码之分。不同的分类方法只是从不同的角度抓住码的某一特性进行归类而己，并不能说明某个码的全部特性。比如某线性码可能同时又是
21、分组码、循环码、纠突发错误码、代数码、二进码。2.1.2 信道错误种类传输信道中常见的错误有以下三种：(1)随机错误,信息在传输过程中错误的出现是随机的，一般而言，错误出现的位置是随机分布的，即各个码元是否发生错误是相互独立，毫无关联的，通常不是成片地出现错误，不是有规律的发生；通常，这种情况一般是由信道的加性随机噪声引起的，因此，一般将具有此特性的信道称为随机信道。(2)突发错误,信息在传输过程中错误的出现是一连串的，通常在一个突发错误持续时间内，开头和末尾的码元总是错的，中间的某些码元可能是错的，也可能是对的，但错误的码元数目相对比较多，如在移动通信中，信号在某一段时间内发生衰落，造成一串
22、差错；汽车发动时，电火花干扰造成的错误；光盘上的一条划痕等等，这样的信道我们称之为突发信道。(3)混合错误,在信息传输过程中既有突发错误，又有随机错误发生的信道我们称之为混合信道。2.1.3 差错控制系统分类1948年，ShannOn在其奠基性的论文通信的数学原理中，把通信系统分为信源、编码器、信道、译码器和信宿五个部分(如图21所示)。其中，编译码器又被相应地分成了信源编/译码器和信道编/译码器。Shannon在此基础上，又以新颖的科学观念和统计的数学方法系统地阐明了通信系统中信息的概念、信息的度量方法和编码变换的重要规律，提出并证明了三个重要的编码定理，成功地建立了基于统计的信息论。图2-
23、1数字通信系统框图在如图2.1所示的数字通信系统中，运用纠/检错码进行差错控制的基本方式大致分成三类；前向纠错(FEC)、反馈重发(ARQ)和混合纠错(HEC)O(1)前向纠错(forwarderrorcorrection,FEC)发送端信息经纠错编码后实行传送，而接收端通过纠错译码自动纠正传递过程中的差错。所谓“前向”，指纠错过程在接收端独立进行，不存在差错信息的反馈。这种方式的优点是无需反向信道，时延小，实时性好，既适用于点对点通信，又适用于点对多点的组播或者广播式通信。缺点是译码设备比较复杂，所选用的纠错码必须与信道特性相匹配，为了获得较好的纠错性能必须插入较多的校验元而导致误码率降低。
24、最关键的一点还在于：前向纠错的纠错能力是有限的，即当差错数大于纠错能力时，接收端发生错误编译却意识不到错译的发生，受信者无法判断译出的码是纠错后的正确码还是误判了的码。是否适合采用前向纠错取决于纠错码的纠错能力、差错特性、误码率以及信息内容的容忍度。数据通信网要求误码率很小，一般不采用前向纠错方案；话音、图像通信对实时性要求高而容错能力强，基本上都是采用前向纠错。随着编码理论和大规摸集成电路的应用，性能优良的实用编译码方法不断出现而实现成本不断降低，前向纠错的应用己从话音、图像扩展到计算机存储系统、磁盘、光盘、和激光唱机等。反馈重发(automaticrepeatrequest,ARQ)发送端
25、发送检错码，如循环冗余校验(CRC)码，接受端通过检测接收码是否符合编码规律来判断该码是否存在差错。若判定码组有错，则通过反向信道通知发端重发该码，如此反复，直到接收端认为正确接收为止。围绕如何重发、由谁重发等，ARQ系统可采取不同的重发策略。比如等待式系统的接收端，以单帧、单码组为单位给发送端反馈ACK或NAK信息,以决定是发下一条还是重发上一条信息。连续式系统则给帧或码字编上顺序号后连接发送，接收端对所有帧的正确与否，按顺序号给出反馈回音。重发可以在通信网各交换节点间逐一发生，也可以像高速通信网那样将反馈重发的任务转移给网络边缘的终端设备去完成。ARQ的优点是编译码设备简单，在同样冗余度下
26、检错码的检错能力比纠错码的纠错能力要高的多。通过ARQ可大大降低整个系统的误码率，早期最成功的例子是分组交换数据网，它用10误码率的PCM物理信道构建出符合数据通信要求的10一9误码率的数据网。目前ARQ方式已广泛应用于其他数据通信网，如计算机局域网、分组交换网、7号信令网等。ARQ的缺点是需要一条反馈信道来传输回音，并要求发送和接收端装备有大容量的存储器以及复杂的控制设备。ARQ是一种自适应系统，由于反馈重发的次数与信道干扰密切相关，当信道误码率很高时，重发将过于频繁而使效率大大降低甚至使系统阻塞。此外，被传输信息的连贯性和实时性也较差。特别是光线通信出现后,信道的高速度使节点的ARQ处理成
27、为真正的瓶颈。因此从帧中继、ATM到MPLS,现代高速网络不再采用反馈重发，而仅在节点处作检错运算。如果分组(或帧、包、信元等)有错，则网络简单地将它们丢弃，而把协商重发的任务移交给终端去处理。(3)混合纠错(hybriderrorcorrection,HEC)此法是前向纠错和反馈纠错的结合，发送端发送的码兼有检错和纠错两种能力，接收端译码器收到码字后首先检验错误情况。如果差错不超过码的纠错能力，则自动进行纠错。如果判断码的差错数量已超过码的纠错能力，则接收端通过反馈信道给发端一个要求重发的信息。HEC方式的性能及优缺点介于FEC和ARQ之间，误码率低，设备不很复杂，实时性和连贯性比较好，在移
28、动通信和卫星通信中得到了应用。除了以上三种基本方式外，还有狭义信息反馈系统(IRQ)。这种方式是接收端把接收到的信息原封不动地通过反馈信道送回发送端，发送端比较发送的与反馈回来的信息，从而发现错误，并且把传错的消息再次发送，最后达到使接收端正确接收信息的目的。为了便于比较，把上述四种方式用图22所示的框图表示。图中有阴影的方框表示在端检出错误。FEC收发ARQ纠错码收发HEC(4)图2-2差错控制的基本方式2.1.4 差错控制编码的基本原理在此我们以重复编码为例来简单地阐述为什么差错控制编码在相同的信噪比情况下会获得更好的系统性能。假设我们发送的信息0、1（等概率出现）采用2PSK方式，我们知
29、道最佳接收的系统比特误码率为：*仙揭（2-1）现假设与=10一3（即平均接收100O个中错一个）如果我们将信息0编码成（X）,信息1编码成11,采用上述系统，则在接收端可以作以下判断：如果发送的是（X）,而收到的是01或10,此时我们知道发生了差错，要求发送端重新传输，直到传送正确为止，只有当收到11时，我们才错误地认为当前发送的是1,因此在这种情况下发生译码错误的概率是0.55二；同理，如果发送的是11,只有收到00时，才可能发生错误译码，因此在这种情况下发生译码错误的概率也是0.5匕。所以采用00、11编码的系统比特误码率为0.5B,即1(60系统的性能将明显提e高。再如，在上例中，将0、
30、1采用00000、IlIIl编码，在接收端我们用如下的译码方法，每收到5个比特译码一次，采用大数判决，即5个比特中0的个数大于1的个数时则译码成0,反之译码成1。如果不采用ARQ方式，那么这种编码方式就变成了纠错编码。由于传输错误，当接收端收到IloOO,10100,10010,10001,01100,01010,01001,00110,00101,00011中的任何一种码元时，都可以自动纠正成OOOOOo2.1.5 差错控制编码的分类差错控制编码根据功能的不同，可分为：检错码、纠错码、纠删码(兼检码、纠错)。差错控制编码根据信息位和校验位的关系为：线性码和非线性码。差错控制编码根据信息码元和
31、监督码元的约束关系，可分为：分组码和卷积码。分组码是将k个信息比特编成n个比特的码字(nk),共有2个码字，所以个码字组成一个分组码，传输时前、后码字之间毫无关系。卷积码也是将k个信息比特编成n个比特，每个比特不但与本码的其它比特关联，而且与前面m个码段的比特位也相互关联，该码的约束长度为(m+1)n比特。2.2 纠错编码的基本原理与分析方法纠错编码的基本原理源于两种基本思路：第一种思路的源点是信道编码定理的基本公式，而另一种思路则起源于两个基本概念。两种思路只是从两个角度看待同一个问题，措施必是殊途同归，结论也应该上吻合的。2.2.1信道编码公式的研究从信道编码的定理公式：P,Ve一幅出发不
32、强调物理意义，只是从数学角度分析如何使不等式左边的P,减小。Pc是复指数函数，从数值看欲减小匕可走增大码长N或增大可靠性函数E(R)两条路。而想增大E(R)又有加大信道容量C或减小码率(传信率)R两条路。对于同样的码率R,信道容量大的，其可靠性函数E(R)也大；若信道容量C不变，码率减小时其可靠性函数E(R)增大。鉴于上面的分析，可采取以下措施减小差错概率P,。增大信道容量C根据香农公式，信道容量C与带宽W、信号平均功率匕,和噪声谱密度NO有关。为此，可以采取以下措施：第一，扩展带宽。比如开发新的宽带媒体，有线通信从明线(150kHz)、对称电缆(600kHz)、同轴电缆(IGHZ)到光纤(2
33、5THZ)；无线由中波、短波、超短波到毫米波、微米波。又比如采取信道均衡措施，如加感、时/频域的自适应均衡器。第二，加大功率。如提高发送功率、提高天线增益，将无方向的漫射改为方向性强的波束或点波束和分集接收等。第三，降低噪声。如采用低噪声器件，及采用滤波、屏蔽、接地、低温运行等技术。(2)减小码率R对于二进制(N,K)分组码，码率R=KNbit/符号；对于Q进制(N,K)分组码(K个Q元符号编成N个Q元符号)，码率=KlbQ/No所以降低码率的方法有：第一，Q,N不变而减小K,这意味着降低信息源速率，每秒少传一些信息。第二，Q,K不变而增大N,这意味着提高符号速率(波特率)，占用更大带宽。第三
34、，N,K不变而减小K,这意味着减小信道的输入输出符号集，在发送功率固定时提高信号间的区分度，从而提高可靠性。(3)增大码长N保持信道容量C和码率R,K/N之比不变，加大码长N并没有增加信道容量的冗余度，这是随机编码的特点：随着N增大，矢量空间元素X以指数量级增大，从统计角度而言码字间距离也将加大，从而可靠性提高。另外，码长N越大，世纪差错概率就越能符合统计规律。比如投掷一个硬币记录，其正面向上的比例，理论之应是0.5,如果比例将到0.4以下或0.6以上,就算差错，投掷10次就做比例统计较之投掷100万次再做比例统计，其差错概率要大得多。可以断言，投掷100万次而正面向上比例在0.4,0.6区间
35、之外的概率几乎是零，增加码长N的作用与增加投掷次数的作用类似。增加码长N带来好处的同时也需要付出代价，那就是N越大编解码算法就越复杂，编解码器也越昂贵。所以虽然香农早在1948年就已指出增大N的途径，但20世纪70年代由于器件水平不允许编解码器做得太复杂，实用的纠错码主要还是靠牺牲功率、带宽效率来取得可靠性。到20世纪80年代后，随着VLSl的发展，编解码器可以做得越来越复杂，很多编解码算法可以在ASIC或数字信号处理专用芯片DSP上实现.因此,码长允许设计的很长。当前，通过增加码长N来提高可靠性已成为纠错编码的主要途径之一，它本质上是以设备的复杂度换取可靠性，从这个意义上说妨碍数字通信系统性
36、能提高的真正限制因素是设备的复杂性。2.2.2纠错码概念的分析从概念上分析纠错码的基本原理，可以把纠错能力的获取归结为两条：一条是利用冗余度，另一条是噪声均化（随机化、概率化产。冗余度就是在信息流中插入冗余比特，这些冗余比特与信息比特之间存在着特定的相关性。这样，即使在传输过程中个别信息受损，也可以利用相关性从其他未受损的冗余比特中推测出受损比特的原貌，保证了信息的可靠性。举例来说，如果用2bit表示4种意义，则无论如何也不能发现差错，因为如果有一信息01误成（X）,则根本无法判断这是在传输过程中由01误成00,还是原本发送的就是00。但是如果用3bit来表示4种意义，就有可能发现差错，因为3
37、bit的8种组合能表示8种意义，用它代表4种意义，还剩4种冗余组合，如果传输差错使收到的3bit组合落入4种冗余组合之一，就可断言一定有差错位。至于加多少冗余、加什么样的相关性最好，这正是纠错编码技术所要解决的问题，但必须有冗余，这是纠错编码的基础。为了传输这些冗余位，必然动用冗余的资源。这些资源可以是：第一，时间比如一位重复发几次，或一段消息重复发几遍，或根据接收端的反馈重发受损信息组，像ARQautomaticrepeatrequest系统那样。第二，频带插入冗余位后传输效率下降，若要保持有用信息的速率不变，最直接的方法就是增大符号传递速率（波特率），结果就占用了更大的带宽。比如采用二进制
38、（8分组码而保持频带利用率等于每赫兹每秒1个符号不变，则编码后符号速率增大一倍，所占带宽也增大一倍。第三，功率采用多进制符号，比如用一个8进制ASK符号代替一个4进制ASK符号来传送2bit信息，可腾出位置另传1冗余位。但为了维持信号集各点之间的距离不变，8进制ASK符号的平均功率肯定比4进制ASK符号的平均功率要大，这就是动用冗余的功率资源来传输冗余比特。第四，设备复杂度加大码长N,采用网格编码调制(TCM),是在功率、带宽受限信道中实施纠错编码的有效方法；其代价是算法复杂度的提高，需动用设备资源。噪声均化就是让差错随机化，以便更符合编码定理的条件从而得到符合编码定理的结果。噪声均化的基本思
39、想是设法将危害较大的，较为集中的噪声干扰分摊开来，使不可恢复的信息损伤最小。这是因为噪声干扰的危害大小不仅与噪声总量有关，而且与其分布有关。举例来说，二进制(7,4)汉明码能纠一个差错，假设噪声在14码元(两码字)上产生2个差错，那么差错的不同分布将产生不同的后果。如果2个差错集中在前7码元(同一码字)上，该码字将出错。如果差错分散在前、后两个码字，每码字承受一个差错，则每码字差错的个数都没有超出起纠错能力范围，这两个码字将全部正确解码。由此可见：集中的噪声干扰(称之为突发差错)的危害甚于分散的噪声干扰(称之为随机差错)。噪声均化正是将差错均匀分摊给各个码字，达到提高总体差错控制能力的目的。2
40、.3 常用检错码与纠错码2.3.1 等重码等重码又叫恒比码，其特点是编码集中每个编码组中“1”和“0”的个数保持恒定比例。该码能检测奇数个差错，故在实际中常运用反馈重发方式使差错明显减少，因此又称为数字保护码。这种码除了“1”错成“0”和“0”错成“1”成对性错误外，其他错误均能发现，故它有很强的检错能力。2.3.2 群计数和水平计数所谓计数就是统计要传送字符信息中“1”的个数,将此计数值作为校验位附加在该字符信息之后传递,例如：一个7单位字符为I(X)Io11,该字符中，“1”的个数为4,则传送的码字为1001011100。这种码的检错能力很强，除了“0”错成“1”和“1”错成“0”成对性错
41、误和信息位与校验位的对偶性错误外，其他形式的错误均能检出。2.3.3 海明码海明码是由海明实现的一位纠错码，其码字位是按顺序编号的，即从左向右为1,2,n凡为2的嘉数位(即1,2,4,16,32)均为校验位，其它位为信息位。码字位中的校验位取值是使一些位的集合（包括校验位在内）的奇偶性为奇（或为偶），一位代码位可加入若干个奇偶性的计算中。为了知道第k位信息位是由哪些校验位加以校验的，只要将k表示为累数和，例如:15=1+2+4+8,27=1+2+8+16,即该位信息位就由展开式中这些校验位加以校验。当一个码被接收端所接收时，将接收器的计数器置为0,然后检查每个校验位k,看它是否有正确值。如不正
42、确就把校验码位号k加到计数器中，当计数器的结果不为0时，表示该码字有错，该计数器的值就是错误的信息位号，只要把该位的值取反，就可达到纠错的目的。例如：发现第1,2,4,8位有错，就知道第15位信息位有错，将第15位的数值取反，即可纠错。海明码只能纠正一位错，但也可用它来纠突发错。其方法是：将K个码字排列成一个矩阵，每个码字占一行。为纠正突发错，发送时从左到右按列进行，一次一列，一列K位发送完再发送第二列，直到最后一列。到达接收端再按列重新构造此矩阵。如果发生了长度为K（一连错K位）的突发错，则矩阵中K个码字中的每一个都有一位错，而海明码能纠正一位错，所以整块数据就能得到纠正。这种方法是用Kl个
43、校验位来纠正KN个数据块所产生的一个长度不大于K位的突发错2.3.4 卷积码以上提到码的都是分组码，它们的特点是将输入的信息序列分割成长度为k的组，在编码时，将一组k个信息序列变成长度为n的码字序列。在一个码字中，n-k个校验码元仅本组的k个信息码元有关，而与其它组的信息码元无关。译码时，也仅从本码字码元内提取有关的译码信息，而与其它各组无关。卷积码则与分组码截然不同。它先是将信息序列分成长度为k的一个个小组，长度为n的每个子组码字（称为子码）包括k个信息码元,n-k个校验码元（也称监督码元）。这n-k个校验码元，不仅与本组的k个信息码元有关，而且也与前面若干个子组的信息码元有关。本组的信息码
44、元不仅决定本组的校验码元，而且也参与决定以后若干组的校验码元。译码时，不但从该时刻收到的码组中提取译码信息，而且还利用以后若干时刻内所收到的码组来提取有关信息。2.4 检错码与纠错码2.4.1 纠错码在了解纠错码之前，先了解一个基本概念：海明距离。通常一帧包括m个数据（报文）位和r个冗余位或者校验位。设整个长度为n（即n=mr）,则此长度为n的单元通常被称作n位码字。给出的任意两个码字，如IoooloOl和IOllOooL可以确定它们有多少个对应位不同。在此例中有3位不同。为了确定有多少位不同，只须对两个码字做异或运算，然后计算结果中1的个数。两个码字中不同位的个数，称为海明距离(Hammin
45、gDistance)0其重要性在于，假如两个码字具有海明距离d,则需要d个位差错才能将其中一个码字转化成另一个。一种编码的校验和纠错能力取决于它的海明距离。为了检测出d比特错，需要使用d+1的编码；因为d个单比特错决不可能将一个有效的码字转变成另一个有效的码字。当接收方看到无效的码字，它就能明白发生传输错误。同样，为了纠正d比特错，必须使用距离为2d+l的编码，这是因为有效码字的距离远到即使发生d个变化，这个发生了变化的码字仍然比其它码字都接近原始码字。作为纠错码的一个简单例子，考虑如下只有4个有效码字的代码：0000000000000001IllU1111100000W1111111111这
46、种代码的距离为5,也就是说,它能纠正双比特错误。假如码字OOOoooOlIl到达后，接收方知道原始码字应该为(X)O(M)Ill11。但是，如果出现了三位错，而将OOOoOOOoOO变成(XX)(XXX)111,则差错将不能正确纠正。2.4.2 检错码检错码有时也用于数据传输也例如，当信道为单工方式，无法要求重传的情况下，大多数采用检错码与重传的方式。假设信道的出错是孤立的信道的误码率为1(6,每位数据块的大小为100位。为IO(X)位的数据块纠错，需要10个校验位；1兆的数据位将需要I(XXX)个校验位。若只需要检测一个数据块的一位错误，每块一个奇偶位就够了。每传送I(M)O个数据块就需要额
47、外传送一个数据块。错误检错+重传方式的整个开销，仅仅是每兆数据只有2001位，而海明码为10000位。假若在一个块上只加一个奇偶位,那么块的长突发错误的检测率就会很糟糕能够检测到差错的概率只有0.5,这是难以接受的。改进的措施可以采取将每个数据块组成n位宽k行高的长方形矩阵进行发送。对每一列的奇偶位分别进行计算，附加在矩阵上，作为矩阵的最后一行，然后按行进行发送。当块到达后，接收方检测所有的奇偶位。如果任何一个出错了，就需要重新传送整个块。这种方法能够检测到单个程度为n的突发错误，因为每一列只有一位改变了。然而如果第一位变反，最后一位变反，且所有其它位都正确，则长度为n+1的突发差错将不会被检
48、测到。假如一个块被一个长的突发差错或者短的突发差错所破坏，n列中的每一列的奇偶值碰巧正确的概率为0.5,那么这个出错块被接受的概率不应该是2。2.4.3 检错码与纠错码的关系下面以（7,4）线形分组码的构筑方法来说明检错码是如何过渡到纠错码的。设某信息经信源编码后成为16个由0和1组成的4位代码组信息，即16=2,k=4o为了纠正一个错误，r=2不行，因为n=4+2=6,校验矩阵只有2行6歹I。但是，为使伴随式能定出错误的位置，要求6列各不相同。位r=2显然不够用。若r=3,WJ23=8,全零列是不能用的（因为伴随式等于零已对应于无错），剩下的非零7列可用来构成一致校验矩阵。例如可取：如当消息为IOlO时:V=IOlON?p3（2-3）JoIo
