信息的基本概念.ppt

《信息的基本概念.ppt》由会员分享，可在线阅读，更多相关《信息的基本概念.ppt（86页珍藏版）》请在三一办公上搜索。

1、,信息论即仙农(Claude Edwood Shannon,19162001)信息论，也称经典信息论，是研究通信系统极限性能的理论。从信息论产生到现在几十年来，随着人们对信息的认识不断深化，对信息论的研究日益广泛和深入，信息论的基本思想和方法已经渗透到许多学科，在人类社会已经进入信息时代的今天，信息理论在自然科学和社会科学研究领域还会发挥更大的作用。,第章 绪论,信息的基本概念 仙农信息论所研究的内容 仙农信息论产生的背景、主要的研究进展及其应用,本章主要内容,1.1 信息的基本概念,信息论的产生 信息的基本概念 信息论的基本内容,本节内容：,物质 客观世界三大基本要素 能量 信息 信息时代社

2、会的发展离不开物质(材料)、能量（能源）和信息资源。美国学者欧廷格说：“没有物质什麽都不存在，没有能量什麽都不发生，没有信息什麽都没意义。”,1.1.1 信息论的产生,按理说，关于信息的课程应该象物理、化学、生物等课程一样，是基础课。但是，由于信息的抽象性以及当前人们且对信息的认识并不完全清楚，所以在当前只能是专业课。,1948年，美国工程师和数学家仙农(Claude Edwood Shannon,1916-2001)发表了通信的数学理论（A Matematical Theory of Communication，BSTJ，1948）标志着信息论的产生。,通信的基本问题：在一点精确地或近似地恢

3、复另一点所选择的消息。通信系统三项性能指标：传输的有效性 传输的可靠性 传输的安全性,有效性 对于离散信源，信源符号平均码长度应尽量短；信息传输应尽量快，即高的传信率；信息传送应该有高的频谱利用率。可靠性 传输差错要尽量少，对数字传输就是要求低的误码率。安全性 传输的信息不能泄露给未授权人。,三项指标所对应的三项基本技术：数据压缩 数据纠错 数据加密仙农信息论解决了前两项技术的理论问题：提高有效性可通过信源编码来实现，即信源压缩编码，并给出了压缩编码的极限；提高可靠性通过信道编码来实现，并给出实现可靠传输的信息传输速率的极限。所以说，仙农揭示了数据压缩和传输的基本定律。,实际上传输安全性的问题

4、也是仙农解决的。1945年，他写了密码学的数学理论（A Mathematical Theory of Cryptography），1949年改名为保密系统的通信理论（Communication Theory of Secrecy System）公开发表。这篇文章建立了保密系统的数学理论，对密码学产生了很大的影响。所以说，仙农建立了通信中的三项基本技术的理论基础,信息论是前两项技术的理论基础。,1.1.2 信息的基本概念,由于信息已成为许多专家学者争相研究的对象，而且他们从不同的角度和侧面研究和定义信息。据说到目前为止已有上百种信息的定义或说法。例如，“信息是事物之间的差异”，“信息是物质与能量

5、在时间与空间分布的不均匀性”，“信息是收信着事先不知道的东西”等等。,如前所述，由于当前还没有一个公认的关于信息的定义，但这并不影响我们对信息的基本特征的认识。信息有许多与物质、能量相同的特征，例如信息可以产生、消失、携带、处理和量度。信息也有与物质、能量不同的特征，例如，信息可以共享，可以无限制地复制等。,1949年，Weaver在通信的数学中解释仙农的工作时，把通信问题分成三个层次：第一层：通信符号如何精确传输？（技术问题）第二层：传输的符号如何精确携带所需要的含义？（语义问题）第三层：所接收的含义如何以所需要的方式有效地影响行为？（效用问题）Weaver认为仙农的工作属于第一层，但他又证

