编码理论简介

第1页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng信息论与编码宋鹏2014年春E-mail：songpeng@（第一讲）

─────────────────

绪论第2页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第1讲：绪论第2讲：信息论概论第3讲：无失真信源编码方法Ⅰ第4讲：无失真信源编码方法Ⅱ第5讲：信道编码原理第6讲：线性分组码第7讲：上机Ⅰ（线性分组码）第8讲：循环码Ⅰ第9讲：循环码Ⅱ第10讲：BCH码与RS码Ⅰ第11讲：BCH码与RS码Ⅱ第12讲：卷积码Ⅰ第13讲：卷积码Ⅱ第14讲：上机Ⅱ（卷积码）第15讲：总复习第16讲：考试目录第3页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng课程概况学时：32目的：了解信息论与编码的作用与意义，对信息论与编码的研究方法和成果有广泛的基本认识，学会应用，为进一步研究打下基础。特点：以概念和物理意义为主，数学推导尽量简化。第4页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng其它有关事项1.课外阅读：参考教材2.作业：20%3.上机：10%4.论文：两年内的国内外期刊，以一两篇为主，结合自己的理解，按电子学报论文形式，有创见更好。占10%5.考试：基本概念和基本计算。60%6.联系方式：Email:songpeng@第5页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng教材与参考书1.《编码理论(第二版)》，田丽华，西安电子科技大学出版社，2007年2.《信息论—基础理论与应用》，傅祖芸，电子工业出版社3.《纠错码—原理与方法》，王新梅，西安电子科技大学出版社4.《ElementofInformationTheory

》，

ThomasM.Cover，清华大学出版社第6页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng其它参考书[5]《信息论与编码（第二版）》，陈运，周亮，陈新，电子工业出版社，2007年[6]《信息论与编码原理》，宋鹏，电子工业出版社，2011年[7]《编码理论》，张鸣瑞，邹世开，北京航空航天大学出版社，1990年

信息论不仅在方法论的层面上解决通信的有效性和可靠性问题，而且在认识论的层面上帮助认识事物的本质。学完信息论之后，再重新审视一下周围的事物，会有许多新的看法和认识。用信息论可以宏观地认识某些政治问题，也可以定量地解决某些经济问题，还可以分析、解释外语学习中存在的问题……总之，信息论是高层次信息技术人才必不可少的基础知识。第7页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第8页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng内容1.线性分组码2.卷积码讲课：28学时上机：4学时重温加深新内容第9页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng内容第10页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章绪论123

通信系统模型Shannon信息论的中心问题4Shannon信息论的局限性

一些基本概念

信息的广义性5

信息科学6第11页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章绪论1.1一些基本概念Shannon于2001年2月24日在纽约谢世信息是构成任何系统的三大要素之一，另外两个要素是物质和能量。信息虽然是无形的和抽象的，但它是系统的灵魂。信息论和晶体管同时诞生在Bell实验室1948年，ClaudeShnnon（克劳德·香农）在他的经典论文“AMathematicalTheoryofCommunication”（通信中的数学理论）的引言部分中写到：“通信中的基本问题就是在某一点精确或近似地再生另一点选择的信息。”第12页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng《QUALCOMMEQUATION》高通的两个关键创始人——艾文·雅各布和安德鲁·维特比都拥有电子工程学博士学位，是克劳德·香农的信息理论的卓越的学生。雅各布和维特比将香农的观点扩大到为高通的成功打下基础的工程学系统中。高通的本质是：它是一家以信息理论为基础的信息技术公司。Qualcomm第13页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章绪论1.1一些基本概念信息、消息、信号的区别信息：是系统传输、交换、存储和处理的对象，信息载荷在语言、文字、数据、图像等消息之中。消息：描述事物的特征和状态。例如：包含有信息的语言、文字和图像等。信号：把消息变换成适合信道传输的物理量，这种物理量称为信号（如电信号、光信号、声音信号等）。第14页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章绪论1.1一些基本概念信息、消息和信号是紧密相联的三个不同的概念。同样一个消息，对于不同的人从中可获得的信息是不一样的。第15页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章绪论

