# 信源编码

对于信源输出序列 $\{\textbf{u}_L\}=\{u_1,u_2,...,u_L\}$ ，满足其中元素都在字母表 $\textbf{A}=\left[\begin{array}{}a_1, a_2, ..., a_K\\ p_1, p_2, ..., p_K\end{array}\right]$ 中。找到一个到码字集合 $B=\{b_1,b_2,...,b_D\}$ 上的码字序列 $\{\textbf{v}_N\}=(v_1,v_2,...,v_N)$ 的映射，这个过程也就是信源编码。

对于有 $D$ 个元素的集合 $B$ ，到这个码字集合上的编码也就是 D 元码。

如果 $B$ 中各个码字长度相等，那么这个编码就是等长编码，反之为不等长编码。

编码的目的是为了对通信系统进行优化，信源编码可以减少信源发出的消息的冗余度，提高单位时间内传输的效率。

# 离散信源无失真等长编码

对于输出长度为 $L$ 、字母表大小为 $K$ 的信源，编码为长度为 $N$ 的 $D$ 元码字，如果需要无失真编码，至少应该有 $D^N\le K^L$ ，也就是 $N\log D\le L\log K$ 。

实际上许多时候这样的无失真编码是难以达成的，一个较弱的条件是几乎无失真等长编码。

在 $L$ 足够大的条件下，满足

$N\log D\le L[H(U)+\varepsilon_L]$

$H(U)$ 为信源熵， $\varepsilon_L$ 和 $L$ 有关，当 $L\to\infty$ ，有 $\varepsilon\to 0$ 。在这样的情况下，编码可以几乎不损失信息。

说明

考虑信源输出的概率分布，有消息的概率 $p(\textbf{u}_L)=\prod_{l}p(u_l)$ ，其信息量 $I(\textbf{u}_L)=-\log p(\textbf{u}_L)=-\log\prod_{l}p(u_l)=\sum_l[-\log p(u_l)]=\sum_lI(u_l)$ ，平均信息量 $I_L=I(\textbf{u}_L)/L$ 。

记信源熵为 $H(U)$ ， $I(u_l)$ 的方差为 $\sigma^2_I$ ，那么 $I_L$ 的均值为

$E[\frac{I(\textbf{u}_L)}{L}]=E[\frac{\sum_l I(u_l)}{L}]=\frac{\sum_l E[I(u_l)]}{L}=H(U)$

$I_L$ 的方差为

$E[\frac{I(\textbf{u}_L)}{L}-H(U)]^2=\frac{E[I(\textbf{u}_L)-LH(U)]^2}{L^2}=\frac{E[\sum_lI(u_l)-LH(U)]^2}{L^2}=\frac{L\sigma_I^2}{L^2}=\frac{\sigma_I^2}{L}$

由 Chebyshev 大数定理可知，对于 $\forall\varepsilon>0$ ：

$P_r[\left|\frac{I(\textbf{u}_L)}{L}-H(U)\right| >\varepsilon]<\frac{\sigma_I^2}{L\varepsilon^2}=\delta\\[2ex] P_r[\left|\frac{I(\textbf{u}_L)}{L}-H(U)\right|\le\varepsilon]\le 1-\frac{\sigma_I^2}{L\varepsilon^2}=1-\delta\\$

使得 $\delta=\varepsilon$ ，有

$P_r[\left|\frac{I(\textbf{u}_L)}{L}-H(U)\right|\le\varepsilon]\ge 1-\varepsilon$

也就是 $L$ 足够大的时候， $I_L$ 取值几乎等于 $H(U)$ 。这样便有：

$N\log D>LH(U)$

# 渐进等分性和典型序列

# 定义

大数定律可以告诉我们，一个试验重复了足够多的次数之后，一个事件发生的频率会接近该事件发生的概率。当一个随机变量的序列足够长，那么这个序列其中一部分序列出现的频数会接近于其出现的概率，且这些序列的概率趋近于相等，概率之和接近于 1。这些序列也就是典型序列 (Typical Set)，这个性质就是渐进等分性 (Asymptotic Equipartition Property, AEP)。

对于典型序列，给出下面的定义：

