信息论——Lossless Encoding

Posted on Edited on In

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

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

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

大数定律（Law of Large Number）

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

Snnp⃯p \frac{S_n}{n} \underrightarrow{p} p

更精确一点的说法：

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

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

−1nlog⁡p(X1,X2,...,Xn)p⃯H(X)-\frac 1 n \log p(X_1,X_2,...,X_n) \underrightarrow{p} H(X)

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

∀N,∃ϵ>0,σ>0,where n>N,p(|−1nlog⁡p(X1,X2,...,Xn)−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(X1,X2,...,Xn)≈2−nH(X)p(X_1,X_2,...,X_n)\approx 2^{-nH(X)}.

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

−1nlog⁡p(X1,X2,...,Xn)=−1nlog⁡p(X1)p(X2)...p(Xn)=−1n∑i=1nlog⁡p(Xi) \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}

因为我们知道，X1,X2,...,XnX_1,X_2,...,X_n是互相独立的，因此，log⁡X1,log⁡X2,...,log⁡Xn\log X_1,\log X_2,...,\log X_n也是互相独立同分布的。利用(1)： −1n∑i=1nlog⁡p(Xi)=−E(log⁡p(X))=∑x∈𝒳(−p(x)log⁡p(x))=H(X) \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)2^{-nH(X)}.

（弱）典型序列（Typical Sequence）

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

所以典型序列具有以下性质： 1. 若𝒙∈Aϵ(n)\mathbf{x} \in A_\epsilon ^ {(n)},则H(X)−ϵ≤−1nlog⁡p(𝒙)≤H(X)+ϵH(X)-\epsilon \leq -\frac 1 n \log p(\mathbf{x}) \leq H(X) + \epsilon. 2. 若nn足够大，$Pr(A_^{(n)}) - $ 3. |Aϵ(n)|≤2n(H(X)+ϵ)\vert A_\epsilon ^{(n)}\vert \leq 2^{n(H(X)+\epsilon)} 4. |Aϵ(n)|≥(1−ϵ)2n(H(X)−ϵ)\vert A_\epsilon ^{(n)}\vert \geq (1-\epsilon)2^{n(H(X)-\epsilon)}

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

  1. 1=∑xn∈𝒳P(xn)≥∑xn∈Aϵ(n)p(xn)≥∑xn∈Aϵ(n)2−n(H(x)+ϵ)=2−n(H(x)+ϵ)|Aϵ(n)| \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。 1−ϵ≤Pr{Aϵ(n)}≤∑xn∈Aϵ(n)2−n(H(X)−ϵ)=2−n(H(X)−ϵ)|Aϵ(n)| \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|X|^n种，大多数情况下，$ 2^{m(H(X)+)} << |X|^n$.所以典型序列集合只是所有可能集合的一个很小（尤其是原来分布远离均匀分布的时候）的子集。但是它几乎一定会出现，而且每个典型序列出现的概率几乎一样。这是很好的消息，为我们刚开始提出来的映射提供了很好的思路。

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

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

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

接下来提供证明：

E(l(Xn))=∑x∈𝒳p(x)l(x)=∑x∈Aϵ(n)p(x)l(x)+∑x∈Aϵ(n)¯p(x)l(x)≤∑x∈Aϵ(n)p(x)[n(H(X)+ϵ)+1+1]+∑x∈Aϵ(n)¯p(x)[nlog⁡|X|+2]=[n(H(X)+ϵ)+1+1]Pr{Aϵ(n)}+[nlog⁡|X|+2]Pr{Aϵ(n)¯}≤n(H(X)+ϵ)+2+nϵlog⁡|X|+2ϵ=n(H(X)+ϵ′) \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} 其中 ϵ′=ϵ+ϵlog⁡|X|+2n+2ϵn\epsilon' = \epsilon + \epsilon \log \vert X \vert +\frac 2 n + \frac {2\epsilon}{n},可以看到的是n→∞,ϵ′→0n \rightarrow \infty,\epsilon' \rightarrow 0.

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

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

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

假设Xn→M∈C={1,2,3,...,2nR}⏟neednRbits→X̂nX^n \rightarrow M \in C = \underbrace{ \{1,2,3,...,2^{nR} \} }_ {need ~nR~ bits} \rightarrow \hat{X}^n.

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

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

因此： nH(X)=H(Xn)...(Why?)=H(Xn)−H(Xn|M)=I(Xn,M)=H(M)−H(M|Xn)≤H(M)≤nR \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≥H(X)R\ge H(X).

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

码的类型

非奇异码

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

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

唯一可译码

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

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

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

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

即时码（前缀码）

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

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