第一讲信息熵课件

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,信息论基础,20,11,年,3,月,信息论基础,1,教材和参考书：,傅祖芸 编著信息论基础理论与应用，,电子工业出版社，,2006,，第二版,.,孟庆生,信息论,，西安交通大学，,1986,。,（数学家写的研究生教材，含编码和密码）,朱雪龙应用信息论基础，清华大学出版社,2000,。,（研究生教材，面向电子类，含编码方法。）,王育民、梁传甲信息与编码理论，西电教材。,（内容深入，推导过程少）,沈连丰、叶芝惠 编著信息论与编码,东南大学硕士教材，科学出版社，2004，,（面向通信专业）,。,教材和参考书：傅祖芸 编著信息论基础理论,2,周荫清主编信息理论基础 北航出版社，2006,（简洁，面向电子类）,T.M.Cover&J.A.Thomas,Elements of Information Theory,，,Addison-Wesley Pub,1990,清华影印。,R.J.McElieceThe Theory of Information and Coding,第二版，电子工业出版社，2003。,（,内容简练，编码方面较全）,*J.H.Van Lint Introduction to coding theory,GTM 86,Springer-Verlag,1998.,*Roman Coding and information theory,GTM 134,，,新的教材,：,在广义信息论、网络信息论方面的内容有所增加。,周荫清主编信息理论基础 北航出版社，2006,3,第一讲,1-1,信息论的主要内容,1-2,信息的度量信息熵,1-3,信息熵的性质,信息熵,第一讲 1-1 信息论的主要内容信息熵,4,1,1.,信息论的主要内容,香农信息论最初是为了解决通信问题而提出的。,通信的重要意义是勿庸置疑的。,人类传递思想、表达情感，就需要相互交流。,人类的劳动、生产、政治、文化、日常生活等都离不开通信。,人类利用眼、耳、鼻、舌、身等五种感觉器官来感受外界的信息，形成一个信息流通的体系。,通信方式的不断提高，代表了人类文明和科技水平的不断提高。,11.信息论的主要内容香农信息论最初是为了解决通信问题,5,通信的根本任务：将一地点的消息可靠地、有效地,传送到另一地点。,信源,干扰源,信道,信宿,通信系统的基本模型：,通信的根本任务：将一地点的消息可靠地、有效地信源干扰源信道信,6,为了使消息可靠地、有效地传送到信宿，就需要,对信源的消息进行处理；,信源编码：实现有效性；信道编码：实现可靠性,；,密码：实现保密性及认证性；,有没有可靠的、有效的处理方法？如何进行编码？,香农信息论奠定了通信的理论基础。,信息是消息的不确定性度量。,某消息出现的概率大，它的信息量就小，相反，某消息出现的概率小，则它的信息量就大。,通信的关键是信息的传输问题。,为了使消息可靠地、有效地传送到信宿，就需要信源编码：实现有,7,信源,信源编码,信宿,信道,信道编码,信道译码,信源译码,加密钥,加密,解密钥,解密,干扰源,信源信源编码信宿信道信道编码信道译码信源译码加密钥加密解密钥,8,提出的背景：,在香农信息论出现以前，没有系统的通信理论。,是香农，开创了信息论的研究，奠定了一般性通信,理论的基础。对数字通信技术的形成有很大贡献。,（不论什么样的干扰信道，抓住了本质问题。）,提出的背景：,9,(Shannon,19162001),“A Mathematical Theory of Communication”,“Communication Theory of Secrecy System ”,(Shannon,19162001)“A Mathe,10,About Claude Elwood Shannon:,1916,年生于,Gaylord,MI,的一个小镇。母亲是一个语言教师和中学校长，父亲是一个商人。,16,岁高中毕业，进入密西根大学。1936年获得电子工程和数学双学士学位。随后进入,MIT，,作为研究生和研究人员。一年后，完成布尔代数用于开关电路的硕士论文。1940年完成“关于遗传学的代数”的博士论文。,1941年以后进入,Bell,实验室。(新理论和技术的摇篮),1945年写出“密码学的数学理论”，1949年正式出版，名为“保密系统的通信理论”。1948年发表“通信系统的数学理论”。其后又取得通信、人工智能等多方面的成果。,About Claude Elwood Shannon:,11,信源,信道,信宿,噪声,信源熵,H,信源编码,R H,信号,信息,信道编码,R C,信源,解码,信道,解码,R,编码信息传输率,R,信道信息传输率,C,信道容量,N,L,n,L/N,L/n,信源信道信宿噪声信源熵信源编码信号信息信道编码信源信道R,12,香农信息论主要讨论如下内容：,1、围绕信息的度量所展开的讨论。这是信息论建立的基础，,给出了各种信息量和各种熵的概念；,2、围绕无失真信源编码所展开的讨论。最主要的结论是,香农第一定理以及各种信源编码方法。,3、围绕信道编码所展开的讨论。它给出了信息传输率、,信道容量等概念，最主要的结论是香农第二定理，以及,基于该定理的各种信道编码，如分组码、卷积码等。,4、,围绕带限信道传输的能力所展开的讨论，最主要的结论,是信道容量公式，即香农公式。,香农信息论主要讨论如下内容：,13,5、,基于信息传输时允许一定程度的失真和差错所展开,的讨论。由此得到信息率失真理论、香农第三定理、,信息价值等。这是目前还在不断发展和完善的理论，,在通信以外得学科不断得到应用。,6、,围绕通信网的发展带来的信息传输问题展开的讨论。,即网络信息理论，随着通信网、因特网的发展，它越,来越受到重视。,7、围绕通信的保密所展开的讨论。包括保密通信的技术,体制及其数学模型，传输线路保密技术的信息论基础，,信息保密技术的基础知识以及保密通信的各种方法。,5、基于信息传输时允许一定程度的失真和差错所展开,14,本课程的讲授内容：,第一讲信息熵,1.,信息论的主要内容,2.,信息的度量信息熵,3.,信息熵的性质,第二讲,信源的信息熵,1.,信源的描述,2.,无记忆扩展信源,3.,离散平稳信源,4.,马尔可夫信源,第三讲 平均,互信息,1.,信道和平均互信息,2.,平均互信息的性质,3.,数据处理定理,本课程的讲授内容：,15,第四讲信道容量及其计算,1.,信道容量,2,.,信道容量的计算,第五讲连续信源和信道,1.,连续信源的微分熵,2.,具有最大熵的连续信源,3.,连续信道和波形信道,4.,连续信道和波形信道的信道容量,第六讲 等长信源编码定理,1.,信源编码,2.,典型序列和信源划分定理,3.,等长信源编码定理,第七讲 变长信源编码定理,1,变长信源编码定理,2,Huffman,编码,第四讲信道容量及其计算,16,第八讲 有噪声信道编码定理,1.,错误概率与译码准则,2,FANO,不等式,3.,联合典型序列,4.,无失真信道编码定理,第九讲 限失真信源编码定理与多用户信息论,1.,信息率失真函数,2.,限失真信源编码定理,3.,相关信源编码,4,多址信道和广播信道,第十讲 通信系统的保密理论,1.,完全保密性,2.,理论保密性,3.,实际保密性,第八讲 有噪声信道编码定理,17,第十一讲 线性码,1.,线性码的一般概念,3.,线性码的构造,2,Hamming,码,第十二讲 循环码,1,BCH,码,2,RS,码,3.Goppa,码,第十三讲 卷积码,1.,编码过程,2.,译码过程,第十四讲 其它类型的码,1.,非线性码,2.,几何码,第十一讲 线性码,18,香农信息论就是编码的理论，就是从信息的角度,研究如何提高通信的可靠性、有效性的理论。,香农信息论和编码方法是密不可分的，有的课程叫,做信息论与编码。我们将,侧重学习基础理论方面,的内容，对于具体的编码方法，仅做简单介绍。例如,霍夫曼编码、分组码和卷积码等。,香农信息论的编码定理是理论极限，是“,非构造性的,”，具体实现的编码方法还需要具体构造。（实际中有,各式各样的编码方法。）,几点解释,：,香农信息论就是编码的理论，就是从信息的角度,19,信号、消息与信息的区别,信号是消息的载体，是物理的；,消息利用信号承载，是非物质的；,消息和,符号,可以视为一回事，消息用符号表示。,信息不能单独存在，必须依附一定的物理形式,。,物质、能量和信息构成自然界三大要素。,香农信息论中的信息是,消息中的不确定成份,。,消息实际是全信息的概念，与“,数据,”等混为一谈了。,信号、消息与信息的区别信号是消息的载体，是物理的；消息和符号,20,信息论的发展,自香农提出信息论以来，信息论得到了不断完善和发展。,狭义信息论：香农的研究结果，也称香农信息论；,一般信息论：除香农信息论，还包括维纳的微弱信号,检测（滤波）理论，也称最佳接收理论；,广义信息论：包括所有与信息有关的领域，从主观和,客观两个方面全面研究信息的度量、获取、,传输、存储、加工处理、利用以及功用等。,全信息：语法信息（香农信息）、语义信息和语用信息。,Grammar,Semantic,Pragmatics,信息论的发展自香农提出信息论以来，信息论得到了不断完善和发展,21,香农信息论只是,概率语法信息论,，即用概率的观点研究语法信息，只考虑消息符号本身出现的概率，与内容无关。,获得了消息所携带的原有的信息量，消息的不确定性也就消除了。所以从信息的角度，只要保持消息的信息，就能够不失真地传输消息（可靠性），也能够解决有效性问题。,“香农信息与消息的内容无关”，并不是不传输消息内,容而只传输信息。传送的还是经过处理的消息（编码），,只是“如何处理”是从保持信息的角度来考虑的。,香农信息论只是概率语法信息论，即用概率的观点研究语法信息，只,22,信息论与其它学科的联系：,统计物理（热力学，热力学第二定律：热熵不减）；,计算机科学（,Kolmogorov,复杂性，或算法复杂性）；,数学（概率统计大偏差分析、假设检验）；,经济（投资、股市的熵和财产增长率为对偶关系）。,熵概念的发展：,加权熵；,相对熵,；平滑熵,还有人将信息论分为：基本理论、编码方法和密码。,信息论与其它学科的联系：还有人将信息论分为：基本理论、编码方,23,不确定性：信源输出的消息或符号，对于发送者来说，,是已知的，但对于通信系统和接受者来说，,是不确定的。信源消息的出现，或者说发送,者选择哪个消息，具有一定的不确定性，,信息量：信息量就是信息大小或多少的度量，即解除,信源不确定性所需的信息的度量。信源发出,某个消息或符号时，获得这一事件的信息量,后，它的不确定性就被解除了。,1,2.,信息的度量信息熵,不确定性：信源输出的消息或符号，对于发送者来说，信息量：,24,要描述一个离散随机变量构成的离散信源，就是,规定,随机变量,X,的取值集合,及其概率测度,一般情况，我们用概率的倒数的对数函数来表示,某一事件（某一符号）出现所带来的信息量。,每个符号的自信息量：,要描述一个离散随机变量构成的离散信源，就是 一,25,符号集的平均信息量就用信息熵来度量。,信息熵：信源的平均信息量（概率平均）。,信源的每个符号所提供的平均信息量！,熵,Entropy E,Expectation,期望,信息量的单位为：比特,bit（,以2为底），,奈特,Nat（,以,e,为底），,迪特,Det（,以10为底）。,符号集的平均信息量就用信息熵来度量。信息熵：信源的,26,例：,掷骰子。随机变量,X,表示结果。符号集为,符号出现概率为,当,X0,1,时,现在推广为：一位二进制数为1,bit，,八位为1,byte,例：掷骰子。随机变量X表示结果。符号集为 符号出现概率为 当,27,例,：,对于二元符号集,X0,1,如果,则,log2,1/2,p,H,称为熵函数,写法：,H(p),例：对于二元符号集X0,1,如果则log21/2p,28,1、