第1讲——信息论的对象与方法

1、 教材教材信息论与编码理论信息论与编码理论，王育民、李晖编，高等教育出版社王育民、李晖编，高等教育出版社 参考书参考书1.Elements of Information Theory, Thomas M. Cover, Joy A. Thomas著著2.信息论信息论基础理论与应用基础理论与应用,傅祖芸编傅祖芸编,电子工业出版社电子工业出版社3.应用信息论基础应用信息论基础，朱雪龙编，清华大学出版社，朱雪龙编，清华大学出版社什么是信息什么是信息?科学名词科学名词： 统计数学、通信技术统计数学、通信技术 用严格的用严格的数学公式数学公式定义的科学名词，它定义的科学名词，它与与 内容无关内容无关，而

2、且不随信息具体表现形式的，而且不随信息具体表现形式的 变化而变化，因而变化而变化，因而也独立于形式也独立于形式。情报、知识、消息情报、知识、消息计算机处理中的数据、文字计算机处理中的数据、文字广义信息广义信息：技术术语技术术语：是事物运动状态或存在方式不确定性的描述。是事物运动状态或存在方式不确定性的描述。情报情报知识知识消息消息信 源信 源输 出输 出码 字码 字输 出输 出消 息 先消 息 先验 概 率验 概 率消息后验概率消息后验概率收到收到0 收到收到01收到收到011x1x2x3x4x5x6x7x80000010100111001011101111/81/81/81/81/81/81

3、/81/8信息、消息和信号信息、消息和信号 信息信息 是事物运动状态或存在方式是事物运动状态或存在方式不确定性不确定性的描述。的描述。 消息消息 是指包含有信息的语言、文字和图像等是指包含有信息的语言、文字和图像等 。 信号信号 是消息的物理体现。是消息的物理体现。 信 源信 源输 出输 出码 字码 字输 出输 出消 息 先消 息 先验 概 率验 概 率消息后验概率消息后验概率收到收到0 收到收到01收到收到011x1x2x3x4x5x6x7x80000010100111001011101111/81/81/81/81/81/81/81/8消息消息 信号信号Shannon信息定义信息定义信源信

4、源信道信道信宿信宿噪声或干扰噪声或干扰简单通信系统框图简单通信系统框图不知、不确定不知、不确定消除或部分消除消除或部分消除不知、不确定不知、不确定信息的特征信息的特征 不确定性，接收者在收到信息之前，对它不确定性，接收者在收到信息之前，对它的内容是不知道的；的内容是不知道的； 信息能使认识主体对某一事物的未知性或信息能使认识主体对某一事物的未知性或不确定性减少；不确定性减少； 信息是可以量度的信息是可以量度的不确定性不确定性 【例例】摸球试验摸球试验 甲袋共甲袋共100个球，红球白球各个球，红球白球各50个；乙袋共个；乙袋共100个个球，红、白、蓝、黑球各球，红、白、蓝、黑球各25个；现随意从

