信息论——Lossless Encoding

Posted on Edited on In

信息论算是应用数学，因此我们希望用熵，互信息这些东西来解决一些实际的问题。首先介绍下无失真编码定理，它早已经被广泛用在我们生活当中了。

首先，说到无失真编码，我们首先想到的是无损压缩了。无损压缩实际上是一个最大熵的问题。这样的情况下，能包含最多的信息，如果信息量一定，也就是最大熵的情况下需要平均较小的比特数（比如一个均匀分布随机变量X的熵为3,另一个非均匀分布随机变量熵Y也为3，那么|Y|>|X|,如果普通编码的话，Y的编码更长，但是它们包含的信息量却是一样的）。我们都知道的是，在均匀分布的时候熵是最大的。但是我们不能选择信源的分布，因为信源就在那里已经确定了。我们能否通过一个映射，一一对应的映射，使得一个非等概分布逐渐走向等概呢？答案是，可以，但是这太反直觉了。是啊虽然反直觉，但是它不反数学，所以它就是对的。

渐进等同分割性质（Asymptotic Equipartition Property）

大数定律（Law of Large Number）

这里先伯奴利大数定律(属于弱大数定律)。实际上所有的大数定律都在说一件事：当实验次数非常大的时候，频率趋向于概率（经验分布逼近于统计分布）。

$$
\frac{S_n}{n} \underrightarrow{p} p
$$

更精确一点的说法：

$$
\forall N, \exists \epsilon >0,\sigma>0, \text{where }n > N,p(\vert \frac{s_n}{n} - p\vert \geq \epsilon) <\sigma.
$$
另外一个大数定理（辛钦大数定律）：
$$
\begin{align}
\frac 1 n \sum_{i=1}^n X_i\underrightarrow{p} EX
\end{align}
$$
渐进等同分割性质定义如下：

如果$X_1,X_2,…$是独立同分布的离散随机变量，分布服从$p(x)$,则

$-\frac 1 n \log p(X_1,X_2,…,X_n) \underrightarrow{p} H(X)$

使用上面的更准确的写法如下：

$$
\forall N, \exists \epsilon>0, \sigma >0, \text{where }n > N,p(\vert - \frac 1 n \log p(X_1,X_2,…,X_n) - H(X)\vert \geq \epsilon) <\sigma.
$$

即$p(X_1,X_2,…,X_n)\approx 2^{-nH(X)}$.

这个定理可以使用弱大数定理地证明：

$$
\begin{aligned}
&-\frac 1 n \log p(X_1,X_2,…,X_n)\
& = -\frac 1 n \log p(X_1)p(X_2)…p(X_n)\
&=-\frac 1 n \sum_{i=1}^n \log p(X_i)
\end{aligned}
$$

因为我们知道，$X_1,X_2,…,X_n$是互相独立的，因此，$\log X_1,\log X_2,…,\log X_n$也是互相独立同分布的。利用(1)：
$$
\begin{aligned}
-\frac 1 n \sum_{i=1}^n \log p(X_i) &= -E(\log p(X))\
&= \sum_{x \in \mathcal{X} } (-p(x)\log p(x)) \
&= H(X)
\end{aligned}
$$

这意味着，当n很大的时候，一个序列出现的概率是几乎相等的，这个概率为$2^{-nH(X)}$.

（弱）典型序列（Typical Sequence）

典型序列定义如下：
相对于分布$p(x)$和序列$(x_1,x_2,…,x_n) \in X_n$,典型序列集合$A_\epsilon ^ {(n)}$定义为满足下列不等式约束的所有序列$\mathbf{x}$的集合：
$$
2^{-n(H(X)+\epsilon) \leq p(\mathbf{x}) = p(x_1,x_2,…,x_n) \leq 2^{-n(H(X)-\epsilon)} }
$$

所以典型序列具有以下性质：

  1. 若$\mathbf{x} \in A_\epsilon ^ {(n)}$,则$H(X)-\epsilon \leq -\frac 1 n \log p(\mathbf{x}) \leq H(X) + \epsilon$.
  2. 若$n$足够大，$Pr(A_\epsilon ^{(n)}) \geq 1 - \epsilon $
  3. $\vert A_\epsilon ^{(n)}\vert \leq 2^{n(H(X)+\epsilon)}$
  4. $\vert A_\epsilon ^{(n)}\vert \geq (1-\epsilon)2^{n(H(X)-\epsilon)}$

性质1,2可以用定义得到。因此这里证明3和4.

  1. $$
    \begin{aligned}
    1 &= \sum_{x^n \in \mathcal{X} }P(x^n)\
    &\geq \sum_{x^n \in A_\epsilon ^{(n)} } p(x^n)\
    &\geq \sum_{x^n \in A_\epsilon ^{(n)} } 2^{-n(H(x)+\epsilon)}\
    &= 2^{-n(H(x)+\epsilon)}\vert A_\epsilon ^{(n)} \vert
    \end{aligned}
    $$

