香农信源编码定理

在信息论中，香农信源编码定理 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$ 表示两个有限字母，并让[math]\displaystyle{ \Sigma _{1}^{*} }[/math] 和[math]\displaystyle{ \Sigma _{2}^{*} }[/math]分别表示这些字母中所有有限词的集合。

假设 $X$ 是一个随机变量，取值在 $Σ 1$ ，让 $f$ 是一个唯一可解码代码，从[math]\displaystyle{ \Sigma _{1}^{*} }[/math]到[math]\displaystyle{ \Sigma _{2}^{*} }[/math]，其中[math]\displaystyle{ \left | \Sigma _{2} \right |=a }[/math]。让 $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]

典型集，[math]\displaystyle{ A_{n}^{\varepsilon } }[/math]定义如下：

[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$ ，使得由源在于典型的集合生成的序列的概率，[math]\displaystyle{ A_{n}^{\varepsilon } }[/math]，如定义接近一。特别是，对于足够大的 $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$ 中抽取[math]\displaystyle{ \underset{n}{\varepsilon } }[/math]大于 $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$ 的总概率的下界[math]\displaystyle{ \underset{n}{\varepsilon } }[/math].

自从[math]\displaystyle{ \left| A_n^\varepsilon \right| \leq 2^{n(H(X)+\varepsilon)}, n(H(X)+\varepsilon) }[/math] 位足以指向该集合中的任何字符串。

编码算法：编码器检查输入序列是否在典型集合内；如果是，则输出输入序列在典型集合中的索引；如果不是，则编码器输出任意 $n (H (X) + ε)$ 位数字。只要输入序列位于典型集合内（概率至少为 $1 - ε$ ), 位数字。只要输入序列位于典型集合内概率至少为 $ε$ 为界。

Converse的证明：反过来证明，任何小于 $A$ 的集合[math]\displaystyle{ \underset{n}{\varepsilon } }[/math]在指数的意义上）将涵盖一组远离 $1$ 的概率。

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

对于 $1 \leq i \leq n$ 让 $s i$ 表示每个可能的 $x i$ 的字长。定义[math]\displaystyle{ q_i = a^{-s_i}/C }[/math]，其中选择 $C$ 使得 $q 1 + ... + q n = 1$ 。然后

[math]\displaystyle{ \begin{align} 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{align} }[/math]

其中第二行来自Gibbs 不等式，第五行来自Kraft 不等式：

[math]\displaystyle{ C = \sum_{i=1}^n a^{-s_i} \leq 1 }[/math]

所以 $log C \leq 0$ 。

对于第二个不等式，我们可以设置

[math]\displaystyle{ s_i = \lceil - \log_a p_i \rceil }[/math]

以便

[math]\displaystyle{ - \log_a p_i \leq s_i \lt -\log_a p_i + 1 }[/math]

所以

[math]\displaystyle{ a^{-s_i} \leq p_i }[/math]

和

[math]\displaystyle{ \sum a^{-s_i} \leq \sum p_i = 1 }[/math]

因此，根据卡夫不等式，存在具有这些字长的无前缀代码。因此最小的 $S$ 满足

[math]\displaystyle{ \begin{align} \mathbb{E} S & = \sum p_i s_i \\ & \lt \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{align} }[/math]

非平稳独立源的扩展

离散时间非平稳独立源的固定速率无损源编码

定义典型集合[math]\displaystyle{ A_{n}^{\varepsilon } }[/math]作为：

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

然后，对于给定的 $δ > 0$ ，对于足够大的 $n$ ,[math]\displaystyle{ A_{n}^{\varepsilon }) \gt 1 − \delta }[/math]。现在我们只对典型集合中的序列进行编码，源码中的常用方法表明该集合的基数小于[math]\displaystyle{ 2^{n(\bar{H}_{\bar{n}}(X)+\varepsilon)} }[/math]。因此，平均而言[math]\displaystyle{ \bar{H}_{\bar{n}}(X)+\varepsilon }[/math]比特足以以大于 $1 - δ$ 概率进行编码，其中通过使 $n$ 更大，可以使 $ε$ 和 $δ$ 任意小。

编者推荐

集智俱乐部

集智文章推荐

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

美术研究中的一个核心问题是，不同年代和流派的绘画作品，在组织架构上，是否有着相似之处？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]