6、明仙农的工作是交叉的，对第二、三层也有意义。,信息是认识主体（人、生物、机器）所感受的和所表达的事物运动的状态和运动状态变化的方式。以这种定义为基础，信息分成三个基本层次，即语法信息，语义信息，语用信息，分别反映事物运动状态及其变化方式的外在形式、内在含义和效用价值。与Weaver对信息的解释基本一致。,信息的三个基本层次：语法(Syntactic)信息 语义(Semantic)信息 语用(Pragmatic)信息,语法(Syntactic)信息 它是事物运动的状态和变化方式的外在形式，不涉及状态的含义和效用。象语言学领域的“词与词的结合方式”，而不考虑词的含义与效用。在语言学中称为语法学。语

7、法信息还可细分为，概率信息、偶发信息、确定信息、模糊信息等。,语义(Semantic)信息 是事物运动的状态和变化方式的含义。在语言学里，研究“词与词的结合方式含义”的学科称为语义学。,语用(Pragmatic)信息,是事物运动状态及其状态改变方式效用。,信息三个层次的含义 有一个情报部门，其主要任务是对经济情报进行收集、整理与分析以提供给决策机构。该部门设三个组：信息收集组、信息处理组和信息分析组。信息收集组的任务是将收集到的资料按中文、英文或其他文字、明文、密文进行分类，不管这些资料的含义如何都交到信息处理组。信息处理组根据资料的性质进行翻译或破译得到这些资料的含义，然后交到信息分析组。信

8、息分析组从这些资料中挑选出有价值的情报提交给决策机构。,可见，信息收集组是根据所得到的消息提取出语法信息，信息处理组是根据所得到的语法信息提取出语义信息，而信息分析组是根据所得到的语义信息提取出语用信息。可以看到，研究语义信息要以语法信息为基础，研究语用信息要以语义信息和语法信息为基础。三者之间，语法信息是最简单、最基本的层次，语用信息则是最复杂、最实用的层次。,仙农在1948年指出：,“通信的基本问题是在一点精确地或近似地恢复另一点所选择的消息。通常，这些消息是有含义的，即它对于某系统指的是某些物理的或概念的实体。这些通信的语义方面与通信问题无关，而重要的方面是实际消息是从一个可能消息集合中

9、选择出的一条消息。”,可见，仙农在研究信息理论时，排除了语义信息与语用信息的因素，先从语法信息入手，解决当时最重要的通信工程一类的信息传递问题。同时他还把信源看成具有输出的随机过程，所研究的事物运动状态和变化方式的外在形式遵循某种概率分布。因此仙农信息论或经典信息论所研究的信息是语法信息中的概率信息。不过，随着信息论研究的深入，仙农信息论的方法已经渗透到语义信息领域，例如最大熵建模方法用于机器翻译等自然语言处理问题。,信号 通信信息三个层次 消息 信息 消息是信息的携带者，信息包含于消息之中。信号是消息的载体，消息是信号的具体内容。,信息各层次之间的关系如图,1.2 信息论研究的内容,通信系统

10、模型 仙农信息论的主要内容,本节内容：,1.2.1 通信系统模型,如前面所述，仙农的建立是从研究通信系统开始的，并首先建立了通信系统模型。由于技术发展水平的限制，当时的通信基本限制在点对点的通信，所以这种通信系统模型是指“从一个地方向另一个地方传送信息的系统”。例如，电话、电报、电视、无线通信、光通信等。而存储系统在某种意义上也可看成从现在向将来发送信息的通信系统。例如，磁盘或光盘驱动器、磁带记录器、视频播放器等,通信系统是从空间的一点到另一点传送信息的，而存储系统是从时间的一点到另一点传送信息的。,信道,信源,译码器,编码器,信宿,噪声,图1.2.1 通信系统模型,信号,信号加噪声,消息,消

11、息,1.信源(information source)信源是信息的来源，其功能是直接产生可能包含信息的消息 按输出符号的取值分类：离散信源和连续信源：连续信源又分为：离散时间连续信源；波形信源或模拟信源。,按输出符号之间的依赖关系分类 无记忆信源 信源输出符号的概率与以前输出的符号无关 有记忆信源 信源输出符号的概率与以前输出的符号有关 核心问题：信源的消息中所包含的信息量 以及信息如何量度,2.编码器(Encoder)编码器的功能：将消息变成适合于信道传输的信号 信源编码器(source encoder)信道编码器(channel encoder)调制器(modulator),信道编码器,信源

