香农信源编码定理 - 版本历史

薄荷：/* 说明 */

2021-12-29T13:35:32Z

说明

2021年12月29日 (三) 13:34 薄荷

2021-12-29T13:34:18Z

薄荷：/* 符号码的源码定理 */

2021-12-29T13:31:55Z

符号码的源码定理

薄荷：/* 符号码的源码定理 */

2021-12-29T13:30:01Z

符号码的源码定理

薄荷：/* 非平稳独立源的扩展 */

2021-12-29T13:27:38Z

非平稳独立源的扩展

2021年12月29日 (三) 13:22 薄荷

2021-12-29T13:22:05Z

2021年12月29日 (三) 13:02 薄荷

2021-12-29T13:02:34Z

显示更改

2021年1月1日 (五) 15:14 Flipped

2021-01-01T15:14:10Z

2020年11月1日 (日) 10:24 11

2020-11-01T10:24:16Z

Moonscar：Moved page from wikipedia:en:Shannon's source coding theorem (history)

2020-10-27T10:23:54Z

Moved page from wikipedia:en:Shannon's source coding theorem (history)

显示更改

@@ 第18行： / 第18行： @@
 ===信源编码定理===
-在信息论中，信源编码定理(Shannon，1948) <ref name="Shannon">C.E. Shannon, "A Mathematical Theory of Communication", Bell System Technical Journal, vol. 27, pp. 379–423, 623-656, July, October, 1948</math>非正式地表明(MacKay 2003, pg. 81,<ref name="MacKay">David J. C. MacKay. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1</ref><ref name="Cover">Cover, Thomas M. (2006). "Chapter 5: Data Compression". Elements of Information Theory. John Wiley & Sons. ISBN 0-471-24195-4.</ref>):
+在信息论中，信源编码定理(Shannon，1948) <ref name="Shannon">C.E. Shannon, "A Mathematical Theory of Communication", Bell System Technical Journal, vol. 27, pp. 379–423, 623-656, July, October, 1948</ref><ref name="MacKay">David J. C. MacKay. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1</ref><ref name="Cover">Cover, Thomas M. (2006). "Chapter 5: Data Compression". Elements of Information Theory. John Wiley & Sons. ISBN 0-471-24195-4.</ref>):
 <blockquote>{{mvar|N}} [[独立和相同分布的随机变量|i.i.d.]]每个随机变量都有[[熵（信息论）|熵]] {{math|''H''(''X'')}}可以压缩成超过{{math|''N&thinsp;H''(''X'')}}。随着{{math|''N'' → ∞}}，[[位]]的信息丢失风险可以忽略不计；但反过来说，如果它们被压缩成少于{{math|''N&thinsp;H''(''X'')}} 位，则信息肯定将丢失。</blockquote>

@@ 第18行： / 第18行： @@
 ===信源编码定理===
-在信息论中，信源编码定理(Shannon，1948) <ref name="Shannon"/>非正式地表明(MacKay 2003, pg. 81,<ref name="MacKay"/> Cover 2006, Chapter 5<ref name="Cover"/>):
+在信息论中，信源编码定理(Shannon，1948) <ref name="Shannon">C.E. Shannon, "A Mathematical Theory of Communication", Bell System Technical Journal, vol. 27, pp. 379–423, 623-656, July, October, 1948</math>非正式地表明(MacKay 2003, pg. 81,<ref name="MacKay">David J. C. MacKay. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1</ref><ref name="Cover">Cover, Thomas M. (2006). "Chapter 5: Data Compression". Elements of Information Theory. John Wiley & Sons. ISBN 0-471-24195-4.</ref>):
 <blockquote>{{mvar|N}} [[独立和相同分布的随机变量|i.i.d.]]每个随机变量都有[[熵（信息论）|熵]] {{math|''H''(''X'')}}可以压缩成超过{{math|''N&thinsp;H''(''X'')}}。随着{{math|''N'' → ∞}}，[[位]]的信息丢失风险可以忽略不计；但反过来说，如果它们被压缩成少于{{math|''N&thinsp;H''(''X'')}} 位，则信息肯定将丢失。</blockquote>

←上一版本		2021年12月29日 (三) 13:31的版本
第27行：		第27行：


