信息论基础
目录
1 信息熵 2
1.1 信息熵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 联合熵和条件熵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 相对熵和互信息 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 熵的链式法则 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 数据压缩 5
2.1 编码 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 最优编码 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 香农编码 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3 信道容量 6
1
1 信息熵
1.1 信息熵
香农认为, 信息是不确定性的减少. 为了衡量不确定性, 引入信息熵. 假定随机变量 𝑋 服从某个概率分布,
记 𝐻 (𝑋) 为其信息熵, 即为了确定 𝑋 的取值所需信息量. 希望满足以下性质
• 如果 𝑋 只有一个可能取值, 则 𝐻 (𝑋) = 0, 因为不需要任何信息就能确定 𝑋 的取值
• 如果 𝑋 的分布可以分为多个条件分布, 则 𝐻(𝑋) 等于条件的不确定度加上各条件分布的信息熵按概
率加权平均
基于此性质, 可以先给出等概率分布下的信息熵. 记有 𝑛 个等概率取值的随机变量 𝑋 其信息熵为 𝐻 (𝑛),
那么按照第二个性质, 为了确定具有 𝑚𝑛 个等概率取值的随机变量, 可以引入一个中间变量 𝑌, 它是一个
具有 𝑚 个等概率取值的随机变量
• 条件 𝑌 = 1: 𝑋 在前 𝑛 个取值中, 概率为 1/𝑚
• 条件 𝑌 = 2: 𝑋 在后 𝑛 个取值中, 概率为 1/𝑚
• · · ·
• 条件 𝑌 = 𝑚: 𝑋 在最后 𝑛 个取值中, 概率为 1/𝑚
那么 𝑋 的信息熵就是 𝑌 的信息熵加上各条件下 𝑋 的信息熵按概率加权平均. 在 𝑌 的每个取值下, 𝑋 都
是一个具有 𝑛 个等概率取值的随机变量, 其信息熵为 𝐻 (𝑛). 因此有
𝐻(𝑚𝑛) = 𝐻 (𝑚) +
𝑚
∑
𝑖=1
1
𝑚
𝐻(𝑛) = 𝐻(𝑚) + 𝐻(𝑛)
这说明此时的信息熵是对数函数
𝐻(𝑛) = 𝑘 log 𝑛
其中 𝑘 是一个常数, 简单起见取 𝑘 = 1. 进而可以将其推广到有理数情形. 设随机变量 𝑋 有 𝑛 个取值, 对
应概率为 {𝑝
𝑖
}, 那么可以取一个相当大的整数 𝑁, 使得 𝑁 𝑝
𝑖
都是整数. 引入一个新的随机变量 𝑌 , 它有 𝑁
个等概率取值, 满足
• 条件 𝑋 = 1: 𝑌 在前 𝑁 𝑝
1
个取值中, 概率为 𝑝
1
• 条件 𝑋 = 2: 𝑌 在后 𝑁 𝑝
2
个取值中, 概率为 𝑝
2
• · · ·
• 条件 𝑋 = 𝑛: 𝑌 在最后 𝑁 𝑝
𝑛
个取值中, 概率为 𝑝
𝑛
此时 𝑋 变为条件, 当 𝑋 取某个值时, 𝑌 是一个具有 𝑁 𝑝
𝑖
个等概率取值的随机变量, 其信息熵为 log(𝑁 𝑝
𝑖
).
因此有
𝐻(𝑌) = 𝐻 (𝑋) +
𝑛
∑
𝑖=1
𝑝
𝑖
log(𝑁 𝑝
𝑖
)
又因为 𝑌 有 𝑁 个等概率取值, 其信息熵为 log 𝑁, 因此
𝐻(𝑋) = log 𝑁 −
𝑛
∑
𝑖
=
1
𝑝
𝑖
log(𝑁 𝑝
𝑖
) = −
𝑛
∑
𝑖
=
1
𝑝
𝑖
log 𝑝
𝑖
只要将 𝑁 取得足够大, 就能无限逼近实数概率. 因此, 对于随机变量 𝑋 有可能取值 {𝑥
𝑖
}, 对应概率为 {𝑝
𝑖
},
则 𝑋 的信息熵定义为
𝐻(𝑋) = −
∑
𝑖
𝑝
𝑖
log
2
𝑝
𝑖
信息熵的单位是比特, 它是概率负对数的期望值
1.2 联合熵和条件熵
设有两个随机变量 𝑋, 𝑌 , 将其联合起来看作一个新的随机变量 (𝑋,𝑌 ) , 其信息熵称为 𝑋 和 𝑌 的联合熵
𝐻(𝑋, 𝑌) = −
∑
𝑥, 𝑦
𝑝(𝑥, 𝑦) log
2
𝑝(𝑥, 𝑦)
其中 𝑝(𝑥, 𝑦 ) 是 𝑋 = 𝑥 且 𝑌 = 𝑦 的联合概率. 当 𝑌 的取值已知时, 𝑋 的信息熵称为 𝑋 的条件熵. 它是在 𝑌
的各个取值下 𝑋 的信息熵按概率加权平均
𝐻(𝑋 |𝑌) =
∑
𝑦
𝑝(𝑦)𝐻(𝑋 |𝑌 = 𝑦) = −
∑
𝑦
𝑝(𝑦)
∑
𝑥
𝑝(𝑥|𝑦) log
2
𝑝(𝑥|𝑦)
因此
𝐻(𝑋 |𝑌) = −
∑
𝑥, 𝑦
𝑝(𝑥, 𝑦) log
2
𝑝(𝑥|𝑦)
条件熵的含义是, 在知道 𝑌 的取值后, 为了确定 𝑋 的取值所需的信息量, 也即包含在 𝑋 中的, 而不包含在
𝑌 中的信息量. 那么自然 𝑌 的信息熵加上 𝑋 的条件熵应该等于联合熵
𝐻(𝑋, 𝑌) = 𝐻 (𝑌) + 𝐻 (𝑋 |𝑌)
代入各个熵的表达式可以简单地验证其正确性
1.3 相对熵和互信息
𝑋 和 𝑌 共同携带的信息量称为互信息, 记为 𝐼 (𝑋;𝑌 ), 那么自然它等于联合熵减去各自的条件熵
𝐼 (𝑋;𝑌) = 𝐻(𝑋, 𝑌 ) − 𝐻(𝑋 |𝑌) − 𝐻 (𝑌 |𝑋)
稍加计算即可得到
𝐼 (𝑋;𝑌) =
∑
𝑥, 𝑦
𝑝(𝑥, 𝑦) log
2
𝑝(𝑥, 𝑦)
𝑝(𝑥) 𝑝(𝑦)
本质上来说, 互信息衡量的是 𝑋 和 𝑌 之间的相关性 , 也就是分布 𝑝(𝑥, 𝑦) 和独立分布 𝑝(𝑥) 𝑝 (𝑦) 之间的差
异. 那么上式就可以看作是这两个分布之间的相对熵或 Kullback-Leibler 散度
𝐷( 𝑝(𝑥)||𝑞(𝑥)) =
∑
𝑥
𝑝(𝑥) log
2
𝑝(𝑥)
𝑞(𝑥)
令 𝑝 为联合分布 𝑝(𝑥, 𝑦), 𝑞 为独立分布 𝑝 (𝑥) 𝑝(𝑦), 则有
𝐼 (𝑋;𝑌) = 𝐷 ( 𝑝(𝑥, 𝑦)||𝑝(𝑥) 𝑝(𝑦))
可以画出如下的韦恩图来表示各个熵之间的关系
𝐻(𝑋 |𝑌) 𝐼 (𝑋; 𝑌 ) 𝐻 (𝑌 |𝑋)
𝐻(𝑋) 𝐻(𝑌)
𝐻(𝑋, 𝑌 )
1.4 熵的链式法则
显然, 可以一个个地引入随机变量,
每一次补足缺失的信息
, 从而得到多个随机变量的联合熵, 也就是
𝐻(𝑋
1
, 𝑋
2
, · · · , 𝑋
𝑛
) = 𝐻 (𝑋
1
) + 𝐻 (𝑋
2
|𝑋
1
) + · · · + 𝐻(𝑋
𝑛
|𝑋
1
, 𝑋
2
, · · · , 𝑋
𝑛−1
)
只需要将多个随机变量视为一个, 然后反复使用两个变量情形的条件熵即可验证. 互信息也有类似的链式
法则, 𝑋
1
, 𝑋
2
, · · · , 𝑋
𝑛
与 𝑌 的互信息可以一次次补足缺失信息
𝐼 (𝑋
1
, 𝑋
2
, · · · , 𝑋
𝑛
; 𝑌 ) = 𝐼 (𝑋
1
; 𝑌 ) + 𝐼 (𝑋
2
; 𝑌 |𝑋
1
) + · · · + 𝐼 (𝑋
𝑛
; 𝑌 |𝑋
1
, 𝑋
2
, · · · , 𝑋
𝑛−1
)
其中带有竖线的互信息是条件互信息
𝐼 (𝑋;𝑌 |𝑍) = 𝐻 (𝑋 |𝑍) − 𝐻(𝑍 |𝑌, 𝑍) =
∑
𝑥, 𝑦,𝑧
𝑝(𝑥, 𝑦, 𝑧) log
2
𝑝(𝑥, 𝑦|𝑧)
𝑝(𝑥|𝑧) 𝑝(𝑦|𝑧)
相对熵也有类似的链式法则
𝐷( 𝑝(𝑥, 𝑦)||𝑞(𝑥, 𝑦)) = 𝐷 ( 𝑝(𝑥)||𝑞 (𝑥)) + 𝐷 ( 𝑝(𝑦|𝑥)||𝑞 (𝑦|𝑥))
其中带有竖线的相对熵是条件相对熵
𝐷( 𝑝(𝑦|𝑥)||𝑞(𝑦|𝑥)) =
∑
𝑥, 𝑦
𝑝(𝑥, 𝑦) log
2
𝑝(𝑦|𝑥)
𝑞(𝑦|𝑥)
它是在给定 𝑥 的条件下, 𝑦 的两个条件分布之间的相对熵按 𝑥 取值概率的加权平均
2 数据压缩
2.1 编码
假定有一个字母表, 其中元素构成的字符串称为码字. 关于随机变量 𝑋 的信源编码是指每一个取值 𝑥
𝑖
到
某个码字 𝑠
𝑖
的映射. 记这个映射为 𝐶 : 𝑥
𝑖
→ 𝑠
𝑖
, 则编码的平均长度为
𝐿(𝐶) =
∑
𝑖
𝑝(𝑥
𝑖
)𝑙(𝑠
𝑖
)
如果每一个不同的 𝑥
𝑖
都映射到不同的 𝑠
𝑖
, 则称编码是非奇异的. 进而可以得到输入字符串的编码字符串,
称为扩展编码
𝐶(𝑥
𝑖
1
𝑥
𝑖
2
· · · 𝑥
𝑖
𝑛
) = 𝐶 (𝑥
𝑖
1
)𝐶 (𝑥
𝑖
2
) · · · 𝐶(𝑥
𝑖
𝑛
)
其中等号后面表示字符串的串联. 如果扩展编码是非奇异的, 则称编码是唯一可译的, 也就是说可以从编
码字符串唯一地还原出输入字符串. 如果编码中没有任何码字是另一个码字的前缀, 则称编码是前缀码
前缀码的数量是有限的. 如果记字母表的大小为 𝐷, 则码字的长度 𝑙
1
, 𝑙
2
, · · · 必须满足 Kraft 不等式
∑
𝑖
𝐷
−𝑙
𝑖
≤ 1
反过来, 只要满足 Kraft 不等式的一组长度 𝑙
𝑖
, 就可以构造出对应的前缀码. 无论限制或者不限制编码长
度, 不等式总是成立
2.2 最优编码
假定有一个大小为 𝐷 的字母表, 希望设计一个前缀码, 使得平均长度 𝐿 最小, 即最小化
𝐿 =
∑
𝑖
𝑝(𝑥
𝑖
)𝑙
𝑖
事实上 𝐿 有下界
𝐿 ≥ 𝐻
𝐷
(𝑋) = −
∑
𝑖
𝑝(𝑥
𝑖
) log
𝐷
𝑝(𝑥
𝑖
)
并且当且仅当 𝐷
−𝑙
𝑖
= 𝑝(𝑥
𝑖
) 时取等号. 事实上如果限制编码是逐字符的, 还可以给出最优码长度的上界
𝐻
𝐷
(𝑋) ≤ 𝐿 < 𝐻
𝐷
(𝑋) + 1
哈夫曼编码是一种最优的前缀码构造方法
2.3
香农编码
香农编码方案首先将每一个 𝑋 的取值按照概率从大到小排序
𝑝(𝑥
1
) ≥ 𝑝(𝑥
2
) ≥ · · · ≥ 𝑝(𝑥
𝑛
)
随后为每一个取值分配码字长度
𝑙
𝑖
= ⌈− log
𝐷
𝑝(𝑥
𝑖
)⌉
为了确定具体的编码, 对于每一个 𝑥
𝑖
, 计算其累积概率
𝐹
1
= 0, 𝐹
2
= 𝑝(𝑥
1
), 𝐹
3
= 𝑝(𝑥
1
) + 𝑝(𝑥
2
), · · · , 𝐹
𝑛
=
𝑛−1
∑
𝑗=1
𝑝(𝑥
𝑗
)
随后将 𝐹
𝑖
表示为 𝐷 进制小数, 取其前 𝑙
𝑖
位作为 𝑥
𝑖
的码字
3 信道容量
将信道输入记为 𝑋, 输出记为 𝑌, 对于每一个输入 𝑥, 信道会以条件概率 𝑝(𝑦|𝑥) 输出 𝑦. 信道的信道容量
定义为输入和输出的互信息的最大值
𝐶 = max
𝑝 ( 𝑥)
𝐼 (𝑋;𝑌)
此处的最大值是对输入分布 𝑝(𝑥) 取的最大值. 它的含义是信道在一次传输中所能携带的最大信息量. 香
农证明, 只要信息传递的速率不超过信道容量, 就可以通过适当的编码使得误码率任意小
二元对称信道如下图所示
0
1
0
1
1 − 𝑝
1 − 𝑝
𝑝
𝑝
计算互信息
𝐼 (𝑋;𝑌) = 𝐻(𝑌) − 𝐻(𝑌 |𝑋) = 𝐻 (𝑌) −
∑
𝑥
𝑝(𝑥)𝐻(𝑌 |𝑋 = 𝑥) = 𝐻(𝑌) −
∑
𝑥
𝑝(𝑥)𝐻(𝑝) = 𝐻 (𝑌) − 𝐻 ( 𝑝)
其中 𝐻 (𝑝) = −𝑝 log
2
𝑝 − (1 − 𝑝) log
2
(1 − 𝑝), 是二元分布 ( 𝑝, 1 − 𝑝) 的信息熵. 由此得到信道容量
𝐶 = 1 − 𝐻(𝑝)
当输入均匀分布时达到最大值
二元擦除信道如下图所示
0
1
0
e
1
1 − 𝛼
1 − 𝛼
𝛼
𝛼
计算互信息
𝐼 (𝑋;𝑌) = 𝐻(𝑌) − 𝐻(𝑌 |𝑋) = 𝐻 (𝑌) −
∑
𝑥
𝑝(𝑥)𝐻(𝑌 |𝑋 = 𝑥) = 𝐻(𝑌) −
∑
𝑥
𝑝(𝑥)𝐻(𝛼) = 𝐻(𝑌) − 𝐻(𝛼)
为了得到 𝐻 (𝑌) 的最大值, 设 𝑥 取 0 的概率为 𝑝, 则 𝑦 取 0 的概率为 𝑝(1− 𝛼), 取 1 的概率为 (1 − 𝑝) (1 −𝛼),
取 𝑒 的概率为 𝛼. 因此
𝐻(𝑌) = 𝐻 (𝛼) + (1 − 𝛼)𝐻( 𝑝)
𝐻( 𝑝) 在 𝑝 = 1/2 时取得最大值 1, 因此信道容量为
𝐶 = 1 − 𝛼
