7,129
个编辑
更改
跳到导航
跳到搜索
第46行：
第46行： − + − + 第61行：
第61行： − + − + − 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}}. + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
无编辑摘要
典型集，{{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>
:<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）。
概率:
概率:
*序列的概率<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| \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>.
自从<math>\left| A_n^\varepsilon \right| \leq 2^{n(H(X)+\varepsilon)}, n(H(X)+\varepsilon)</math> 位足以指向该集合中的任何字符串。
编码算法：编码器检查输入序列是否在典型集合内；如果是，则输出输入序列在典型集合中的索引；如果不是，则编码器输出任意{{math|''n''(''H''(''X'') + ''ε'')}}位数字。只要输入序列位于典型集合内（概率至少为 {{math|1 − ''ε''}}), 位数字。只要输入序列位于典型集合内概率至少为{{mvar|ε}}为界。
'''Converse的证明'''：反过来证明，任何小于{{math|''A''}}的集合<math>\underset{n}{\varepsilon }</math>在指数的意义上）将涵盖一组远离{{math|1}}的概率。
==证明：符号代码的源编码定理==
对于{{math|1 ≤ ''i'' ≤ ''n''}}让{{math|''s<sub>i</sub>''}} 表示每个可能的{{math|''x<sub>i</sub>''}}的字长。定义<math>q_i = a^{-s_i}/C</math>，其中选择 {{mvar|C}} 使得{{math|''q''<sub>1</sub> + ... + ''q<sub>n</sub>'' {{=}} 1}}。然后
:<math>\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>C = \sum_{i=1}^n a^{-s_i} \leq 1</math>
所以{{math|log ''C'' ≤ 0}}。
对于第二个不等式，我们可以设置
:<math>s_i = \lceil - \log_a p_i \rceil </math>
以便
:<math> - \log_a p_i \leq s_i < -\log_a p_i + 1 </math>
所以
:<math> a^{-s_i} \leq p_i</math>
和
:<math> \sum a^{-s_i} \leq \sum p_i = 1</math>
因此，根据卡夫不等式，存在具有这些字长的无前缀代码。因此最小的{{mvar|S}}满足
:<math>\begin{align}
\mathbb{E} S & = \sum p_i s_i \\
& < \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>A_{n}^{\varepsilon }</math>作为：
:<math>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| < \varepsilon \right \}.</math>
然后，对于给定的{{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|δ}} 任意小。