《信息论与编码基础》第1章 绪论

1、信息论与编码周三：78 (13:3015:10)/A105中山大学计算机科学系 蔡国扬E_mail: 信息科学是研究不同领域里有关信息的收集、加工、存储、传递以及使用的学科。其出发点是认识信息的本质和它的运动规律；其归宿则是利用信息来达到某种具体的目的。以信息作为主要研究对象，以信息的运动规律作为主要研究内容，以信息方法论作为主要研究方法，这是信息科学区别于一切传统科学的最根本的特征。信息方法以信息概念作为分析和处理问题的基础，它完全撇开研究对象的具体结构和运动形态，把系统的有目的性运动抽象为一个信息变换过程，即信息的输入、存储、处理、输出和反馈过程。信息方法包括两个方面，即信息分析方法和信息

2、综合方法。前者解决认识问题；后者解决实践问题。信息科学体系信息科学体系信息输入反馈处理存储输出信息信息方法示意图信息科学是一个包含从不同角度研究信息及其运动形态的学科群，是由信息理论科学、信息技术科学和信息应用科学三个层次构成的完整体系。信息科学体系信息论计算机科学通信科学信息物理学信息学图书馆学传播学信息经济学信息社会学信息心理学信息科学也可以认为，信息科学由信息科学理论、信息应用技术和信息科学方法三者组成。信息科学理论主要包含信息定性理论、信息定量理论和信息应用理论。信息应用技术包括信息的获取、传递、加工处理、存储等代替和延伸人的感官及大脑的信息功能的技术，可以细分为信息获取技术（感测技术

3、）、信息传递技术（电信技术）、信息加工处理技术（计算机技术）及信息控制技术（自动智能控制技术）。信息科学方法包括信息分析方法和信息综合方法，指导人类通过信息窗口去认识世界、改造世界。信息科学体系第1章 绪论信息的一般概念香农信息的概念信息论研究的对象和目的信息论研究的内容信息论发展简史与现状课程讨论主要内容第2章 离散信源及其信息测度信源的数学模型及分类离散信源的信息测度-信息熵信息熵的基本性质离散无记忆的扩展信源离散平稳信源及其极限熵信源的冗余度课程讨论主要内容第3章 离散信道及其信道容量信道的数学模型及分类信道疑义度与平均互信息平均互信息的特性离散无记忆扩展信道离散信道的信道容量信源与信道

4、的匹配课程讨论主要内容第4章 波形信源及波形信道波形信源的统计特性和离散化连续信源和波形信源的信息测度连续信源熵的性质及最大差熵定理具有最大差熵的连续信源连续信道和波形信道的分类连续信道和波形信道的信息传输率连续信道和波形信道的信道容量课程讨论主要内容第5章 基本的信源和信道编码定理无失真信源编码定理编码器的概念等长码等长信源编码定理变长码变长信源编码定理（香农第一定理）有噪信道编码定理错误概率与编译码规则有噪信道编码定理（香农第二定理）联合信源信道编码定理课程讨论主要内容第6章 保真度准则下的信源编码失真的测度信息率失真函数及其性质离散无记忆信源的信息率失真函数保真度准则下的信源编码定理（香

5、农第三定理）联合有失真信源信道编码定理课程讨论主要内容第7章 无失真的信源编码无失真信源编码的概念香农编码费诺编码Huffman编码游程编码算术编码通用编码课程讨论主要内容参考书目傅祖芸，信息论与编码，电子工业出版社, 2005曹雪虹等，信息论与编码，北邮出版社，2001唐朝京，信息论与编码基础， 国防科技大学出版社周荫清，信息理论基础，北京航空航天大学出版社Thomas M. Cover, Joy A. Thomas，Elements of Information Theory，清华大学出版社，2003R. J. McEliece, The Theory of Information and

