首页计算机科学算法信息论和编码

# 信源编码

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

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

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

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

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

对于输出长度为LL、字母表大小为KK 的信源，编码为长度为NN 的DD 元码字，如果需要无失真编码，至少应该有DN≤KLD^N\le K^L，也就是Nlog⁡D≤Llog⁡KN\log D\le L\log K。

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

在LL 足够大的条件下，满足

Nlog⁡D≤L[H(U)+εL]N\log D\le L[H(U)+\varepsilon_L]

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

说明

考虑信源输出的概率分布，有消息的概率p(uL)=∏lp(ul)p(\textbf{u}_L)=\prod_{l}p(u_l)，其信息量I(uL)=−log⁡p(uL)=−log⁡∏lp(ul)=∑l[−log⁡p(ul)]=∑lI(ul)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)，平均信息量IL=I(uL)/LI_L=I(\textbf{u}_L)/L。

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

E[I(uL)L]=E[∑lI(ul)L]=∑lE[I(ul)]L=H(U)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)

ILI_L 的方差为

E[I(uL)L−H(U)]2=E[I(uL)−LH(U)]2L2=E[∑lI(ul)−LH(U)]2L2=LσI2L2=σI2LE[\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 大数定理可知，对于∀ε>0\forall\varepsilon>0：

Pr[∣I(uL)L−H(U)∣>ε]<σI2Lε2=δPr[∣I(uL)L−H(U)∣≤ε]≤1−σI2Lε2=1−δ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，有

Pr[∣I(uL)L−H(U)∣≤ε]≥1−εP_r[\left|\frac{I(\textbf{u}_L)}{L}-H(U)\right|\le\varepsilon]\ge 1-\varepsilon

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

Nlog⁡D>LH(U)N\log D>LH(U)

# 渐进等分性和典型序列

# 定义

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

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

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

TU(L,ε)={uL:H(U)−ε<IL≤H(U)+ε}T_U(L,\varepsilon)=\{\textbf{u}_L:H(U)-\varepsilon<I_L\le H(U)+\varepsilon\}

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

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

TU(L,ε)={uL:L[p(ak)−ε]−ε<Lk≤L[p(ak)+ε]}T_U(L,\varepsilon)=\{\textbf{u}_L:L[p(a_k)-\varepsilon]-\varepsilon<L_k\le L[p(a_k)+\varepsilon]\}

其中LkL_k 为序列中aka_k 出现的次数。

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

  1. 给定信源{U,p(ak)}\{U,p(a_k)\}，ε>0\varepsilon>0，当L→∞L\to\infty，Pr{TU(L,ε)}→1P_r\{T_U(L,\varepsilon)\}\to 1。
  2. 对于任意小ε>0\varepsilon>0，存在正整数L0L_0，使得L>L0L>L_0，Pr{uL∈TU(L,ε)}≥1−εP_r\{\textbf{u}_L\in T_U(L,\varepsilon)\}\ge 1-\varepsilon。

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

# 特定序列出现概率

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

证明

通过定义式：

TU(L,ε)={uL:H(U)−ε<IL≤H(U)+ε}T_U(L,\varepsilon)=\{\textbf{u}_L:H(U)-\varepsilon<I_L\le H(U)+\varepsilon\}

有

H(U)−ε≤−1Llog⁡p(uL)≤H(U)+εH(U)-\varepsilon\le-\frac{1}{L}\log p(\textbf{u}_L)\le H(U)+\varepsilon

也就是

−L[H(U)+ε]≤log⁡p(uL)≤−L[H(U)−ε]-L[H(U)+\varepsilon]\le\log p(\textbf{u}_L)\le-L[H(U)-\varepsilon]

两边取 2 的幂，得证。

# 典型序列数目

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

证明

1=∑ULp(uL)≥∑uL∈TU(L,ε)p(uL)≥∑uL∈TU(L,ε)2−L[H(U)+ε]=∣TU(L,ε)∣2−L[H(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]}

即

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

由

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

有

1−ε≤∑uL∈TU(L,ε)p(uL)≤∑uL∈TU(L,ε)2−L[H(U)−ε]=∣TU(L,ε)∣2−L[H(U)−ε]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]}

即

∣TU(L,ε)∣≥(1−ε)2L[H(U)−ε]\left|T_U(L,\varepsilon)\right|\ge(1-\varepsilon)2^{L[H(U)-\varepsilon]}

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

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

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

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

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

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

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

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

证明

充分性：

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

∣TU(L,ϵ)∣≤2L[H(U)+ε]<2LR\left|T_U(L,\epsilon)\right|\le 2^{L[H(U)+\varepsilon]}<2^{LR}

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

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

那么pe=Pr{u^L≠uL}=Pr{uL∈T‾(L,ε)}≤εp_e=P_r\{\hat{\textbf{u}}_L\neq\textbf{u}_L\}=P_r\{\textbf{u}_L\in \overline{T}(L,\varepsilon)\}\le\varepsilon。这样子RR 是可达速率。

必要性：

令R=H(U)−2εR=H(U)-2\varepsilon，那么正确译码的概率是Pr{u^L=uL}=Pr{uL∈TU(L,ε)∩u^L=uL}+Pr{uL∈T‾U(L,ε)∩u^L}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εR=H(U)-2\varepsilon，所以有2L[H(U)−2ε]2^{L[H(U)-2\varepsilon]} 个码字，又因为典型序列个数至少为(1−ε)2L[H(U)−ε](1-\varepsilon)2^{L[H(U)-\varepsilon]}，所以在TU(L,ε)T_U(L,\varepsilon) 中可以找到码字的概率是：

p≤2L[H(U)−2ε](1−ε)2L[H(U)−ε]=2−Lε1−εPr{uL∈TU(L,ε)∩u^=uL}≤p≤2−Lε1−ε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}

而

Pr{uL∈T‾U(L,ε)∩u^L=uL}≤εP_r\{\textbf{u}_L\in \overline{T}_U(L,\varepsilon)\cap\hat{\textbf{u}}_L=\textbf{u}_L\}\le\varepsilon

因而

Pr{u^L=uL}≤2−Lε1−ε+εP_r\{\hat{\textbf{u}}_L=\textbf{u}_L\}\le \frac{2^{-L\varepsilon}}{1-\varepsilon}+\varepsilon

随着LL 的增加，上面的式子趋于 0，也就是pe→1p_e\to 1，因而RR 不可达。