4的证明首先要使用性质2。
$$
\begin{aligned}
1 - \epsilon &\leq Pr{A_\epsilon ^{(n)} }\
&\leq \sum_{x^n \in A_\epsilon ^{(n)} } 2 ^{-n(H(X) - \epsilon)}\
&= 2 ^{-n(H(X) - \epsilon)} \vert A_\epsilon ^{(n)}\vert
\end{aligned}
$$

所有可能出现的序列一共有$|X|^n$种，大多数情况下，$ 2^{m(H(X)+\epsilon)} << |X|^n$.所以典型序列集合只是所有可能集合的一个很小（尤其是原来分布远离均匀分布的时候）的子集。但是它几乎一定会出现，而且每个典型序列出现的概率几乎一样。这是很好的消息，为我们刚开始提出来的映射提供了很好的思路。

定长编码定理(香农第一定理)

假设$X^n$是由独立同分布离散随机变量$X\tilde{}p(X)$构成的序列。对于任意正数$\epsilon$，总有足够大的n，可以找到一个一一映射，将$X^n$映射到二进制序列，且满足:
$$
E\left[\frac 1 n l(X^n) \right] \leq H(X)+\epsilon
$$

上式中，$l(X^n)$表示的是编码需要的bit数。

接下来提供证明：

$$
\begin{aligned}
E(l(X^n)) &= \sum_{x \in \mathcal{X} } p(x) l(x)\
&= \sum_{x \in A_\epsilon ^{(n)} } p(x) l(x) + \sum_{x \in \overline{A_\epsilon ^{(n)} } } p(x) l(x)\
& \leq \sum_{x \in A_\epsilon ^{(n)} } p(x) [ n(H(X)+\epsilon)+1+1 ] + \sum_{x \in \overline{A_\epsilon ^{(n)} } } p(x) [ n\log \vert X\vert +2 ]\
&=[ n(H(X)+\epsilon)+1+1 ] Pr{ A_\epsilon ^{(n)} } + [ n\log \vert X\vert +2] Pr{\overline{A_\epsilon ^{(n)} } } \
&\leq n(H(X)+\epsilon)+2 + n\epsilon \log\vert X\vert+2\epsilon
= n(H(X) + \epsilon ‘)
\end{aligned}
$$
其中 $\epsilon’ = \epsilon + \epsilon \log \vert X \vert +\frac 2 n + \frac {2\epsilon}{n}$,可以看到的是$n \rightarrow \infty,\epsilon’ \rightarrow 0$.

上面证明过程中值得注意的事情是，为什么要加2？第一个加一是为了处理log后为非整数的情况，第二个+1是留一个比特位置来区分典型序列与非典型序列的编码。

但是，定长编码定理是无法应用到工业界的。因为它需要对序列长度为n来进行编码，由于精确度的要求，这个n往往很大（上亿），这在现实中是无法实现的。

顺便我们证明一下，平均每个字符编码所需要的bit数一定是大于等于$H(X)$.

假设$X^n \rightarrow M \in C = \underbrace{ {1,2,3,…,2^{nR} } }_{need nR bits} \rightarrow \hat{X}^n$.

意思就是，M为X^n编码后的结果，它一定是属于后面的某个数字。

如果我们想要$P_e = 0$,也就是无失真编码，那么根据Fano不等式：
$$
H(X^n|M) = 0
$$

因此：
$$
\begin{aligned}
nH(X) &= H(X^n)…(Why?)\
&=H(X^n) - H(X^n|M)\
&=I(X^n,M)\
&=H(M) - H(M|X^n)\
&\leq H(M) \leq nR
\end{aligned}
$$

所以可以得到：$R\ge H(X)$.

可见，熵是平均码长的下界。

码的类型

非奇异码

若一个码C可以将不同的x映射为不同的$D^*$中 的序列，即：
$$
x \ne x’ \rightarrow C(x) \ne C(x’)
$$
则该码为非奇异码。

但是仅仅是非奇异码的序列可能会有歧义（很好笑）。$x_1 \rightarrow 0,x_2 \rightarrow 1,x_3 \rightarrow 01$，那么我收到$01$就不知道该如何介绍它了。

唯一可译码

唯一可译码是非奇异码的子集。称码$C^*$为码$C$的扩展，当$C^*$是有限长X的序列到有限长D序列的映射，且满足：
$$
C(x_1,x_2,…,x_n) = C(x_1)C(x_2)…C(x_n)
$$
则该码为唯一可译码。

从另一方面来说，如果码的扩展为非奇异码，则该码为唯一可译码。

换句话说，没有码字是码字的组合。

这样的也是有缺点的，因为解码器复杂度要求较高。如$x_1 = 01,x_2 = 10,x_3 = 0111$,当收到0110的时候，在前三个的时候解码器预测可能是个$x_3$,但是最后一个不满足，因此就需要回退。

即时码（前缀码）

前缀码大家就比较熟悉了。前缀码是唯一可译码的子集。如常用的霍夫曼编码。它的意思是没有什么码字是另一个码字的前缀。所以解码器只要发现有认识的，立马就可以解码了，所以叫即时码。

莫尔斯电码是非奇异码，但不是唯一可译码。汉语也不是唯一可译码，因为断句不对就会引起歧义。