12、编码器,调制器,符号,符号,信号,消息,图1.2.2 编码器的组成,各部分的主要功能信源编码器的功能是将信源消息变成符号，目的是提高传输有效性，也就是压缩每个信源符号传输所需代码（通常为二进制代码）的数目（对二进制代码称比特数）。例如，一个信源含4个符号a,b,c,d，概率分别为1/2，1/4，1/8，1/8。如果不采用信源编码，每个信源符号至少需要用2个二进制代码传输。如果采用信源编码，分别将a,b,c,d编码成为：0，10，110，111，那么平均每信源符号只需1.75个二进制代码传输。可见，采用合适的信源编码确实能通过压缩码率提高传输有效性。所以，信源编码也称信源压缩编码。,信道编码器给

13、信源编码符号增加冗余符号，目的是提高传输可靠性。信源编码输出直接传送，不能保证传输可靠性。利用信道编码对信源编码器的输出符号增加一些冗余符号，并让这些符号满足一定的数学规律，使传输具有纠错或检错能力。因为出现传输错误就会破坏这种数学规律。在接收端就会发现错误。例如，最简单的奇偶纠错，将信源编码输出的每个码组的尾补一个1或0，使得整个码组“1”的个数为奇或偶（或模二加为1或0）。当传输发生奇数差错，打乱了“1”数目的奇偶性，就可以检测出错误。这是最简单的检错方式，而实际的信道编码技术要复杂得多.,图1.2.3 增加冗余符号提高传输可靠性（图中，有阴影的点表示码字）,图中，（a）4个消息用4个2维

14、矢量传送，没有冗余符号。如果出现任何差错都会使传送的码字变成另一个码字，所以无检错能力；（b）在（a）的基础上每个码字增加一个校验符号，构成奇校验，4个消息用4个3维矢量传送。如果出现任何奇数差错都会使传送的码字变成不是码字的3维矢量，这样就能检测出错误，但不能纠正错误；（c）用2个汉明距离为3的3维矢量传送2个消息。如果出现一个错误，可以根据接收矢量和码字汉明距离的大小判决是哪个消息被传输，因此可以纠1个错误。,调制器功能是，将编码器的输出符号变成适合信道传输的信号，目的是，提高传输效率（使远距离传输成为可能）。信道编码符号不能直接通过信道输出，要将编码器的输出符号变成适合信道传输的信号，例

15、如，0、1符号变成两个电平，为远距离传输，还需载波调制，例如，ASK，FSK，PSK等。,3.信道 信道是信号从编码器传输到译码器的中间媒介。信道可以分为狭义信道和广义信道。狭义信道是某些物理通信信道，也可以是物理的存储介质。例如有线、无线、光纤、磁盘、光盘等。广义信道是一种逻辑信道，它和信息所通过的介质无关，只反映信源与信宿的连接关系。信息论中只研究广义信道。,信道还分为无噪声信道和有噪声信道。通常，系统中其它部分的噪声和干扰都等效成信道噪声。通信系统中主要有两种噪声：加性噪声和乘性噪声。一般，背景噪声为加性，而衰落为乘性。这里主要研究加性噪声。在信息论中研究最多的是理想加性高斯白噪声（AW

16、GN）信道。研究高斯噪声的主要原因是它的普遍性和易于处理的特性。,高斯分布的普遍性主要基于两种原因：（1）根据中心极限定理，无数独立随机变量的和的分布趋近高斯分布，因此高斯噪声普遍存在；（2）在限功率条件下产生最大熵的信源分布为高斯分布，而最大熵分布是最容易被观察到的分布。,信源的分类类似，信道还分为离散信道、离散时间连续信道和波形信道（或模拟信道），其中，离散信道和离散时间连续信道输入与输出都是符号序列，只不过符号取值不同，前者取离散值，而后者取连续值；而波形信道的输入与输出均为时间的连续波形。信道也可有无记忆信道和有记忆的区分，离散信道和离散时间连续信道可以是无记忆的，也可以是有记忆的；而

