信源编码定理

信息论中,香农的信源编码定理(或无噪声编码定理)确立了数据压缩的限度,以及香农熵的操作意义。

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

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

陈述

编辑

信源编码是从信息源的符号(序列)到码符号集(通常是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):

 

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

编辑

对于 1 ≤ insi 表示每个可能的 xi 的字长。定义  ,其中 C 会使得 q1 + ... + qn = 1。于是

 

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

 

因此 log C ≤ 0.

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

 

于是

 

因此

 

并且

 

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

 

参考资料

编辑
  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.