香农信源编码定理

命题陈述

设一个离散无记忆信源按某概率分布发出字母表中的符号，该分布的熵为 $H$（单位为比特，使用 $\log_2$）。那么对任意 $\varepsilon > 0$，存在一种无损分组编码，其每符号平均长度可以小于 $H + \varepsilon$（只要分组长度 $n$ 足够大）；反之，任何无损编码的每符号平均长度都不能低于 $H$。简言之，熵 $H$ 恰好是每符号可达到的最小平均比特数。

为什么成立?

一条消息所需的长度恰好等于它携带的『惊奇度』：一个几乎必然出现的符号几乎不需要比特来传递，而一个罕见的符号则需要许多比特。熵是把这种『惊奇度』（用 $-\log_2 p$ 衡量）在整个信源上取平均，从而给出一个硬性下限：你可以压缩掉常见的模式，但永远无法把一个随机信源压缩到低于其自身统计中固有的真实不可预测程度。

用到此定理的主题

分步证明

该定理暂无分步证明。