17、波形信道是通常有记忆的。,4.译码器(decoder)译码器实现的功能即从信号中恢复消息。包括:解调器 信道译码器 信源译码器,信道译码器,解调器,信源译码器,符号,符号,消息,信号,图1.2.3 译码器的组成,解调器功能是，将信道输出信号恢复成符号；信道译码器的功能是，去掉解调器输出符号中的冗余符号；信源译码器的功能是，将信道译码器输出符号变成消息。总之，功能与发信机中的对应部分功能相反，目的相同。在模拟通信系统中仅包含解调器。,5.信 宿(Destination)信宿的功能是接收信息，包括人或设备。当前人们对信宿的研究也取得某些成果。例如，利用人的视觉残留效应可以对图像采用不连续传输的方式

18、达到连续的视觉效果，从而进一步压缩码率。利用人听觉的掩蔽效应可以压缩在大幅度频率分量附近的信号而不影响听觉效果。总之，对信宿的研究和压缩编码结合可以在不影响视听效果的条件下，显著压缩码率。,6.通信系统性能指标的评价 有效性用频谱利用率来衡量。提高有效性的措施是，采用信源编码以压缩码率，采用频谱利用率高的调制减小传输带宽；可靠性用传输错误率来衡量。提高可靠性的措施是，采用信道编码以降低错误率；安全性可通过信息的加密强度来衡量。提高安全性的措施是，采用强度高的加密和伪装技术。,1.2.2 仙农信息论,信息论是在概率论、随机过程和通信技术相结合的基础上发展起来的学科，可分为狭义信息论和广义信息论。

19、狭义信息论即仙农信息论或经典信息论，所研究的基本问题是：信源、信道及编码问题，核心是三个编码定理。广义信息论包括，仙农或经典信息论、信源编码、信道编码、近代信息论、统计通信理论、通信网理论、信号与信息处理、保密通信等。,仙农信息论的内容可用一句话概括为：“一个概念，三个定理”，就是信息熵的概念和三个编码定理。,1关于信源信息的度量 如前所述，仙农将信源限制为具有某一先验概率的随机过程，对信息进行量度是信息论的首要问题。仙农定义了信息熵作为信源所含信息的量度，是信息论中最重要的概念。信息熵的含义与应用以及不同于仙农定义的信息量度方法是研究的主要内容。,2.无失真信源编码定理（仙农第一定理）无失真

20、信源编码定理，也称仙农第一定理，是信源压缩编码的理论基础，其内容是:如果信源编码码率（编码后传送信源符号所需比特数）不小于信源的熵，就存在无失真编码，反之，不存在无失真编码。可以简述为：其中，R为信源编码码率，H为信源的熵。,编码,例如，英文字母加空共27符号，用代码传送，每个符号需5比特。但通过试验发现，实际的英文字母信源熵大约为1.4比特/符号，所以根据仙农第一定理，存在某种信源编码方式，使得每字母仅用1.4个二进制符号就能无失真传送，这样可以显著提高传输效率。由于定理解决的是信源无损压缩极限的理论问题，并未给出普遍的信源编码的方法，所以寻找接近或达到信源熵的压缩编码技术、分析其性能并有效

21、实现是研究的主要问题。,3.关于信道容量与信息的可靠传输 有噪信道编码定理（仙农第二定理）是信道编码的理论基础，其内容是：如果信息传输速率小于信道容量，则总可找到一种编码方式使得当编码序列足够长时传输差错任意小，反之不存在使差错任意小的编码。可以简述为：其中，R为信息传输速率，也称信道编码码率，C为信道容量。,存在译码差错任意小的编码,例如，一个带宽为3kHz的系统，用二进符号传输，如果不进行信道编码，无码间干扰的最大传输速率为6kbps，按照仙农AWGN信道容量公式可知，通过合适的信道编码，在信噪比为26dB的条件下，实现可靠传输的最大速率可达到25.6kbps。,由于信道类型的复杂性，所以

