1.信息论简介

信息论基础赵春明[e-mail]参考书1．信息论—基础理论与应用，傅祖芸编，电子工业出版社2．应用信息论基础，朱雪龙编，清华大学出版社3.ThomasM.Cover,Joya.Thomas“ElementsofInformationTheory”4.RaymondW.YeungInformationTheoryandNetworkCoding信息论简介信息论简介信息论简介第一章第一章什么是信息?科学名词：统计数学、通信技术–用严格的数学公式定义的科学名词，它与内容无关，而且不随信息具体表现形式的变化而变化，因而也独立于形式。情报、知识、消息计算机处理中的数据、文字广义信息：技术术语：–是事物运动状态或存在方式不确定性的描述。情报知识消息信源输出码字输出消息先验概率消息后验概率收到0收到01收到011x1x2x3x4x5x6x7x80000010100111001011101111/81/81/81/81/81/81/81/8√√√√××××××√√×××××××√××××信息、消息和信号•信息–是事物运动状态或存在方式不确定性的描述。•消息–是指包含有信息的语言、文字和图像等。•信号–是消息的物理体现。信息、物质、能量是系统的三大要素，信息不可定义。信源输出码字输出消息先验概率消息后验概率收到0收到01收到011x1x2x3x4x5x6x7x80000010100111001011101111/81/81/81/81/81/81/81/8√√√√××××××√√×××××××√××××消息信号Shannon信息定义信源信道信宿噪声或干扰简单通信系统框图不知、不确定消除或部分消除不知、不确定信息的特征–不确定性，接收者在收到信息之前，对它的内容是不知道的；–信息能使认识主体对某一事物的未知性或不确定性减少；–信息是可以量度的不确定性【例】摸球试验甲袋共100个球，红球白球各50个；乙袋共100个球，红、白、蓝、黑球各25个；现随意从甲袋或乙袋中取出一球，并猜测取出球的颜色？事物出现某状态不确定性的大小，与该状态出现的概率大小有关不确定性度量【例】气象预报甲地：乙地：⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡4/1,4/1,4/1,4/1)(小雨大雨阴晴ypY⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡8/1,8/1,4/1,2/1)(小雨大雨阴晴xpX事物出现某状态不确定性的大小，与该状态出现的概率大小有关不确定性度量输入消息码字输出消息先验概率消息后验概率收到0收到01收到011x1x2x3x4x5x6x7x80000010100111001011101111/81/81/81/81/81/81/81/81/41/41/41/40000001/21/2000000010000概率空间•样本空间–信源所有可能发送的消息符号•先验概率p(xi)–选择符号xi作为发送消息的概率⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡)()()(2121nnxpxpxpxxxPX(())ifpx不确定性大小(())fpx不确定性大小信息定义应该满足以下3个条件(1)0f=(())fpx是单调减函数独立可加性(()())(())(())fpxpyfpxfpy=+1.2.3.•自信息•条件自信息)(1log)(iixPxI=1()log()ijijIxypxy=信息定义先验概率p(xi)－选择符号xi作为发送消息的概率后验概率p(xi|yj)－接收端收到消息yj后而发送端发的是xi的概率输入消息码字输出消息先验概率消息后验概率收到0收到01收到011x1x2x3x4x5x6x7x80000010100111001011101111/81/81/81/81/81/81/81/81/41/41/41/40000001/21/2000000010000香农定义的信息的优缺点•优点–有明确的数学模型和定量计算公式–与日常用语中的信息含意一致–排除了对信息一词某些主观上的含意•局限性–没有考虑收信者的主观特性和主观意义–定义的出发点假定事物状态可以用一个概率模型来描述信息论研究对象信道信源信源编码加密信道编码干扰源信宿信源译码解密信道译码加密密钥解密密钥信息论研究目的寻找信息传输过程中的共同规律，以提高信息传输的可靠性、有效性、保密性和认证性，使达到信息传输系统最优化数字通信系统模型信道信源信源编码加密信道编码干扰源信宿信源译码解密信道译码加密密钥解密密钥信源信源编码信道信道编码信息论研究的内容•狭义信息论（香农基本理论）–主要研究信息的测度、信道容量以及信源和信道编码理论等问题。•一般信息论–除香农信息论，还包括噪声理论、信号滤波和预测、统计检测和估计等。•广义信息论–不仅包括上述两方面内容，而且包括所有与信息有关的自然和社会领域，如模式识别、心理学等本课程研究的主要内容信源信道信宿噪声源编码器译码器消息干扰信号＋干扰消息•信息论基础：信息量和熵（第2章）•信源编码（第3章）•信道及其容量（第4章）•信道编码定理（第5章）•线性分组码（第6章）•无记忆信源的有失真编码（第9章）ClaudeShannon(1916-2001)1916年生于美国密歇根州的加洛德镇，2001年在马萨诸塞州辞世，享年85岁。阿尔茨海默症（退化性老年痴呆症）父亲是加洛德镇的法官，母亲是镇里中学校长，他生长在一个有良好教育的环境，不过父母给他的科学影响好像还不如祖父的影响大。香农的祖父是一位农场主兼发明家，发明过洗衣机和许多农业机械。香农心目中的英雄是爱迪生，后来才知道他与爱迪生还有远亲关系。ClaudeShannon(1916-2001)1936年在密歇根大学获数学与电气工程学士学位。1938年在MIT获得电气工程硕士学位，硕士论文题目是《ASymbolicAnalysisofRelayandSwitchingCircuits》(继电器与开关电路的符号分析)。他把布尔代数的真与假和电路系统的开与关对应起来,用布尔代数分析并优化开关电路，奠定了数字电路的理论基础。哈佛大学的Gardner教授说“这可能是本世纪最重要、最著名的一篇硕士论文”。1940年在MIT获数学博士学位，博士论文关于人类遗传学的，题目是《AnAlgebraforTheoreticalGenetics》(理论遗传学的代数学)。ClaudeShannon(1916-2001)就职于贝尔电话研究所，他受着前辈的工作的启示,在信息论的领域中钻研了8年之久，终于在1948年也在《贝尔系统技术杂志》上发表了244页的长篇论著《通信的数学理论》,次年,他又在同一杂志上发表了另一篇名著《噪声下的通信》，这两篇文章成了信息论的奠基著作。在这两篇论文中，香农解决了过去许多悬而未决的问题：阐明了通信的基本问题，给出了通信系统的模型，提出了信息量的数学表达式，并解决了信道容量、信源统计特性、信源编码、信道编码等一系列基本技术问题。两篇论文成为了信息论的基础性理论著作。那时，他才不过刚刚三十出头。ClaudeShannon(1916-2001)Shannon所给出的编码定理的证明是非构造性的，所给出的证明也不够严格，但“他的数学直观出奇地正确”(A.N.Kolmogrov，1963)，他是“最近几十年最伟大的工程师之一，同时是最伟大的数学家之一。”经过无数科技工作者50年来的努力奋斗，人们不仅在数学上已严格地证明了Shannon编码定理，而且发现了各种具体可构造的有效编码理论和方法，可以实现Shannon指出的极限。文章曾遭受到数学家的抨击，责难Shannon的一些结果未经证明，在数学上不严格，靠不大住。Shannon对此评论说，“我不喜欢他的评论，他并未仔细看这篇文章。我确信我是正确的，我清楚地知道我所做的。”ClaudeShannon(1916-2001)为了表彰Shannon的伟大功绩，IEEEInformationSociety的25名成员于2000年10月6日在儿童时代的老家Gaylord镇举行了Shannon塑像的落成典礼。著名信息论和编码学者Dr.RichardBlahut在Shannon塑像的落成典礼时的题词说：“在我看来，两三百年之后，当人们回过头来看我们这个时代的时候，他们可能不会记得谁曾是美国的总统。他们也不会记得谁曾是影星或摇滚歌星。但是仍然会知晓Shannon的名字。学校里仍然会讲授信息论。”ClaudeShannon(1916-2001)他的同事D.Slepian写到：“我们大家都带着午饭来上班，饭后在黑板上玩玩数学游戏，但克劳德很少过来。他总是白天关起门来工作，晚上则骑着他的独轮车来到贝尔实验室。但是，如果你要找他，他会非常耐心地帮助你。他能立刻抓住问题的本质。他真是一位天才，在我认识的人中，我只对他一人使用这个词。”1.兴趣驱动，淡漠名利自述道：“我总是受我的兴趣驱动，不大关心其经济价值或对于世界的价值。”2.探索股市，变得富有思索股票价格起伏的规律性和信息论应用于投资的可能性。在投资股票方面很成功，并变得富有。3.心灵手巧，善制机器制作计算器Throbac和玩六连棋的机器Hex。研究计算机下棋、老鼠走迷宫、杂技演员最多能控制多少个球，要抛多高才行？机器解魔方问题以及用计算机研究和进行股票投资等。4.酷爱杂技，乐在其中曾制作杂耍机，成为杂耍机器人的先驱。Shannon的大师风范1924年奈奎斯特“影响电报速率的一些因素”1928年哈特莱“信息的传输”－信息速率与信道带宽成正比－给出了信息度量方法1936年阿姆斯特朗－增大带宽可以提高抗干扰能力1948年Shannon“通信的数学理论”－用概率论的方法研究通信系统，是现代信息论开创性的权威论文信息论的形成–1948年香农提出了无失真信源定理，给出了简单的编码方法(香农编码)–1952年Fano码，Huffman码–1968年埃利斯(P．Elias)提出了算术编码的初步思路;1976Rissanen给出和发展了算术编码1982年他和兰登(G．G．Langdon)一起将算术编码系统实现化–1977,1978年Ziv和Lempel的LZ通用信源编算法无失真信源编码发展–1959年，Shannon提出率失真函数和率失真信源编码定理–1971年，伯格尔(T．Berger)给出更一般信源的率失真编码定理–率失真信源编码理论是信源编码的核心问题，是频带压缩、数据压缩的理论基础–目前，已提出多种限失真编码方案如音频、视频:MPEG,JEPG等率失真信源编码发展–1950年汉明码–1960年卷积码的概率译码，Viterbi译码–1982年Ungerboeck编码调制技术–1993年Turbo编译码技术–目前，已构造出性能接近香农限的好码，如Turbo(PCC,SCC,TPC,LDPC)码信道编码发展–香农在1949年发表的“保密通信的信息理论”论文中，首先用信息论的观点对信息保密问题作了全面的论述。–1976年迪弗(Diffe)和海尔曼(Hellman)发表了“密码学的新方向”一文，提出了公开密钥密码体制，保密通信问题才得到广泛研究。–人们把初等数论、近世代数等引入保密问题的研究，已形成了独树一帜的分支——密码学理论。–安全服务：认证性机密性不可否认性数据完整性访问控制可用性可信性密码学信任与信誉•定义1.信任(trust)是一种建立在已有知识上的主观判断,是主体A根据所处的环境,对主体B能够按照主体A的意愿提供特定服务(或者执行特定动作)的度量.•定义2.信誉(reputation)是对节点已有服务的质量或特性的综合度量,反映节点履行其承诺服务的水平及网络中其它节点对其信任程度.目前信息论的目前信息论的主要研究成果主要研究成果信息论的主要研究成果语音信号压缩•长途电话网标准–1972年CCITTG.711标准中的64kbit/s，–1995年CCITTG.723.1标准中的6.3kbit/s。•移动通信中–1989年GSM标准中语音编码速率为13.2kbit/s–1994年在为半码速GSM研究的VSELP编码算法中，码速率为5.6kbit/s•目前在实验室中已实现600bit/s的低速率语音编码，