6、 Coding, 电子工业出版社, 2005课程讨论主要内容信息论是将通信技术、概率论、随机过程、数理统计等学科相结合逐步发展而形成的一门新兴科学。奠基人：美国数学家香农 (C. E. Shannon)，1948年发表著名论文 “A Mathematical Theory of Communication” ，用概率测度和数理统计的方法系统研究了通信的基本问题，给出了信息的度量方法，得出了带有普遍意义的重要结论，由此奠定了信息论的理论基础，为信息的表达、存储、传送和处理的具体实现提供了理论依据。在香农信息论的指导下，人们在信源编码和信道编码两个领域进行了卓有成效的研究，在提高通信系统信息传输的

7、有效性和可靠性上取得了丰硕成果。第一章 绪论“通信的基本问题就是在一点重新准确地或近似地再现另一点所选择的消息”。 Claude Shannon 1916-2001 第一章 绪论随着信息概念的不断深化和信息理论的发展，信息论所涉及的内容已经超出了狭义的通信工程范畴，渗透到许多学科。本课程主要内容：香农(Shannon)信息论：信息的统计度量，离散信源，离散信道和信道容量；编码理论和实现原理：信源编码与信道编码。第一章 绪论信息是信息论中最基本、最重要的概念，既抽象又复杂。而在日常生活中，信息常常被认为是“消息”、“知识”、“情报”等。“信息”不同于消息在现代信息论形成之前，信息一直被看作是通信

8、中消息的同义词，没有严格的数学含义。信息论认为，消息是一种能够被人们感觉器官所感知的客观物质运动和主观思维活动的状态的表达形式（如文字、符号、数据、语言、音符、图片、视频等），而信息才是其中包含的告知的实质性内容。1.1 信息的一般概念“信息”不同于情报情报是人们对于某个特定对象所见、所闻、所理解而产生的知识，其含义比“信息”窄的多。情报 (intelligence) 与信息(information) 有着严格的区别，前者是指经过慎密分析得到的特殊的信息，作为决策的依据。后者为泛指。 “信息”不同于信号信号是承载消息的物理量。“信息”不同于知识知识是人们根据需要，从自然界收集得来的数据中提取得

9、到的有价值的信息，它们是对客观事物规律性的概括，是一种具有普遍性和概括性的高层次的信息。1.1 信息的一般概念在通信中对信息的表达分为三个层次：信号、消息、信息。信号：是信息的物理表达层，是三个层次中最具体的层次。它是一个物理量，是一个载荷信息的实体，可测量、可描述、可显示。消息(或称为符号)：是信息的数学表达层，它虽不是一个物理量，但是可以定量地加以描述，它是具体物理信号的进一步数学抽象。可将具体物理信号抽象为两大类型：离散(数字)消息：由随机序列描述的一组未知量： X=(X1, , Xi , , Xn)连续(模拟)消息：由随机过程描述的未知量：X( t, ) 信息：是信号与消息的更抽象的表

10、达层次。 1.1 信息的一般概念信息、消息和信号是既有区别又有联系的三个不同的概念。消息中包含信息，是信息的载体。信号携带着消息，它是消息的运载工具。信息是由具体的物理信号、数学描述的消息的内涵，它是信号具体载荷的内容，也是消息描述的含义。信号是抽象信息在物理层表达的外延；消息是抽象信息在数学层表达的外延。同一信息，可以采用不同的信号形式(比如文字、语言、图象等)来载荷；也可以采用不同的数学表达形式(比如离散或连续)来定量描述。同一信号形式，比如“0”与“1”，可以表达不同形式的信息，如无与有、断与通、低与高(电平)等等。1.1 信息的一般概念“信息”一词，来源于拉丁文，原意指解释、陈述。在英

11、文、法文、德文、西班牙文中均为 “information”。根据牛津大词典记载，information 在14世纪时被解释为传播的行为，在1920世纪则被解释为传播的内容。从其英语语源上看，“in”是 接收到消息， “formation” 是 顺理成章。也就是说，信息用于增长人们的知识、传播各种事物，把我们不明确的知识弄清楚后整理成章，再传递给需要的人。作为科学术语，信息一词最早出现在哈特莱(R. V. Hartley)于1928年撰写的信息传输一文中：“发信者所发出的信息，就是他在通信符号表中选择符号的具体方式”。定义不涉及到信息的价值和具体内容，只考虑选择的方式。即使考虑了选择的方法，但没