22、根据实际研究的问题建立信道模型，分析特性，计算容量以及在这些信道条件下各类通信系统的性能是研究的主要问题。此外，定理解决的是信息传输极限的理论问题，并未给出普遍的信道编码的方法，所以寻找接近或达到信源信道容量的信道编码技术、分析其性能并有效实现也是研究的主要问题。不过这些内容主要归入信道编码理论与技术的范畴。,4信息率失真理论（数据压缩的理论基础）在很多情况下，我们并不需要信息精确的传输，而是容许有一定限度差错的传输。这样在保证获取足够信息的前提下，可以提高传输效率，降低通信成本。仙农指出：“实际上，当我们有一个连续信源时，我们感兴趣的不是精确的传输，而只是在一个给定容限内的传输。问题就是，当

23、我们仅需要一定的以合适方式度量的恢复保真度时，我们能不能给连续信源分配一个确定的速率。”为实现限失真传输的有效性，我们总是希望在满足一定的失真要求条件下，使编码器的码率最小，这是一个最优有损数据压缩编码的理论问题，其理论基础就是信息率失真理论，核心是限失真信源编码定理。,限失真信源编码定理（仙农第三定理）的是有损压缩编码的理论基础，其内容是：对任何失真测度D 0，只要码字足够长，总可找到一种编码，使得当信源编码的码率 R（D）时，码的平均失真 D；反之，如果信源编码的码率 R（D），就不存在平均失真 D的编码。可以简述为：其中，R为信源编码码率，R（D）称为信息率失真函数，是满足失真准则（平均

24、失真 D）下，每信源符号所需最小编码比特数。,例如，一个等概率16个符号的离散信源，如果要求不失真信源编码，那么每个信源符号需要4个二进制符号，即平均码长为4比特。但如果允许失真，就可以减小平均码长。如果要求平均失真不超过1/2，即对编码序列进行译码时，最多允许1/2的错误。很明显，我们可以将信源的前7个符号分别编码，而信源的后9个符号都编成一个相同的（第8个）码字传输，在接收端译码时，接收到前7个码字与接收端符号表的前7符号一一对应，无译码差错。当接收到第8个码字时，随机的译成接收端符号表中第8个码字,随机的译成接收端符号表中第8到第16个符号中的任意一个。总译码正确率为7/16+1/16=

25、1/2，所以错误率也为1/2，即编码失真为1/2。如果用最优二元编码（例如，Huffman编码）可以计算，编码的平均码长可达2.25比特，小于4比特。但是，在理论上，同样的信源，为实现1/2差错率的信源编码最小的码长由R(D)函数来决定，为1.05比特。,与无失真信源编码类似，限失真信源编码定理解决了有损压缩极限的理论问题，也未给出实际的有损信源编码的方法。在各种失真度准则下对信源R（D）函数的研究，利用率失真理论对实际有损压缩编码性能的分析，寻找接近或达到理想有损压缩的信源编码方法是该领域研究的主要问题。,5.信息论的特点以概率论、随机过程为基本研究工具；研究通信系统的整个过程，而不是单个环