信息化社会对人类社会发展的影响经济全球化和知识化，互联网已成为社会资源重新分配的基本工具。人们的一切活动都将在信息空间中进行竞争和接受检验。导致第三次军事革命，数字化部队，数字化战场。许多有形的东西开始向数字的、无形的方向转变。也使人们越来越忙碌、越来越浮躁，在信息的大洋中有弄潮儿，也有溺水者。第16页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章绪论为了表彰信息论的创始人Shannon的伟大功绩，2000年10月6日IEEEInformationSociety的25名成员，在Shannon儿童时代的老家Michigan的Gaylord举行了Shannon塑像的落成典礼。第17页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章绪论著名信息论和编码学者Dr.RichardBlahut在Shannon塑像落成典礼上的题词中说：“在我看来，两三百年之后，当人们回过头来看我们这个时代的时候，他们可能不会记得谁曾是美国的总统，他们也不会记得谁曾是影星或摇滚歌星，但是仍然会知晓Shannon的名字，学校里仍然会讲授信息论”。第18页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章绪论

塞缪尔·莫尔斯（SamuelFinleyBreeseMorse，1791-1872），作为一名画家是成功的。莫尔斯曾两度赴欧洲留学，在肖像画和历史绘画方面成了当时公认的一流画家。1826年至1842年任美国画家协会主席。

在一次远洋旅途中，莫尔斯结识了杰克逊。杰克逊是波士顿城的一位医生，也是一位电学博士。闲聊中，杰克逊把话题转到电磁感应现象上。

从此，莫尔斯走上了科学发明的崎岖道路。为了维持生活，莫尔斯于1836年不得不重操旧业，担任纽约大学艺术及设计教授。课余时间，他仍然继续从事电报发明工作。终于在1837年9月4日，莫尔斯制造出了一台电报机。

1844年5月24日，在华盛顿国会大厦联邦最高法院会议厅里，进行电报发收试验。年过半百的莫尔斯在预先约定的时间，兴奋地向巴尔的摩发出人类历史上的第一份电报。他的助手很快收到那份只有一句话的电报：“上帝创造了何等的奇迹!”第19页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章绪论1862年31岁，麦克斯韦发表了第二篇论文《论物理力线》，不但进一步发展了法拉第的思想，扩充到磁场变化产生电场，而且得到了新的结果：电场变化产生磁场，由此预言了电磁波的存在，并证明了这种波的速度等于光速，揭示了光的电磁本质。这篇文章包括了麦克斯韦研究电磁理论达到的主要结果。1864年他的第三篇论文《电磁场的动力学理论》，从几个基本实验事实出发，运用场论的观点，以演绎法建立了系统的电磁理论。1873年出版的《电学和磁学论》一书是集电磁学大成的划时代著作，全面地总结了19世纪中叶以前对电磁现象的研究成果，建立了完整的电磁理论体系。这是一部可以同牛顿的《自然哲学的数学原理》、达尔文的《物种起源》和赖尔的《地质学原理》相媲美的里程碑式的著作。

麦克斯韦的主要科学贡献在电磁学方面，同时在天体物理学、气体分子运动论、热力学、统计物理学等方面，都作出了卓越的成绩。正如量子论的创立者普朗克（MaxPlankl858—1947）指出的：“麦克斯韦的光辉名字将永远镌刻在经典物理学家的门扉上，永放光芒。从生地来说，他属于爱丁堡；从个性来说，他属于剑桥大学；从功绩来说，他属于全世界”。第20页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章绪论

赫兹是一个短命的物理学家。他于1894年逝世时，年仅37岁。

1886年29岁发现电磁波，其后不到6年，意大利的马可尼、俄国的波波夫分别实现厂无线电传播，并很快投入实际使用。其他利用电磁波的技术：无线电报（1894年）、无线电广播（1906年）、无线电导航（1911年）、无线电话（1916年）、短波通讯（1921年）、无线电传真（1923年）、电视（1929年）、微波通讯（1933年）、雷达（1935年），以及遥控、遥感、卫星通讯、射电天文学……它们使整个世界面貌发生了深刻的变化。

赫兹关于电磁波的实验，为无线电技术的发展开拓了新的道路，构成了现代文明的骨架，后人为了纪念他，把频率的单位定为赫兹。第21页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章绪论1876-------------贝尔发明电话贝尔制成的电话机

