信息熵课件讲义整理

信息论基础

2011年3月信息论基础1教材和参考书：傅祖芸编著《信息论－基础理论与应用》，电子工业出版社，2006，第二版.孟庆生《信息论》，西安交通大学，1986。

（数学家写的研究生教材，含编码和密码）朱雪龙《应用信息论基础》，清华大学出版社,2000。

（研究生教材，面向电子类，含编码方法。）

王育民、梁传甲《信息与编码理论》，西电教材。

（内容深入，推导过程少）沈连丰、叶芝惠编著《信息论与编码》东南大学硕士教材，科学出版社，2004，

（面向通信专业）。教材和参考书：傅祖芸编著《信息论－基础理论2周荫清主编《信息理论基础》北航出版社，2006（简洁，面向电子类）T.M.Cover&J.A.Thomas,ElementsofInformationTheory，Addison-WesleyPub,1990,清华影印。R.J.McEliece《TheTheoryofInformationandCoding》

第二版，电子工业出版社，2003。（内容简练，编码方面较全）*J.H.VanLint《Introductiontocodingtheory》

GTM86,Springer-Verlag,1998.*Roman《Codingandinformationtheory》,GTM134，新的教材：在广义信息论、网络信息论方面的内容有所增加。周荫清主编《信息理论基础》北航出版社，20063第一讲

1-1信息论的主要内容

1-2信息的度量－信息熵1-3信息熵的性质信息熵第一讲1-1信息论的主要内容信息熵41－1.信息论的主要内容香农信息论最初是为了解决通信问题而提出的。通信的重要意义是勿庸置疑的。人类传递思想、表达情感，就需要相互交流。人类的劳动、生产、政治、文化、日常生活等都离不开通信。人类利用眼、耳、鼻、舌、身等五种感觉器官来感受外界的信息，形成一个信息流通的体系。通信方式的不断提高，代表了人类文明和科技水平的不断提高。1－1.信息论的主要内容香农信息论最初是为了解决通信问题5通信的根本任务：将一地点的消息可靠地、有效地传送到另一地点。信源干扰源信道信宿通信系统的基本模型：

通信的根本任务：将一地点的消息可靠地、有效地信源干扰源信道信6为了使消息可靠地、有效地传送到信宿，就需要对信源的消息进行处理；信源编码：实现有效性；信道编码：实现可靠性；密码：实现保密性及认证性；有没有可靠的、有效的处理方法？如何进行编码？香农信息论奠定了通信的理论基础。信息是消息的不确定性度量。某消息出现的概率大，它的信息量就小，相反，某消息出现的概率小，则它的信息量就大。通信的关键是信息的传输问题。为了使消息可靠地、有效地传送到信宿，就需要信源编码：实现有7信源信源编码信宿信道信道编码信道译码信源译码加密钥加密解密钥解密干扰源信源信源编码信宿信道信道编码信道译码信源译码加密钥加密解密钥8提出的背景：在香农信息论出现以前，没有系统的通信理论。是香农，开创了信息论的研究，奠定了一般性通信理论的基础。对数字通信技术的形成有很大贡献。（不论什么样的干扰信道，抓住了本质问题。）提出的背景：9(Shannon,1916－2001)“AMathematicalTheoryofCommunication”“CommunicationTheoryofSecrecySystem”(Shannon,1916－2001)“AMathe10AboutClaudeElwoodShannon:

1916年生于Gaylord,MI的一个小镇。母亲是一个语言教师和中学校长，父亲是一个商人。16岁高中毕业，进入密西根大学。1936年获得电子工程和数学双学士学位。随后进入MIT，作为研究生和研究人员。一年后，完成布尔代数用于开关电路的硕士论文。1940年完成“关于遗传学的代数”的博士论文。1941年以后进入Bell实验室。(新理论和技术的摇篮)1945年写出“密码学的数学理论”，1949年正式出版，名为“保密系统的通信理论”。1948年发表“通信系统的数学理论”。其后又取得通信、人工智能等多方面的成果。AboutClaudeElwoodShannon:11信源信道信宿噪声信源熵H信源编码R’>H信号信息信道编码R<C信源解码信道解码R’－编码信息传输率R－信道信息传输率C－信道容量NLnL/NL/n信源信道信宿噪声信源熵信源编码信号信息信道编码信源信道R’－12香农信息论主要讨论如下内容：1、围绕信息的度量所展开的讨论。这是信息论建立的基础，给出了各种信息量和各种熵的概念；2、围绕无失真信源编码所展开的讨论。最主要的结论是香农第一定理以及各种信源编码方法。