12、有考虑各种可能选择方法的统计特性。 1.1 信息的一般概念1948年，维纳 (N. Wiener)首次将信息与物质、能量相提并论。在控制论-动物和机器中通信与控制问题一书中指出：“机械大脑不能像初期唯物论者所主张的 如同肝脏分泌出胆汁 那样分泌出思想来，也不能认为它像肌肉发出动作那样能以能量的形式发出思想来。信息就是信息，不是物质也不是能量。不承认这一点的唯物论，在今天不能存在下去”。将“信息”上升到“最基本概念”的位置。后来，维纳在人有人的用处一书中提出：“信息是人们适应外部世界并且使这种适应反作用于外部世界的过程中，同外部世界进行互相交换的内容的名称。” 1.1 信息的一般概念从维纳的观点

13、，物质、能量和信息是相互有区别的，是人类社会赖以生存、发展的三大基础：世界由物质组成，能量是一切物质运动的动力，信息是人类了解自然及人类社会的凭据。如果说，香农主要是从信息的发送端来研究信息的，那么，维纳则着重从接受端如何利用信息来加以研究。正是在写于1948年的这段话里，维纳第一次把信息同哲学相关联，尖锐地触及了信息的本质定位问题。也正是这段话，启示人们将信息与物质、能量并列为人类生存的三大要素。 1.1 信息的一般概念Norbert Wiener, 18941964, founder of cybernetics.1.1 信息的一般概念1948年，香农 (C. E. Shannon) 发表

14、了一篇著名的论文：“通信的数学理论”。 他从研究通信系统传输的实质出发，对信息作了科学的定义，并进行了定性和定量的描述。香农信息定义：信息是事物运动状态或存在方式的不确定性的描述。(Information is a measure of ones freedom of choice when one selects a message) 纵观信息的定义，强调的主要有三点：信息能够减少不确定性的讯息，并以符号的形式存储、处理和传播；信息是一切通信和反馈控制系统的构成要素；信息能够再现或部分再现物质与能量过程。 1.1 信息的一般概念诞生于20世纪4060年代的系统理论，还包括奥地利生物学家贝塔郎