令 $H(U)$ 为集合 $\{U,p(a_k)\}$ 的熵， $\forall \varepsilon>0$ ，将

$T_U(L,\varepsilon)=\{\textbf{u}_L:H(U)-\varepsilon<I_L\le H(U)+\varepsilon\}$

定义为信源 $U$ 输出长度为 $L$ 的典型序列集，或弱 $\varepsilon$ 典型序列集，其补集为非典型序列集。

一个更强的定义是强典型序列集 (Strongly typical set)：

$T_U(L,\varepsilon)=\{\textbf{u}_L:L[p(a_k)-\varepsilon]-\varepsilon<L_k\le L[p(a_k)+\varepsilon]\}$

其中 $L_k$ 为序列中 $a_k$ 出现的次数。

利用前面的性质和定义，我们可以知道：

给定信源 $\{U,p(a_k)\}$ ， $\varepsilon>0$ ，当 $L\to\infty$ ， $P_r\{T_U(L,\varepsilon)\}\to 1$ 。
对于任意小 $\varepsilon>0$ ，存在正整数 $L_0$ ，使得 $L>L_0$ ， $P_r\{\textbf{u}_L\in T_U(L,\varepsilon)\}\ge 1-\varepsilon$ 。

同时我们能够推出典型序列的一些性质：

# 特定序列出现概率

如果 $\textbf{u}_L\in T_U(L,\varepsilon)$ ，那么 $2^{-L[H(U)+\varepsilon]}\le p(\textbf{u}_L)\le 2^{-L[H(U)-\varepsilon]}$ ，即 $p(\textbf{u}_L)\approx 2^{-LH(U)}$ 。

证明

通过定义式：

$T_U(L,\varepsilon)=\{\textbf{u}_L:H(U)-\varepsilon<I_L\le H(U)+\varepsilon\}$

有

$H(U)-\varepsilon\le-\frac{1}{L}\log p(\textbf{u}_L)\le H(U)+\varepsilon$

也就是

$-L[H(U)+\varepsilon]\le\log p(\textbf{u}_L)\le-L[H(U)-\varepsilon]$

两边取 2 的幂，得证。

# 典型序列数目

$L$ 足够大的情况下，给定信源 $\{U,p(a_k)\}$ ， $\varepsilon>0$ ，典型序列个数 $\left|T_U(L,\varepsilon)\right|$ 满足 $(1-\varepsilon)2^{L[H(U)-\varepsilon]}\le\left|T_U(L,\epsilon)\right|\le 2^{L[H(U)+\varepsilon]}$ ，也就是 $\left|T_U(L,\varepsilon)\right|\approx 2^{LH(U)}$ 。

证明

$1=\sum_{U^L}p(\textbf{u}_L)\ge\sum_{\textbf{u}_L\in T_U(L,\varepsilon)}p(\textbf{u}_L)\ge\sum_{\textbf{u}_L\in T_U(L,\varepsilon)}2^{-L[H(U)+\varepsilon]}=\left|T_U(L,\varepsilon)\right|2^{-L[H(U)+\varepsilon]}$

即

$\left|T_U(L,\varepsilon)\right|\le 2^{L[H(U)+\varepsilon]}$

由

$2^{-L[H(U)+\varepsilon]}\le p(\textbf{u}_L)\le 2^{-L[H(U)-\varepsilon]}$

有

$1-\varepsilon\le\sum_{\textbf{u}_L\in T_U(L,\varepsilon)}p(\textbf{u}_L)\le\sum_{\textbf{u}_L\in T_U(L,\varepsilon)}2^{-L[H(U)-\varepsilon]}=\left|T_U(L,\varepsilon)\right|2^{-L[H(U)-\varepsilon]}$

即

$\left|T_U(L,\varepsilon)\right|\ge(1-\varepsilon)2^{L[H(U)-\varepsilon]}$

这样子，一个离散无记忆信源 (discrete memoryless source, DMS) 输出的消息序列应该是分为两个部分：典型序列和非典型序列。

其中各个典型序列出现的概率近于相等，平均符号信息量接近于信源熵且概率之和接近于 1。

# DMS 编码模型和信源编码定理

