通信工程毕业设计论文.docx

北京邮电大学世纪学院毕业设计(论文)题 目 AWGN信道下线性分组码 性能研究与仿真 学 号 09010125 学生姓名 宫旭瑞 专业名称 通信工程 所在系（院） 通信与信息工程系 指导教师 李殷 2013年 5月 30日45 / 54北京邮电大学世纪学院毕业设计（论文）任务书姓名宫旭瑞学号09010125专业通信工程系（院）通信与信息工程系设计（论文）题目AWGN信道下线性分组码性能研究与仿真题目分类 工程设计； 工程技术研究； 软件工程（如CAI课题等）； 专题研究；艺术设计； 其他 题目来源 自然科学基金与部、省、市级以上科研课题； 企、事业单位委托课题； 院级课题； 自拟课题 其他 指导教师（指导教师组组长及成员姓名）职 称工作单位备注李殷讲师北京邮电大学世纪学院组长毕业设计(论文)的内容和要求：信道编码是为了改善数字通信系统的传输质量。由于实际信道存在噪声或干扰，发送码元和接收码元之间可能会存在差异，这种差异被称为差错。一般来讲，信道噪声和干扰越大，码元产生差错的概率也就越大。这就要求我们探索一类能够最大限度保证信息传输的可靠性的编码方式，使得传输差错尽可能小。 从信道编码的构造方法来看，其基本思路是根据一定的规律在待发送的信息码中加入一些多余的码元，以保证传输过程的可靠性。而信道编码的任务就是构造出以最小冗余度换取最大抗干扰性能的“好码”。本课题要求：1、 研究通信信道的特性；2、 信道编码的基本原理；3、 线性分组码基本理论，循环码的性能；4、 用MATLAB仿真AWGN信道下线性分组码性能； 应完成的工作和提交材料要求： 开题报告：3000字左右； 论文的中文摘要：200-300字左右，包含关键词，并译成英文。英文摘要以250个左右实词为宜； 论文正文不少于15000字； 尽量结合课题，翻译1500汉字以上的有关技术资料或专业文献； 参考文献中，主要的文献应达到10篇以上，其中外文文献在2篇以上。主要参考文献（参考文献不少于4篇，参考文献目录按GB/T77142005的要求填写）：1邓华等. MATLAB通信仿真及应用实例详解M.北京:人民邮电出版社，2003. 2徐明远，邵玉斌。MATLAB 仿真在通信与电子工程中的应用M.西安：西安电子科技大学 出版社，2005。 3樊昌信.通信原理第6版M.北京：国防工业出版社，2006.4吴伟陵.信息处理与编码M.北京：人民邮电出版社，2005.5王新梅.纠错码原理与方法M.西安：电子科技大学出版社，1991.6McEliece R.J The Theory of Information and CodingM. Addision-Wesley Publishing Company,Inc,19977John G.Proakis.Digital Communications(4th ed.)影像版M.北京：电子工业出版社，2001.毕业设计（论文）进度计划（从正式启动时间开始，以周为单位填写）：第 1周-第 2周 课题调研、查资料、撰写开题报告第 3周 根据查询的资料确定总体设计思路，完成开题报告并上交.第 4周-第 7周 毕业设计单元部分研究,并设计出整体框架第 8周 完成论文中期检查报告第 9周-第15周 资料整理，撰写毕业论文；上交毕业设计论文，指导教师审查评阅设计报告，毕业设计答辩资格审查。学生修改毕业设计论文，准备答辩。第16周 进行毕设答辩。指导教师签字： 日期： 年 月 日教学单位意见 审核人签字： 年 月 日 北京邮电大学世纪学院毕业设计（论文）诚信声明本人声明所呈交的毕业设计（论文），题目AWGN信道下线性分组码性能研究与仿真是本人在指导教师的指导下，独立进行研究工作所取得的成果，除了文中特别加以标注和致谢中所罗列的内容以外，毕业设计（论文）中不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他教育机构的学位或证书而使用过的材料。申请学位论文与资料若有不实之处，本人承担一切相关责任。本人签名： 日期： 毕业设计（论文）使用权的说明本人完全了解北京邮电大学世纪学院有关保管、使用论文的规定，其中包括：学校有权保管、并向有关部门送交学位论文的原件与复印件；学校可以采用影印、缩印或其它复制手段复制并保存论文；学校可允许论文被查阅或借阅；学校可以学术交流为目的，复制赠送和交换学位论文；学校可以公布学位论文的全部或部分内容。本人签名： 日期： 指导教师签名： 日期： 题目 AWGN信道下线性分组码性能研究与仿真 摘要差错控制编码技术是为提高数字通信系统的可靠性而建立的一门信息处理技术，自20世纪50年代诞生以来，已经经历了50余年的发展和演变。而今，随着信息时代的到来，它也作为一项标准技术被广泛采用。鉴于线性分组码在差错控制编码领域的基础性作用，本文以Hamming码、BCH码为例，着重研究了几种典型的线性分组码在加性高斯白噪声信道下的传输性能。本文从理论出发，首先对差错控制编码的相关知识和目前广泛应用的几种线性分组码做了简单介绍，然后引入生成矩阵与校验矩阵以及生成多项式等概念，详细说明了其编译码原理。仿真测试方面，运用“矩阵实验室”Matlab/Simulink编写代码绘制出已编码和未编码两种情况下，这类码字的信噪比与误比特率关系曲线。最后，基于前面的实验结果，计算出编码增益这一重要性能指标，并通过分析数据得出结论。关键词： 差错控制编码 线性分组码 信噪比 误比特率 编码增益Title Research and Simulation of the Linear Block Codes Performance under the AWGN channelAbstract A Coding Technology of Error Control is an information processing technology to improve the reliability of digital communication systems. Since its inception in the 1950s, it has experienced 50 years of development and evolution and now it has been widely adopted as a standard technology with the arrival of the information age. Given the linear block codes fundamental role in the field of error control coding, this paper focuses on the linear block codes transmission performance which is under the additive white Gaussian noise and take Hamming code, BCH code as examples to elaborate. Starting from the theory, we have done a simple introduction of several widely used linear block code and a detailed description of the encoding and decoding principle by introducing the generator matrix and parity check matrix. Thus, we can establish a transmission system model and write code to draw out several relationship curves between the signal-to-noise ratios (SNR) and bit error rate concerning code and uncode by MATLAB. Finally, we calculate the important performance indicators “coding gain”, basing on the results of the previous experiment. Thus, the conclusion is obtained.Keywords: error control coding linear block code signal-to-noise ratio bit error rate coding gain目录1. 前言11.1 背景和意义11.2 线性分组码的发展历史与研究现状21.3 论文内容概述32. 编码理论简介42.1 差错控制系统42.2 差错控制码的分类42.3 编码信道模型52.4 汉明距离62.5 信道容量和信道编码定理72.5.1 信道容量72.5.2 信道编码定理72.6 小结83. 线性分组码的编码和译码93.1 概念和描述方法93.1.1 概念93.1.2 线性分组码与生成矩阵93.1.3 线性分组码与校验矩阵103.2 编译码过程分析103.2.1 线性分组码的编码103.2.2 线性分组码的译码113.3 Hamming码的设计与编解码过程分析113.3.1 Hamming码简介113.3.2 (7,4)汉明码的设计123.4 循环码及其描述方法153.4.1 概念153.4.2 循环码的表示163.4.3 循环码的编码173.4.4 循环码的译码183.5 循环码的设计与编译码过程分析183.5.1 (7,3)循环码的设计183.5.2 (15,5)BCH码的设计213.6 小结244. 线性分组码的传输性能研究254.1 差错控制编码的性能估计254.1.1 编码增益的提出254.1.2 线性分组码的性能限254.2 线性分组码性能的影响因素264.3 小结275. MATLAB建模仿真与结果分析285.1 通信系统仿真的意义285.2 传输模型的建立285.3 传输性能的仿真分析295.3.1 Hamming码性能的仿真与分析295.3.2 循环码性能的仿真与分析315.4 小结356. 结论366.1 结论366.2 存在的问题366.3 改进方案36致谢38参考文献39附录401. 前言1.1 背景和意义目前，中国固定和移动两大网络的规模都已位居世界第二，互联网用户也早已突破5亿。在国内信息通信制造业迅速发展的大势下，我国将加快建设新一代信息通信网络技术、完善通信系统生产体系。与此同时，随着计算机、卫星通信及高速数据网的飞速发展，数据的交换、处理和存储技术得到了广泛的应用，人们对数据传输和存储系统的可靠性提出了越来越高的要求1。然而，由于实际信道存在噪声或干扰，发送码元和接收码元之间可能会存在差异（这种差异被称为差错）。一般来讲，信道噪声和干扰越大，码元产生差错的概率也就越大。这些差错会造成接收端图像的跳跃、不连续、出现马赛克等问题。为了解决这些问题，科学家们进行着不懈的探索与研究，最终得出了这样的结论：通过信道编码这一环节，对数码流进行相应的处理，使系统具有一定的纠错能力和抗干扰能力，可极大地避免码流传送中差错的产生。信道编码的目的是改善数字通信系统的传输质量，本质是增加通信的可靠性。但信道编码会使有用的信息数据传输减少2。不同的编码方式，其编码效率有所不同，这就要求我们探索一类能够最大限度保证信息传输的可靠性的编码方式，使得传输差错尽可能小。从信道编码的构造方法来看，其基本思路是根据一定的规律在待发送的信息码中加入一些多余的码元，以保证传输过程的可靠性。而信道编码的任务就是提高数据传输效率，降低误码率，构造出以最小冗余度换取最大抗干扰性能的“好码”。人们对信道编码的研究大致着眼于两个方面：信道编码定理，从理论上解决理想编码器、译码器的存在性问题。构造性的编码方法以及这些方法能达到的性能界限。在此，我们按照信息码元和监督码元约束关系的不同将其分为分组码和卷积码，其中，线性分组码是编码学中最简单，最基本的一种码型，是编码理论的基石。本课题研究的是上述编码中“线性分组码”在通信系统中的传输性能，并且将传输信道假设为加性高斯白噪声AWGN(Additive White Gaussian Noise)信道，虽然这是一种理想化的假设，但实际上很多频谱较宽的信道（太空信道），均可以近似看作AWGN信道，因此，这一假设在理论与现实中具有重要意义。研究线性分组码的编码、译码原理及其在不同信噪比(SNR)条件下传输的误码、误符率，对优化编译码算法、提高传输效率、发现新型码字等方面的推动作用尤为显著。1.2 线性分组码的发展历史与研究现状 差错控制编码始于1948年信息论开创者Shannon发表的奠基性论文通信的数学理论。Shannon在那篇论文中给出了著名的信道编码定理，即：只要实际传输速率Rb小于信道容量C，就可以设计出一种差错控制码，使得传输过程中的差错率任意小。人们从此开始了对这一类码字的寻找和探索。首先出现的是分组码。1950年，由Hamming（汉明）描述了一类可纠正单个差错的码字Hamming码，然而，Hamming码与Shannon指出的性能极限（Shannon限）相差甚远。随后，以纠正多个差错的BCH码以及一种非二进制纠错的RS码，其中BCH码是目前应用最为广泛的码字之一，它使得人们开始研究其译码算法。而概率知识的引入加速了序列译码理论的诞生，这种理论要求引入一类不定长的非分组码，卷积码是其中最重要的一类。20世纪60年代Viterbi（维特比）译码算法的出现使卷积码得以广泛应用。大约10年之后，Goppa等人从几何观点讨论提出了分析码，利用代数曲线构造出所谓的代数几何码，也就是后来的Shannon码。到了20世纪80年代，在数字通信系统及数字存储系统中，编码器和译码器开始大量出现，这给分组编码论的研究带来了许多新的思路。1993年C.Berrou等人提出的Turbo码以及1996年Mackay和Neal对LDPC码的重新发现是纠错编码领域的又一重大突破，仿真结果显示：在AWGN信道下，当信噪比大于或等于0.7dB时，其码率离Shannon限仅差0.7dB,误比特率小于或等于10-5。如此逼近Shannon限的卓越性能使得它们已经成为当今编码领域最热门的话题3。可以说，编码领域中线性分组码的研究开始较早，取得的成果也较为丰硕。就目前来看，Turbo分组码和LDPC码是研究的重点和热点。还有最近正在研究的：低码率二进制线性分组码的盲识别、空时分组码与线性分组码相结合的MIMO系统、线性分组码与时空分组码级联的迭代译码，等等。这些都是21世纪纠错编码领域新的发展方向和重要课题。总之，纠错编码理论，包括这里的线性分组码已经历了50多年发展。在理论方面，它沿着Shannon编码定理所指引的方向不断前进；在实践方面，它随着数字技术的不断发展，也越来越广泛的应用到各种数字通信和存储系统之中。1.3 论文内容概述由于作者水平有限，这篇论文仅对目前已经发现的几种典型的线性分组码的性能做了简单研究，研究内容包括：（1）从理论上推导了线性分组码的一般性编译码原理（运用矩阵和多项式两种描述方法），然后着重以(7,4)汉明码、(7,3)循环码、(15,5)BCH码为例，详细分析了它们的编译码过程。需要说明的是，文中的编码和译码算法均采用实现较为容易的代数算法，对于能够进一步提高译码性能的其他算法，鉴于其仿真实现困难就没有采用；（2）讨论了影响线性分组码传输性能的主要因素，给出了三个常用的性能限，并以此作为编码性能估计的理论依据；（3）用MATLAB“矩阵实验室”对上述几种码字的编码和译码进行了仿真，并做出误码率和信噪比的关系曲线。对仿真结果做数据分析和误差分析，计算出编码增益等能够反映出信道编码对传输性能起改善作用的指标，又将已编码和线性分组码的理想性能限作比较，根据比较结果得出了最终的结论。2. 编码理论简介2.1 差错控制系统在数字通信中，利用差错控制码进行差错控制的方式分为三类：前向纠错FEC(Forward Error)、自动请求重发ARQ(Automatic Repeat Request)和在前两者基础上产生的混合纠错方式HEC(Hybrid Error Control) 。由于本文中用到的纠错方式只有FEC，下面重点讨论一下这种纠错方式的特点及其传输模型：编码器解码器前向信道信源用户图2-1 前向纠错方式FEC在发送端发送能够纠错的编码，接收端在收到这些码后，通过纠错译码器不仅能够自动发现错误，而且还能够自动纠正接收码字传输中的错误。这种方式的优点是不需要反馈信道，能进行一用户对多用户的同时通信，也就是说，译码实时性好，控制电路较为简单4。缺点是译码设备相对复杂，所选用的纠错码必须与信道的干扰情况相匹配，因而对信道的适应性较差。为了获得比较低的误码率，往往必须以最坏的信道条件来设计纠错码，故所需的监督码元数比信息码元多得多，这就大大降低了编码效率。值得注意的是，FEC的纠错能力是有限的，当错码数目大于纠错能力时就无能为力了，而且出现这种状况后，系统无法给出反馈，这就给收信者的判断带来不便。因此，FEC一般不用于数据通信网，而用于容错能力较强的语音、图像通信。在实际通信系统中，根据实际情况选择差错控制方式是一个比较复杂的问题。本文旨在模拟恒定参数通信等容错能力较强的通信系统传输，研究这种情形下发送码字的性能特点，因此采用了前向纠错这一差错控制方式。2.2 差错控制码的分类各种差错控制系统所用到的码，不外乎是能在译码器自动发现错误的检错码，或者不仅能发现错误而且能自动纠正错误的纠错码，或者能纠正删除错误的纠删码。本课题要研究的线性分组码就是一种纠错码。除以上划分方式，我们还可以从这样的角度对差错控制编码进行分类：（1） 按照校验元与信息元之间的关系可分为线性码和非线性码；若校验元与信息元之间呈线性关系，即可把校验规则用线性方程表示的，则称为线性码如果不存在线性关系，这是非线性码。本文中的编码均是线性码。（2） 按照对信息元的处理方法可以分为分组码与卷积码。对于信源输出序列，按k个信息元进行分组，每组设置r个校验元，形成一个长度为n=k+r的码字，该码字的校验元仅与本码字的k个信息元有关，这样按组分别进行处理的编码是分组码。如果对信源输出序列仍按k个信息元进行分组，每组r个校验元，但不同的是，这r个校验元不仅与本组k个信息元有关，还与前m组的信息元有关，称这样的码为卷积码。可以说，有多少种观察方式就会有多少种分类方法。本文主要研究上面所介绍的分组码中最特殊的一类线性分组码。2.3 编码信道模型为了研究方便，将整个通信传输系统进一步简化成下面的模型。此模型由信源、编码器、信道、译码器、信宿以及噪声源构成。信源输出已编码二进制序列；信道包括调制器、传输设备、解调器以及传输媒质，其输入一般是二进制或多进制的数字序列，输出可以是数字序列，也可以是未量化的实数序列；信宿只能是人或者计算机。模型框图如下：信源信宿纠、检错编码器编码信道纠、检错译码器噪声源图2-2 数字通信系统模型简化图编码信道有很多种，如：离散无记忆信道、二进制对称信道、二进制删除信道、离散输入连续输出信道等，接下来仅就本课题用到的离散输入连续输出信道模型做出讨论。假设信道是无记忆的，且输入符号集是一个有限、离散的集合F=ai，aj，as，而信道输出的是未量化信息，这时译码器输入可以是任意实数，即Q=(-,+)。定义这样的编码信道模型为时间离散的连续无记忆信道，它的特性由离散输入A、连续输出B以及一组条件概率密度函数来决定5。时间离散的连续无记忆信道有利于分析编译码性能的理论极限。这类信道中最重要的一种便是课题中的加性高斯白噪声AWGN信道。它存在于各种传输媒质中。加性高斯白噪声表现为信号围绕平均值的一种随机波动过程，其均值为0，方差取决于噪声功率大小。在研究通信系统的误码率与信道质量的关系时，一般先研究它在AWGN信道下的性能，然后在推广到其他信道。对AWGN信道而言，其信道输出为： b=ai+nG 式（2-1）上式中ng是一个方差为N0/2、均值为0的高斯随变量。于是输出为ai，输出为b的条件概率密度函数为：Pbai=1N0e-b-ai2/N0 式（2-2）在二进制判决情况下，如果信道输出为输入与高斯白噪声相加，则这种信道为二进制输入加性高斯白噪声信道。为了便于在AWGN信道上使用软判决，将信道输入发送码的符号表示为1或a，而不表示为0和1。但本文中为了简化译码过程，采用硬判决译码方式，假定在AWGN信道的条件下，展开对所关注的差错控制编码的理论探索。2.4 汉明距离下面介绍汉明重量、汉明距离、最小距离和距离分布等基本概念。这些都与译码性能密切相关。（1）汉明重量：一个码子c中非零码元的个数，称为汉明重量，用w(c)表示。（2）汉明距离：两个码字之间对应位不同取值的个数，叫做汉明距离，用d(x,y)表示。它具有非负性、对称性。（3）最小距离：任意两个码字之间距离的最小值，称为该码的最小汉明距离。对于分组码而言，最小距离越大，其抗干扰能力就越强。而其纠检错能力可以用下面关系表达： 如果最小距离d e+1，则该码可以检出所有不多于e个错误。 如果最小距离d 2t+1，则该码可以纠正所有不多于t个错误。 如果最小距离d e+t+1，则该码可以纠正不多于t个错误，并能检测出t+1到e个错误。2.5 信道容量和信道编码定理2.5.1 信道容量 用X表示一个随机序列，则定义X的信息熵为： H(X)=-xPxlog2P(x) 式（2-3）H(X)是X的平均自信息量，其单位为比特/符号，表示X的平均不确定度。给定一个离散信道，其输入、输出随机序列分别是X和Y。定义X相对于Y的条件熵为：IX,Y=HX-H(X|Y) 式（2-4）平均互信息量I(X，Y)表示接收到Y后平均每个符号所获得的关于X的信息量。我们定义互信息量的最大值为信道容量： C = maxP(x)I (X，Y) 式（2-5）信道容量的单位是比特/符号。他表征了信道传输信息的最大能力。实际中信道传送信息量必须小于信道容量，否则会引起错误6。2.5.2 信道编码定理信道编码定理于1948年由Shannon提出，它奠定了纠错码发展的基石。这里简要给出这一定理的基本思想：对于一个给定的有扰离散信道，设其信道容量为C，只要带传送的码率RC，则一定存在码率为R、码长为n的分组码。若采用最大似然译码，可使其译码错误概率 Pe 随码长n的增加而降至任意小，即 Pee-nEC(R) 式（2-6）式中EC(R)是误差函数或随机编码指数。三者函数关系如下图所示：0 R R1R2C1 C2 EC(R)图2-3 ECR 与R和C的关系对于一个数字编码通信系统，有上述信道编码定理可知，为满足一定的误码要求，可采用两种方法。一是增加信道容量C，从而使得ECR增加，具体方法是加大信道带宽或增大信噪比。二是在R一定时，增加分组编码长度n。但是随着n的增加，码的冗余度和编/译码设备复杂性也随之增加。研究纠错编码的意义在于：在一定码率的条件下，尽量降低误码率,以实现可靠通信；或在给定误码率下，尽量提高码率，以实现有效通信；并力求编、译码器结构简单，易于实现。Shannon的信道编码定理表明：通信系统中有效性和可靠性是一对主要矛盾，为了提高可靠性就要牺牲有效性。信道编码定理指明了为提高可靠性进行纠错编码的方向，但并未提出怎样构造纠错编码的方法7。2.6 小结本章对编码理论的基本概念和核心思想做了一个简单的介绍，为后面线性分组码的编译码原理以及性能研究做了铺垫。介绍的内容主要包括：差错控制系统、差错控制编码、并且着重引出了编码信道模型，这一模型贯穿于整个论文的始末，也是数字通信这门学科的重要模型。之后，由此给出了汉明距离的概念和与码字纠错能力与最小汉明距离的简单关系。尤其要注意的是，最小汉明距离只能从一个侧面衡量码字性能，而码字性能的影响因素有很多，汉明距离分布就是其中很重要的一点。最后，还将信道编码定理加以阐述，这一定理既是信道编码学的理论基础，又是本文研究码字性能的理论依据。下面一章要介绍的是线性分组码的编码和译码原理，它与线性分组码的性能研究密切相关。3. 线性分组码的编码和译码3.1 概念和描述方法3.1.1 概念在(n,k)分组码中，若每一个监督元都是码组中某些信息元按模二和得到的，即监督元是信息元按线性关系相加而得到的，则称为线性分组码。它是一类重要的纠错码，应用十分广泛，后面讨论的Hamming码、BCH码等都可以看作线性分组码的特例。3.1.2 线性分组码与生成矩阵线性分组码的编码过程较为简单，我们可以用多种方式来表示这一过程，在此，我们引入生成矩阵。对于线性分组码，生成矩阵是一个kn阶的矩阵。设输入的信息为U=u1,u2,uk，生成的码字为C=cn-1,cn-2,c0，则C=UG，其中，G是生成矩阵。显然，对于一定的输出序列，产生它的生成矩阵不是唯一的。我们把前k位码字与输入的k位信息完全相同的已编码称为系统码，相应的生成矩阵称为典型生成矩阵。两者的一般定义如下8：令表示一个GF(2)上的(n,k)线性分组码，则必有一个秩为k的kn阶矩阵G满足： =C | C=UG，CVk 式（3-1）其中，Vk是长度为k的GF(2)上的k维线性空间，称矩阵G为的生成矩阵。它具有两个重要性质：（1） 任意两个码字a，b之和ab。（2） 最小码距d等于码的最小重量。 对于一个GF(2)上的(n,k)线性分组码，若输入信息序列以不变形式在码字的任意k位出现，则称是系统码。例如，对于一个(n,k)系统码，其生成矩阵表示为：G = Ik P = 1 0 0 p11 p12 p1n-k0 1 0 p21 p22 p2n-k 0 0 1 pk1 pk2 pkn-k 式（3-2）其中，Ik是k阶单位矩阵，P矩阵的取值依具体情况而定。系统码和非系统码在纠检错性能以及抗干扰性能上是完全一样的。但由于系统码的表达和构造简单，因此常被人们采用。3.1.3 线性分组码与校验矩阵令表示一个GF(2)上的(n,k)线性分组码，则必有一个秩为n-k的(n-k)n阶矩阵H满足：=C|HCT=0,CVn 式（3-3）其中，Vn是长度为n的GF(2)上的n维线性空间，称矩阵H为的一个校验矩阵或者监督矩阵。而且监督矩阵和生成矩阵可以相互转化，尤其对系统矩阵来说它们满足关系：若， G = Ik P 式（3-4）则， H = PT In-k 式（3-5）上式中，Ik代表k阶单位矩阵，P矩阵的取值依具体情况而定。可以说，校验矩阵反映了已编码序列各码字之间的线性约束关系，在线性分组码的译码过程中起重要作用。3.2 编译码过程分析3.2.1 线性分组码的编码以上引入了生矩阵和校验矩阵，下面对其编码过程分析，对于任意给定的k位信息序列：U=u1,u2,uk，将他与生成矩阵（这里假设为系统矩阵）G=Ik P 相乘，可以求编码后的n个码字： cn-1,cn-2,ck,c0=u1,u2,uk 1 0 0 p11 p12 p1n-k0 1 0 p21 p22 p2n-k 0 0 1 pk1 pk2 pkn-k 式（3-6）容易看到，k个信息位经过编码之后变为n位，且前k位码字保持不变，相当于在原来的码字后面直接加了n-k个多余比特，也就是监督码元。显然，其编码效率为k/n。为了更清楚的表示编码过程，可以假设生成矩阵为非系统矩阵：G = g11g1ngk1gkn=g1gk 式（3-7）k位信息码U=u1,u2,uk的编码过程重写如下： C=UG= u1g1+u2g2+ukgk 式（3-8）对某一码字而言： cn-i= u1g1i+u2g2i+ukgki 式（3-9）其中，uk和gij 均取自二进制的0和1。这是利用生成矩阵的一般编码过程，在这一过程中编解码十分容易实现，同时又提供了强大的纠错和检错能力。3.2.2 线性分组码的译码假定系统采用一个GF(2)上的(n,k)分组码来通信，其校验矩阵为H。若发送的已编码码字为：C =cn-1,cn-2,c0，在传输过程中，信道产生的误码(错误图样)为E=en-1,en-2,e0，则接收端得到的码组为V=CE=vn-1,vn-2,v0。我们可以定义一个向量：S = VHT，并称向量S为伴随式。根据线性分组码的性质CHT=0可得 ：S=EHT 式（3-10）看到，S取值仅与错误图样E有关，所以只要求出伴随式S，便可恢复出发送码字，这提供了一种简便易行的译码思路。具体来讲，当伴随式S=0时，表明接收码字v没有错误，即：C=V。反之，接收码字V有错，且C=VE。由于H矩阵是一个n-k行n列的矩阵，所以S是一个n-k维矢量，它可以给出n-k个独立的方程，然而传输的差错E则是一个n维矢量，有n种可能取值，所以S并不能唯一确定E。对某个给定的S，E可以有2k个的解，即同一个伴随式可以得到2k个错误图样，而真正的错误图样是其中之一。在接收端，译码器的作用便是从这些候选错误矢量中确定出一个能够使平均错判概率最小的矢量。在二进制对称信道信道下，最可能的错误图样也就是汉明重量最小的接收码组，也就是非零码字最少的码组。3.3 Hamming码的设计与编解码过程分析3.3.1 Hamming码简介以上内容从原理上描述了线性分组码编码和译码。下面具体来说明在给定n、k的情况下，如何设计一种高效率的线性分组码Hamming码。Hamming码是1950年由汉明首先构造的，它是一种能纠正一位错码的效率最高的分组码。或者说，Hamming码是一种纠正单个错误的完备码，即SEC(Single Error Correcting)码。这种编码不仅具有良好的性能，而且编译码电路非常简单，易于实现。所以，从20世纪50年代问世以来，它最先被用于磁芯存储器，60年代初用于大型计算机，70年代在MOS存储器中得到应用，后来在中小型计算机中普遍采用，目前常用于RFID系统中多位错误的纠正。总之，Hamming码在提高系统可靠性方面获得了广泛的应用。Hamming码的构造必须满足关系式： 码长：n=2m-1 信息位：k=2m-1-m 监督位：n-k=m,且m3 最小距离：dmin=3 上式中，n 为码元总位数，m为监督码元位数。Hamming码能纠正单个错误，所以每一种错误图样不能相同且与伴随式一一对应。这就要求监督矩阵H中，任意两列线性无关且不为0，而一个m行的H矩阵，最多只能有2m-1列，即为Hamming码码长。Hamming码的构造原理类似于偶校验码。偶校验码是在信息码元后增加一位监督码元，使包括信息码元和监督码元的总码元中1的个数为偶数，这种关系用数学式子表示为：cn-1cn-2c0=S 式（3-11）因为在偶监督码中非零码字的个数为偶数，所以在正确传输时，必有 S = 0。这样，就可以在接收端通过计算S的值判断传输有无出错：S = 0，无错； S = 1，有错。Hamming码的编码与之类似，只是将监督码元增加到多位。也就是说，要指示n位码元中所有一位错码的情况，就必须满足条件： r个监督码元有2r种组合方式，全零用来表示无错传输，剩下2r-1种情况用来表示2r-1种错误。如果2r-1=n，则可以指出所有n位单比特错误。3.3.2 (7,4)汉明码的设计下面我们通过构造（7，4）汉明码来分析这一过程。由信息位k=4，且2r-1=n可得：r=3，现取r=3，则n=7。用c6，c5，c0表示这7个码元，用S=s1,s2,s3表示三位矫正子，也就是前面提到的伴随式9。可列出校正子的取值与错码位置的对应关系之一：表3-1校正子与错码位置对应关系s1，s2，s3错码位置000001010100011101110111无错a0a1a2a3a4a5a6根据表中关系，不难看出这种（7,4）汉明码所对应的线性约束方程如下： s1=c6c5c4c2 s2=c6c5c3c1 式（3-12） s3=c6c4c3c0 若无错，必有：0=c6c5c4c2 0=c6c5c3c1 式（3-13） 0=c6c4c3c0 将上面方程组移项整理得： c2=c6c5c4 c1=c6c5c3 式（3-14） c0=c6c4c3 写为矩阵形式有：c6,c5,c4,c3P=(c2,c1,c0)其中，P= 1 1 1 1 1 0 1 0 1 0 1 1 由此可得生成矩阵的典型形式：G=I4 P=1 0 0 0 1 1 10 1 0 0 1 1 00 0 1 0 1 0 10 0 0 1 0 1 1 式（3-15）接下来，用U表示未编码的信息码组u1,u2,u3,u4，用C表示编码后的信息码组c6,c5,c0。那么，根据关系式：C=UG，我们就可以得到编码后的7位信息序列。假设信息输入为U=1010，则有C=UG=10101 0 0 0 1 1 10 1 0 0 1 1 00 0 1 0 1 0 10 0 0 1 0 1 1=1010010 式（3-16）其他编码的对应关系如下：表3-2信息位与监督位对应关系0000000100100011010001010110011110001001101010111100110111101111000011101110110101011000111100010001001010100111信息位 监督位信息位 监督位c6,c5,c4,c3 c2,c1,c0c6 , c5, c4, c3 c2,c1,c0讨论过编码，再来看译码。将约束方程变化形式为：1 1 1 0 1 0 01 1 0 1 0 1 01 0 1 1 0 0 1c6c5c0=000 式（3-17）上式简记为：CHT=0，其中，H=1 1 1 0 1 0 01 1 0 1 0 1 01 0 1 1 0 0 1，C=c6,c5,c4,c3,c2,c1,c0 。 这里的H就是典型的监督矩阵。设接收码字为V，则在无错情况下，一定可以得到同样的关系式：VHT=0 ；否则，VHT0，此时接收码字对应的错误图样是E=CV。检错能力方面，根据误码个数与最小汉明距离的关系dmin=3e+1可知，码组至少可以检测出1个或2个比特错误。纠错能力方面，由dmin2t+1可知，它可以保证纠正一位错码。又根据前面的分析结果，错误图样满足关系：S=VHT=EHT，S是伴随式（或矫正子）。显然，E有128种可能值，而S只有8种，因此一般情况下取这16种图样中汉明重量最小的作为最优结果。假设译码器收到的码字为：0100000，那么计算可得对应的伴随式：S=VHT=0100000111110101011100001=110 式（3-18）看到伴随式S也就是监督矩阵H的第二列，即接收码字的第二位出错，可纠正错误图样为0100000，将此错误图样与接收码字相加就得到了译码结果0000000。下面是错误图样和伴随式的对应关系：表3-3错误图样和伴随式的对应关系0000000000000100000100001000000010000100000100000100000000000101001110010111011101111111伴随式 可纠正错误图样 纠错个数有了上述对应关系，将接收到的码字V与监督矩阵H相乘求出伴随式S，然后通过查表立即可得错误图样E，从而利用C=VE较为准确的译码。但是应该清楚的是，这里的译码为最大似然译码，译码结果只保证正确的概率取到最大，而非一定正确。3.4 循环码及其描述方法3.4.1 概念循环码(Cyclic Code)同样是线性分组码中重要的子类，它除了线性分组码具有的一般性质外，还具有循环性，即循环码允许集合中任意码字循环移位所得的码字仍为该码组集合中的一个码字。循环码的两个最引人瞩目的特点是：（1） 可以用反馈线性移位寄存器很容易的实现其编码和伴随式计算。（2） 由于循环码有许多固有的代数结构，从而可以找到各种简单实用的译码方法。正是由于上述特点，在目前的计算机纠错系统中所使用的线性分组码几乎都是循环码。而且近来发现的许多新型分组码都与循环码密切相关，所以无论在理论还是现实中，对它的研究都有着十分重要的意义。3.4.2 循环码的表示在Hamming码的分析中，我们曾引入生成矩阵和校验矩阵作为它的描述工具，现在，考虑到循环码自身特点，我们引入生成多项式，这样便可以运用数学语言使整个描述过程更加条理、清楚。设码长为n的循环码表示为：cn-1,cn-2,c0 ，如果把码组中各码元的取值当作多项