信息论基础课程讲义1

第10章信息论基础＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝运用概率论与数理统计方法研究信息的度量、传递、变换等规律基本概念：1) 熵——度量消息中的不确定性；2)互信息——度量传递信息的多少。

基本结论：1)通信的效率可以借助信源压缩编码来提高——压缩信源的极限是信源的熵；2)噪声信道中可以借助信道编码来实现无差错的通信——无差错通信的速率上限是信道的容量。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝本章目录：10.1 熵与互信息10.2 离散信道与信道容量10.3 相对熵与高斯信道容量10.4 离散信源编码与压缩算法10.5 *率失真函数与限失真编码定理＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝10.1熵与互信息＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝10.1.1 熵及其特性“无记忆”——各时刻的符号独立同分布离散无记忆信源（DMS ）——字符集为12,,,M a a a 取值概率12,,,M p p p 熵——X 所蕴含的不确定：1log Mi ii H Xp p 是自信息量log i i I p p 的平均值＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝熵的范围为20,log M ：1)最小值为0：消息完全确定（某个1i p ）2)最大值为2log M ：消息完全随机（取值等概）；采用log 原因：（1）只依赖于概率i p ，与取值i a 无关；（2）i p 的非负、连续函数，它的取值；（3）独立性对应可加性＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝例10.1二进制DMS ：X 的二种取值为0,1，概率分别为p 与1p 222,1log 1log 1()H X H p pH p p p p p bits ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝10.1.2 联合熵与条件熵随机变量,X Y ：取值为,i j x y ，概率为,i j p x y ，条件概率为|i jp x y 1）联合熵：,,log ,i j i ji j H X Yp x y p x y X 与Y 共同蕴含的不确定性，因此，,H X Y H X H YX 与Y 独立时，取等号＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝2）条件熵：|,log |i j i ji j H X Yp x y p x y 给定Y 总是减少X 的不确定性：|H X YH X 基本性质：（1）|(|)j H X YE H X Y y （2）X Y 时，|0H X Y ；（3）X 与Y 独立时，|H X Y H X ；。