15、非(Karl Ludwig von Bertalanffy, 1901年9月19日1972年6 月12日）创始的一般系统论 (General Systems Theory)，与信息论 (Information Theory)、控制论(Cybernetics)一起形成所谓的“老三论”。1.1 信息的一般概念不光“老三论”突出地强调信息的意义，包括耗散结构论、超循环论和协同论在内的所谓“新三论”，对信息的重视程度也相当高。例如耗散结构论就认为，一个远离平衡状态的开放系统，是不断地在和外界交换物质、能量和信息的。在经济学家眼里，信息更是与物质、能量相并列的客观世界的三大要素之一。美国哈佛大学的研究小

16、组给出了著名的资源三角形。1.1 信息的一般概念物质信息能量他们认为：没有物质，什么也不存在；没有能源，什么也不会发生；没有信息，任何事物都没有意义。 信息的意义 “世界由物质、能量、信息三大要素组成”是控制论的著名观点之一，也由当今科学界所普遍认同。能量是物质做功的能力，包括势能、动能、热能、电能、磁能、光能、化学能和原子能在内的各类能量在物质世界里具有强大功能和巨大作用。信息作为客观存在的物质世界中各种符号的载荷，特别是其内容为接收者预先所不知道时，具有减少或消除不确定性的实际效用，因而亦为人们所重视和强调。1.1 信息的一般概念信息的作用信息是人类认识世界的媒介。信息是事物的普遍属性，人

17、类都是在接受、感知、识别、分析、整理信息的基础上来认识事物的。信息“消除系统不确定性”的重要属性，正是反映了信息在帮助人类认识世界中的巨大作用。信息是人类社会存在的必要条件。人类社会是一个群体性的组织，个体之间如果没有畅通高效的交流方式，就不可能凝聚成如此庞大的集体。信息是强大的生产力要素。被人类处理后的信息用于指导人类改造世界。现在所谓“信息社会”、“信息化革命”的观点之所以被广泛采纳，是因为信息日益突现的创造性作用确实深刻地改变着我们的整个世界。1.1 信息的一般概念从通信的角度出发，构成消息的各种形式需要具备两个条件：一是能够被通信双方所理解；二是可以传递。但是：收信者在收到消息之前，并

18、不一定知道消息的具体内容（包括消息描述的对象和对象的状态）；收信者在收到消息之后，由于可能存在的干扰，并不一定能确定得收到的消息的正确性和可靠性。通信过程是一种消除上述不确定性的过程。不确定性一旦被消除，收信者就得到了信息。可以认为，信息量与不确定性消除的程度有关。 在这里不确定性指的是随机性，因此可以考虑运用研究随机事件的数学工具 概率论和随机过程来测度不确定性的大小，从而给出测度信息的基本方法。 1.2 香农信息概念某一事物状态的不确定性的大小，与该事物可能出现的不同状态数目以及各状态出现的概率大小有关。如果不确定性的大小能够度量，那么信息也是可以测度的。 与信息测度相关的几个概念包括：样

19、本空间、概率空间 、先验概率 、自信息 、后验概率 、互信息等。样本空间：某事物所有可能选择的消息的集合（即该事物所有可能出现的不同状态）构成该事物的样本空间。每个可能选择的消息（或称一个事件）是这个空间的一个元素。概率测度：对于一个离散的消息空间，为其中每一个消息选择一个概率，构成这个空间的一个概率测度。1.2 香农信息概念概率空间：一个样本空间 X=a1, a2, , aq 和它的概率测度P(X)=P(a1), P(a2), , P(aq)统称为一个概率空间，可用 X, P 来表示：先验概率：选择符号 ai 作为消息的概率 P(ai) 称为先验概率。自信息：在接收端，选择 ai 作为消息（

20、猜测事件 ai 发生）的不确定性与 ai 作为消息的先验概率成反比，表示为 ：称为 ai 的自信息。自信息描述了 ai 本身携带的信息量，与接收端无关。1.2 香农信息概念后验概率：接收端收到的消息(符号)为 bj ，而发送端发的是 ai 的概率 P(ai/bj) 称为后验概率。后验概率反映了在接收端收到的消息(符号)为 bj 后，对于发送端发送的是 ai ，尚存在不确定性。类似地，这种不确定性描述为：互信息：收信者收到消息(符号) bj 后，将事件 ai 先验的不确定性（自信息）减去尚存在的不确定性定义为互信息：互信息被认为是此时收信者获得的信息量。1.2 香农信息概念如果信道没有干扰，信道

21、的统计特性使 ai 以概率“1”传送到接收端。这时，收信者接到消息后尚存在的不确定性等于零，即 P(ai/bj)1，log(1/P(ai/bj)0，尚存在的不确定性全部消除。此时互信息等于自信息：对于必然事件 ai，P(ai)=1，其自信息 I(ai)=0。可以解释为收信者早已确知该事件必然发生，如果事件真的发生了，事件本身携带的信息量等于 0。同理，如果一个小概率事件发生了，则事件本身将携带很大的信息量。1.2 香农信息概念有关自信息和互信息的概念即为香农关于信息的定义和度量，通常也称为概率信息。香农信息概念有突出的优势：对信息的定义和度量有明确的数学模型和定量计算模型，是一个科学的定义；对

22、信息的定义与日常理解的信息的含义一致；定义排除了信息的主观含义，信息成为一种纯形式化的概念。同一信息对任何一个收信者具有同样的自信息量。进一步地，在具有同样信道干扰程度的前提下，同一信息对任何一个收信者具有同样的互信息量。1.2 香农信息概念香农信息概念的局限性：定义和度量的出发点假定了事物状态可以用一个以经典集合论为基础的概率模型来描述，在实际中要寻找一个合适的概率模型往往非常困难。有时对是否存在这样一种模型还值得探讨。定义和度量没有考虑收信者的主观特性和主观意义，也未顾及信息的具体含意、具体用途、重要程度和引起后果等因素，这与实际情况不完全一致。其实，信息具有很强的主观性和实用性。1.2

23、香农信息概念有关信息本体性的一些观点： 信息的普遍性：物质、能量和信息构成了物质世界的三大支柱。世界是物质的，物质世界中的任何事物都处于永恒的运动和普遍的相互作用之中。上述运动和作用需要能量的支持，并产生各种各样的状态和方式，从而产生信息。信息既是物质存在方式和状态的显示，也是相互作用的显示。信息源于物质世界本身的运动和相互作用，所以信息是普遍存在的，是物质的一种普遍属性。信息的绝对性：信息不能脱离物质而独立存在，必须以物质为载体，以能量为动力，三者相辅相成，缺一不可。1.2 香农信息概念信息的无限性、动态性和时效性：物质运动和相互作用是永恒的、无限的、动态的，所以信息具有无限性、动态性，永远

24、处在产生、演变、更新当中，也形成了对信息的主观认识的时效性。信息的相对独立性：信息是物质的属性，但并非物质本身，具有相对独立性。事物运动的状态和方式一旦体现出来，就可以脱离原来的事物而相对独立地栽负于别的事物上，而被提取、变换、传递、存储、加工处理。因此，信息不同于它的源事物，也不同于它的载体。1.2 香农信息概念信息的共享性：信息的相对独立性使得它可被传递、复制、存储、转换、扩散（流动性），因而具有了共享性。信息的客观性：信息是对客观现实的反映，不随人的主观意志而改变。如果人为的窜改信息，那么信息就会失去它的价值。信息的可识别性：人类可以通过感觉器官和科学仪器等方式来获取，整理，认知信息。这

25、是信息得到利用的前提。 信息的度量性：信息可以度量，信息量有多少之分。1.2 香农信息概念各种通信系统的本质都是信息传输系统。将他们具有共同特性的部分抽取出来，概括成一个统一的理论模型，通常称为通信系统模型。通信系统模型适用于其他的信息流通系统，如生物有机体的遗传系统、神经系统、视觉系统，人类社会的管理系统等等，也称为信息传输系统模型。通信系统模型正是信息论的研究对象。通过对系统中消息的传输和处理来研究信息传输和处理过程的共同规律，以提高信息传输的可靠性、有效性、保密性和认证性。1.3 信息论研究的对象和目的信源编码器信道编码器信宿信源译码器信道译码器编码信道信源调制器解调器信道干扰源通信系统

26、理论模型1.3 信息论研究的对象和目的信源：产生消息或消息序列的来源。消息可以是离散的，也可以是连续的（数据、文字、语言、图像），通常信源的消息序列是随机发生的，因此要用随机变量来描述。编码器：把消息变换成适合于信道传输的信号。信源编码器：将信源的输出进行适当的变换，以提高信息传输的有效性。信道编码器：对信源编码器的输出进行变换，用增加冗余度的方法提高信道的抗干扰能力，以提高信息传输的可靠性。调制器：将信道编码器输出的数字序列变换为振幅、频率或相位受到调制控制的形式，以适合在信道中进行较长距离的传输。1.3 信息论研究的对象和目的信道：信号由发送端传输到接收端的媒介。典型的传输信道有明线、电缆

27、、高频无线信道、微波通道和光纤通道等；典型的存储媒介有磁芯、磁鼓、磁盘、磁带等。干扰源：对传输信道或存储媒介构成干扰的来源的总称。干扰或噪声往往具有随机性，所以信道的特征也可以用概率空间来描述；而噪声源的统计特性又是划分信道的依据。加性干扰：它是由外界原因产生的随机干扰，它与信道中传送的信号的统计特性无关，因而信道的输出是输入和干扰的叠加；乘性干扰：信道的输出信号可看成输入信号和一个时变参量相乘的结果。1.3 信息论研究的对象和目的解调器：从载波中提取信号，是调制的逆过程。信道译码器：利用信道编码时所提供的冗余度，检查或纠正数字序列中的错误。信源译码器：把经过信道译码器核对过的信息序列转换成适

28、合接收者接收的信息形式。转换过程与信源编码方式相关。信宿：消息传送的终点（人或机器）。在通信系统中传输的形式内容是消息，而信息才是我们需要利用系统传输的实质内容。消息只是用来表达信息的工具，是载荷信息的客体。通信的结果是消除或部分消除传递过程中的不确定性，从而获得准确的信息。1.3 信息论研究的对象和目的研究目的：找到信息传输过程的共同规律，提高信息传输的可靠性、有效性、保密性和认证性，以达到信息传输系统的最优化。可靠性 使信源发出的消息经过信道传输以后，尽可能准确地、不失真地再现于接收端。有效性 经济性好，即用尽可能短的时间和尽可能少的设备来传送一定数量的信息。 保密性 隐蔽和保护通信系统中

29、传送的消息，使它只能被授权接收者获取，而不能被未授权者接收和理解。认证性 接收者能正确判断所接收的消息的正确性，验证消息的完整性，而不是伪造的和被窜改的。1.3 信息论研究的对象和目的狭义信息论（经典信息论）：主要研究信息的测度、信道容量以及信源和信道编码理论等问题。这部分内容是信息论的基础理论，又称为香农信息论。香农理论的核心是：在通信系统中，采用适当的编码后，能够实现高效率和高可靠地传输信息，并给出了信源编码定理和信道编码定理。从数学观点看，这些定理是最优编码的存在定理。但从工程的观点看，这些定理不是结构性的， 即不能从定理的结果直接得到实现最优编码的具体途径。然而，它们给出了编码的性能极

30、限，在理论上阐明了通信系统中各种因素之间的相互关系，为人们寻找最佳通信系统提供了重要的理论依据。1.4 信息论研究的内容1.4 信息论研究的内容无噪声有噪声有失真信源编码无失真信源编码率失真理论等长编码定理变长编码定理压缩编码信道编码定理码构成最优码构成网络信息理论保密系统信息理论网络信道网络最佳码保密码香农信息论纠错码代数编码卷积码香农信息论的研究体系一般信息论（工程信息论）：主要研究信息传输和处理问题，除了香农理论外，还包括编码理论、噪声理论、信号滤波和预测、统计检测和估计理论、调制理论、信息处理理论、保密理论等。维纳和前苏联的柯尔莫哥洛夫 (Andrey Nikolaevich Kolm

31、ogorov) 在最佳线形滤波理论、统计检测和估计理论、噪声理论等领域做出了重要贡献。广义信息论：广义信息论是现代信息科学理论，它是一门新兴的综合性学科，不仅包括上述两方面的内容，而且包括所有与信息有关的领域，如模式识别、计算机翻译、心理学、遗传学、生物学、神经生理学、语言学、语义学等，甚至包括了社会、人文、经济等学科中有关信息的问题。1.4 信息论研究的内容总的来说，信息论是一门应用概率论、随机过程、数理统计和近代代数的方法，来研究广义的信息传输、提取和处理系统中的一般规律的学科。它的主要目的是提高信息系统的可靠性、有效性、保密性和认证性，以使达到系统最优化；它的主要内容（或分支）包括香农理

32、论、编码理论、维纳理论、检测和估计理论、信号设计和处理理论、调制理论、随机噪声理论和密码学理论等。本课程主要讨论香农信息理论。1.4 信息论研究的内容信息论从诞生到今天，已有60年历史，它在长期的通信工程实践和理论研究的基础上逐渐发展，已成为一门独立的理论科学。通信系统是人类社会的神经系统。纵观100多年电通信系统(电信系统)的发展历史，一个很有意义的事实是：一旦物理学中的电磁理论以及电子学理论有某些进展，很快就会促进电信系统的创造发明或改进。1820年-1830年期间法拉第 (M. Faraday) 发现电磁感应的基本规律后，不久莫尔斯 (F. B. Morse) 就建立起电报系统(1832

33、-1835)。1876年，贝尔 (A. G. Bell) 又发明了电话系统。1.5 信息论发展简史与现状 1864年麦克斯韦 (Maxell) 预言了电磁波的存在，1888年赫兹 (H. Hertz) 用实验证明了这一预言。接着1895年英国的马可尼 (G. Marconi) 和俄国的波波夫 (A. C. Popov) 发明了无线电通信系统。1907年福雷斯特 (Lee de Forest) 发明能把电磁波进行放大的电子管之后，出现了远距离无线电通信系统。大功率超高频电子管的发明则促成了电视广播系统的建立(1925-1927)。之后，随着微波电子管的出现，在30年代末和40年代的二次世界大战初

34、期，微波通信系统、微波雷达等得到迅速发展。50年代后期发明的量子放大器，60年代初发明的光技术，使人类进入了光纤通信的时代。1.5 信息论发展简史与现状 现代信息论的理论研究可以认为开始于20世纪20年代奈奎斯特和哈特莱的工作。1832年莫尔斯电报系统中的高效率编码方法对后来香农的编码理论是有启发的。1885年凯尔文 (L. Kelvin) 曾经研究过一条电缆上的极限传信问题。1922年卡逊 (J. R. Carson) 对调幅信号的频谱结构作了研究，并明确了边带的概念。1924年奈奎斯特 (H. Nyquist) 的 “影响电报速率因素的确定” 一文，1928年哈特莱 (R. V. Hart

35、ley) 的“信息传输” 一文研究了通信系统传输信息的能力，并给出了信息度量的初步方法。1.5 信息论发展简史与现状 1936年阿姆斯特朗 (E. H. Armstrong) 提出增加信号带宽可以增强系统抑制噪声干扰的能力，推动了调频通信的发展。1939年达德利 (H. Dudley) 发明了声码器。他指出：通信所需要的带宽至少应与所传送的消息的带宽相同。40年代初期，维纳把随机过程和数理统计的观点引入到通信和控制系统中，揭示了信息传输和处理过程的统计本质。他还利用自己在30年代提出的广义谐波分析理论对信息系统中的谐波过程进行谱分析。1.5 信息论发展简史与现状 1948年6月和10月香农在贝

36、尔实验室的贝尔系统技术杂志上发表权威性长文“通信的数学理论”，用概率测度和数理统计的方法系统地讨论了通信的基本问题。他首先严格定义了信息的度量熵 (Entropy) 的概念，定义了信道容量的概念，得出几个重要且带有普遍意义的结论，并讨论了信源和信道特性。加上1949年香农的“噪声中的通信”，奠定了现代信息论的理论基础。随后一些著名数学家如柯尔莫哥洛夫、范恩斯坦 (A. Feinstein)、沃尔夫维兹 (J. Wolfowitz) 等将香农的数学结论作了进一步的严格论证和推广，使之具备更为坚实的数学基础。1.5 信息论发展简史与现状 信息论产生后的重要发展：信道编码定理：1952年费诺 (R.

37、 M. Fano) 给出并证明了费诺不等式，并给出了关于香农信道编码逆定理的证明。1961年费诺描述了分组码的码率、码长和错误概率的关系，并提供了香农信道编码定理的充要性证明。1965年格拉格尔 (R. G. Gallager) 提供了更为简明的证明方法。1972年阿莫托 (S. Arimoto) 和布莱哈特 (R. Blahut) 分别发展了信道容量的迭代算法。信道容量：1964年霍尔辛格 (J. L. Holsinger) 继续香农的工作，开展对有色高斯噪声信道容量的研究。1969年平斯克 (M. S. Pinsker) 提出了具有反馈的非白噪声高斯信道容量问题，并由科弗尔 (T. M.

38、Cover) 在1989年证明。1.5 信息论发展简史与现状 无失真信源编码：1952年费诺提出了一种费诺码，同年 霍夫曼 (D. A. Huffman) 构造了一种 Huffman 编码方法，并证明了它是一种最优码。1956年麦克米伦 (B. Mcmillan) 首先证明了唯一可译变长码的 Kraft 不等式。1968年艾利斯 (P. Elias) 在香农-费诺码的基础上提出了算术编码的初步思路。1976年瑞斯桑尼 (J. Rissanen) 给出了算术编码方案，并于1982年和兰登 (G. G. langdon) 合作将算术编码系统化，省去了乘法运算。1977年齐弗 (J. Ziv) 和兰

39、佩尔 (A. Lempel) 提出LZ码，并证明此方法可以达到信源的熵值。1990年贝尔 (T. C. Bell) 对LZ算法作了一系列的改进，现已广泛用于文本的数据压缩中。1.5 信息论发展简史与现状 纠错码理论：1950年汉明 (R. W. Hamming) 为使贝尔实验室的计算机具备有检测错误能力的运行程序，首先提出了纠正一位错误的编码方法，建立了线性分组码的基本思想。随后格雷 (Marcel J. E. Golay) 提出了纠正二位和三位错误的格雷码。1954年 Reed 和 Muller 提出新的分组码 RM 码。(在1969年到1977年之间，RM 码在火星探测方面得到了极为广泛的

40、应用。即使在今天，RM 码也具有很大的研究价值，其快速的译码算法非常适合于光纤通信系统)。1957年 E. Prange 提出循环码，代数编码理论成型。循环码的一个非常重要的子集就是分别由 Hocquenghem 在1959年、Bose 和 Ray-Chaudhuri 研究组在1960年几乎同时提出的 BCH 码 (Bose-Chaudhuri-Hocquenghem)。1.5 信息论发展简史与现状 纠错码理论：1960年 Reed 和 Solomon 将 BCH 码扩展到非二元的情况，得到了RS (Reed-Solomon) 码。1967年，Berlekamp 给出了一个非常有效的译码算法后

41、，RS 码得到了广泛的应用。此后，RS 码在CD播放器、DVD播放器中得到了很好的应用。虽然分组码在理论分析和数学描述方面已经非常成熟，并且在实际的通信系统中也已经得到了广泛的应用，但分组码固有的缺陷大大限制了它的进一步发展。首先，由于分组码是面向数据块的，因此，在译码过程中必须等待整个码字全部接收到之后才能开始进行译码。在数据块长度较大时，引入的系统延时是非常大的。分组码的第二个缺陷是它要求精确的帧同步，即需要对接收码字或帧的起始符号时间和相位精确同步。1.5 信息论发展简史与现状 纠错码理论： 1955年 Elias 等人提出卷积码以改善分组码所存在的固有缺点。卷积码充分利用了各个信息块之

42、间的相关性，编码过程连续进行。同样，在卷积码的译码过程中，不仅要从本码中提取译码信息，还要充分利用以前和以后时刻收到的码组，从这些码组中提取译码相关信息，而且译码也是可以连续进行的，这样可以保证卷积码的译码延时相对比较小。通常，在系统条件相同的条件下，在达到相同译码性能时，卷积码的信息块长度和码字长度都要比分组码的信息块长度和码字长度小，相应译码复杂性也小一些。1.5 信息论发展简史与现状 纠错码理论： 1961年由 Wozencraft 和 Reiffen 提出，Fano和 Jelinek 分别在1963年和1969年进行改进了卷积码的序贯译码算法，是基于码字树图结构的一种次最优概率译码算法。 1963年 Massey 提出门限译码算法，利用码字的代数结构进行代数译码。 1967年 Viterbi 提出 Viterbi 最优算法，是基于码字格图结构的一种最大似然译码算法。在Viterbi 译码算法提出之后，卷积码在通信系统中得到了极为广泛的应用，如 GSM、3G、商业卫星通信系统等。 (A. J. Viterbi 也是高通公司 Qualcomm 的创始人之一。高通是最早实现商用 CDMA 蜂窝移动系统的公司，因此 Viterbi被世界公认为 CDMA 之父)1.5 信息论发展简史与现状 纠错码理论： 近年来，在信道编码定理的指引下