香农信源编码定理

在信息论中，香农信源编码定理 Shannon's source coding theorem（或无噪声编码定理）建立了可能的数据压缩 data compression 的极限，以及香农熵 Shannon entropy的操作意义。

以克劳德·香农 Claude Shannon命名的信源编码定理表明，（在极限情况下，当独立的均匀分布的随机变量（i.i.d.）数据流的长度趋于无穷大时）不可能压缩数据使编码率（每个符号的平均比特数）小于信源的香农熵，而事实上又不能确定信息会丢失。然而，可以任意地使码率接近香农熵，损失的概率可以忽略不计。

符号码的信源编码定理根据输入单词(被视为一个随机变量)熵和目标字母表大小将最小可能期望码字长度作为一个函数，并设置了一个上下界。

说明

信源编码是从信源符号序列到字母符号序列(通常是比特)的映射，使信源符号能够准确地从二进制比特位(无损源编码)恢复或在某种失真(有损源编码)范围内恢复。这就是数据压缩的概念。

信源编码定理

在信息论中，信源编码定理(Shannon，1948) ^[1]非正式地表明(MacKay 2003, pg. 81,^[2] Cover 2006, Chapter 5^[3]):

$N$ i.i.d.每个随机变量都有熵 $H (X)$ 可以压缩成超过 $N H (X)$ 。随着 $N \to \infty$ ，位的信息丢失风险可以忽略不计；但反过来说，如果它们被压缩成少于 $N H (X)$ 位，则信息肯定将丢失。

符号码的源码定理

令 $Σ 1, Σ 2$ 表示两个有限字母，并让 $Σ 模板:Su$ 和 $Σ 模板:Su$ 分别表示这些字母中所有有限词的集合。

假设 $X$ 是一个随机变量，取值在 $Σ 1$ ，让 $f$ 是一个唯一可解码代码，从 $Σ{su$ }}到 $Σ{su$ }}，其中 $|Σ 2 模板:！。= a$ . 让 $S$ 表示由码字 $f (X)$ 的长度给出的随机变量。

如果 $f$ 是最优的，因为它具有 $X$ 的最小预期字长，则(Shannon 1948): X

[math]\displaystyle{ \frac{H(X)}{\log_2 a} \leq \mathbb{E}[S] \lt \frac{H(X)}{\log_2 a} +1 }[/math]

其中[math]\displaystyle{ \mathbb{E} }[/math]表示期望值运算符。

证明：源代码定理

给定 $X$ 是一个iid源，它的时间序列 $X 1, ..., X n$ 是 iid ，在离散值情况下熵 $H (X)$ 和在连续值情况下微分熵。源编码定理指出，对于任何 $ε > 0$ ，即对于大于源熵的任何速率 $H (X) + ε$ ，有足够大的 $n$ 和一个编码器，该编码器采用源的 $n$ iid 重复， $X 1: n$ ，并将其映射到 $n (H (X) + ε)$ 个二进制位，使得源符号 $X 1: n$ 可以至少 $1 - ε$ .的概率从二进制位中恢复。

可实现性证明。修正一些 $ε > 0$ ，让

[math]\displaystyle{ p(x_1, \ldots, x_n) = \Pr \left[X_1 = x_1, \cdots, X_n = x_n \right]. }[/math]

典型集， $A 模板:Su$ 定义如下：

[math]\displaystyle{ A_n^\varepsilon =\left\{(x_1, \cdots, x_n) \ : \ \left|-\frac{1}{n} \log p(x_1, \cdots, x_n) - H_n(X)\right| \lt \varepsilon \right\}. }[/math]

该渐近均分割性（AEP）示出了对于足够大 $n$ ，使得由源在于典型的集合生成的序列的概率， $A 模板:Su$ ，如定义接近一。特别是，对于足够大的 $n$ ，[math]\displaystyle{ P((X_1,X_2,\cdots,X_n) \in A_n^\varepsilon) }[/math]可以任意接近 1，具体来说，大于 [math]\displaystyle{ 1-\varepsilon }[/math]（有关证明，请参阅 AEP）。

典型集合的定义意味着那些位于典型集合中的序列满足：

[math]\displaystyle{ 2^{-n(H(X)+\varepsilon)} \leq p \left (x_1, \cdots, x_n \right ) \leq 2^{-n(H(X)-\varepsilon)} }[/math]

概率:

序列的概率[math]\displaystyle{ (X_1,X_2,\cdots X_n) }[/math]从 $A 模板:Su$ 大于 $1 - ε$ .
[math]\displaystyle{ \left| A_n^\varepsilon \right| \leq 2^{n(H(X)+\varepsilon)} }[/math]从左侧（下限）得出[math]\displaystyle{ p(x_1,x_2,\cdots x_n) }[/math].
[math]\displaystyle{ \left| A_n^\varepsilon \right| \geq (1-\varepsilon) 2^{n(H(X)-\varepsilon)} }[/math]，从上界得出[math]\displaystyle{ p(x_1,x_2,\cdots x_n) }[/math] 以及整个集合A的总概率的下界 $A 模板:Su$ .

Since [math]\displaystyle{ \left| A_n^\varepsilon \right| \leq 2^{n(H(X)+\varepsilon)}, n(H(X)+\varepsilon) }[/math] bits are enough to point to any string in this set.

The encoding algorithm: The encoder checks if the input sequence lies within the typical set; if yes, it outputs the index of the input sequence within the typical set; if not, the encoder outputs an arbitrary $n (H (X) + ε)$ digit number. As long as the input sequence lies within the typical set (with probability at least $1 - ε$ ), the encoder doesn't make any error. So, the probability of error of the encoder is bounded above by $ε$ .

Proof of Converse. The converse is proved by showing that any set of size smaller than $A 模板:Su$ (in the sense of exponent) would cover a set of probability bounded away from $1$ .

编者推荐

集智俱乐部

集智文章推荐

计算美学前沿速递：用信息论“重新发现”风景画艺术史

美术研究中的一个核心问题是，不同年代和流派的绘画作品，在组织架构上，是否有着相似之处？2020年10月发表在美国国家科学院院刊PNAS的论文中，研究者通过信息论和网络分析，对来自61个国家，1476名画家总计14912幅西方风景画的研究，证实了该假说。

Science前沿：用信息论解释动植物间的军备竞赛

在植物与植食性昆虫组成的生态系统中，不同物种在相互作用的过程中，彼此适应，形成了一个相互影响的协同适应系统。近期Sicence的一项研究从气味信息的角度，讨论动植物协同进化中的军备竞赛，对研究生态网络内部的交流机制很有启发。同期的一篇相关评论文章对该话题进行了全新解答，本文是该评论文章的编译。

本中文词条由11初步翻译，由Flipped审校，薄荷编辑，如有问题，欢迎在讨论页面留言。

本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。

↑ 引用错误：无效<ref>标签；未给name属性为Shannon的引用提供文字
↑ 引用错误：无效<ref>标签；未给name属性为MacKay的引用提供文字
↑ 引用错误：无效<ref>标签；未给name属性为Cover的引用提供文字

[Shannon-1] 引用错误：无效<ref>标签；未给name属性为Shannon的引用提供文字

[MacKay-2] 引用错误：无效<ref>标签；未给name属性为MacKay的引用提供文字

[Cover-3] 引用错误：无效<ref>标签；未给name属性为Cover的引用提供文字

[1]

[2]

[3]