−	假设{{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'')}}的长度给出的随机变量。	+	假设{{mvar\|X}}是一个随机变量，取值在{{math\|Σ<sub>1</sub>}}，让{{math\| ''f''  }}是一个[[可变长度代码#唯一可解码代码\|唯一可解码]]代码，从<math>\Sigma _{1}^{}</math>到<math>\Sigma _{2}^{}</math>，其中<math>\left \| \Sigma _{2} \right \|=a</math>。让{{mvar\|S}}表示由码字{{math\| ''f'' (''X'')}}的长度给出的随机变量。

	如果{{math\| ''f'' }}是最优的，因为它具有{{mvar\|X}}的最小预期字长，则(Shannon 1948):		如果{{math\| ''f'' }}是最优的，因为它具有{{mvar\|X}}的最小预期字长，则(Shannon 1948):

@@ 第24行： / 第24行： @@
 ===符号码的源码定理===
-令{{math|Σ<sub>1</sub>, Σ<sub>2</sub>}}表示两个有限字母，并让{{math|Σ{{su|b=1|p=∗}}}} 和 {{math|Σ{{su|b=2|p=∗}}}}分别表示这些字母中所有有限词的集合。
+令{{math|Σ<sub>1</sub>, Σ<sub>2</sub>}}表示两个有限字母，并让<math>\Sigma _{1}^{*}</math> 和<math>\Sigma _{2}^{*}</math>分别表示这些字母中所有有限词的集合。
@@ 第36行： / 第36行： @@
 其中<math>\mathbb{E}</math>表示期望值运算符。
 ==证明：源代码定理==

←上一版本		2021年12月29日 (三) 13:27的版本
第131行：		第131行：


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

		+
		+	<br>

	==编者推荐==		==编者推荐==

@@ 第46行： / 第46行： @@
-典型集，{{math|''A''{{su|b=''n''|p=''ε''}}}} 定义如下：
+典型集，<math>A_{n}^{\varepsilon }</math>定义如下：
 :<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）。
+该渐近均分割性（AEP）示出了对于足够大{{mvar|n}}，使得由源在于典型的集合生成的序列的概率，<math>A_{n}^{\varepsilon }</math>，如定义接近一。特别是，对于足够大的{{mvar|n}}，<math>P((X_1,X_2,\cdots,X_n) \in A_n^\varepsilon)</math>可以任意接近 1，具体来说，大于 <math>1-\varepsilon</math>（有关证明，请参阅 AEP）。
@@ 第61行： / 第61行： @@
 概率:
-*序列的概率<math>(X_1,X_2,\cdots X_n)</math>从{{math|''A''{{su|b=''n''|p=''ε''}}}} 大于{{math|1 − ''ε''}}.
+*序列的概率<math>(X_1,X_2,\cdots X_n)</math>从{{math|''A''}}中抽取<math>\underset{n}{\varepsilon }</math>大于{{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=''ε''}}}}.
+*<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> 以及整个集合{{math|''A''}}的总概率的下界<math>\underset{n}{\varepsilon }</math>.
-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|ε}}.
+自从<math>\left| A_n^\varepsilon \right| \leq 2^{n(H(X)+\varepsilon)}, n(H(X)+\varepsilon)</math> 位足以指向该集合中的任何字符串。

@@ 第1行： / 第1行： @@
-本词条由11初步翻译
+本词条由11初步翻译，由Flipped审校
 https://wiki.swarma.org/index.php?title=%E5%B9%B3%E8%A1%A1%E7%90%86%E8%AE%BA#:~:text=%E6%9C%AC%E8%AF%8D%E6%9D%A1%E7%94%B1,11%E5%88%9D%E6%AD%A5%E7%BF%BB%E8%AF%91
@@ 第19行： / 第19行： @@
 In information theory, Shannon's source coding theorem (or noiseless coding theorem) establishes the limits to possible data compression, and the operational meaning of the Shannon entropy.
-在信息理论中，'''<font color="#ff8000"> 香农信源编码定理Shannon's source coding theorem </font>'''（或无噪声编码定理）建立了可能的数据压缩的极限，以及香农熵的操作意义。
+在信息理论中，'''<font color="#ff8000"> 香农信源编码定理  Shannon's source coding theorem </font>'''（或无噪声编码定理）建立了可能的'''<font color="#ff8000"> 数据压缩 data compression </font>'''的极限，以及'''<font color="#ff8000"> 香农熵 Shannon entropy </font>'''的操作意义。
@@ 第26行： / 第26行： @@
 Named after Claude Shannon, the source coding theorem shows that (in the limit, as the length of a stream of independent and identically-distributed random variable (i.i.d.) data tends to infinity) it is impossible to compress the data such that the code rate (average number of bits per symbol) is less than the Shannon entropy of the source, without it being virtually certain that information will be lost. However it is possible to get the code rate arbitrarily close to the Shannon entropy, with negligible probability of loss.