26、节，并以编、译码器为重点；关心的是最优系统的性能和怎样到达这个性能（并不具体设计系统）；语法信息中的概率信息，要求信源为随机过程。,1.3 仙农信息论研究的进展与应用,本节主要内容：仙农信息论创立的背景 仙农的主要贡献 仙农信息论的研究进展仙农信息论的应用,13.1 仙农信息论创立的背景,仙农的信息论的创立主要是由于仙农的杰出贡献，但也与当时的技术发展背景和前人的工作密不可分。当时通信理论与技术已有较大发展，存在的主要通信技术与手段有：电报(Morse,1830s)、电话(Bell,1876)、无线电报(Marconi,1887)、AM 无线电(1900s 早期)、单边带调制(Carson,1

27、922)、电视(1925-1927)、电传(1931)、调频(Armstrong,1936)、脉码调制(Reeves,1937-1939)、声码器(Dudley,1939)、扩频(1940s)等。,1948年以前，Nyquist，Hartley等人也做了许多有影响的工作。例如Nyquist发现传输速率正比于在单位时间信号电平数目的对数（1924）；Hartley提出“传输速率”，“码间干扰”，“系统传输信息的容量”等术语；Wiener，Rice等人把随机过程作为通信工程师的工具。所有这些都为信息理论的建立产生了重要影响,热力学对仙农信息论的创立也产生很大影响，仙农提出用熵作为信息的度量，实际上

28、也参考了热熵的概念。人们对热熵的认识主要有三个阶段：最早由克劳修斯提出宏观熵的公式：S=Q/T，其中S为熵的变化，Q为宏观系统热量的变化，T为绝对温度。波尔兹曼提出微观系统的熵和微观系统状态数的对数成正比，后来由普郎克总结成公式：S=klog，其中k为波尔兹曼常数，为系统的微观系统状态数，该公式称为波尔兹曼方程。吉布斯提出在微观系统状态概率不等情况下的热熵计算公式：S=-kipilogpi，该公式称为吉布斯方程。实际上，除常数k外，仙农熵和吉布斯方程的热熵表达式相同。,1.3.2 仙农的主要贡献,在信息论的产生与发展过程中仙农所起的作用是关键性的，主要列举如下：1948年，发表通信的数学理论，

29、奠定了信息论的理论基础。1956年，发表The Zero-Error Capacity of a Noisy Channal（噪声信道的零差错容量），指出当不允许有任何传输错误时，信道编码的概率方面问题消失，而仅保留图论方面的问题，开创了零差错容量的研究领域。,1959年，发表Coding Theorem for a Discrete Source with a Fidelity Criterion（在保真度准则下的离散信源编码定理），给出率失真定理的简单详细的证明，然后推广到更一般的信源和失真测度，最后到模拟信源，推动了信息率失真理论研究。,1961年，发表Two-Way Communica

30、tion Channels（双路通信信道），将信息论应用到连接两个点A、B的信道，其中A、B需要双向通信，但两个方向互相干扰的情况，证明了信道的容量区域是凸的，并建立了此区域的内外边界，从而开拓了多用户理论（现称做网络信息论）的研究。,1.3.3 仙农信息论的研究进展,五十多年来，无论是理论方面，还是应用方面，仙农信息论得到很大的发展。可分以下四个方面来叙述。1信息的量度 仙农熵作为信息的量度，是信息论中最重要的概念，在这方面有两个重要研究内容，一是以仙农熵为基础，研究信源信息熵的估计方法，二是将信息熵用做推断工具的最大熵原理，另外就是提出新的信息量度方法，以适应新的应用，主要进展如下：,（1

31、）信息熵的估计 自从仙农信息论创立以来，已经提出了多种信息熵估计方法，并得到广泛应用，信息熵估计技术就是研究的热点之一。当前，信息熵估计方法已经从主要针对文本、图象等一般信源，转移到针对特殊信源（例如DNA序列熵的估计）的研究。,（2）最大熵原理 1957年，统计物理学家Jaynes，根据仙农熵的概念，提出了当已知条件不充分时利用部分信息推断概率分布的方法，称为最大熵原理。它的基本思想是，求满足某些约束的信源事件概率分布时，应使得信源的熵最大，这样可以使我们依靠有限的数据达到尽可能客观的效果，克服可能引入的偏差。当前，最大熵原理已经应用于多个领域，其中包括信号检测与处理、模式分类、自然语言处理