3、围绕信道编码所展开的讨论。它给出了信息传输率、信道容量等概念，最主要的结论是香农第二定理，以及基于该定理的各种信道编码，如分组码、卷积码等。4、围绕带限信道传输的能力所展开的讨论，最主要的结论是信道容量公式，即香农公式。

香农信息论主要讨论如下内容：135、

基于信息传输时允许一定程度的失真和差错所展开的讨论。由此得到信息率失真理论、香农第三定理、信息价值等。这是目前还在不断发展和完善的理论，在通信以外得学科不断得到应用。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符号集的平均信息量就用信息熵来度量。

信息熵：信源的平均信息量（概率平均）。

－－信源的每个符号所提供的平均信息量！熵－EntropyE－Expectation期望信息量的单位为：比特bit（以2为底），奈特Nat（以e为底），迪特Det（以10为底）。符号集的平均信息量就用信息熵来度量。信息熵：信源的26例：掷骰子。随机变量X表示结果。符号集为

符号出现概率为

当X＝{0,1}时现在推广为：一位二进制数为1bit，八位为1byte例：掷骰子。随机变量X表示结果。符号集为符号出现概率为当27例：对于二元符号集X＝{0,1},如果则log21/2pH称为熵函数写法：H(p)例：对于二元符号集X＝{0,1},如果则log21/2p281、对称性：

熵只与随机变量的总体结构有关，与个别符号的概率没有直接关系。与随机变量的取值无关。例如以下三个随机变量的熵是一样的。其中上面一行是可能的取值，下面一行是对应的概率。

1－3

信息熵的性质1、对称性：熵只与随机变量的总体结构有关，与个别符号292、非负性：3、确定性：4、扩展性：因为每个p<1，所以它们的以不小于1的数为底的对数是不大于零的。

确定的事物是无信息可言的。有一个符号概率为1的信源，其熵为0。

（0概率的事件信息量为0？）2、非负性：3、确定性：4、扩展性：因为每个p<1，所以它们305、可加性与强可加性：（涉及到了两个变量！）H（XY）为两个随机变量的联合熵。可加性：H（XY）等于X的无条件熵，加上已知X时Y的条件概率的熵的平均值，即条件熵。对于X与Y独立的情况有：（强可加性）5、可加性与强可加性：（涉及到了两个变量！）H（XY）为31第一讲信息熵课件326、递增性（子集再划分，第n个分为m个）按照定义证明：6、递增性（子集再划分，第n个分为m个）按照定义证33例题：计算例题：计算347、极值性：可利用两个引理证明；（以后再利用Jensen证明。）引理1

：对于x>0引理2

：其中：7、极值性：可利用两个引理证明；（以后再利用Jensen证明35引理2证明：两边求和即得结论:引理2证明：两边求和即得结论:36是

P

的上凸函数。

即对于，有：8、上凸性：几何解释：f(EP)总在Ef(P)上边和两个概率矢量函数f的图象是P的上凸函数。即对于，有：8、上凸性：几何解释：37凸集：令是定义在矢量空间中的区域

R

上的实值分量的

K维矢量。若对于有：则称

R

为凸集或凸区域。

概率矢量：

凸集：令是定义在矢量空间中的区域38引理：概率空间中任意区域都是凸集。证明：则对于可构造矢量若例如：引理：概率空间中任意区域都是凸集。则对于可构造矢量若例如：39凸函数：定义在凸集R上的一个实函数f，若它对所有的满足：则称函数f为R上的上凸函数，若不等式符号相反，则为下凸函数。

