2024-04-25

2024-2025学年秋冬学期信息理论课程笔记

引言：

ACEE信息理论课程笔记, 好难的数学。（信息的度量，信息的无损压缩，信息的传输1-3章）

信息的度量

随机变量的熵和互信息

概率论的一些基本概念

我们定义随机变量的概率空间 $，$
的取值空间，
事件发生的概率，

联合变量对：

二维随机变量

对于二维随机变量，有如下边际概率分布：

的边际概率分布：
的边际概率分布：

对于条件概率，有：

事件的自信息

事件的信息量基于该事件发生的概率
定义：对于概率空间事件的自信息定义为：

单位：当a=2时，为比特（bit），当a=e时，为奈特
特点：
- 事件发生的概率越小，事件的信息量越大
- 两事件的信息量之和，信息量相加，概率相乘
事件的条件自信息，事件发生的条件下事件的条件自信息定义为：

事件的互信息

事件与事件之间的互信息定义为；

事件互信息的本质：一个事件对另一个事件不确定性的降低
事件互信息的对称性：

事件的联合自信息的定义

事件和的联合自信息定义为：

表示两事件同时发生需要的信息量，或者同时发生后对外界提供的信息量

事件的条件互信息

在给定的条件下，时间与之间的条件互信息为：

事件的联合互信息

联合事件与事件之间的互信息：

表示事件联合提供给事件的信息量

需要注意：

时间的自信息，条件自信息都大于0，而事件的互信息可小于，大于，等于0

随机变量的熵

定义：随机变量的熵定义为随机变量各个事件的平均自信息

熵与自信息的区别：熵针对的是随机变量，自信息针对具体事件

随机变量的联合熵

表示两个随机变量的不确定性度量

随机变量的条件熵

定义：给定的条件下，X的条件熵为：

定义：随机变量相对于随机变量的条件熵为

性质：当X和Y统计独立时，

随机变量联合熵的链式法则

随机变量X和Y的联合熵的链式法则：

性质：当X和Y统计独立时， ,

熵的性质

有如下性质：
- 对概率矢量的分量是对称的
- 非负性，即
- 确定性，即若中有一个分量为1，其余均为0，则
- 可扩展性，即

熵的可加性

如图，在这种情况下,有如下等式：

对变量X可以进行多步分层的观察，每一步都可从上一步的观察结果中得到更为细致的结果，变量X在最后的观察结果集合中的不确定性等于第一次观察结果的不确定性，加上其后每次观察结果在前一次观察结果已知的前提下的条件不确定性。

熵的极值性

性质：条件熵熵：增加条件使熵减少

熵的凸性

是的严格上凸函数，即对任何, 和任何二个维概率矢量有：

凸函数的性质：

不等式：

随机变量的加权熵*

随机变量的Renyi熵*

随机变量间的平均互信息

两个事件和之间相互提供的信息量定义为：随机变量相互提供的平均信息量称之为二者之间的平均互信息，简称互信息：

互信息的性质

非负性：
对称性：

由此可得：

条件互信息

事件的条件互信息：在随机变量Z已知的条件下变量X与Y相互提供的信息量为：

联合互信息

事件的联合互信息：随机变量Y和Z共同提供给变量X的信息量为：

相对熵（散度）

定义在相同字符表上的两个概率分布和之间的相对熵，或者称为距离，表示为：表示实际分布与假定分布之间的平均差距，因而也称为鉴别熵

性质：
- 若P1，P2是独立分布，并且联合分布是,如果是独立分布，并且联合分布是,则

关于疑义度的Fano不等式

定义在相同字符表上的两个随机变量和,其中是对的某种估计，估计错误概率定义为：则已知条件下的疑义度满足下述不等式：

马尔科夫链

定义：如果随机变量序列的联合概率分布可以写成如下形式：

则称这个随机变量构成马尔科夫链，记为：定义：

如果那么：(越近越大)

如果则：

互信息的凸性

互信息有凸性。。。。（PPT看不明白一点）

连续随机变量的互信息和微分熵

连续随机变量的概率密度

是连续随机变量的联合概率密度函数
是的边际密度函数
是Y的边际概率密度

有

连续随机变量的离散化

联合概率分布：

连续随机变量的互信息

联合连续随机变量之间的互信息

连续随机变量的微分熵

连续随机变量的离散化熵

定义连续随机变量的微分熵：

微分熵的本质和性质

性质：