32、，生物医学，甚至经济学领域，都取得很好的效果。,3）Kolmogorov熵 上世纪60年代，Kolmogorov等提出一种与概率无关的信息量度，称为Kolmogorov算法熵。在数值y给定条件下使计算机输出x值最短的程序的长度，定义为在y条件下x的条件算法熵。算法熵可以作为算法复杂度的度量。,（4）Renyi熵 Renyi熵有一个参数，是仙农熵的单参数推广。Renyi熵称为与概率分布有关的阶的信息度量，不满足可加性；当1时，收敛于仙农熵。Renyi熵在很多领域都有应用，例如生物学、医学、遗传学、语言学、经济学和电器工程、计算机科学、地球物理学、化学和物理学等，在图象处理技术中也有应用，也广泛用

33、于量子系统的研究，特别是用于量子纠缠态、量子通信协议、量子相关性的分析等。,（5）Tsallis熵 表示大范围的相互作用或长时间的记忆系统可能不满足遍历性，例如引力系统、Levy fligHts、分形现象、湍流物理、甚至经济学等领域，称为非广延系统。已经证明，波尔兹曼吉布斯统计学不适于这类系统。1988年，由Tsallis提出一种适用于非广延系统的信息度量，推广了波尔兹曼吉布斯熵，称作 Tsallis熵。它也是仙农熵的单参数（q）推广，满足伪可加性；当q1时，收敛于仙农熵。当前，Tsallis熵已经应用到很多系统，例如Levy异常扩散、自引力系统、星系的特殊速度、线性响应理论、扰动与变分方法、

34、格林函数、光子-电子相互作用、低维耗散系统等。通常认为，Tsallis熵适用于非规则的但又不完全随机或混沌的运动的处理。Tsallis熵在信息处理的应用也是当前研究的热点之一。,2.无损数据压缩 无损数据压缩的理论基础是仙农第一定理，主要包括概率匹配编码（也称熵编码）和通用编码的理论与技术。主要进展如下：（1）熵编码的进展Huffman解决了从固定到可变长度最优编码的构造，即Huffman编码；Tunstall解决了可变到固定长度最优编码的构造，即Tunstall编码；Golomb提出了可变到可变长度最优编码，即Golomb编码；Rissanen等提出算术编码（非分组码）；,（2）通用编码的进

35、展由A.Lempel和J.Ziv提出的方法（L-Z算法）是当前最广泛使用的通用编码方法，该方法基于对信源序列的分段，简单的分段原则使编译码都很简单，已经证明L-Z算法对任何平稳遍历信源都能以熵率编码；Broose和Wheeler提出基于Broose-Wheeler变换的压缩编码，性能优于LZ系列的编码；Cleary和 Witten提出部分匹配预测（Prediction by Partial Matching,PPM）压缩编码，是压缩率最好的编码；,在提高瞬时压缩效率的编码方面，Rissanen提出上下文树模型，由F.Willems等提出了上下文树加权编码方法，该方法实际是用文本树加权的方法估计

36、条件概率对信源序列进行算术编码，理论与实验证明这种方法的编码速率达到熵率。（3）分布信源编码D.Slepian和J.Wolf提出相关信源编码是数据压缩理论的最重要的进展之一。他们证明，即使对两个相关信源分别编码但联合译码，所需总的编码速率也可以小于两个信源熵的和。此外具有边信息的信源编码和数据压缩的研究还在开展。,3.可靠通信 可靠通信的理论基础是仙农第二定理，它的进展主要包括以下方面：（1）各种特殊信道容量与有关的编译码技术研究高斯信道的研究；衰落信道的研究反馈信道的研究；迭代译码的研究；,有约束信道（仙农称做离散无噪声信道）的容量的研究（成为有约束序列编码的理论基础，这些技术广泛应用在磁与

37、光记录设备中）；零差错信道容量（这是仙农开辟的另一个研究领域，信息可以无错误编码的速率称零差错容量，这种容量的研究不同与非零差错容量的研究，它要以组合图论作为研究工具）的研究,（2）多用户信道的研究多接入信道、无记忆高斯多接入信道容量区域、干扰信道、广播信道、未知参数信道、窃听信道等，都是多用户信道研究的内容，现已构成信息论中的一个重要分支网络信息论。（3）多入多出（MIMO）信道与空时编码的研究Paulraj、Telatar、Foschini等人的工作奠定了空时信道研究的理论基础，Tarokh提出了空时格码技术，推动了空时编码的研究，对无线系统中多天线以及空时编码与调制技术的研究已成为新的研