上凸：Convexcap（orConcave）下凸：Convexcup（orConvex）凸函数：定义在凸集R上的一个实函数f，若它对所有的上凸：Co40Jensen不等式：若是R上的上凸函数，则：为随机变量，取值在R上，概率分布为P（归纳法证明）（为了简化，省略了矢量的上箭头）对于多个点的组合：Jensen不等式：若是R上的上凸函数，则：41第三步：设第一步：由定义第二步：若（－－前n项和）第三步：设第一步：由定义第二步：若（－－前n项和）42熵函数的极值性证明：对数函数是上凸函数，点空间是凸集：（此说明仅为示意，不太确切）熵函数的极值性证明：对数函数是上凸函数，43熵函数的上凸性证明：熵函数的上凸性证明：44第一讲信息熵

结束

第一讲信息熵45信息论基础

2011年3月信息论基础46教材和参考书：傅祖芸编著《信息论－基础理论与应用》，电子工业出版社，2006，第二版.孟庆生《信息论》，西安交通大学，1986。

（数学家写的研究生教材，含编码和密码）朱雪龙《应用信息论基础》，清华大学出版社,2000。

（研究生教材，面向电子类，含编码方法。）

王育民、梁传甲《信息与编码理论》，西电教材。

（内容深入，推导过程少）沈连丰、叶芝惠编著《信息论与编码》东南大学硕士教材，科学出版社，2004，

（面向通信专业）。教材和参考书：傅祖芸编著《信息论－基础理论47周荫清主编《信息理论基础》北航出版社，2006（简洁，面向电子类）T.M.Cover&J.A.Thomas,ElementsofInformationTheory，Addison-WesleyPub,1990,清华影印。R.J.McEliece《TheTheoryofInformationandCoding》

第二版，电子工业出版社，2003。（内容简练，编码方面较全）*J.H.VanLint《Introductiontocodingtheory》

GTM86,Springer-Verlag,1998.*Roman《Codingandinformationtheory》,GTM134，新的教材：在广义信息论、网络信息论方面的内容有所增加。周荫清主编《信息理论基础》北航出版社，200648第一讲

1-1信息论的主要内容

1-2信息的度量－信息熵1-3信息熵的性质信息熵第一讲1-1信息论的主要内容信息熵491－1.信息论的主要内容香农信息论最初是为了解决通信问题而提出的。通信的重要意义是勿庸置疑的。人类传递思想、表达情感，就需要相互交流。人类的劳动、生产、政治、文化、日常生活等都离不开通信。人类利用眼、耳、鼻、舌、身等五种感觉器官来感受外界的信息，形成一个信息流通的体系。通信方式的不断提高，代表了人类文明和科技水平的不断提高。1－1.信息论的主要内容香农信息论最初是为了解决通信问题50通信的根本任务：将一地点的消息可靠地、有效地传送到另一地点。信源干扰源信道信宿通信系统的基本模型：

通信的根本任务：将一地点的消息可靠地、有效地信源干扰源信道信51为了使消息可靠地、有效地传送到信宿，就需要对信源的消息进行处理；信源编码：实现有效性；信道编码：实现可靠性；密码：实现保密性及认证性；有没有可靠的、有效的处理方法？如何进行编码？香农信息论奠定了通信的理论基础。信息是消息的不确定性度量。某消息出现的概率大，它的信息量就小，相反，某消息出现的概率小，则它的信息量就大。通信的关键是信息的传输问题。为了使消息可靠地、有效地传送到信宿，就需要信源编码：实现有52信源信源编码信宿信道信道编码信道译码信源译码加密钥加密解密钥解密干扰源信源信源编码信宿信道信道编码信道译码信源译码加密钥加密解密钥53提出的背景：在香农信息论出现以前，没有系统的通信理论。是香农，开创了信息论的研究，奠定了一般性通信理论的基础。对数字通信技术的形成有很大贡献。（不论什么样的干扰信道，抓住了本质问题。）提出的背景：54(Shannon,1916－2001)“AMathematicalTheoryofCommunication”“CommunicationTheoryofSecrecySystem”(Shannon,1916－2001)“AMathe55AboutClaudeElwoodShannon:

1916年生于Gaylord,MI的一个小镇。母亲是一个语言教师和中学校长，父亲是一个商人。16岁高中毕业，进入密西根大学。1936年获得电子工程和数学双学士学位。随后进入MIT，作为研究生和研究人员。一年后，完成布尔代数用于开关电路的硕士论文。1940年完成“关于遗传学的代数”的博士论文。1941年以后进入Bell实验室。(新理论和技术的摇篮)1945年写出“密码学的数学理论”，1949年正式出版，名为“保密系统的通信理论”。1948年发表“通信系统的数学理论”。其后又取得通信、人工智能等多方面的成果。AboutClaudeElwoodShannon:56信源信道信宿噪声信源熵H信源编码R’>H信号信息信道编码R<C信源解码信道解码R’－编码信息传输率R－信道信息传输率C－信道容量NLnL/NL/n信源信道信宿噪声信源熵信源编码信号信息信道编码信源信道R’－57香农信息论主要讨论如下内容：1、围绕信息的度量所展开的讨论。这是信息论建立的基础，给出了各种信息量和各种熵的概念；2、围绕无失真信源编码所展开的讨论。最主要的结论是香农第一定理以及各种信源编码方法。

3、围绕信道编码所展开的讨论。它给出了信息传输率、信道容量等概念，最主要的结论是香农第二定理，以及基于该定理的各种信道编码，如分组码、卷积码等。4、围绕带限信道传输的能力所展开的讨论，最主要的结论是信道容量公式，即香农公式。

香农信息论主要讨论如下内容：585、

基于信息传输时允许一定程度的失真和差错所展开的讨论。由此得到信息率失真理论、香农第三定理、信息价值等。这是目前还在不断发展和完善的理论，在通信以外得学科不断得到应用。6、

围绕通信网的发展带来的信息传输问题展开的讨论。即网络信息理论，随着通信网、因特网的发展，它越来越受到重视。

7、围绕通信的保密所展开的讨论。包括保密通信的技术体制及其数学模型，传输线路保密技术的信息论基础，信息保密技术的基础知识以及保密通信的各种方法。

5、

基于信息传输时允许一定程度的失真和差错所展开59本课程的讲授内容：

第一讲

信息熵1.信息论的主要内容

2.信息的度量－信息熵

3.信息熵的性质第二讲

信源的信息熵

1.信源的描述

2.无记忆扩展信源

3.离散平稳信源

4.马尔可夫信源第三讲平均互信息

1.信道和平均互信息

2.平均互信息的性质

3.数据处理定理本课程的讲授内容：60第四讲

信道容量及其计算1.信道容量2.信道容量的计算第五讲

连续信源和信道

1.连续信源的微分熵

2.具有最大熵的连续信源

3.连续信道和波形信道

4.连续信道和波形信道的信道容量

第六讲等长信源编码定理1.信源编码

2.典型序列和信源划分定理

3.等长信源编码定理第七讲

变长信源编码定理1．变长信源编码定理2．Huffman编码第四讲

信道容量及其计算61第八讲有噪声信道编码定理

1.错误概率与译码准则2．FANO不等式3.联合典型序列

4.无失真信道编码定理第九讲限失真信源编码定理与多用户信息论

1.信息率失真函数

2.限失真信源编码定理

3.相关信源编码4．多址信道和广播信道第十讲通信系统的保密理论

1.完全保密性2.理论保密性

3.实际保密性第八讲有噪声信道编码定理62第十一讲线性码

1.线性码的一般概念3.线性码的构造2．Hamming码第十二讲循环码1．BCH码

2．RS码

3.Goppa码第十三讲卷积码

1.编码过程

2.译码过程第十四讲其它类型的码

1.非线性码2.几何码第十一讲线性码63香农信息论就是编码的理论，就是从信息的角度研究如何提高通信的可靠性、有效性的理论。

香农信息论和编码方法是密不可分的，有的课程叫做《信息论与编码》。我们将侧重学习基础理论方面

