Nov 3, 2025

信息论与编码___2025-11-03

信息论与编码___2025-11-03

基础定义

熵

以二进制为底, 单位是比特(bit)每符号(symbol), 此时单位称为 香农(Shannon), 其他单位如以自然对数为底, 单位是 纳特(nat), 以10为底, 单位是 哈特利(Hartley)

定义式: $H({X}) = - \sum_{i\in \mathcal{X}} p(x_i) \log p(x_i)$
期望: $H(\mathcal{X}) = - E[\log p(x)]$
联合熵: $H({X}, {Y}) = - \sum_{x \in \mathcal{X}} \sum_{y \in \mathcal{Y}} p(x,y) \log p(x,y) = - E[\log p(x,y)]$
条件熵:

$$ \begin{aligned} H(Y\mid X) &= \sum_{x\in\mathcal{X}} p(x),H(Y\mid X=x) \ &= -\sum_{x\in\mathcal{X}} p(x)\sum_{y\in\mathcal{Y}} p(y\mid x)\log p(y\mid x) \ &= -\sum_{x\in\mathcal{X}} \sum_{y\in\mathcal{Y}} p(x,y)\log p(y\mid x) \ &= -\mathbb{E}[\log p(Y \mid X)] \end{aligned} $$

条件熵描述的是: 在已知随机变量$X$的情况下, 随机变量$Y$的不确定性

链式法则: $H(X,Y) = H(X) + H(Y\mid X)$

其实就是 $log(ab) = log(a) + log(b)$ 的期望形式
推论: $H(X,Y\mid Z) = H(X\mid Z) + H(Y\mid X,Z)$

还是刚才的思路, 简单理解就是: 联合熵可以拆成条件熵的和
方便的记忆方式: “联合熵 = 第一个的熵 + 第二个在第一个已知条件下的熵”

条件熵计算时要注意:

先乘以条件的概率

再在此时条件下重新计算另一个变量的概率

$H(Y \mid X=x) = P_X(x) * \sum_{y\in\mathcal{Y}} P_Y(y\mid X=x) \log P_Y(y\mid X=x)$

相对熵与互信息

相对熵(KL散度): $D(p \space | \space q) = \sum_{i\in \mathcal{X}} p(x_i) \log \frac{p(x_i)}{q(x_i)} = E\left[\log \frac{p(x)}{q(x)}\right]$
其中: $D(0 \space | \space q) = 0$, $D(p \space | \space 0) = \infty$

即 似然比的对数的期望 相对熵衡量的是: 当实际分布是 $p$ 时, 假定分布是 $q$ 时的无效性可以视为一种距离度量, 但不满足对称性和三角不等式, 但视作"距离"会很有帮助

似然比是指在两个不同概率分布下, 某个事件发生的概率之比

互信息: $I(X;Y) = D(p(x,y) \space | \space p(x)p(y)) = \sum_{x\in\mathcal{X}} \sum_{y\in\mathcal{Y}} p(x,y) \log \frac{p(x,y)}{p(x)p(y)} = E\left[\log \frac{p(X,Y)}{p(X)p(Y)}\right]$

互信息衡量的是: 知道 $Y$ 后, 对 $X$ 的不确定性减少了多少
即, 给定知识$Y$的条件下, $X$不确定度的缩减量

互信息与熵的关系:

$$ \begin{aligned} I(X;Y) &= H(X) - H(X\mid Y) \ &= H(Y) - H(Y\mid X) \ &= H(X) + H(Y) - H(X,Y) \ \ I(X;X) &= H(X) - H(X\mid X) \ &= H(X) - 0 \ &= H(X) \end{aligned} $$

画成韦恩图更容易理解: 熵的韦恩图