38、究领域。,（4）编译码理论与技术的研究Berlekamp系统总结了代数编码理论；BCH、RS码、卷积码、级联码以及TCM编码调制的出现大大提高了通信的可靠性；Berrou等提出的Turbo码和Gallager首先提出后来被重新认识的LDPC（低密度奇偶校验）码是信道编码理论研究的重要里程碑，其性能已经接近仙农的信道容量界限。3）信道编码定理的研究,4.有损数据压缩 有损数据压缩的理论基础是信息率失真理论，它的进展主要包括以下方面：（1）Berger给出了更一般的率失真编码定理，发展了信息率失真编码理论；（2）Wyner和Ziv研究了在译码器具有边信息的有损信源编码问题，推动了多端有损压缩编码的

39、研究；（3）Hajek和Berger建立了随机场率失真编码理论的基础；,（4）Yang和Kieffer证明，对于信源统计特性和失真测度都通用的有损压缩编码是存在的，为通用有损压缩编码的研究提供了理论依据；（5）信源和信道联合编码；（6）实现有损压缩的技术得到很大发展，其中包括：标量与矢量量化、预测编码、变换编码等。这些技术都成功应用到语音、图象、视频以及多媒体的压缩编码中。,1.34 仙农信息论的应用,仙农信息论产生于通信，所以它最重要的应用就在通信领域，除此以外，仙农信息论已经渗透到多种其他学科，并取得了成功，其重要应用概括如下：1.信息论是评估通信系统性能优劣的基本标准。仙农信息论解决了通

40、信系统传输有效性和传输可靠性性能指标的理论问题。在实际工作中将通信系统实际的性能指标与仙农指出的理论界限相比较，可以评估该系统性能的优劣，从而确定系统性能改进的方向，达到预期的目的,2.信息论提供从全局的观点观察和设计通信系统的理论方法。信息论提供的是一系列支持通信实践的指导原则，而某些数学原理仅处理通信系统的个别的方面。例如，在通信系统的设计中，给定信源编码的失真度要求、信道容量信息传输速率，那么信源编码和信道编码的方式可以自由选择，因此可以设计不同的方案，但是可能对应不同的设备复杂度和成本。利用仙农信息论可以从全局考虑设计问题，从而达到通信系统的最佳设计。,信息论是从事与信息处理有关的研究

41、、开发与管理人员的必备知识。信息论并不仅仅是通信的数学理论，而且它的处理方法适用于很宽的信息处理领域，所以也是从事与信息行业有关的各类人员必备的知识。实践证明，不掌握信息论的基本原理，往往不能从全局的角度处理具体的信息处理问题，限制了解决问题的思路。4.信息论在其他领域的应用已获得很大的成功 除通信、计算机、信号处理和自动控制领域（电子信息领域）等外，信息理论方法已经渗透到生物学、医学、气象学、水文环境学、语言学、社会学和经济学等诸多领域，并取得成功。本书的第12章列举了仙农信息论的主要应用，包括信源熵的估计、最大熵最小交叉熵原理及其最大熵法在自然语言处理、经济学等领域的应用等。,11 信息论是何时创立的？创始人是谁？12 信息和物质、能量有什么联系与区别？13 从认识论层次上看，信息分成几个层次，这些层次的含义和它们之间的关系如何？14 通信系统的主要性能指标是什么，如何衡量？如何提高这些性能指标？15 仙农信息论研究的是什么层次信息？研究的主要内容是什么？16 通信系统模型分成几部分？各自的功能如何？17 仙农的三个编码定理的内容是什么？18 简述仙农信息论的研究进展。19 如何理解学习仙农信息论的重要性？,思考题,谢谢大家！,