微分熵不反映连续随机变量的不确定性，连续随机变量的不确定性一般都是无穷大。但微分熵在一定程度上反映了该连续随机变量的相对不确定性。
可正可负可为0

条件微分熵和联合微分熵及其性质

$$ H_C(X,Y)=-p_{XY}(x,y)log,p_{XY}(x,y)dxdy \ H_C(X|Y)=-p_{XY}(x,y)log, p_{X|Y}(x|y)dxdy \ H_C(X,Y)=H_C(X) + H_C(Y|X) = H_C(Y)+H_C(X|Y) \

H_C(U^N)=H_C(U_1,U_2,,U_N)\={n=1}^NH_C(U_n|U_1,U_2U{n-1})\=_{n=1}^N H_C(U_n|U^{n-1})

\ $$

微分熵在线性变化下不具有不变性

即，对于离散随机变量，令是上的一对一函数，则

对于连续随机变量对于线性变换，微分熵不具有不变形

微分熵的极大化：峰值受限

定理：设X取值限于即,这时，微分熵

等号在均匀分布时达到。

微分熵的极大化：平均功率受限

定理：在方差一定条件下，当服从正态分布时，微分熵最大，

即：

熵功率

熵功率的定义：高斯随机变量的熵功率：其微分熵为：其熵功率为：刚好为高斯随机变量的方差

有如下熵功率不等式：

平稳离散信源的熵

平稳随机过程

定义：对于任意的,任意的和,若与具有同样的分布，则称随机过程是平稳随机过程

平稳随机过程的性质：

的均值和方差对于所有都一样

平稳离散信源的定义

平稳信源：任意长度片段的联合概率分布与时间起点无关：

简单无记忆信源：不同时间的随机变量不想管

阶马尔科夫信源：

当m=1时，称为马尔科夫信源

平稳信源的熵

如果一个平稳信源发出长度为N的序列，令维随机矢量

，则：其中：H（X）随N的增长而增长，趋向于无穷大

平均每符号熵：
熵速率：
平均条件熵：

性质：

熵的相对率：
信源的冗余度：

马尔科夫信源

m阶马尔科夫信源：
马尔科夫信源的状态空间：
特点：
- 状态空间有限
- 有状态转移函数确定：

时齐既约马尔科夫源的稳态状态分布

时齐：状态转移概率与时间无关
既约：从任意状态触发，经有限步总可以到达任一其他状态
状态转移矩阵：
n时刻的状态概率分布：

其中：对时齐既约马尔科夫源，状态的稳态分布存在

二元一阶马尔科夫源的熵率：

则：其中：

信息的无损压缩

等长编码

离散无记忆信源（DMS）

: 长度为的消息序列
: 长度为N的码字
: 码书，码字的集合
: 译码器

离散无记忆信源

字符表
概率分布：

输出长度为的消息序列。这样的序列一共有K个

编码

编码字符表
编码长度：
无损编码：

整数编码

- 编码字符表,则
或者或者
- 则, 每个字符要比特

可以看出，信源的输出序列越长，编码效率就越高，接近

编码序列越长，译码时延也越长

香农编码定理

当, 可以实现无损编码
当, 不存在无损编码
编码速率：
- 无损编码指信源编码的错误概率可以任意小，但并非是0
- 香农编码定理通常是对非常长的消息序列进行编码，特别当消息序列长度趋于无穷时，才能实现编码

典型列

当长度为的信源输出序列，个数为。当非常大时，根据大叔定理，输出序列中符号的个数约为, 具有这样构成成分的序列称为典型列。

典型列出现的概率为：典型列的个数：

典型列几乎等概率
当, 输出非典型列的可能性趋向于0
对典型列编码，编码速率为

渐进等分性质

长度为的输出序列：
序列发生的概率：
序列的自信息：
若定义随机变量

由切比雪夫不等式和一堆我看不懂的证明可得：

典型列集及典型列的性质

令为一个离散无记忆信源的熵，为任意正数

我们给出：为给定输出长度为的的典型列集合，简称典型列集，其中

典型列性质

当足够大时，有：

离散无记忆信源输出序列

：典型列集合，高概率集
：非典型列集合，低概率集

不等长编码

DMS的不等长编码

性质：

唯一可译性
- 非奇异：
- 码扩展：
如果码的任意扩展都是非奇异的，则称码是唯一可译的
即时可译性

平均码字长度：(码字长度的数学期望)