贝尔于1875年制成左图电话的原型。这个装置由一圈电线、一个磁臂和一块张紧薄膜组成。声音震动薄膜，再振动磁臂。磁石的移动令线圈产生波动的电流。这个电讯号可利用线路另一端的相同装置再转换回声音。第22页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章绪论信息论的创始人香农Shannon，1916年生于美国，大学时代在美国密执安大学和麻省理工学院学习，修过布尔代数课，并曾在发明微分分析仪的数学家布什的指导下使用微分分析仪，这使他对继电器电路的分析产生兴趣。他认为这些电路的设计可用符号逻辑来实现，并意识到分析继电器的有效数学工具正是布尔代数。1938年，香农发表了著名的论文《继电器和开关电路的符号分析》，首次用布尔代数进行开关电路分析，并证明布尔代数的逻辑运算，可以通过继电器电路来实现，明确地给出了实现加、减、乘、除等运算的电子电路的设计方法。这篇论文成为开关电路理论的开端。

后来，香农到贝尔实验室工作，他进一步证明了可以采用能实现布尔代数运算的继电器或电子元件来制造计算机，香农的理论还为计算机具有逻辑功能奠定了基础，从而使电子计算机既能用于数值计算，又具有各种非数值应用功能，使得以后的计算机在几乎任何领域中都得到了广泛的应用。

无失真变长信源编码定理（香农第一定理）；有噪信道编码定理（香农第二定理）；保真准则下信源编码定理（香农第三定理）。第23页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章绪论香农证明：只要信息传输速率小于信道容量C，传输的错误概率可以任意地小，反过来如果超过信道容量，则传输的错误是不可避免的。信息论解决了通信中的两个基本问题信道编码：在香农以前的错误观点：增加信道的信息传输速率总要引起错误概率增加，认为要使错误概率为零，则传输速率只能为零。信源编码：达到不失真信源压缩编码的极限（最低）编码速率是多少？答案：这个极限速率等于该信源的熵H。第24页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章绪论1.2通信系统模型信息论—

通信的数学理论：是研究信息的传输、存储和处理的科学。通信的基本问题：是在彼时（存储情况）或彼地（通信情况）精确地或近似地再现此时、此地发出的消息。信息论研究的主要问题：在通信系统设计中如何实现有效性和可靠性。第25页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章绪论1.2通信系统模型各种通信系统的形式和用途各不相同，但从信息传输、存储和处理的角度来看，本质上有许多共同之处。有收发两端的单向通信系统模型：第26页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章绪论1.2通信系统模型

信源：是产生消息的源。信源研究的主要问题：消息的统计特性和信源产生信息的速率。

编码器：将信源发出的消息变换成适于信道传送的信号的设备。信源编码器纠错编码器调制器不一定每个系统的编码器都含有这3个部分信道编码器：纠错编码器＋调制器第27页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章绪论1.2通信系统模型第28页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章绪论1.2通信系统模型

信道：将信号从发端传送到收端的媒质或通道。信道的种类：干扰源：为了分析方便，将整个通信系统中各部分引入的各种干扰，如衰落、多径、码间干扰、非线性失真、可加噪声等都集中表示为一个方框作用于信道。干扰源的统计特性：划分信道的重要因素，决定信道传输能力的决定因素。两大类干扰：加性干扰；乘性干扰。信道的中心课题：信道的统计特性和信道容量。实现有效和可靠通信主要困难：系统中的干扰。通信理论研究的中心课题：如何抗干扰。第29页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章绪论1.2通信系统模型

译码器：编码的逆变换从受干扰的信号中最大限度地提取出有关信源输出消息的信息，应尽可能精确地恢复信源的输出，并将它们送给信宿。

信宿：信息的接收者，可以是人或物，且与信源处于不同地点或存在于不同时刻。第30页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章绪论1.2通信系统模型它根据实际情况而定信源编码和信道编码统一设计问题Shannon开创的在20世纪七八十年代得到广泛研究的“多用户信息论”系统的模型不是不变的多用户信息系统第31页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章绪论1.3Shannon信息论的中心问题Shannon信息论的基本任务：为设计有效、可靠的通信系统提供理论依据。通信的基本目的：在接收端精确地或以给定的失真度重现信源的输出。第32页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章绪论1.3Shannon信息论的中心问题

信源编码问题

信源编码器作用：根据失真度准则对信源的输出进行划分，给每一类以不同的表示，即码字。

