香农信源编码定理

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
薄荷讨论 | 贡献2021年12月29日 (三) 21:35的版本 →‎说明
(差异) ←上一版本 | 最后版本 (差异) | 下一版本→ (差异)
跳到导航 跳到搜索


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


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


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


说明

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

信源编码定理

在信息论中,信源编码定理(Shannon,1948) [1][2][3]):

N i.i.d.每个随机变量都有 H(X)可以压缩成超过N H(X)。随着N → ∞的信息丢失风险可以忽略不计;但反过来说,如果它们被压缩成少于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源,它的时间序列X1, ..., Xn是 iid ,在离散值情况下熵H(X)和在连续值情况下微分熵。源编码定理指出,对于任何ε > 0,即对于大于源熵的任何速率H(X) + ε,有足够大的n和一个编码器,该编码器采用源的niid 重复,X1:n,并将其映射到n(H(X) + ε)个二进制位,使得源符号X1: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 ≤ insi 表示每个可能的xi的字长。定义[math]\displaystyle{ q_i = a^{-s_i}/C }[/math],其中选择 C 使得q1 + ... + qn = 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协议。

  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. (2006). "Chapter 5: Data Compression". Elements of Information Theory. John Wiley & Sons. ISBN 0-471-24195-4.