链式法则: $$ \begin{aligned} H(X_1, X_2, \ldots, X_n) &= \sum_{i=1}^{n} H(X_i \mid X_1, X_2, \ldots, X_{i-1}) \ &= H(X_1) + H(X_2 \mid X_1) + H(X_3 \mid X_1, X_2) + \ldots \ \ I(X_1, X_2, \ldots, X_n; Y) &= \sum_{i=1}^{n} I(X_i; Y \mid X_1, X_2, \ldots, X_{i-1}) \ &= I(X_1; Y) + I(X_2; Y \mid X_1) + I(X_3; Y \mid X_1, X_2) + \ldots \end{aligned} $$
相对熵的条件形式: $$ \begin{aligned} D(p | q \mid Z) &= \sum_{x \in \mathcal{X}} \sum_{y \in \mathcal{Y}} p(x,y \mid Z) \log \frac{p(x,y \mid Z)}{q(x,y \mid Z)} \ &= \sum_{x \in \mathcal{X}} p(x \mid Z) D(p(y \mid x, Z) | q(y \mid x, Z) \mid x) \ &= E[D(p(Y \mid X, Z) | q(Y \mid X, Z) \mid X)] \ \ D(p(y|x) | q(y|x)) &= \sum_{x \in \mathcal{X}} p(x) D(p(y \mid x) | q(y \mid x)) \ &= E[D(p(Y \mid X) | q(Y \mid X))] \end{aligned} $$

凸函数

定义: 对于定义域内的任意两点 $x_1, x_2$ 和任意 $\lambda \in [0,1]$, 若有 $$ f(\lambda x_1 + (1-\lambda)x_2) \leq \lambda f(x_1) + (1-\lambda)f(x_2) $$ 则称函数 $f$ 在该区间上是凸函数

该不等式也称为Jensen不等式
若$-f$是凸函数, 则称$f$为凹函数

直观地, 如果一个函数始终在弦的下方, 则该函数是凸函数; 反之, 若始终在弦的上方, 则该函数是凹函数

如果函数$f$在区间上二阶可导, 则:
- 若对区间内任意$x$, $f’’(x) \geq 0$, 则$f$在该区间上是严格凸函数
- 若对区间内任意$x$, $f’’(x) \leq 0$, 则$f$在该区间上是严格凹函数

Jensen(琴生)不等式

定义: 设$f$为定义在实数集上的凸函数, $X$为一个随机变量, 则有 $$ E[f(X)] \geq f(E ) $$ 若$f$为凹函数, 则不等式方向相反
进一步, 如果$f$为严格凸函数, 则等式中蕴含$ X = E $ 的概率为1, 即所有取值均相等

简单而言, 凸函数的期望大于等于期望的函数值; 凹函数的期望小于等于期望的函数值
而且, 严格凸函数只有在随机变量取值恒等时才取等号
直观理解: 函数在弦的下方, 因此期望值处的函数值小于等于期望的函数值

数学分析形式: $$ \begin{aligned} \text{若 } \sum_{i=1}^{n} \lambda_i = 1, \lambda_i \geq 0, \text{ 则有 } \ f\left(\sum_{i=1}^{n} \lambda_i x_i\right) &\leq \sum_{i=1}^{n} \lambda_i f(x_i) \quad \text{(凸函数)} \end{aligned} $$

各类不等式

信息不等式: $D(p | q) \geq 0$, 当且仅当对于 $\forall x \in \mathcal{X}, p(x) = q(x)$ 时取等号

距离非负性, 两个分布相等时取等号
互信息的非负性: $I(X;Y) \geq 0$, 当且仅当 $X$ 与 $Y$ 独立时取等号

韦恩图中互信息部分面积只能是非负的, 如果两个变量独立, 则互信息为0
条件熵的不等式: $H(Y \mid X) \leq H(Y)$, 当且仅当 $X$ 与 $Y$ 独立时取等号

条件作用会减少熵, 信息没有负面作用
熵的独立界: $H(X_1, X_2, \ldots, X_n) \leq \sum H(X_i)$, 当且仅当 $X_1, X_2, \ldots, X_n$ 相互独立时取等号

