信息论基础 1~8

1 绪论与概览

2 熵 相对熵与互信息

2.1 熵

2.2 联合熵

定理2.2.1(链式法则):

2.3 相对熵与互信息

相对熵(relative entropy):

互信息(mutual information):

2.4 熵与互信息的关系

互信息I(X;Y)是在给定Y知识的条件下X的不确定度的缩减量

2.5 熵,相对熵与互信息的链式法则

定理2.5.1(熵的链式法则):

定理2.5.2(互信息的链式法则):

条件相对熵:

定理2.5.3(相对熵的链式法则):

2.6 Jensen不等式及其结果

定理2.6.2(Jensen不等式): 若给定凸函数f和一个随机变量X,则

定理2.6.3(信息不等式):

推论(互信息的非负性):

定理2.6.4:

定理2.6.5(条件作用使熵减小):

从直观上讲,此定理说明知道另一随机变量Y的信息只会降低X的不确定度. 注意这仅对平均意义成立. 具体来说, \(H(X|Y=y)\) 可能比大或者小,或者两者相等.

定理2.6.6(熵的独立界):

2.7 对数和不等式及其应用

定理2.7.1(对数和不等式):

定理2.7.2(相对熵的凸性): 关于对(p,q)是凸的

定理2.7.3(熵的凹性): H(p)是关于p的凹函数

2.8 数据处理不等式

2.9 充分统计量

这节很有意思,利用统计量代替原有抽样,并且不损失信息.

2.10 费诺不等式

定理2.10.1(费诺不等式): 对任何满足

上述不等式可以减弱为

引理 2.10.1: 如果X和X’独立同分布,具有熵H(X),则

3 渐进均分性

4 随机过程的熵率

4.1 马尔科夫链

4.2 熵率

4.3 例子:加权图上随机游动的熵率

4.4 热力学第二定律

4.5 马尔科夫链的函数

5 数据压缩

5.1 有关编码的几个例子

5.2 Kraft不等式

定理5.2.1(Kraft不等式): 对于D元字母表上的即时码,码字长度 必定满足不等式

5.3 最优码

5.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 信道容量

离散信道:

7.1 信道容量的几个例子

7.2 对称信道

如果信道转移矩阵 \(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 定义

均匀分布

正态分布

8.2 连续随机变量的AEP

8.3 微分熵与离散熵的关系

8.4 联合微分熵与条件微分熵

8.5 相对熵与互信息

8.6 微分熵, 相对熵以及互信息的性质