-以Claude Shannon克劳德·香农命名的信源编码定理表明，（在极限情况下，当独立的、相同分布的随机变量（i.i.d.）数据流的长度趋于无穷大时）不可能压缩数据，使码率（每个符号的平均比特数）小于信源的香农熵，而事实上又不能确定信息会丢失。然而，可以任意地使码率接近香农熵，损失的概率可以忽略不计。
+以克劳德·香农 Claude Shannon命名的信源编码定理表明，（在极限情况下，当独立的均匀分布的随机变量（i.i.d.）数据流的长度趋于无穷大时）不可能压缩数据使编码率（每个符号的平均比特数）小于信源的香农熵，而事实上又不能确定信息会丢失。然而，可以任意地使码率接近香农熵，损失的概率可以忽略不计。
@@ 第34行： / 第34行： @@
 The source coding theorem for symbol codes places an upper and a lower bound on the minimal possible expected length of codewords as a function of the entropy of the input word (which is viewed as a random variable) and of the size of the target alphabet.
-符号码的信源编码定理在最小可能期望码字长度上设置了一个上下界，该上下界是输入字(被视为一个随机变量)熵和目标字母表大小的函数。
+符号码的信源编码定理根据输入单词(被视为一个随机变量)熵和目标字母表大小将最小可能期望码字长度作为一个函数，并设置了一个上下界。
@@ 第45行： / 第45行： @@
 Source coding is a mapping from (a sequence of) symbols from an information source to a sequence of alphabet symbols (usually bits) such that the source symbols can be exactly recovered from the binary bits (lossless source coding) or recovered within some distortion (lossy source coding).  This is the concept behind data compression.
-信源编码是从信源符号序列到字母符号序列(通常是比特)的映射，以使信源符号能够准确地从二进制比特位(无损源编码)恢复或在某种失真(有损源编码)范围内恢复。这就是数据压缩的概念。
+信源编码是从信源符号序列到字母符号序列(通常是比特)的映射，使信源符号能够准确地从二进制比特位(无损源编码)恢复或在某种失真(有损源编码)范围内恢复。这就是数据压缩的概念。
@@ 第56行： / 第56行： @@
 In information theory, the source coding theorem (Shannon 1948)
-在信息论中，信源编码定理(Shannon，1948)
+在信息论中，信源编码定理(Shannon，1948) <ref name="Shannon"/>非正式地表明(MacKay 2003, pg. 81,<ref name="MacKay"/> Cover 2006, Chapter 5<ref name="Cover"/>):
@@ 第65行： / 第65行： @@
 }}
-<blockquote>{{mvar|N}}。[[独立和相同分布的随机变量|i.i.d.]]每个随机变量都有[[熵（信息论）|熵]]。{{math|''H''(''X'')}}可以压缩成多个{{math|''N&thinsp;H''(''X'')}}。[[位]]的信息丢失风险可以忽略不计，如{{math|''N'' → ∞}}；但反过来说，如果它们被压缩成少于{{math|''N&thinsp;H''(''X'')}}位，则几乎可以肯定信息将丢失。
+<blockquote>{{mvar|N}}。[[独立和相同分布的随机变量|i.i.d.]]每个随机变量都有[[熵（信息论）|熵]]。{{math|''H''(''X'')}}可以压缩成超过{{math|''N&thinsp;H''(''X'')}}。随着{{math|''N'' → ∞}} ，[[位]]的信息丢失风险可以忽略不计；但反过来说，如果它们被压缩成少于{{math|''N&thinsp;H''(''X'')}}位，则信息肯定将丢失。
@@ 第76行： / 第76行： @@
 Let {{math|Σ<sub>1</sub>, Σ<sub>2</sub>}} denote two finite alphabets and let {{math|Σ{{su|b=1|p=∗}}}} and {{math|Σ{{su|b=2|p=∗}}}} denote the [[Kleene star|set of all finite words]] from those alphabets (respectively).
 Category:Coding theory

@@ 第1行： / 第1行： @@
-此词条暂由彩云小译翻译，翻译字数共241，未经人工整理和审校，带来阅读不便，请见谅。
+本词条由11初步翻译
 {{short description|Establishes the limits to possible data compression}}
 {{Information theory}}
+{{信息论}}
 {{about|the theory of source coding in data compression|the term in computer programming|Source code}}