的内容，对于具体的编码方法，仅做简单介绍。例如霍夫曼编码、分组码和卷积码等。香农信息论的编码定理是理论极限，是“非构造性的”，具体实现的编码方法还需要具体构造。（实际中有各式各样的编码方法。）几点解释：香农信息论就是编码的理论，就是从信息的角度64信号、消息与信息的区别信号是消息的载体，是物理的；消息利用信号承载，是非物质的；消息和符号可以视为一回事，消息用符号表示。

信息不能单独存在，必须依附一定的物理形式。物质、能量和信息构成自然界三大要素。香农信息论中的信息是消息中的不确定成份。消息实际是全信息的概念，与“数据”等混为一谈了。信号、消息与信息的区别信号是消息的载体，是物理的；消息和符号65信息论的发展自香农提出信息论以来，信息论得到了不断完善和发展。狭义信息论：香农的研究结果，也称香农信息论；一般信息论：除香农信息论，还包括维纳的微弱信号检测（滤波）理论，也称最佳接收理论；广义信息论：包括所有与信息有关的领域，从主观和客观两个方面全面研究信息的度量、获取、传输、存储、加工处理、利用以及功用等。

全信息：语法信息（香农信息）、语义信息和语用信息。

Grammar,Semantic,Pragmatics信息论的发展自香农提出信息论以来，信息论得到了不断完善和发展66香农信息论只是概率语法信息论，即用概率的观点研究语法信息，只考虑消息符号本身出现的概率，与内容无关。获得了消息所携带的原有的信息量，消息的不确定性也就消除了。所以从信息的角度，只要保持消息的信息，就能够不失真地传输消息（可靠性），也能够解决有效性问题。“香农信息与消息的内容无关”，并不是不传输消息内容而只传输信息。传送的还是经过处理的消息（编码），只是“如何处理”是从保持信息的角度来考虑的。香农信息论只是概率语法信息论，即用概率的观点研究语法信息，只67信息论与其它学科的联系：统计物理（热力学，热力学第二定律：热熵不减）；计算机科学（Kolmogorov复杂性，或算法复杂性）；数学（概率统计－－大偏差分析、假设检验）；经济（投资、股市的熵和财产增长率为对偶关系）。－－－－－－熵概念的发展：加权熵；相对熵；平滑熵

还有人将信息论分为：基本理论、编码方法和密码。信息论与其它学科的联系：还有人将信息论分为：基本理论、编码方68不确定性：信源输出的消息或符号，对于发送者来说，是已知的，但对于通信系统和接受者来说，是不确定的。信源消息的出现，或者说发送者选择哪个消息，具有一定的不确定性，信息量：信息量就是信息大小或多少的度量，即解除信源不确定性所需的信息的度量。信源发出某个消息或符号时，获得这一事件的信息量后，它的不确定性就被解除了。1－2.信息的度量－信息熵不确定性：信源输出的消息或符号，对于发送者来说，信息量：69要描述一个离散随机变量构成的离散信源，就是规定随机变量X的取值集合及其概率测度

一般情况，我们用概率的倒数的对数函数来表示某一事件（某一符号）出现所带来的信息量。每个符号的自信息量：要描述一个离散随机变量构成的离散信源，就是一70符号集的平均信息量就用信息熵来度量。

信息熵：信源的平均信息量（概率平均）。

－－信源的每个符号所提供的平均信息量！熵－EntropyE－Expectation期望信息量的单位为：比特bit（以2为底），奈特Nat（以e为底），迪特Det（以10为底）。符号集的平均信息量就用信息熵来度量。信息熵：信源的71例：掷骰子。随机变量X表示结果。符号集为

符号出现概率为

当X＝{0,1}时现在推广为：一位二进制数为1bit，八位为1byte例：掷骰子。随机变量X表示结果。符号集为符号出现概率为当72例：对于二元符号集X＝{0,1},如果则log21/2pH称为熵函数写法：H(p)例：对于二元符号集X＝{0,1},如果则log21/2p731、对称性：

熵只与随机变量的总体结构有关，与个