香农信源编码定理

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

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

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

说明

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

信源编码定理

在信息论中，信源编码定理(Shannon，1948) ):

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

符号码的源码定理

令Σ₁, Σ₂表示两个有限字母，并让[math]\displaystyle{ \Sigma _{1}^{*} }[/math] 和[math]\displaystyle{ \Sigma _{2}^{*} }[/math]分别表示这些字母中所有有限词的集合。

假设X是一个随机变量，取值在Σ₁，让 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₁, ..., X_n是 iid ，在离散值情况下熵H(X)和在连续值情况下微分熵。源编码定理指出，对于任何ε > 0，即对于大于源熵的任何速率H(X) + ε，有足够大的n和一个编码器，该编码器采用源的niid 重复，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 ≤ i ≤ n让s_i 表示每个可能的x_i的字长。定义[math]\displaystyle{ q_i = a^{-s_i}/C }[/math]，其中选择 C 使得q₁ + ... + 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 ≤ 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协议。