联合熵小于等于各个熵之和, 独立时取等号
联合熵考虑了变量间的相关性, 这些信息会减少整体的不确定性
对数和不等式: 字母表$\mathcal{X}$上,以$|\mathcal{X}|$表示其中的元素数目,则有$H(X) \leq \log |\mathcal{X}|$, 当且仅当$X$服从均匀分布, 等号成立

只有均匀分布才能达到最大熵, 不确定性最大
相对熵的凸性: $$ \begin{aligned} &D(p||q)关于(p,q)是凸的,\ \ &D(\lambda p_1 + (1-\lambda)p_2 | \lambda q_1 + (1-\lambda)q_2) \ &\leq \lambda D(p_1 | q_1) + (1-\lambda) D(p_2 | q_2),\ \ &其中0 \leq \lambda \leq 1 \end{aligned}$$

相对熵作为距离度量, 满足凸性
记忆方式: “混合分布的相对熵小于等于各自相对熵的加权和”
熵的凹性: $H(p)$ 关于 $p(x)$ 是凹函数

熵作为不确定性度量, 满足凹性

费诺不等式 & 马尔科夫过程

没介绍

信源编码

也就是 数据压缩, 最优编码
也就是用 $D {0,1,2, … , D-1}$ 这 $D$ 个符号来描述随机事件 $X$ 的取值

编码长度

编码$C$是随机变量$X$在字母表$\mathcal{D}$上的一个映射, 即$C: \mathcal{X} \to \mathcal{D}^$, $\mathcal{D}^$表示在D元字母表上有限长度字符串的集合

$C(x)$ 表示随机变量$X$的码字
$l(x)$ 表示码字$C(x)$的长度
编码$C$的期望长度: $$ L(C) = E[l(X)] = \sum_{x \in \mathcal{X}} p(x) l(x) $$

Mcmillan - Kraft 不等式

Mcmillan(麦克米兰)不等式: 对于任意唯一可译的D元码的码字长度$l(x)$, 都有(反之亦然) $$ \sum_{x \in \mathcal{X}} D^{-l(x)} \leq 1 $$
Kraft不等式: 对于任意即时的D元码的码字长度$l(x)$, 都有 $$ \sum_{x \in \mathcal{X}} D^{-l(x)} \ \leq 1 $$

这里的"即时"指的是前缀编码, 即任意码字都不是另一个码字的前缀, 所以可以即时解析

也就是说, 对于任意的唯一可译编码或前缀编码, 其码字长度的指数和不能超过1
但不超过1可能是唯一可译编

最优码

随机变量$X$的任意D元即时码的期望长度都有: $L(C) \geq H_D(X)$
对于随机变量$X$, 其码长分布为 $L_i = ⌈ \log_D \frac{1}{p(x_i)} ⌉$, 则有最优码: $$ H(x) \leq L(C) \leq H(x) + 1 $$
对随机变量$X$的一个估计分布为 $q(x)$ , 取码长分配为 $L_i = ⌈ \log_D \frac{1}{p(x_i)} ⌉$, 则有: $$ H(p) + D(p | q) \leq L(C) \leq H(p) + D(p | q) + 1 $$

Huffman编码

对于分布已知的随机变量$X$, 可以使用Huffman霍夫曼编码来构造最优码:

将所有符号的概率按从小到大排序
取概率最小的两个符号, 合并为一个新符号, 新符号的概率为两个符号概率之和
将新符号插入到排序列表中, 重新排序
重复步骤2-3, 直到只剩一个符号
从根节点开始, 分配左子树为0, 右子树为1, 直到叶子节点, 得到每个符号的码字

信道编码

为了增强抗干扰, 添加冗余信息, 以便在接收端检测和纠正错误

信道容量

信道容量$C$定义为在给定信道条件下, 每次传输中能够可靠传输的最大信息量, 单位通常为比特每秒( bps )或比特每次传输( bits per transmission )。在离散无记忆信道中, 信道容量定义为: $$ C = \max_{p(x)} I(X;Y) $$

固定p(y|x)后, I(X;Y)关于p(x)是凹函数, 因此存在唯一的最大值