为判定一种不等长编码是否满足唯一可译性和即时可译性，我们引入一种判定方法：

即可以判定一种码是否是唯一可译的，即通过其唯一可译性可以确定它是即时可译的。

Sardinas & Petterson 判据

核心算法：后缀分解

现在我们有码字

从码字长度中最小的开始，查其是否为其他码字的前缀，如有，则将该码字的后缀填入
之后，从上到下查中的码字是否为中其他码字的前缀，接着查自身中，当前码字是否为其他码字的前缀。如果有，则将其后缀填入
重复上述操作继续向下迭代直到有以下几种情况：
1. 在后续的任意分解集中出现中的码字——不是唯一可译码
2. 某后缀分解集无法再继续分解——是唯一可译码

由此我们可知：

一个码是唯一可译码的充分必要条件是除外没有任何一个后缀分解集中包含码字

即时可译性与唯一可译性的判定

若, 则该码是即时可译并且唯一可译的
若,则该码是唯一可译的，且译码延时有限

异字头码

如果一个码中没有任何一个码字是其它码字的前缀，则称该码是异字头码，即

异字头码必为唯一可译码与即时可译码

在异字头码的树形表示中，可以发现所有的码字都只出现在叶节点上

如果有非叶子节点为码字，则其必为其叶子结点的前缀，不满足异字头码的规定。

Kraft不等式

存在长度为的元异字头码的充要条件为：

任何唯一可译码必然满足Kraft不等式

唯一可译码与异字头码的关系

唯一可译码
- 不等式成立
- 存在一个同样长度的异字头码

不等长编码定理

任意一个唯一可译码得到平均码字长度必须满足, 同时一定存在一个元唯一可译码，其平均长度满足
证明，，，去tmd吧，证了三页PPT，干啥啊

不等长编码定理的扩展

对于长为的平稳信源，有：

即：即：

编码速率：

即：

编码效率：

Huffman编码（最佳不等长编码）

最佳不等长编码：给定信源分布，在平均码长最短的意义上最佳
二元最佳码：给定信源分布，则最佳二元编码必然满足：
- 其出现概率越小的消息所对应的码长越长
- 出现概率最小的两个消息所对应的码长相等，且码字最后一位不同

首先对各个字符出现的概率从高到低进行排序（从上到下）
霍夫曼编码满足以下几条性质：
- 对和,有

霍夫曼编码是一个递归的编码，

可递归编码原理

辅助源：设有矩阵表示为

则其辅助源为：有如下定义：

对辅助源的最佳编码也是对原始源的最佳编码

Huffman编码原理

首先我们有一个原始源，并按照出现频率从大到小的顺序对所有码字进行排序
从下到上进行消息的合并，概率的相加，即创建原始源的辅助源，原始源中被合并之后的两个消息整体对应辅助源中的一个消息.

即图中和合并之后，辅助源中的为0.01，原始编码为
比较和的大小，如果则继续向上合并，则从开始，重复(2)过程。如果,则从辅助源的的开始，进行从下到上的字符合并。
重复（3）过程，直到迭代生成的辅助源中只有一个字符，即。如图所示，此时模拟异字头码中以树的形式进行不等长编码的过程，从该根节点开始对其叶子结点进行回溯遍历，得到每个叶子结点的码字。

例如的编码，由根节点，先走的路径到达子节点，再走的路径到达，则的编码为

D元Huffman编码

若, 则每次均由的消息要合并，短标号得到充分利用
若，则必须增补个概率为0的虚拟消息，使得最后一次合并仍然有个消息要合并，而充分利用短标号。

反正用CS一点的话就是，，，二元的霍夫曼编码一个节点有俩孩子，D元每个节点就要有D个孩子，为了保证合并到最后的根节点也必须有个孩子，就需要去补一些虚拟节点，使得倒数第二次合并的时候仍然有D个节点可以合并（倒数第二次合并的时候节点数可以为D，也可以为D+1）。

缺点：每次合并之后都要进行排序，时间复杂度（一般排序方法），很花费时间

几种不等长编码

Shannon 编码

编码的码长
- 的编码长度：
- 原始源：

其的二进制展开，从小数点后取码长的，即为对应的码字

编码是一个前缀码，且等同于最佳编码（编码）