这样一个 DMS 信源编码模型中，我们定义编码速率 $R=\cfrac{1}{L}\log M=\cfrac{N}{L}\log D$ 。

如果译码结果 $\hat{\textbf{u}}_L$ 和原始消息 $\textbf{u}_L$ 不相同，那么说明有错误，概率为 $p_e=p\{\hat{\textbf{u}}_L\neq\textbf{u}_L\}$ 。

如果给定信源和编码速率 $R$ ，对于任意 $\varepsilon>0$ ， $\exists L_0$ ，使得码长 $L>L_0$ ， $p_e<\varepsilon$ ，那么 $R$ 是可达的。

而编码速率是否可达，由下面的无扰编码定理给出；

信源编码定理 / 无扰编码定理
若 $R>H(U)$ ，则 $R$ 是可达的。若 $R<H(U)$ ，则 $R$ 是不可达的。
对于给定的 DMS 信源，若 $D$ 元码速率 $R$ 超过信源熵，即 $\cfrac{N}{L\log D}\ge[H(U)+\varepsilon]$ ，则存在有编码方式，使得 $L$ 足够大时译码错误概率任意小。

证明

充分性：

另 $R>H(U)$ ，取 $L>L_0$ 。通过上面的典型序列数目的结论，对于 $\varepsilon>0$ ，可以选择足够大的 $L$ 使得

$\left|T_U(L,\epsilon)\right|\le 2^{L[H(U)+\varepsilon]}<2^{LR}$

对于每个典型序列 $\textbf{u}_L\in T_U(L,\varepsilon)$ ，将其依次编号为 $1,2,...,2^{LR}-1$ ，采用相应号码的二进制序列来表示对应的码字。对于非典型序列 $\textbf{u}\in \overline{T}_U(L,\varepsilon)$ ，采用第 $2^{LR}$ 号号码 $000...000$ 表示。

这样，在译码的时候，如果 $\textbf(x)<2^{LR}$ ， $\hat{\textbf{u}}_L=\textbf{u}_L$ 。而若 $\textbf(x)=2^{LR}$ ， $\hat{\textbf{u}}_L=(000...000)$ 。

那么 $p_e=P_r\{\hat{\textbf{u}}_L\neq\textbf{u}_L\}=P_r\{\textbf{u}_L\in \overline{T}(L,\varepsilon)\}\le\varepsilon$ 。这样子 $R$ 是可达速率。

必要性：

令 $R=H(U)-2\varepsilon$ ，那么正确译码的概率是 $P_r\{\hat{\textbf{u}}_L=\textbf{u}_L\}=P_r\{\textbf{u}_L\in T_U(L,\varepsilon)\cap\hat{\textbf{u}}_L=\textbf{u}_L\}+P_r\{\textbf{u}_L\in \overline{T}_U(L,\varepsilon)\cap\hat{\textbf{u}}_L\}$ 。

因为 $R=H(U)-2\varepsilon$ ，所以有 $2^{L[H(U)-2\varepsilon]}$ 个码字，又因为典型序列个数至少为 $(1-\varepsilon)2^{L[H(U)-\varepsilon]}$ ，所以在 $T_U(L,\varepsilon)$ 中可以找到码字的概率是：

$p\le \frac{2^{L[H(U)-2\varepsilon]}}{(1-\varepsilon)2^{L[H(U)-\varepsilon]}}=\frac{2^{-L\varepsilon}}{1-\varepsilon}\\[2ex] P_r\{\textbf{u}_L\in T_U(L,\varepsilon)\cap\hat{\textbf{u}}=\textbf{u}_L\}\le p\le\frac{2^{-L\varepsilon}}{1-\varepsilon}$

而

$P_r\{\textbf{u}_L\in \overline{T}_U(L,\varepsilon)\cap\hat{\textbf{u}}_L=\textbf{u}_L\}\le\varepsilon$

因而

$P_r\{\hat{\textbf{u}}_L=\textbf{u}_L\}\le \frac{2^{-L\varepsilon}}{1-\varepsilon}+\varepsilon$

随着 $L$ 的增加，上面的式子趋于 0，也就是 $p_e\to 1$ ，因而 $R$ 不可达。

信息论