信源编码定理

此条目介绍的是信源编码的数据压缩理论。关于计算机编程术语，请见“源代码”。

在信息论中，香农的信源编码定理（或无杂讯编码定理）确立了数据压缩的限度，以及香农熵的操作意义。

信源编码定理表明（在极限情况下，随着独立同分布随机变量数据流的长度趋于无穷）不可能把数据压缩得码率（每个符号的位元的平均数）比信源的香农熵还小，又不丢失资讯。但是有可能使码率任意接近香农熵，且损失的概率极小。

码符号的信源编码定理把码字的最小可能期望长度看作输入字（看作随机变量）的熵和目标编码表的大小的一个函数，给出了此函数的上界和下界。

陈述

信源编码是从资讯源的符号（串行）到码符号集（通常是bit）的映射，使得信源符号可以从二进制位元（无损信源编码）或有一些失真（有损信源编码）中准确恢复。这是在数据压缩的概念。

信源编码定理

在信息论中，信源编码定理^[1]非正式地陈述^[2][3]为：

N 个熵均为 H(X) 的独立同分布的随机变量在 N → ∞ 时，可以很小的资讯损失风险压缩成多于 N H(X) bit；但相反地，若压缩到少于 N H(X) bit，则资讯几乎一定会丢失。

码符号的信源编码定理

令 Σ₁, Σ₂ 表示两个有限编码表，并令 Σ∗
1 和 Σ∗
2 （分别）表示来自那些编码表的所有有限字的集合。

设 X 为从 Σ₁ 取值的随机变量，令  f  为从 Σ∗
1 到 Σ∗
2 的唯一可译码，其中 |Σ₂| = a。令 S 表示字长  f (X) 给出的随机变量。

如果  f  是对 X 拥有最小期望字长的最佳码，那么(Shannon 1948)：

${\displaystyle {\frac {H(X)}{\log _{2}a}}\leq \mathbb {E} S<{\frac {H(X)}{\log _{2}a}}+1}$

证明：码符号的信源编码定理

对于 1 ≤ i ≤ n 令 s_i 表示每个可能的 x_i 的字长。定义 ${\displaystyle q_{i}=a^{-s_{i}}/C}$，其中 C 会使得 q₁ + ... + q_n = 1。于是

${\displaystyle {\begin{aligned}H(X)&=-\sum _{i=1}^{n}p_{i}\log _{2}p_{i}\\&\leq -\sum _{i=1}^{n}p_{i}\log _{2}q_{i}\\&=-\sum _{i=1}^{n}p_{i}\log _{2}a^{-s_{i}}+\sum _{i=1}^{n}p_{i}\log _{2}C\\&=-\sum _{i=1}^{n}p_{i}\log _{2}a^{-s_{i}}+\log _{2}C\\&\leq -\sum _{i=1}^{n}-s_{i}p_{i}\log _{2}a\\&\leq \mathbb {E} S\log _{2}a\\\end{aligned}}}$

其中第二行由吉布斯不等式推出，而第五行由克拉夫特不等式推出：

${\displaystyle C=\sum _{i=1}^{n}a^{-s_{i}}\leq 1}$

因此 log C ≤ 0.

对第二个不等式我们可以令

${\displaystyle s_{i}=\lceil -\log _{a}p_{i}\rceil }$

于是

${\displaystyle -\log _{a}p_{i}\leq s_{i}<-\log _{a}p_{i}+1}$

因此

${\displaystyle a^{-s_{i}}\leq p_{i}}$

并且

${\displaystyle \sum a^{-s_{i}}\leq \sum p_{i}=1}$

因此由克拉夫特不等式，存在一种有这些字长的无前缀编码。因此最小的 S 满足

${\displaystyle {\begin{aligned}\mathbb {E} S&=\sum p_{i}s_{i}\\&<\sum p_{i}\left(-\log _{a}p_{i}+1\right)\\&=\sum -p_{i}{\frac {\log _{2}p_{i}}{\log _{2}a}}+1\\&={\frac {H(X)}{\log _{2}a}}+1\\\end{aligned}}}$

参考资料

1. C.E. Shannon, "A Mathematical Theory of Communication （页面存档备份，存于互联网档案馆）", Bell System Technical Journal, vol. 27, pp. 379–423, 623-656, July, October, 1948
2. David J. C. MacKay. Information Theory, Inference, and Learning Algorithms （页面存档备份，存于互联网档案馆） Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1
3. Cover, Thomas M. Chapter 5: Data Compression. Elements of Information Theory. John Wiley & Sons. 2006. ISBN 0-471-24195-4.