1、 北京邮电大学世纪学院北京邮电大学世纪学院 毕业设计毕业设计( (论文论文) ) 题 目 AWGNAWGN 信道下线性分组码信道下线性分组码 性能研究与仿真性能研究与仿真 学 号 09010125 学生姓名 宫旭瑞 专业名称 通信工程 所在系（院） 通信与信息工程系 指导教师 李殷 2013 年 5 月 30 日 北京邮电大学世纪学院毕业设计（论文）任务书北京邮电大学世纪学院毕业设计（论文）任务书 姓名 宫旭瑞 学号 09010125 专业 通信工程 系（院） 通信与信息工 程系 设计（论文）题目 AWGN 信道下线性分组码性能研究与仿真 题目分类 工程设计； 工程技术研究； 软件工程（如 C
2、AI 课题等）； 专题研究；艺术设 计； 其他 题目来源 自然科学基金与部、省、市级以上科研课题； 企、事业单位委托课题； 院级课题； 自拟课题 其他 指导教师 （指导教师组 组长及成员姓名） 职 称 工作单位 备注 李殷 讲师 北京邮电大学世纪学院 组长 毕业设计(论文)的内容和要求： 信道编码是为了改善数字通信系统的传输质量。由于实际信道存在噪声或干扰，发送码 元和接收码元之间可能会存在差异，这种差异被称为差错。一般来讲，信道噪声和干扰越大， 码元产生差错的概率也就越大。这就要求我们探索一类能够最大限度保证信息传输的可靠性 的编码方式，使得传输差错尽可能小。 从信道编码的构造方法来看，其基
3、本思路是根据一定的规律在待发送的信息码中加入一 些多余的码元，以保证传输过程的可靠性。而信道编码的任务就是构造出以最小冗余度换取 最大抗干扰性能的“好码” 。 本课题要求： 1、研究通信信道的特性； 2、信道编码的基本原理； 3、线性分组码基本理论，循环码的性能； 4、用 MATLAB 仿真 AWGN 信道下线性分组码性能； 应完成的工作和提交材料要求： 开题报告：3000 字左右； 论文的中文摘要：200-300 字左右，包含关键词，并译成英文。英文摘要以 250 个左 右实词为宜； 论文正文不少于 15000 字； 尽量结合课题，翻译 1500 汉字以上的有关技术资料或专业文献； 参考文献
4、中，主要 的文献应达到 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 Theo
5、ry of Information and CodingM. Addision-Wesley Publishing Company,Inc,1997 7John G.Proakis.Digital Communications(4 th ed.)影像版M.北京：电子工业出版社， 2001. 毕业设计（论文）进度计划（从正式启动时间开始，以周为单位填写） ： 第 1 周-第 2 周 课题调研、查资料、撰写开题报告 第 3 周 根据查询的资料确定总体设计思路，完成开题报告并上交. 第 4 周-第 7 周 毕业设计单元部分研究,并设计出整体框架 第 8 周 完成论文中期检查报告 第 9 周-第 15
6、 周 资料整理，撰写毕业论文；上交毕业设计论文，指导教师审查评阅设 计报告，毕业设计答辩资格审查。学生修改毕业设计论文，准备答辩。 第 16 周 进行毕设答辩。 指导教师签字： 日期： 年 月 日 教学单 位意见 审核人签字： 年 月 日 北京邮电大学世纪学院北京邮电大学世纪学院 毕业设计（论文）诚信声明毕业设计（论文）诚信声明 本人声明所呈交的毕业设计（论文） ，题目AWGN 信道下线性分组码性能研 究与仿真是本人在指导教师的指导下，独立进行研究工作所取得的成果，除了文 中特别加以标注和致谢中所罗列的内容以外，毕业设计（论文）中不包含其他人已 经发表或撰写过的研究成果，也不包含为获得北京邮电
7、大学或其他教育机构的学位 或证书而使用过的材料。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 日期： 毕业设计（论文）使用权的说明毕业设计（论文）使用权的说明 本人完全了解北京邮电大学世纪学院有关保管、使用论文的规定，其中包括： 学校有权保管、并向有关部门送交学位论文的原件与复印件；学校可以采用影 印、缩印或其它复制手段复制并保存论文；学校可允许论文被查阅或借阅；学 校可以学术交流为目的，复制赠送和交换学位论文；学校可以公布学位论文的全 部或部分内容。 本人签名： 日期： 指导教师签名： 日期： I 题目题目 AWGNAWGN 信道下线性分组码性能研究与仿真信道下线性分
8、组码性能研究与仿真 摘要 差错控制编码技术是为提高数字通信系统的可靠性而建立的一门信息处理技 术，自 20 世纪 50 年代诞生以来，已经经历了 50 余年的发展和演变。而今，随着 信息时代的到来，它也作为一项标准技术被广泛采用。鉴于线性分组码在差错控制 编码领域的基础性作用，本文以 Hamming 码、BCH 码为例，着重研究了几种典型 的线性分组码在加性高斯白噪声信道下的传输性能。 本文从理论出发，首先对差错控制编码的相关知识和目前广泛应用的几种线性 分组码做了简单介绍，然后引入生成矩阵与校验矩阵以及生成多项式等概念，详细 说明了其编译码原理。仿真测试方面，运用“矩阵实验室”Matlab/
9、Simulink 编写代 码绘制出已编码和未编码两种情况下，这类码字的信噪比与误比特率关系曲线。最 后，基于前面的实验结果，计算出编码增益这一重要性能指标，并通过分析数据得 出结论。 关键词： 差错控制编码 线性分组码 信噪比 误比特率 编码增益 II Title Title R Researchesearch and and S Simulation imulation of of the the L Linearinear B Blocklock C Codeodes s P Performance undererformance under the AWGNthe AWGN channe
10、lchannel Abstract 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 tech
11、nology 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 el
12、aborate. 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 c
13、ode 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.
14、Keywords: error control coding linear block code signal-to-noise ratio bit error rate coding gain III 目录 1. 前言 . 1 1.1 背景和意义 . 1 1.2 线性分组码的发展历史与研究现状 . 2 1.3 论文内容概述 . 3 2. 编码理论简介 . 4 2.1 差错控制系统 . 4 2.2 差错控制码的分类 . 4 2.3 编码信道模型 . 5 2.4 汉明距离 . 6 2.5 信道容量和信道编码定理 . 7 2.5.1 信道容量 . 7 2.5.2 信道编码定理 . 7 2.6 小结
15、 . 8 3. 线性分组码的编码和译码 . 9 3.1 概念和描述方法 . 9 3.1.1 概念 . 9 3.1.2 线性分组码与生成矩阵 . 9 3.1.3 线性分组码与校验矩阵 10 3.2 编译码过程分析 10 3.2.1 线性分组码的编码 10 3.2.2 线性分组码的译码 11 3.3 Hamming 码的设计与编解码过程分析 11 3.3.1 Hamming 码简介 11 3.3.2 (7,4)汉明码的设计 . 12 3.4 循环码及其描述方法 15 3.4.1 概念 15 3.4.2 循环码的表示 16 3.4.3 循环码的编码 17 IV 3.4.4 循环码的译码 18 3.5
16、 循环码的设计与编译码过程分析 18 3.5.1 (7,3)循环码的设计 . 18 3.5.2 (15,5)BCH 码的设计 21 3.6 小结 24 4. 线性分组码的传输性能研究 25 4.1 差错控制编码的性能估计 25 4.1.1 编码增益的提出 25 4.1.2 线性分组码的性能限 25 4.2 线性分组码性能的影响因素 26 4.3 小结 27 5. MATLAB 建模仿真与结果分析 28 5.1 通信系统仿真的意义 28 5.2 传输模型的建立 28 5.3 传输性能的仿真分析 29 5.3.1 Hamming 码性能的仿真与分析 29 5.3.2 循环码性能的仿真与分析 31
17、5.4 小结 35 6. 结论 36 6.1 结论 36 6.2 存在的问题 36 6.3 改进方案 36 致谢 . 38 参考文献 . 39 附录 . 40 北京邮电大学世纪学院毕业设计（论文） 1 1. 前言 1.1 背景和意义 目前，中国固定和移动两大网络的规模都已位居世界第二，互联网用户也早已 突破 5 亿。在国内信息通信制造业迅速发展的大势下，我国将加快建设新一代信息 通信网络技术、完善通信系统生产体系。与此同时，随着计算机、卫星通信及高速 数据网的飞速发展，数据的交换、处理和存储技术得到了广泛的应用，人们对数据 传输和存储系统的可靠性提出了越来越高的要求 1。 然而，由于实际信道存
18、在噪声或干扰，发送码元和接收码元之间可能会存在差 异（这种差异被称为差错） 。一般来讲，信道噪声和干扰越大，码元产生差错的概率 也就越大。这些差错会造成接收端图像的跳跃、不连续、出现马赛克等问题。为了 解决这些问题，科学家们进行着不懈的探索与研究，最终得出了这样的结论：通过 信道编码这一环节，对数码流进行相应的处理，使系统具有一定的纠错能力和抗干 扰能力，可极大地避免码流传送中差错的产生。 信道编码的目的是改善数字通信系统的传输质量，本质是增加通信的可靠性。 但信道编码会使有用的信息数据传输减少 2。 不同的编码方式， 其编码效率有所不同， 这就要求我们探索一类能够最大限度保证信息传输的可靠性
19、的编码方式，使得传输 差错尽可能小。从信道编码的构造方法来看，其基本思路是根据一定的规律在待发 送的信息码中加入一些多余的码元，以保证传输过程的可靠性。而信道编码的任务 就是提高数据传输效率，降低误码率，构造出以最小冗余度换取最大抗干扰性能的 “好码”。 人们对信道编码的研究大致着眼于两个方面：信道编码定理，从理论上解决 理想编码器、译码器的存在性问题。构造性的编码方法以及这些方法能达到的性 能界限。在此，我们按照信息码元和监督码元约束关系的不同将其分为分组码和卷 积码，其中，线性分组码是编码学中最简单，最基本的一种码型，是编码理论的基 石。 本课题研究的是上述编码中“线性分组码”在通信系统中
20、的传输性能，并且将 传输信道假设为加性高斯白噪声 AWGN(Additive White Gaussian Noise)信道， 虽然这 是一种理想化的假设，但实际上很多频谱较宽的信道（太空信道） ，均可以近似看作 AWGN 信道，因此，这一假设在理论与现实中具有重要意义。研究线性分组码的编 北京邮电大学世纪学院毕业设计（论文） 2 码、译码原理及其在不同信噪比(SNR)条件下传输的误码、误符率，对优化编译码算 法、提高传输效率、发现新型码字等方面的推动作用尤为显著。 1.2 线性分组码的发展历史与研究现状 差错控制编码始于 1948 年信息论开创者 Shannon 发表的奠基性论文通信的数 学
21、理论 。Shannon 在那篇论文中给出了著名的信道编码定理，即：只要实际传输速 率Rb小于信道容量 C，就可以设计出一种差错控制码，使得传输过程中的差错率任 意小。人们从此开始了对这一类码字的寻找和探索。 首先出现的是分组码。1950 年，由 Hamming（汉明）描述了一类可纠正单个差 错的码字Hamming 码， 然而， Hamming 码与 Shannon 指出的性能极限 （Shannon 限）相差甚远。随后，以纠正多个差错的 BCH 码以及一种非二进制纠错的 RS 码， 其中 BCH 码是目前应用最为广泛的码字之一，它使得人们开始研究其译码算法。而 概率知识的引入加速了序列译码理论的
22、诞生，这种理论要求引入一类不定长的非分 组码，卷积码是其中最重要的一类。20 世纪 60 年代 Viterbi（维特比）译码算法的出 现使卷积码得以广泛应用。大约 10 年之后，Goppa 等人从几何观点讨论提出了分析 码，利用代数曲线构造出所谓的代数几何码，也就是后来的 Shannon 码。到了 20 世 纪 80 年代，在数字通信系统及数字存储系统中，编码器和译码器开始大量出现，这 给分组编码论的研究带来了许多新的思路。1993 年 C.Berrou 等人提出的 Turbo 码以 及 1996 年 Mackay 和 Neal 对 LDPC 码的重新发现是纠错编码领域的又一重大突破， 仿真结
23、果显示： 在 AWGN 信道下， 当信噪比大于或等于 0.7dB 时， 其码率离 Shannon 限仅差 0.7dB,误比特率小于或等于10;5。如此逼近 Shannon 限的卓越性能使得它们 已经成为当今编码领域最热门的话题 3。 可以说，编码领域中线性分组码的研究开始较早，取得的成果也较为丰硕。就 目前来看，Turbo 分组码和 LDPC 码是研究的重点和热点。还有最近正在研究的：低 码率二进制线性分组码的盲识别、空时分组码与线性分组码相结合的 MIMO 系统、 线性分组码与时空分组码级联的迭代译码，等等。这些都是 21 世纪纠错编码领域新 的发展方向和重要课题。总之，纠错编码理论，包括这
24、里的线性分组码已经历了 50 多年发展。在理论方面，它沿着 Shannon 编码定理所指引的方向不断前进；在实践 方面，它随着数字技术的不断发展，也越来越广泛的应用到各种数字通信和存储系 统之中。 北京邮电大学世纪学院毕业设计（论文） 3 1.3 论文内容概述 由于作者水平有限，这篇论文仅对目前已经发现的几种典型的线性分组码的性 能做了简单研究，研究内容包括： （1）从理论上推导了线性分组码的一般性编译码 原理（运用矩阵和多项式两种描述方法） ，然后着重以(7,4)汉明码、(7,3)循环码、 (15,5)BCH 码为例，详细分析了它们的编译码过程。需要说明的是，文中的编码和译 码算法均采用实现
25、较为容易的代数算法，对于能够进一步提高译码性能的其他算法， 鉴于其仿真实现困难就没有采用；（2） 讨论了影响线性分组码传输性能的主要因素， 给出了三个常用的性能限， 并以此作为编码性能估计的理论依据； （3） 用 MATLAB “矩 阵实验室”对上述几种码字的编码和译码进行了仿真，并做出误码率和信噪比的关 系曲线。对仿真结果做数据分析和误差分析，计算出编码增益等能够反映出信道编 码对传输性能起改善作用的指标，又将已编码和线性分组码的理想性能限作比较， 根据比较结果得出了最终的结论。 北京邮电大学世纪学院毕业设计（论文） 4 2. 编码理论简介 2.1 差错控制系统 在数字通信中，利用差错控制码
26、进行差错控制的方式分为三类：前向纠错 FEC(Forward Error)、自动请求重发 ARQ(Automatic Repeat Request)和在前两者基础 上产生的混合纠错方式 HEC(Hybrid Error Control) 。由于本文中用到的纠错方式只 有 FEC，下面重点讨论一下这种纠错方式的特点及其传输模型： 图 2-1 前向纠错方式 FEC 在发送端发送能够纠错的编码，接收端在收到这些码后，通过纠错译码器 不仅能够自动发现错误，而且还能够自动纠正接收码字传输中的错误。这种方式的 优点是不需要反馈信道，能进行一用户对多用户的同时通信，也就是说，译码实时 性好，控制电路较为简单
27、 4。缺点是译码设备相对复杂，所选用的纠错码必须与信道 的干扰情况相匹配，因而对信道的适应性较差。为了获得比较低的误码率，往往必 须以最坏的信道条件来设计纠错码，故所需的监督码元数比信息码元多得多，这就 大大降低了编码效率。 值得注意的是，FEC 的纠错能力是有限的，当错码数目大于纠错能力时就无能 为力了， 而且出现这种状况后， 系统无法给出反馈， 这就给收信者的判断带来不便。 因此，FEC 一般不用于数据通信网，而用于容错能力较强的语音、图像通信。 在实际通信系统中，根据实际情况选择差错控制方式是一个比较复杂的问题。 本文旨在模拟恒定参数通信等容错能力较强的通信系统传输，研究这种情形下发送
28、码字的性能特点，因此采用了前向纠错这一差错控制方式。 2.2 差错控制码的分类 各种差错控制系统所用到的码，不外乎是能在译码器自动发现错误的检错码， 或者不仅能发现错误而且能自动纠正错误的纠错码，或者能纠正删除错误的纠删码。 本课题要研究的线性分组码就是一种纠错码。除以上划分方式，我们还可以从这样 的角度对差错控制编码进行分类： （1） 按照校验元与信息元之间的关系可分为线性码和非线性码；若校验元与 编码器 解码器 前向信道 信源 用户 北京邮电大学世纪学院毕业设计（论文） 5 信息元之间呈线性关系，即可把校验规则用线性方程表示的，则称为线性码如果不 存在线性关系，这是非线性码。本文中的编码均
29、是线性码。 （2） 按照对信息元的处理方法可以分为分组码与卷积码。 对于信源输出序列， 按 k 个信息元进行分组，每组设置 r 个校验元，形成一个长度为n = k + r的码字，该 码字的校验元仅与本码字的 k 个信息元有关，这样按组分别进行处理的编码是分组 码。如果对信源输出序列仍按 k 个信息元进行分组，每组 r 个校验元，但不同的是， 这 r 个校验元不仅与本组 k 个信息元有关，还与前 m 组的信息元有关，称这样的码 为卷积码。 可以说，有多少种观察方式就会有多少种分类方法。本文主要研究上面所介绍 的分组码中最特殊的一类线性分组码。 2.3 编码信道模型 为了研究方便， 将整个通信传输
30、系统进一步简化成下面的模型。 此模型由信源、 编码器、信道、译码器、信宿以及噪声源构成。信源输出已编码二进制序列；信道 包括调制器、传输设备、解调器以及传输媒质，其输入一般是二进制或多进制的数 字序列，输出可以是数字序列，也可以是未量化的实数序列；信宿只能是人或者计 算机。模型框图如下： 图 2-2 数字通信系统模型简化图 编码信道有很多种，如：离散无记忆信道、二进制对称信道、二进制删除信道、 离散输入连续输出信道等，接下来仅就本课题用到的离散输入连续输出信道模型做 出讨论。 假 设 信 道 是 无 记 忆 的 ， 且 输 入 符 号 集 是 一 个 有 限 、 离 散 的 集 合 F=ai，
31、aj，as，而信道输出的是未量化信息，这时译码器输入可以是任意实 数，即 Q=(,+)。定义这样的编码信道模型为时间离散的连续无记忆信道，它的 特性由离散输入 A、连续输出 B 以及一组条件概率密度函数来决定 5。时间离散的 信源 信宿 纠、检错 编码器 编码信道 纠、检错 译码器 噪声源 北京邮电大学世纪学院毕业设计（论文） 6 连续无记忆信道有利于分析编译码性能的理论极限。 这类信道中最重要的一种便是课题中的加性高斯白噪声 AWGN 信道。它存在于 各种传输媒质中。加性高斯白噪声表现为信号围绕平均值的一种随机波动过程，其 均值为 0， 方差取决于噪声功率大小。 在研究通信系统的误码率与信道
32、质量的关系时， 一般先研究它在 AWGN 信道下的性能，然后在推广到其他信道。 对 AWGN 信道而言，其信道输出为： b=ai+nG 式（2-1） 上式中ng是一个方差为N0/2、均值为 0 的高斯随变量。于是输出为ai，输出为 b 的 条件概率密度函数为： P(b|ai) = 1 N0 e;(b;ai) 2/N0 式（2-2） 在二进制判决情况下，如果信道输出为输入与高斯白噪声相加，则这种信道为 二进制输入加性高斯白噪声信道。为了便于在 AWGN 信道上使用软判决，将信道输 入发送码的符号表示为1或a，而不表示为 0 和 1。但本文中为了简化译码过程， 采用硬判决译码方式，假定在 AWGN
33、 信道的条件下，展开对所关注的差错控制编码 的理论探索。 2.4 汉明距离 下面介绍汉明重量、汉明距离、最小距离和距离分布等基本概念。这些都与译 码性能密切相关。 （1）汉明重量：一个码子 c 中非零码元的个数，称为汉明重量，用 w(c)表示。 （2）汉明距离：两个码字之间对应位不同取值的个数，叫做汉明距离，用 d(x,y) 表示。它具有非负性、对称性。 （3）最小距离：任意两个码字之间距离的最小值，称为该码的最小汉明距离。 对于分组码而言，最小距离越大，其抗干扰能力就越强。而其纠检错能力可以用下 面关系表达： 如果最小距离 d e+1，则该码可以检出所有不多于 e 个错误。 如果最小距离 d
34、 2t+1，则该码可以纠正所有不多于 t 个错误。 如果最小距离 d e+t+1， 则该码可以纠正不多于 t 个错误， 并能检测出 t+1 到 e 个错误。 北京邮电大学世纪学院毕业设计（论文） 7 2.5 信道容量和信道编码定理 2.5.1 信道容量 用 X 表示一个随机序列，则定义 X 的信息熵为： H(X) = P(x)log2P(x) x 式（2-3） H(X)是 X 的平均自信息量，其单位为比特/符号，表示 X 的平均不确定度。给定一个 离散信道，其输入、输出随机序列分别是 X 和 Y。定义 X 相对于 Y 的条件熵为： I(X,Y) = H(X) H(X|Y) 式（2-4） 平均互
35、信息量 I(X，Y)表示接收到 Y 后平均每个符号所获得的关于 X 的信息量。我 们定义互信息量的最大值为信道容量： C = maxP(x)I (X，Y) 式（2-5） 信道容量的单位是比特/符号。他表征了信道传输信息的最大能力。实际中信道 传送信息量必须小于信道容量，否则会引起错误 6。 2.5.2 信道编码定理 信道编码定理于 1948 年由 Shannon 提出，它奠定了纠错码发展的基石。这里简 要给出这一定理的基本思想：对于一个给定的有扰离散信道，设其信道容量为 C， 只要带传送的码率 RC，则一定存在码率为 R、码长为 n 的分组码。若采用最大似 然译码，可使其译码错误概率 Pe 随
36、码长 n 的增加而降至任意小，即 Pe e;nEC(R) 式（2-6） 式中EC(R)是误差函数或随机编码指数。三者函数关系如下图所示： EC(R) 图 2-3 EC(R) 与 R 和 C 的关系 对于一个数字编码通信系统，有上述信道编码定理可知，为满足一定的误码要求， 0 R R1 R2 C1 C2 北京邮电大学世纪学院毕业设计（论文） 8 可采用两种方法。一是增加信道容量 C，从而使得EC(R)增加，具体方法是加大信道 带宽或增大信噪比。二是在 R 一定时，增加分组编码长度 n。但是随着 n 的增加， 码的冗余度和编/译码设备复杂性也随之增加。 研究纠错编码的意义在于：在一定码率的条件下，
37、尽量降低误码率,以实现可靠 通信；或在给定误码率下，尽量提高码率，以实现有效通信；并力求编、译码器结 构简单，易于实现。Shannon 的信道编码定理表明：通信系统中有效性和可靠性是一 对主要矛盾，为了提高可靠性就要牺牲有效性。信道编码定理指明了为提高可靠性 进行纠错编码的方向，但并未提出怎样构造纠错编码的方法 7。 2.6 小结 本章对编码理论的基本概念和核心思想做了一个简单的介绍，为后面线性分组 码的编译码原理以及性能研究做了铺垫。介绍的内容主要包括：差错控制系统、差 错控制编码、并且着重引出了编码信道模型，这一模型贯穿于整个论文的始末，也 是数字通信这门学科的重要模型。之后，由此给出了汉
38、明距离的概念和与码字纠错 能力与最小汉明距离的简单关系。尤其要注意的是，最小汉明距离只能从一个侧面 衡量码字性能，而码字性能的影响因素有很多，汉明距离分布就是其中很重要的一 点。最后，还将信道编码定理加以阐述，这一定理既是信道编码学的理论基础，又 是本文研究码字性能的理论依据。下面一章要介绍的是线性分组码的编码和译码原 理，它与线性分组码的性能研究密切相关。 北京邮电大学世纪学院毕业设计（论文） 9 3. 线性分组码的编码和译码 3.1 概念和描述方法 3.1.1 概念 在(n,k)分组码中，若每一个监督元都是码组中某些信息元按模二和得到的，即 监督元是信息元按线性关系相加而得到的，则称为线性
39、分组码。它是一类重要的纠 错码，应用十分广泛，后面讨论的 Hamming 码、BCH 码等都可以看作线性分组码的 特例。 3.1.2 线性分组码与生成矩阵 线性分组码的编码过程较为简单， 我们可以用多种方式来表示这一过程， 在此， 我们引入生成矩阵。对于线性分组码，生成矩阵是一个k n阶的矩阵。设输入的信 息为U = ,u1,u2,uk-，生成的码字为C = ,cn;1,cn;2,c0-，则C = U G，其中，G 是生成矩阵。显然，对于一定的输出序列，产生它的生成矩阵不是唯一的。我们把 前 k 位码字与输入的 k 位信息完全相同的已编码称为系统码，相应的生成矩阵称为 典型生成矩阵。两者的一般
40、定义如下 8： 令表示一个GF(2)上的(n,k)线性分组码，则必有一个秩为 k 的k n阶矩阵 G 满足： = *C | C = U G，C Vk+ 式（3-1） 其中，Vk是长度为 k 的GF(2)上的 k 维线性空间，称矩阵 G 为的生成矩阵。它具有 两个重要性质： （1）任意两个码字 a，b 之和a b 。 （2）最小码距 d 等于码的最小重量。 对于一个GF(2)上的(n,k)线性分组码，若输入信息序列以不变形式在码字的任 意 k 位出现，则称是系统码。例如，对于一个(n,k)系统码，其生成矩阵表示为： G = ,Ik P- = 1 0 0 p11 p12 p1n;k 0 1 0 p
41、21 p22 p2n;k 0 0 1 pk1 pk2 pkn;k 式（3-2） 北京邮电大学世纪学院毕业设计（论文） 10 其中，Ik是 k 阶单位矩阵，P 矩阵的取值依具体情况而定。系统码和非系统码在 纠检错性能以及抗干扰性能上是完全一样的。但由于系统码的表达和构造简单，因 此常被人们采用。 3.1.3 线性分组码与校验矩阵 令表示一个GF(2)上的(n,k)线性分组码， 则必有一个秩为n k的(n k) n阶 矩阵 H 满足： = *C|H CT= 0,C Vn+ 式（3-3） 其中，Vn是长度为 n 的GF(2)上的 n 维线性空间，称矩阵 H 为的一个校验矩阵或者 监督矩阵。而且监督矩
42、阵和生成矩阵可以相互转化，尤其对系统矩阵来说它们满足 关系： 若， 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 个码字： ,c n;1
43、,cn;2,ck,c0- = ,u1,u2,uk- 1 0 0 p11 p12 p1n;k 0 1 0 p21 p22 p2n;k 0 0 1 pk1 pk2 pkn;k 式（3-6） 容易看到，k 个信息位经过编码之后变为 n 位，且前 k 位码字保持不变，相当于在原 来的码字后面直接加了n k个多余比特， 也就是监督码元。 显然， 其编码效率为k/n。 为了更清楚的表示编码过程，可以假设生成矩阵为非系统矩阵： G = g11g1n gk1gkn = g1 gk 式（3-7） 北京邮电大学世纪学院毕业设计（论文） 11 k 位信息码U = ,u1,u2,uk-的编码过程重写如下： C = U
44、 G = 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,
45、v0-。我们 可以定义一个向量：S = V HT，并称向量 S 为伴随式。根据线性分组码的性质 C HT=0 可得 ： S = E HT 式（3-10） 看到，S 取值仅与错误图样 E 有关，所以只要求出伴随式 S，便可恢复出发送码字， 这提供了一种简便易行的译码思路。具体来讲，当伴随式 S=0 时，表明接收码字 v 没有错误，即：C = V。反之，接收码字 V 有错，且C = V E。 由于 H 矩阵是一个n k行 n 列的矩阵， 所以 S 是一个n k维矢量， 它可以给出 n k个独立的方程，然而传输的差错 E 则是一个 n 维矢量，有 n 种可能取值，所以 S 并不能唯一确定 E。对某个
46、给定的 S，E 可以有2k个的解，即同一个伴随式可以得 到2k个错误图样，而真正的错误图样是其中之一。在接收端，译码器的作用便是从 这些候选错误矢量中确定出一个能够使平均错判概率最小的矢量。在二进制对称信 道信道下，最可能的错误图样也就是汉明重量最小的接收码组，也就是非零码字最 少的码组。 3.3 Hamming 码的设计与编解码过程分析 3.3.1 Hamming 码简介 以上内容从原理上描述了线性分组码编码和译码。下面具体来说明在给定 n、k 的情况下，如何设计一种高效率的线性分组码Hamming 码。 Hamming 码是 1950 年由汉明首先构造的， 它是一种能纠正一位错码的效率最高
47、 北京邮电大学世纪学院毕业设计（论文） 12 的分组码。或者说，Hamming 码是一种纠正单个错误的完备码，即 SEC(Single Error Correcting)码。 这种编码不仅具有良好的性能， 而且编译码电路非常简单， 易于实现。 所以，从 20 世纪 50 年代问世以来，它最先被用于磁芯存储器，60 年代初用于大型 计算机，70 年代在 MOS 存储器中得到应用，后来在中小型计算机中普遍采用，目 前常用于 RFID 系统中多位错误的纠正。总之，Hamming 码在提高系统可靠性方面 获得了广泛的应用。 Hamming 码的构造必须满足关系式： 码长：n = 2m 1 信息位：k = 2m 1 m 监督位：n k = m,且 m 3 最小距离：dmin= 3 上式中，n 为码元总位数，m为监督码元位数。Hamming码能纠正单个错误，所以每 一种错误图样不能相同且与伴随式一一对应。这就要求监督矩阵H中，任意两列线性 无关且不为0，而一个m行的H矩阵，最多只能有2m 1列，即为Hamming码码长。 Hammi
