“香农信源编码定理”的版本间的差异
跳到导航
跳到搜索
| 第1行： | 第1行： | ||
| − | + | {{#seo: | |
| − | + | |keywords=信息论，源码理论，编程 | |
| − | + | |description=建立可能的数据压缩限制 | |
| − | + | }} | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | 在[[信息论]]中，'''香农信源编码定理 Shannon's source coding theorem'''（或无噪声编码定理）建立了可能的'''数据压缩 data compression '''的极限，以及'''香农熵 Shannon entropy'''的操作意义。 | |
| − | + | 以[[克劳德·香农]] Claude Shannon命名的信源编码定理表明，（在极限情况下，当独立的均匀分布的随机变量（i.i.d.）数据流的长度趋于无穷大时）不可能压缩数据使编码率（每个符号的平均比特数）小于信源的香农熵，而事实上又不能确定信息会丢失。然而，可以任意地使码率接近香农熵，损失的概率可以忽略不计。 | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
符号码的信源编码定理根据输入单词(被视为一个随机变量)熵和目标字母表大小将最小可能期望码字长度作为一个函数，并设置了一个上下界。 | 符号码的信源编码定理根据输入单词(被视为一个随机变量)熵和目标字母表大小将最小可能期望码字长度作为一个函数，并设置了一个上下界。 | ||
| + | ==说明== | ||
| + | 信源编码是从信源符号序列到字母符号序列(通常是比特)的映射，使信源符号能够准确地从二进制比特位(无损源编码)恢复或在某种失真(有损源编码)范围内恢复。这就是数据压缩的概念。 | ||
| − | == | + | ===信源编码定理=== |
| − | |||
| − | + | 在信息论中，信源编码定理(Shannon，1948) <ref name="Shannon"/>非正式地表明(MacKay 2003, pg. 81,<ref name="MacKay"/> Cover 2006, Chapter 5<ref name="Cover"/>): | |
| − | + | <blockquote>{{mvar|N}} [[独立和相同分布的随机变量|i.i.d.]]每个随机变量都有[[熵（信息论）|熵]] {{math|''H''(''X'')}}可以压缩成超过{{math|''N H''(''X'')}}。随着{{math|''N'' → ∞}}，[[位]]的信息丢失风险可以忽略不计；但反过来说，如果它们被压缩成少于{{math|''N H''(''X'')}} 位，则信息肯定将丢失。</blockquote> | |
| − | |||
| + | ===符号码的源码定理=== | ||
| + | 令{{math|Σ<sub>1</sub>, Σ<sub>2</sub>}}表示两个有限字母，并让{{math|Σ{{su|b=1|p=∗}}}} 和 {{math|Σ{{su|b=2|p=∗}}}}分别表示这些字母中所有有限词的集合。 | ||
| − | === | + | 假设{{mvar|X}}是一个随机变量，取值在{{math|Σ<sub>1</sub>}}，让{{math| ''f''  }}是一个[[可变长度代码#唯一可解码代码|唯一可解码]]代码，从{{math|Σ{su|b=1|p=∗}}}}到{{math|Σ{su|b=2|p=∗}}}}，其中{{math|{{! }}Σ<sub>2</sub>{{！}}。{{=}} ''a''}}. 让{{mvar|S}}表示由码字{{math| ''f'' (''X'')}}的长度给出的随机变量。 |
| − | |||
| − | + | 如果{{math| ''f'' }}是最优的，因为它具有{{mvar|X}}的最小预期字长，则(Shannon 1948): | |
| + | X | ||
| − | + | :<math> \frac{H(X)}{\log_2 a} \leq \mathbb{E}[S] < \frac{H(X)}{\log_2 a} +1 </math> | |
| − | + | 其中<math>\mathbb{E}</math>表示期望值运算符。 | |
| + | ==证明：源代码定理== | ||
| + | 给定{{mvar|X}}是一个iid源，它的时间序列{{math|''X''<sub>1</sub>, ..., ''X<sub>n</sub>''}}是 iid ，在离散值情况下熵{{math|''H''(''X'')}}和在连续值情况下微分熵。源编码定理指出，对于任何{{math|''ε'' > 0}}，即对于大于源熵的任何速率{{math|''H''(''X'') + ''ε''}}，有足够大的{{mvar|n}}和一个编码器，该编码器采用源的{{mvar|n}}iid 重复，{{math|''X''<sup>1:''n''</sup>}}，并将其映射到{{math|''n''(''H''(''X'') + ''ε'')}}个二进制位，使得源符号{{math|''X''<sup>1:''n''</sup>}}可以至少{{math|1 − ''ε''}}.的概率从二进制位中恢复。 | ||
| − | |||
| − | }} | + | 可实现性证明。修正一些{{math|''ε'' > 0}}，让 |
| − | + | :<math>p(x_1, \ldots, x_n) = \Pr \left[X_1 = x_1, \cdots, X_n = x_n \right].</math> | |
| − | < | ||
| − | == | + | 典型集，{{math|''A''{{su|b=''n''|p=''ε''}}}} 定义如下： |
| − | |||
| − | + | :<math>A_n^\varepsilon =\left\{(x_1, \cdots, x_n) \ : \ \left|-\frac{1}{n} \log p(x_1, \cdots, x_n) - H_n(X)\right| < \varepsilon \right\}.</math> | |
| − | |||
| − | + | 该渐近均分割性（AEP）示出了对于足够大{{mvar|n}}，使得由源在于典型的集合生成的序列的概率，{{math|''A''{{su|b=''n''|p=''ε''}}}}，如定义接近一。特别是，对于足够大的{{mvar|n}}，<math>P((X_1,X_2,\cdots,X_n) \in A_n^\varepsilon)</math>可以任意接近 1，具体来说，大于 <math>1-\varepsilon</math>（有关证明，请参阅 AEP）。 | |
| − | |||
| − | + | 典型集合的定义意味着那些位于典型集合中的序列满足： | |
| − | + | :<math>2^{-n(H(X)+\varepsilon)} \leq p \left (x_1, \cdots, x_n \right ) \leq 2^{-n(H(X)-\varepsilon)}</math> | |
| + | 概率: | ||
| − | + | *序列的概率<math>(X_1,X_2,\cdots X_n)</math>从{{math|''A''{{su|b=''n''|p=''ε''}}}} 大于{{math|1 − ''ε''}}. | |
| + | *<math>\left| A_n^\varepsilon \right| \leq 2^{n(H(X)+\varepsilon)}</math>从左侧（下限）得出<math> p(x_1,x_2,\cdots x_n)</math>. | ||
| + | *<math>\left| A_n^\varepsilon \right| \geq (1-\varepsilon) 2^{n(H(X)-\varepsilon)}</math>，从上界得出<math> p(x_1,x_2,\cdots x_n)</math> 以及整个集合A的总概率的下界{{math|''A''{{su|b=''n''|p=''ε''}}}}. | ||
| − | + | Since <math>\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 {{math|''n''(''H''(''X'') + ''ε'')}} digit number. As long as the input sequence lies within the typical set (with probability at least {{math|1 − ''ε''}}), the encoder doesn't make any error. So, the probability of error of the encoder is bounded above by {{mvar|ε}}. | |
| − | + | '''Proof of Converse.''' The converse is proved by showing that any set of size smaller than {{math|''A''{{su|b=''n''|p=''ε''}}}} (in the sense of exponent) would cover a set of probability bounded away from {{math|1}}. | |
| − | |||
| − | |||
| + | ==编者推荐== | ||
| + | [[File:Last1.png|400px|thumb|right|[https://swarma.org/?p=13364 用神经学习模型计算海量实际网络中的节点中心性度量 | 论文速递1篇|集智俱乐部]]] | ||
| + | ===集智文章推荐=== | ||
| + | ====[https://swarma.org/?p=21423 计算美学前沿速递：用信息论“重新发现”风景画艺术史]==== | ||
| + | 美术研究中的一个核心问题是，不同年代和流派的绘画作品，在组织架构上，是否有着相似之处？2020年10月发表在美国国家科学院院刊PNAS的论文中，研究者通过信息论和网络分析，对来自61个国家，1476名画家总计14912幅西方风景画的研究，证实了该假说。 | ||
| + | <br/><br/> | ||
| − | + | ====[https://swarma.org/?p=20253 Science前沿：用信息论解释动植物间的军备竞赛]==== | |
| + | 在植物与植食性昆虫组成的生态系统中，不同物种在相互作用的过程中， 彼此适应，形成了一个相互影响的协同适应系统。近期Sicence的一项研究从气味信息的角度，讨论动植物协同进化中的军备竞赛，对研究生态网络内部的交流机制很有启发。同期的一篇相关评论文章对该话题进行了全新解答，本文是该评论文章的编译。 | ||
| − | |||
| − | + | ---- | |
| + | 本中文词条由11初步翻译，由Flipped审校，[[用户:薄荷|薄荷]]编辑，如有问题，欢迎在讨论页面留言。 | ||
| − | |||
| − | |||
| − | + | '''本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。''' | |
| − | |||
| − | [[Category: | + | [[Category:信息论]] |
| + | [[Category:编码理论]] | ||
| + | [[Category:数据压缩]] | ||
| + | [[Category: 表示层协议]] | ||
| + | [[Category:理论计算机科学中的数学定理]] | ||
2021年12月29日 (三) 21:02的版本
在信息论中，香农信源编码定理 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 → ∞，位的信息丢失风险可以忽略不计；但反过来说，如果它们被压缩成少于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源，它的时间序列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]
典型集，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协议。