![](//upload.wikimedia.org/wikipedia/commons/thumb/5/5f/Disambig_gray.svg/25px-Disambig_gray.svg.png)
此条目介绍的是信源编码的数据压缩理论。关于计算机编程术语,请见“
源代码”。
在信息论中,香农的信源编码定理(或无噪声编码定理)确立了数据压缩的限度,以及香农熵的操作意义。
信源编码定理表明(在极限情况下,随着独立同分布随机变量数据流的长度趋于无穷)不可能把数据压缩得码率(每个符号的比特的平均数)比信源的香农熵还小,又不丢失信息。但是有可能使码率任意接近香农熵,且损失的概率极小。
码符号的信源编码定理把码字的最小可能期望长度看作输入字(看作随机变量)的熵和目标编码表的大小的一个函数,给出了此函数的上界和下界。
信源编码是从信息源的符号(序列)到码符号集(通常是bit)的映射,使得信源符号可以从二进制位元(无损信源编码)或有一些失真(有损信源编码)中准确恢复。这是在数据压缩的概念。
在信息论中,信源编码定理[1]非正式地陈述[2][3]为:
N 个熵均为 H(X) 的独立同分布的随机变量在 N → ∞ 时,可以很小的信息损失风险压缩成多于 N H(X) bit;但相反地,若压缩到少于 N H(X) bit,则信息几乎一定会丢失。
令 Σ1, Σ2 表示两个有限编码表,并令 Σ∗
1 和 Σ∗
2 (分别)表示来自那些编码表的所有有限字的集合。
设 X 为从 Σ1 取值的随机变量,令 f 为从 Σ∗
1 到 Σ∗
2 的唯一可译码,其中 |Σ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}](//wikimedia.org/api/rest_v1/media/math/render/svg/7af710c13eb23a7c771ef38abd9939d3fc71e3e8)
对于 1 ≤ i ≤ n 令 si 表示每个可能的 xi 的字长。定义
,其中 C 会使得 q1 + ... + qn = 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}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/169fe13cd5879db40f5ca63e9a73e6d99b6e3b14)
其中第二行由吉布斯不等式推出,而第五行由克拉夫特不等式推出:
![{\displaystyle C=\sum _{i=1}^{n}a^{-s_{i}}\leq 1}](//wikimedia.org/api/rest_v1/media/math/render/svg/11b1781597af68ac79e69f30c8e40237bc6bc12c)
因此 log C ≤ 0.
对第二个不等式我们可以令
![{\displaystyle s_{i}=\lceil -\log _{a}p_{i}\rceil }](//wikimedia.org/api/rest_v1/media/math/render/svg/0d4ce1b2b20eab899e13952689f57ae0e7ec84ea)
于是
![{\displaystyle -\log _{a}p_{i}\leq s_{i}<-\log _{a}p_{i}+1}](//wikimedia.org/api/rest_v1/media/math/render/svg/f3d69b1c1785dffb4b1df15103823e42e6daf02f)
因此
![{\displaystyle a^{-s_{i}}\leq p_{i}}](//wikimedia.org/api/rest_v1/media/math/render/svg/36657790767da95f5abe28686bc7a957c20d9f74)
并且
![{\displaystyle \sum a^{-s_{i}}\leq \sum p_{i}=1}](//wikimedia.org/api/rest_v1/media/math/render/svg/a6555a9325950933aaab932fb998351d6fe2497a)
因此由克拉夫特不等式,存在一种有这些字长的无前缀编码。因此最小的 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}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/e378e7d9efe7511f0bee22c33d1ead2e80f2e1cb)