信息论基础1~81 绪论与概览2 熵相对熵与互信息2.1 熵H(X)=−∑x∈X p(x)logp(x)H(X)=−∑x∈Xp(x)log⁡p(x)2.2 联合熵H(X,Y)=−∑x∈X∑y∈Y p(x,y)logp(x,y)H(X,Y)=−∑x∈X∑y∈Yp(x,y)log⁡p(x,y)H(Y|X)=∑x∈X p(x)H(Y|X=x)H(Y|X)=∑x∈Xp(x)H(Y|X=x)定理2.2.1(链式法则): H(X,Y)=H(X)+H(Y|X)H(X,Y)=H(X)+H(Y|X) 2.3 相对熵与互信息相对熵(relative entropy): D(p||q)=∑x∈X p(x)logp(x)q(x)=Eplogp(x)q(x)D(p||q)=∑x∈Xp(x)lo g⁡p(x)q(x)=Eplog⁡p(x)q(x)互信息(mutual information): I(X;Y)=∑x∈X∑y∈Y p(x,y)logp(x,y)p(x)p(y)=D(p(x,y)||p(x)p(y))I(X;Y) =∑x∈X∑y∈Yp(x,y)log⁡p(x,y)p(x)p(y)=D(p(x,y)||p(x)p(y))2.4 熵与互信息的关系I(X;Y)=H(X)−H(X|Y)=H(Y)−H(Y|X)I(X;Y)=H(X)−H(X|Y)=H(Y)−H(Y|X)互信息I(X;Y)是在给定Y知识的条件下X的不确定度的缩减量I(X;Y)=H(X)+H(Y)−H(X,Y)I(X;Y)=H(X)+H(Y)−H(X,Y)2.5 熵,相对熵与互信息的链式法则定理 2.5.1(熵的链式法则): H(X1,X2,...,X n)=∑ni=1H(Xi|X i−1,...,X1)H(X1,X2,...,Xn)=∑i=1nH(Xi| Xi−1, (X1)定理 2.5.2(互信息的链式法则): I(X1,X2,...,X n;Y)=∑ni=1I(Xi;Y|X i−1,...,X1)I(X1,X2,...,Xn;Y)=∑i=1nI(Xi ;Y|Xi−1, (X1)条件相对熵: D(p(y|x)||q(y|x))=∑x p(x)∑yp(y|x)logp(y|x)q(y|x)=Ep(x,y)logp(Y|X)q( Y|X)D(p(y|x)||q(y|x))=∑xp(x)∑yp(y|x)log⁡p(y|x)q(y|x)=Ep(x,y)log⁡p (Y|X)q(Y|X)定理 2.5.3(相对熵的链式法则): D(p(x,y)||q(x,y))=D(p(x)||q(x))+D(p(y|x)||q(y|x))D(p(x,y)||q(x,y))=D( p(x)||q(x))+D(p(y|x)||q(y|x))2.6 Jensen不等式及其结果定理2.6.2(Jensen不等式): 若给定凸函数f和一个随机变量X,则Ef(X)≥f(EX)Ef(X)≥f(EX)定理2.6.3(信息不等式): D(p||q)≥0D(p||q)≥0推论(互信息的非负性): I(X;Y)≥0I(X;Y)≥0定理2.6.4: H(X)≤log|X|H(X)≤log⁡|X|定理2.6.5(条件作用使熵减小): H(X|Y)≤H(X)H(X|Y)≤H(X)从直观上讲,此定理说明知道另一随机变量Y的信息只会降低X的不确定度. 注意这仅对平均意义成立. 具体来说, H(X|Y=y)H(X|Y=y) 可能比H(X)H(X)大或者小,或者两者相等.定理 2.6.6(熵的独立界): H(X1,X2,…,X n)≤∑ni=1H(Xi)H(X1,X2,…,Xn)≤∑i=1nH(Xi)2.7 对数和不等式及其应用定理 2.7.1(对数和不等式): ∑ni=1ailogaibi≥(∑ni=1ai)log∑ni=1ai∑ni=1bi∑i=1nailog⁡aibi≥(∑i =1nai)log⁡∑i=1nai∑i=1nbi定理2.7.2(相对熵的凸性): D(p||q)D(p||q) 关于对(p,q)是凸的定理2.7.3(熵的凹性): H(p)是关于p的凹函数2.8 数据处理不等式2.9 充分统计量这节很有意思,利用统计量代替原有抽样,并且不损失信息.2.10 费诺不等式定理2.10.1(费诺不等式): 对任何满足X→Y→X^,X→Y→X^, 设Pe=Pr{X≠X^},Pe=Pr{X≠X^}, 有H(Pe)+Pe log|X|≥H(X|X^)≥H(X|Y)H(Pe)+Pelog⁡|X|≥H(X|X^)≥H(X|Y)上述不等式可以减弱为1+Pe log|X|≥H(X|Y)1+Pelog⁡|X|≥H(X|Y)或Pe≥H(X|Y)−1log|X|Pe≥H(X|Y)−1log⁡|X|引理 2.10.1: 如果X和X’独立同分布,具有熵H(X),则Pr(X=X′)≥2−H(X)Pr(X=X′)≥2−H(X)3 渐进均分性4 随机过程的熵率4.1 马尔科夫链4.2 熵率4.3 例子:加权图上随机游动的熵率4.4 热力学第二定律4.5 马尔科夫链的函数H(Yn|Y n−1,…,Y1,X1)≤H(Y)≤H(Y n|Y n−1,…,Y1)H(Yn|Yn−1,…,Y1,X1)≤H(Y)≤H(Yn|Yn−1,…,Y1)5 数据压缩5.1 有关编码的几个例子5.2 Kraft不等式定理5.2.1(Kraft不等式): 对于D元字母表上的即时码,码字长度l1,l2,…,l m l1,l2,…,lm必定满足不等式∑iD−li≤1∑iD−li≤15.3 最优码l∗i=−log Dpili∗=−logD⁡pi5.4 最优码长的界5.5 唯一可译码的Kraft不等式5.6 赫夫曼码5.7 有关赫夫曼码的评论5.8 赫夫曼码的最优性5.9 Shannon-Fano-Elias编码5.10 香农码的竞争最优性5.11由均匀硬币投掷生成离散分布6 博弈与数据压缩6.1 赛马6.2 博弈与边信息6.3 相依的赛马及其熵率6.4 英文的熵6.5 数据压缩与博弈6.6 英语的熵的博弈估计7 信道容量离散信道: C=maxp(x)I(X;Y)C=maxp(x)I(X;Y)7.1 信道容量的几个例子7.2 对称信道如果信道转移矩阵p(y|x)p(y|x) 的任何两行相互置换,任何两列也相互置换,那么称该信道是对称的.7.3 信道容量的性质7.4 信道编码定理预览7.5 定义7.6 联合典型序列7.7 信道编码定理7.8 零误差码7.9 费诺不等式与编码定理的逆定理7.10 信道编码定理的逆定理中的等式7.11 汉明码7.12 反馈容量7.13 信源信道分离定理8 微分熵8.1 定义h(X)=−∫Sf(x)logf(x)dxh(X)=−∫Sf(x)log⁡f(x)dx均匀分布 h(X)=logah(X)=log⁡a正态分布h(X)=1/2log2πeδ2h(X)=1/2log⁡2πeδ2 8.2 连续随机变量的AEP8.3 微分熵与离散熵的关系8.4 联合微分熵与条件微分熵8.5 相对熵与互信息8.6 微分熵, 相对熵以及互信息的性质。

信息论基础教程(一)
信息论基础教程
一、引言
1.什么是信息论？
2.由来和应用领域
二、信息的定义
1.信息的测量单位
2.信息的数学表示
三、信息的熵
1.熵的概念
2.熵的计算公式
3.熵的性质
四、信息的压缩与编码
1.无损压缩与编码
2.哈夫曼编码
3.香农编码
五、信道容量
1.信道模型
2.信道容量的计算
3.极限定理
六、误差检测和纠正
1.奇偶校验
2.海明码
七、信息论在通信领域的应用
1.数据压缩
2.信道编码
3.无线传输
八、信息论的未来发展
1.量子信息论
2.生物信息学
以上是详细的信息论基础教程大纲，通过Markdown格式的标题副标题形式来展现。

文章采用列点的方式生成，遵守规则的前提下准确
描述了信息论的基础知识，包括信息的定义和测量、熵的概念和计算、
信息的压缩与编码、信道容量、误差检测和纠正等内容。

同时，还介绍了信息论在通信领域的应用以及未来的发展方向。

信息论基础第一讲信息的基本概念与预备知识一、信息的基本概念1、信息论是通信的数学理论，是运用数理统计的方法研究信息的传输、存储与处理的科学。

2、物质、能量、信息是构成客观世界的三大要素，信息存在于任何事物中，有物质的地方就有信息。

3、信息具有的性质（1）无形————不具实体性；（2）共享————交流者不会失去原有信息，还可获得新的信息，可无限传播，也可限制传播，如设密码、安全措施；（3）信息是一种资源————永远在产生、更新、演变，取之不尽用之不竭；（4）可度量————信息的数量和质量可度量。

3、概率信息（香农信息或狭义信息）美国数学家香农（C.E.Shannan）提出，信息源具有随机性不定度，为了消除一定的不定度必须获得与此不定度相等的信息量。

（1）甲袋有100个球，50个红，50个人白，取出一个为红；（2）乙袋有100个球，25个红，25个白，25个蓝，25个黑，取出一个为红；概率大，不确定性小，信息量小，。

4、消息构成消息的条件：能被通信双方理解，可在通信中进行传递和交换。

消息具有不同的形式，如语言、文字、符号、数据、图片等。

消息是信息的载荷者，同一消息可以含不同的信息量，同一信息可以用不同形式的消息来载荷。

5、信号信号是消息的表现形式，消息是信号的具体内容。

信号是消息的载体。

6、信息的传输系统信源——编码——信道——译码器——信宿 二、预备知识 1、全概公式∑∑====nk k k nk k A B p A p B A p B p 11)()()()(2、贝叶斯公式)()()()()()(B p A B p A p B p B A p B A p k k k k == 3、条件概率)()()(B p AB p B A p =4、乘法公式)()()()()(B A p B p A B p A p AB p ==4、不等式1ln 110-≤≤-⇒>x x xx三、自信息的度量 1、自信息随机事件ix 发生概率为)(ix p ，则随机事件ix 的自信息量为)(log )(i i x p x I -= 。