@@ 第15行： / 第19行： @@
 In information theory, Shannon's source coding theorem (or noiseless coding theorem) establishes the limits to possible data compression, and the operational meaning of the Shannon entropy.
-在信息论中，香农信源编码定理(或无噪声编码定理)建立了可能数据压缩的极限，以及香农熵的操作意义。
+在信息理论中，'''<font color="#ff8000"> 香农信源编码定理Shannon's source coding theorem </font>'''（或无噪声编码定理）建立了可能的数据压缩的极限，以及香农熵的操作意义。
@@ 第23行： / 第26行： @@
 Named after Claude Shannon, the source coding theorem shows that (in the limit, as the length of a stream of independent and identically-distributed random variable (i.i.d.) data tends to infinity) it is impossible to compress the data such that the code rate (average number of bits per symbol) is less than the Shannon entropy of the source, without it being virtually certain that information will be lost. However it is possible to get the code rate arbitrarily close to the Shannon entropy, with negligible probability of loss.
-以香农命名的信源编码定理表明(在极限下，作为独立同分布随机变量(i.i.d)流的长度数据趋于无穷大)不可能压缩数据，使码率(每个符号的平均比特数)小于信源的香农熵，而事实上又不能确定信息会丢失。然而，可以任意地使码率接近香农熵，损失的概率可以忽略不计。
+以Claude Shannon克劳德·香农命名的信源编码定理表明，（在极限情况下，当独立的、相同分布的随机变量（i.i.d.）数据流的长度趋于无穷大时）不可能压缩数据，使码率（每个符号的平均比特数）小于信源的香农熵，而事实上又不能确定信息会丢失。然而，可以任意地使码率接近香农熵，损失的概率可以忽略不计。
@@ 第36行： / 第39行： @@
 == Statements ==
 ''Source coding'' is a mapping from (a sequence of) symbols from an information [[Information theory#Source theory|source]] to a sequence of alphabet symbols (usually bits) such that the source symbols can be exactly recovered from the binary bits (lossless source coding) or recovered within some distortion (lossy source coding).  This is the concept behind [[data compression]].
@@ 第41行： / 第45行： @@
 Source coding is a mapping from (a sequence of) symbols from an information source to a sequence of alphabet symbols (usually bits) such that the source symbols can be exactly recovered from the binary bits (lossless source coding) or recovered within some distortion (lossy source coding).  This is the concept behind data compression.
-信源编码是从信源符号序列到字母符号序列(通常是比特)的映射，以使信源符号能够准确地从二进制比特位(无损源编码)恢复或在某种失真(有损源编码)内恢复。这就是数据压缩的概念。
+信源编码是从信源符号序列到字母符号序列(通常是比特)的映射，以使信源符号能够准确地从二进制比特位(无损源编码)恢复或在某种失真(有损源编码)范围内恢复。这就是数据压缩的概念。
 === Source coding theorem ===
 In information theory, the '''source coding theorem''' (Shannon 1948)<ref name="Shannon"/> informally states that (MacKay 2003, pg. 81,<ref name="MacKay"/> Cover 2006, Chapter 5<ref name="Cover"/>):
@@ 第60行： / 第65行： @@
 }}
+<blockquote>{{mvar|N}}。[[独立和相同分布的随机变量|i.i.d.]]每个随机变量都有[[熵（信息论）|熵]]。{{math|''H''(''X'')}}可以压缩成多个{{math|''N&thinsp;H''(''X'')}}。[[位]]的信息丢失风险可以忽略不计，如{{math|''N'' → ∞}}；但反过来说，如果它们被压缩成少于{{math|''N&thinsp;H''(''X'')}}位，则几乎可以肯定信息将丢失。
 === Source coding theorem for symbol codes ===
 Category:Information theory
@@ 第82行： / 第88行： @@
 Suppose that {{mvar|X}} is a random variable taking values in {{math|Σ<sub>1</sub>}} and let {{math|&thinsp;''f''&thinsp;}} be a [[Variable-length code#Uniquely decodable codes|uniquely decodable]] code from {{math|Σ{{su|b=1|p=∗}}}} to {{math|Σ{{su|b=2|p=∗}}}} where {{math|{{!}}Σ<sub>2</sub>{{!}} {{=}} ''a''}}. Let {{mvar|S}} denote the random variable given by the length of codeword {{math|&thinsp;''f''&thinsp;(''X'')}}.
 Category:Presentation layer protocols