信源译码器的作用：根据收到的信源表示恢复出信源所属的类。

失真度与码长的关系：精确度要求越高（失真度要求越低）对信源的划分就要越细，因而表示信源所需的信息量或码长就越大。

信息论关心的信源编码问题：在给定信源和失真度条件下，要多大信息速率才行？或对给定信源保留一定的信息速率下，可以达到的最小失真是多少？如何实现这一理论结果（即找出实际可行的信源编码和译码方法）？第33页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章绪论1.3Shannon信息论的中心问题

信道编码问题研究在保证信息传输可靠性（如错误概率小于给定值）的条件下最有效地利用信道的传信能力；寻找实际可行的编、译码方法。若R<C，则可以将速率为R的信息以任意高的可靠性传送至接收端；若R>C，则不可能。第34页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章绪论1.3Shannon信息论的中心问题

编码理论的产生信息论在研究信源和信道编码定理时所用的方法都是随机编码的方法，是非构造性的，不能提供具体的编、译码方法。

纠错编码理论：Hamming（1950）编码理论—在20世纪50年代末～60年代大发展。

信源编码理论：信息率失真理论（Shannon（1959）和Berger（1971））数据压缩技术（Davisson&Gray（1976）以及Gilbert（1991））第35页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章绪论1.3Shannon信息论的中心问题Shannon信息论的特点通信系统设计的中心问题

将概率统计的观点和方法引入到通信理论研究中；揭示了通信系统中传送的对象是信息，并对信息给出科学的定量的描述。

在随机噪声干扰下如何有效而可靠地传送信息；实现这一目标的途径是编码（信源编码和信道编码）。第36页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章绪论1.3Shannon信息论的中心问题信息论研究的内容信息论基础：也称狭义信息论/经典信息论/香农信息论。主要研究信息测度、信道容量、信息率失真函数，与这三个概念相对应的香农三定理，信源编码，信道编码。第37页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章绪论1.3Shannon信息论的中心问题信息论研究的内容一般信息论：主要研究信息传输和处理问题。除香农基本理论之外，还包括噪声理论、信号滤波和预测、统计检测和估计理论、调制理论。后一部分内容以维纳为代表。第38页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章绪论1.3Shannon信息论的中心问题信息论研究的内容广义信息论：是一门综合性的新型学科——信息科学。至今没有严格的定义。凡是能够用广义通信系统模型描述的过程或系统，都能用信息基本理论来研究。第39页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章绪论1.4Shannon信息论的局限性Shannon信息论的局限性：Shannon通信系统的模型

Shannon的模型是很理想的抽象，高度概括了实际中各类通信系统的本质。远远不能面面俱到地刻画人类的实际通信问题。Shannon信息论的功绩

Shannon信息论指出了实现有效而可靠通信的必由之路是数字化和编码。通信的数学理论成为几十年来数字化革命的理论基础。

信息论的发展几十年来信息论的理论发展和实际应用走过了曲折而艰辛的道路。在学术界，信息论的“死”与“活”的争论一直存在。第40页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章绪论1.4Shannon信息论的局限性信源框对于可以定量描述的信息，Shannon信息论就有用武之地；对于那些难于定量描述的信息，Shannon信息论就显得无能为力了。Shannon的通信系统模型将信源用一个框表示，引入概率统计工具来描述信源产生消息的规律。如果实际信源确如这种数学描述，那么这种方法就应该是有效地、确切地表述了实际信源，否则这种表述只能是近似的，甚至是根本无效的。第41页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章绪论1.4Shannon信息论的局限性信宿框人接收消息、提取信息的过程与人毕生的生活经历和经验积累是有关的，有些消息的接收可能对几十年后的判断和信息提取有关。Shannon模型的信宿是信息的接收者，仍然假定它是一个概率空间，而与发端消息空间相同，此时彼地（通信系统）或彼时（存储系统）彼地相互作用。但是当人作为信宿时，他的接收消息空间与发送消息空间往往是不相同的，接收判决策略也因人而异，而且它是动态变化的，可能扩大可能缩小。虽然有些信息我们还给不出可用的数学模型来描述它，因而无法进行量度和计算，但它们常常和可以定量描述的信息有着密切的关系。第42页2023/2/1DepartmentofElectronicsandInformation,NCUTSongPeng第一章绪论1