什么是香农信源编码定理 | 集智百科

“集智百科精选”是一个长期专栏，持续为大家推送复杂性科学相关的基本概念和资源信息。作为集智俱乐部的开源科学项目，集智百科希望打造复杂性科学领域最全面的百科全书，欢迎对复杂性科学感兴趣、热爱知识整理和分享的朋友加入！

本文是对集智百科中“香农信源编码定理”词条的摘录，参考资料及相关词条请参阅百科词条原文。

本词条由集智俱乐部众包生产，难免存在纰漏和问题，欢迎大家留言反馈或者前往对应的百科词条页面进行修改，一经修改，可以获得对应的积分奖励噢！

目录

一、说明二、证明：源代码定理三、证明：符号代码的源编码定理四、非平稳独立源的扩展五、编者推荐六、百科项目志愿者招募

在信息论中，香农信源编码定理 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) 位，则信息肯定将丢失。

符号码的源码定理

令Σ₁,Σ₂表示两个有限字母，并让Σ₁*和Σ₂*分别表示这些字母中所有有限词的集合。

假设X是一个随机变量，取值在Σ₁，让 f  是一个唯一可解码代码，从Σ₁*到Σ₂*，其中|Σ₂|=a。让S表示由码字 f (X)的长度给出的随机变量。

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

其中Ε表示期望值运算符。

证明：源代码定理

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

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

典型集，A_n^ε 定义如下：

该渐近均分割性（AEP）示出了对于足够大n，使得由源在于典型的集合生成的序列的概率，A_n^ε ，如定义接近一。特别是，对于足够大的n，P(X₁,X₂,,,,,X_n)∈A_n^ε )可以任意接近 1，具体来说，大于1 − ε（有关证明，请参阅 AEP）。

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

概率:

• 序列的概率(X₁  ,X₂,,,,,X_n)从A中抽取_n^ε 大于1 − ε

• |A_n^ε |<=2^n(H(X)+ε)从左侧（下限）得出p(x₁,x₂,,,x_n)

• |A_n^ε |>=(1 − ε)2^n(H(X)-ε)，从上界得出p(x₁,x₂,,,x_n)以及整个集合A的总概率的下界_n^ε 

自从|A_n^ε |<=2^n(H(X)+ε，n(H(X)+ε)位足以指向该集合中的任何字符串。

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

Converse的证明：反过来证明，任何小于A的集合_n^ε 在指数的意义上）将涵盖一组远离1的概率。

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

对于1 ≤ i ≤ n让si 表示每个可能的xi的字长。定义q_i=a^-si/C，其中选择 C 使得q₁+ ... + q_n = 1。然后

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

所以log C ≤ 0。

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

以便

所以

和

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

非平稳独立源的扩展

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

定义典型集合A_n^ε作为：

然后，对于给定的δ > 0，对于足够大的n，A_n^ε>1-δ。现在我们只对典型集合中的序列进行编码，源码中的常用方法表明该集合的基数小于

因此，平均而言

比特足以以大于1 − δ概率进行编码，其中通过使n更大，可以使ε和δ 任意小。

编者推荐

集智俱乐部

集智文章推荐

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

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

百科项目志愿者招募

作为集智百科项目团队的成员，本文内容由11初步翻译，由Flipped审校，薄荷编辑。我们也为每位作者和志愿者准备了专属简介和个人集智百科主页，更多信息可以访问其集智百科个人主页。

以上内容都是我们做这项目的起点，作为来自不同学科和领域的志愿者，我们建立起一个有效的百科团队，分配有审校、翻译、编辑、宣传等工作。我们秉持：知识从我而来，问题到我为止的信念，认真负责编撰每一个词条。

在这里从复杂性知识出发与伙伴同行，同时我们希望有更多志愿者加入这个团队，使百科词条内容得到扩充，并为每位志愿者提供相应奖励与资源，建立个人主页与贡献记录，使其能够继续探索复杂世界。

如果你有意参与更加系统精细的分工，扫描二维码填写报名表，我们期待你的加入！

集智百科报名表

来源：集智百科

编辑：王建萍

推荐阅读

点击“阅读原文”，阅读词条香农信源编码定理原文与参考文献