码是前缀码
- 如果把长度为的二进制码字与一个区间, 则一个码是前缀码的充分必要条件为，这些码字所对应的区间彼此不相交
- 证明码是前缀码： 由此，后一个码的区间起点大于前一个码的区间终点，每一个码对应的区间严格不相交，则是一个前缀码
与相比，码渐进收敛性能较差
码逼近信源编码定理

Fano编码

将原始源切一刀：

概率和对分法：

所以实际上编码就是找到一个k，使得上述式子的计算值最小，然后对原始源以为界进行划分

从上到下进行左右子树的延伸，从根节点出现，向左标0，向右标1，生成各个叶子结点的编码。

Shannon-Fano-Elias 编码

信息的传输

离散无记忆信道容量与信道的组合

信道的抽象数学模型

离散无记忆信道
平稳信道

信道容量

信道容量为输出序列对不同输入序列所提供的最大互信息

离散无记忆信道容量

对于离散无记忆信道（DMC）其中等号在输入为独立随机序列时达到

因此

无噪信道

每个确定的x映射一个确定的y

无损信道

每一个y都可以唯一确定一个x

确定信道

每一个x都可以唯一确定一个y

无用信道

不能通过x确定y，也不能通过y确定x

复制信道

每个x可以等同地确定两个y，每个y可以等同确定两个x

二元对称信道(BSC)

当输入取等概分布时，输出Y也是等概分布。

二元除删信道

信道的组合

平行信道

开关信道

级联信道

离散无记忆信道的容量定理

优化目标

约束条件

是输入分布上的凸函数，因此极大值存在

定理：概率分布达到转移概率的离散无记忆信道容量C的充要条件为：

其中表示通过信道传送字符时，信道的输入与输出之间可获得的互信息的期望值即：

凸优化

。。。。

对称离散无记忆信道

离散无记忆信道的转移概率用矩阵来表示：

我们定义：向量的置换向量定义为：其中，是的任意排列

人话就是，假如一个向量是1,2,3,4。那只要把这四个数任意打乱顺序，2,3,1,4； 2,4,1,3 ；等等，都叫这个向量的一个置换向量

若的每一行都是第一行的一个置换，则该信道关于输入对称
若的每一列都是第一列的一个置换，则该信道关于输出对称
若一个信道既关于输出对称，又关于输出对称则该信道是对称的：

准对称离散无记忆信道

对一个信道的转移概率矩阵按列划分，得到若干个子信道，若划分出的所有子信道均是对称的，则称该信道是准对称的：

例如：把它按列拆分成两个子矩阵：这两个个子信道是对称的，所以称该信道为准对称的。

准对称离散无记忆信道的容量定理

达到准对称离散无记忆信道容量得到输入分布为均匀分布
若信道对于输入对称：

若信道同时也关于输出对称：

若信道只关于输入对称：

K元对称信道的容量

元对称信道的容量：信道容量为：

除删信道的容量

由于准对称信道的输入分布的均匀的：可以算出：

为二元除删信道
为二元对称信道

模K加法信道的容量

模K加法信道：
- 为任意分布

该信道是一个对称信道由于确定了和，就是唯一确定的，所以上式可以简化为：所以：

当为等概分布时，信道容量为0，当为确定性分布时，信道容量为

转移概率矩阵可逆信道容量

要求为一个逆矩阵，不要求对称。

假设, 则 =

中间证明过程如下，看不懂了

最后就是得到了：进一步，由 =

可以求出:

例题：

离散无记忆信道的编码定理

使用一种编码方法控制,来让信道容量达到最大。

编码速率（传输率）：单位：比特每传输 bit/s
香农信道编码定理：
- 如果信息传输速率R小于信道容量C，则总存在一种编码方法，使该信息在该信道上无错误的可靠传输
- 所有低于信道容量的速率都是可达的，即当时，总存在一系列码，当时，最大错误译码概率为
- 逆定理：具有的任何码必有

假如中每个符号映射到中的典型列都没有交集，则可以通过来准确译码：

且 也就是说，我们可以找到一种译码方式，使得每个符号的典型列，严格不相交。

离散无记忆信道上的一个码，由如下组成：
- 与个消息对应的标号集合
- 编码器，把消息映射成码字得到的码字为
  - 一个码的全体码字构成码书
- 译码器, ；对应于确定的译码法则，帮助接受者根据接收到的序列确定发送的消息是什么
发送第个消息所发生的错误概率为定义为:
- 最大错误概率定义为
- 平均错误概率
- 若存在一系列码，当时，最大错误概率,则被称为可达的