5、甲袋或个；现随意从甲袋或乙袋中取出一球，并猜测取出球的颜色？乙袋中取出一球，并猜测取出球的颜色？事物出现某状态不确定性的大小，与该状态出现事物出现某状态不确定性的大小，与该状态出现的的概率大小概率大小有关有关不确定性度量不确定性度量 【例例】气象预报气象预报 甲地： 乙地：4/1, 4/1, 4/1, 4/1)(小雨大雨阴晴ypY8/1, 8/1, 4/1, 2/1)(小雨大雨阴晴xpX事物出现某状态不确定性的大小，与该状态出现事物出现某状态不确定性的大小，与该状态出现的的概率大小概率大小有关有关不确定性度量不确定性度量输 入输 入消 息消 息码 字码 字输 出输 出消 息 先消 息 先验 概

6、 率验 概 率消息后验概率消息后验概率收到收到0 收到收到01收到收到011x1x2x3x4x5x6x7x80000010100111001011101111/81/81/81/81/81/81/81/81/41/41/41/40000001/21/2000000010000概率空间概率空间 样本空间样本空间 信源所有可能发送的消息符号信源所有可能发送的消息符号 先验概率先验概率p(xi) 选择符号选择符号xi作为发送消息的概率作为发送消息的概率)()()(2121nnxpxpxpxxxPX( ( )if p x不确定性大小不确定性大小( ( )f p x不确定性大小不确定性大小信息定义信息定

7、义应该满足以下应该满足以下3个条件个条件(1)0f( ( )f p x是单调减函数是单调减函数独立可加性独立可加性( ( ) ( )( ( )( ( )f p x p yf p xf p y1. 2. 3. 自信息自信息 条件自信息条件自信息 )(1log)(iixPxI1()log()ijijI x yp x y信息定义信息定义先验概率先验概率p(xi) 选择符号选择符号xi作为发送消息的概率作为发送消息的概率后验概率后验概率p(xi | yj) 接收端收到消息接收端收到消息yj后而发送端后而发送端 发的是发的是xi 的概率的概率输 入输 入消 息消 息码 字码 字输 出输 出消 息 先消

8、息 先验 概 率验 概 率消息后验概率消息后验概率收到收到0 收到收到01收到收到011x1x2x3x4x5x6x7x80000010100111001011101111/81/81/81/81/81/81/81/81/41/41/41/40000001/21/2000000010000香农定义的信息的优缺点香农定义的信息的优缺点 优优 点点 有明确的数学模型和定量计算公式有明确的数学模型和定量计算公式 与日常用语中的信息含意一致与日常用语中的信息含意一致 排除了对信息一词某些主观上的含意排除了对信息一词某些主观上的含意 局限性局限性 没有考虑收信者的主观特性和主观意义没有考虑收信者的主观特性

9、和主观意义 定义的出发点假定事物状态可以用一个概率模型来定义的出发点假定事物状态可以用一个概率模型来描述描述信息论研究对象信息论研究对象信道信道信源信源信源编码信源编码加密加密信道编码信道编码干 扰 源干 扰 源信宿信宿信源译码信源译码解密解密信道译码信道译码加密加密密钥密钥解密解密密钥密钥信息论研究目的信息论研究目的寻找信息传输过程中的共同规律，以提寻找信息传输过程中的共同规律，以提高信息传输的可靠性、有效性、保密性高信息传输的可靠性、有效性、保密性和认证性，使达到信息传输系统最优化和认证性，使达到信息传输系统最优化数字通信系统模型数字通信系统模型信道信道信源信源信源编码信源编码加密加密信道

10、编码信道编码干 扰 源干 扰 源信宿信宿信源译码信源译码解密解密信道译码信道译码加密加密密钥密钥解密解密密钥密钥信源信源信源编码信源编码信道信道信道编码信道编码信息论研究的内容信息论研究的内容 狭义信息论（香农基本理论）狭义信息论（香农基本理论） 主要研究信息的测度、信道容量以及信源和信道编主要研究信息的测度、信道容量以及信源和信道编码理论等问题。码理论等问题。 一般信息论一般信息论 除香农信息论，还包括噪声理论、信号滤波和预测、除香农信息论，还包括噪声理论、信号滤波和预测、统计检测和估计等。统计检测和估计等。 广义信息论广义信息论 不仅包括上述两方面内容，而且包括所有与信息有不仅包括上述两方

11、面内容，而且包括所有与信息有关的自然和社会领域，如模式识别、心理学等关的自然和社会领域，如模式识别、心理学等本课程研究的主要内容本课程研究的主要内容信源信源信道信道信宿信宿噪声源噪声源编码器编码器译码器译码器消息消息干扰干扰信号干扰信号干扰消息消息 信息论基础：信息量和熵（第信息论基础：信息量和熵（第2章）章） 信源编码（第信源编码（第3章）章） 信道及其容量（第信道及其容量（第4章）章） 信道编码定理（第信道编码定理（第5章）章） 线性分组码（第线性分组码（第6章）章） 率失真初步（第率失真初步（第9章）章）Claude Shannon (1916-2001) 1916年生于美国密歇根州的加

12、洛德镇，年生于美国密歇根州的加洛德镇， 2001年在马萨诸塞州辞世，享年年在马萨诸塞州辞世，享年85岁。岁。 阿尔茨海默症（退化性老年痴呆症）阿尔茨海默症（退化性老年痴呆症） 父亲是加洛德镇的法官，母亲是镇父亲是加洛德镇的法官，母亲是镇里中学校长，他生长在一个有良好教育里中学校长，他生长在一个有良好教育的环境，不过父母给他的科学影响好像的环境，不过父母给他的科学影响好像还不如祖父的影响大。还不如祖父的影响大。 香农的祖父是一位农场主兼发明家，香农的祖父是一位农场主兼发明家，发明过洗衣机和许多农业机械。发明过洗衣机和许多农业机械。 香农心目中的英雄是爱迪生，后来香农心目中的英雄是爱迪生，后来才知

13、道他与爱迪生还有远亲关系。才知道他与爱迪生还有远亲关系。Claude Shannon (1916-2001) 1936年在密歇根大学获数学与电气工程学士年在密歇根大学获数学与电气工程学士学位。学位。1938年在年在MIT获得电气工程硕士学位，获得电气工程硕士学位，硕士论文题目是硕士论文题目是A Symbolic Analysis of Relay and Switching Circuits(继电器与开继电器与开关电路的符号分析关电路的符号分析)。他把布尔代数的真与。他把布尔代数的真与假和电路系统的开与关对应起来假和电路系统的开与关对应起来,用布尔代用布尔代数分析并优化开关电路，奠定了数字电路

14、的数分析并优化开关电路，奠定了数字电路的理论基础。哈佛大学的理论基础。哈佛大学的Gardner教授说教授说“这这可能是本世纪最重要、最著名的一篇硕士论可能是本世纪最重要、最著名的一篇硕士论文文”。1940年在年在MIT获数学博士学位，博士获数学博士学位，博士论文关于人类遗传学的，题目是论文关于人类遗传学的，题目是An Algebra for Theoretical Genetics(理论遗理论遗传学的代数学传学的代数学)。Claude Shannon (1916-2001) 就职于贝尔电话研究所，他受着前辈的工就职于贝尔电话研究所，他受着前辈的工作的启示作的启示, 在信息论的领域中钻研了在信息

15、论的领域中钻研了8年之年之久，终于在久，终于在1948年也在年也在贝尔系统技术杂贝尔系统技术杂志志上发表了上发表了244页的长篇论著页的长篇论著通信的通信的数学理论数学理论,次年次年,他又在同一杂志上发表他又在同一杂志上发表了另一篇名著了另一篇名著噪声下的通信噪声下的通信，这两篇，这两篇文章成了信息论的奠基著作。在这两篇论文章成了信息论的奠基著作。在这两篇论文中，香农解决了过去许多悬而未决的问文中，香农解决了过去许多悬而未决的问题：阐明了通信的基本问题，给出了通信题：阐明了通信的基本问题，给出了通信系统的模型，提出了信息量的数学表达式，系统的模型，提出了信息量的数学表达式，并解决了信道容量、信

16、源统计特性、信源并解决了信道容量、信源统计特性、信源编码、信道编码等一系列基本技术问题。编码、信道编码等一系列基本技术问题。两篇论文成为了信息论的基础性理论著作。两篇论文成为了信息论的基础性理论著作。那时，他才不过刚刚三十出头。那时，他才不过刚刚三十出头。 Claude Shannon (1916-2001) Shannon所给出的编码定理的证明是非构造性所给出的编码定理的证明是非构造性的，所给出的证明也不够严格，但的，所给出的证明也不够严格，但“他的数学他的数学直观出奇地正确直观出奇地正确” (A. N. Kolmogrov，1963)，他是，他是“最近几十年最伟大的工程师之一，同最近几十年

17、最伟大的工程师之一，同时是最伟大的数学家之一。时是最伟大的数学家之一。”经过无数科技工作者经过无数科技工作者50年来的努力奋斗，人年来的努力奋斗，人们不仅在数学上已严格地证明了们不仅在数学上已严格地证明了Shannon编码编码定理，而且发现了各种具体可构造的有效编定理，而且发现了各种具体可构造的有效编码理论和方法，可以实现码理论和方法，可以实现Shannon指出的极限。指出的极限。文章曾遭受到数学家的抨击，责难文章曾遭受到数学家的抨击，责难Shannon的一些结果未经证明，在数学上不严格，靠的一些结果未经证明，在数学上不严格，靠不大住。不大住。Shannon对此评论说，对此评论说，“我不喜欢我

18、不喜欢他的评论，他并未仔细看这篇文章。我确信他的评论，他并未仔细看这篇文章。我确信我是正确的，我清楚地知道我所做的。我是正确的，我清楚地知道我所做的。” Claude Shannon (1916-2001) 为了表彰为了表彰Shannon的伟大功绩的伟大功绩，IEEE Information Society的的25名成员于名成员于2000年年10月月6日在儿童时代的老家日在儿童时代的老家Gaylord镇举行了镇举行了Shannon塑像的落成典礼。塑像的落成典礼。 著名信息论和编码学者著名信息论和编码学者Dr. Richard Blahut 在在Shannon塑像的落成典礼时的题塑像的落成典礼时

19、的题词说：词说：“在我看来，两三百年之后，当人在我看来，两三百年之后，当人们回过头来看我们这个时代的时候，他们们回过头来看我们这个时代的时候，他们可能不会记得谁曾是美国的总统。他们也可能不会记得谁曾是美国的总统。他们也不会记得谁曾是影星或摇滚歌星。但是仍不会记得谁曾是影星或摇滚歌星。但是仍然会知晓然会知晓Shannon的名字。学校里仍然会的名字。学校里仍然会讲授信息论。讲授信息论。”Claude Shannon (1916-2001) 他的同事他的同事D. Slepian写到：写到：“我们大家都带我们大家都带着午饭来上班，饭后在黑板上玩玩数学游着午饭来上班，饭后在黑板上玩玩数学游戏，但克劳德很

20、少过来。他总是白天关起戏，但克劳德很少过来。他总是白天关起门来工作，晚上则骑着他的独轮车来到贝门来工作，晚上则骑着他的独轮车来到贝尔实验室。但是，如果你要找他，他会非尔实验室。但是，如果你要找他，他会非常耐心地帮助你。他能立刻抓住问题的本常耐心地帮助你。他能立刻抓住问题的本质。他真是一位天才，在我认识的人中，质。他真是一位天才，在我认识的人中，我只对他一人使用这个词。我只对他一人使用这个词。”1. 兴趣驱动，淡漠名利兴趣驱动，淡漠名利 自述道：自述道：“我总是受我的兴趣驱动，不大关心其经济价值或对于世我总是受我的兴趣驱动，不大关心其经济价值或对于世界的价值。界的价值。”2. 探索股市，变得富有

21、探索股市，变得富有 思索股票价格起伏的规律性和信息论应用于投资的可能性。思索股票价格起伏的规律性和信息论应用于投资的可能性。 在投资股票方面很成功，并变得富有。在投资股票方面很成功，并变得富有。3. 心灵手巧，善制机器心灵手巧，善制机器 制作计算器制作计算器Throbac和玩六连棋的机器和玩六连棋的机器Hex。 研究计算机下棋、老鼠走迷宫、杂技演员最多能控制多少个球，要研究计算机下棋、老鼠走迷宫、杂技演员最多能控制多少个球，要抛多高才行？机器解魔方问题以及用计算机研究和进行股票投资等。抛多高才行？机器解魔方问题以及用计算机研究和进行股票投资等。4. 酷爱杂技，乐在其中酷爱杂技，乐在其中 曾制作

22、杂耍机，成为杂耍机器人的先驱。曾制作杂耍机，成为杂耍机器人的先驱。 Shannon的大师风范的大师风范1924年年 奈奎斯特奈奎斯特 “影响电报速率的一些因素影响电报速率的一些因素”1928年年 哈特莱哈特莱 “信息的传输信息的传输”信息速率与信道带宽成正比信息速率与信道带宽成正比 给出了信息度量方法给出了信息度量方法 1936年年 阿姆斯特朗阿姆斯特朗 增大带宽可以提高抗干扰能力增大带宽可以提高抗干扰能力 1948年年 Shannon “通信的数学理论通信的数学理论”用概率论的方法研究通信系统，是现代信息用概率论的方法研究通信系统，是现代信息论开创性的权威论文论开创性的权威论文 信息论的形成

23、信息论的形成 1948年香农提出了无失真信源定理，给出了简年香农提出了无失真信源定理，给出了简单的编码方法单的编码方法(香农编码香农编码) 1952年年Fano码，码，Huffman码码 1968年埃利斯年埃利斯(PElias)提出了算术编码的初提出了算术编码的初步思路步思路; 1976 Rissanen给出和发展了算术编码给出和发展了算术编码 1982年他和兰登年他和兰登(GGLangdon)一起将算术一起将算术编码系统实现化编码系统实现化 1977,1978年年Ziv和和Lempel的的LZ通用信源编算法通用信源编算法无失真信源编码发展无失真信源编码发展 1959年，年，Shannon提出

24、率失真函数和率失真提出率失真函数和率失真信源编码定理信源编码定理 1971年，伯格尔年，伯格尔(TBerger)给出更一般信给出更一般信源的率失真编码定理源的率失真编码定理 率失真信源编码理论是信源编码的核心问率失真信源编码理论是信源编码的核心问题，是频带压缩、数据压缩的理论基础题，是频带压缩、数据压缩的理论基础 目前，已提出多种限失真编码方案如音频、目前，已提出多种限失真编码方案如音频、视频视频:MPEG,JEPG等等率失真信源编码发展率失真信源编码发展 1950年汉明码年汉明码 1960年卷积码的概率译码，年卷积码的概率译码，Viterbi译码译码 1982年年Ungerboeck编码调制

25、技术编码调制技术 1993年年Turbo编译码技术编译码技术 目前，已构造出性能接近香农限的好码，目前，已构造出性能接近香农限的好码，如如Turbo(PCC,SCC,TPC,LDPC) 码码信道编码发展信道编码发展 香农在香农在1949年发表的年发表的“保密通信的信息理论保密通信的信息理论”论文中，首先用信息论的观点对信息保密问题论文中，首先用信息论的观点对信息保密问题作了全面的论述。作了全面的论述。 1976年迪弗年迪弗(Diffe)和海尔曼和海尔曼(Hellman)发表了发表了“密码学的新方向密码学的新方向”一文，提出了公开密钥密一文，提出了公开密钥密码体制，保密通信问题才得到广泛研究。码

26、体制，保密通信问题才得到广泛研究。 人们把初等数论、矩阵、近世代数等引入保密人们把初等数论、矩阵、近世代数等引入保密问题的研究，已形成了独树一帜的分支问题的研究，已形成了独树一帜的分支密密码学理论。码学理论。 密码学发展密码学发展信息论的主要研究成果信息论的主要研究成果 语音信号压缩语音信号压缩 长途电话网标准长途电话网标准 1972年年 CCITT G.711标准中的标准中的 64kbit/s， 1995年年 CCITT G. 723.1标准中的标准中的 6.3kbit/s。 移动通信中移动通信中 1989年年 GSM标准中语音编码速率为标准中语音编码速率为13.2 kbit/s 1994年

27、年 在为半码速在为半码速GSM研究的研究的VSELP编码算法中，编码算法中，码速率为码速率为5.6kbit/s 目前在实验室中已实现目前在实验室中已实现600bit/s的低速率语音编码，特的低速率语音编码，特别是按音素识别与合成原理构造的声码器其速率可低别是按音素识别与合成原理构造的声码器其速率可低于于100bit/s，已接近信息论指出的极限。，已接近信息论指出的极限。信息论的主要研究成果信息论的主要研究成果 图像信号压缩图像信号压缩 1989年年 CCITT提出电视电话提出电视电话/会议电视的压缩标准会议电视的压缩标准H.261,其压缩比达到其压缩比达到25:1到到48:1左右左右 1991

28、年年 CCITT与与ISO联合提出的联合提出的“多灰度静止图像多灰度静止图像压缩编码压缩编码”标准标准JPEG,其压缩比为其压缩比为24:1 在运动图像方面在运动图像方面,运动图像专家组继成功定义了运动图像专家组继成功定义了MPEG-1和和MPEG-2之后之后,于于1993年年7月开始制订全新月开始制订全新的的MPEG-4标准。随着标准。随着MPEG-4标准的不断扩展标准的不断扩展,它它不但能支持码率低于不但能支持码率低于64kbit/s的多媒体通信的多媒体通信,也能支也能支持广播级的视频。持广播级的视频。 降低信息传输所需的功率降低信息传输所需的功率 在远距离无线通信在远距离无线通信,特别是深空通信中如何降低信息传特