Chapter 5 : 等长编码¶

约 1049 个字 3 张图片预计阅读时间 5 分钟

信息论的信源问题¶

信源¶

信源是产生消息（包括消息序列）的源：图像、声波、符号，DNA序列等等。

信息论中的信源问题¶

构成描述信源的模型：随机变量序列或随机过程
计算信源输出的信息量，或者说信源的熵
如何有效地表示信源的输出，即信源编码

信源编码的目标：

在代价最小的意义上来最有效地表示一个信源。包括量化、压缩、映射、变换、自然语言翻译等许多具体和抽象的过程。
- 代价最小：最少的比特数；即到底用多少个比特可以对一个信源进行编码?

离散无记忆信源（DMS）¶

$u^L=(u_1,u_2,\cdots,u_L)$：长度为 $L$ 的消息序列
$x^N=(x_1,x_2,\cdots,x_N)$：长度为 $N$ 的码字
$\mathcal{C}$：码书、码字的集合（标号的集合）
$\mathcal{D}$：译码器

基本概念¶

一个离散无记忆信源，它的输出字符表为 $\mathcal{A} = \{a_1,a_2,\cdots,a_K\}$，相应的概率分布为 $\{p_1,p_2,\cdots,p_K\}$，满足 $\sum\limits_{i=1}^Kp_i=1$。如果信源输出长度为 $L$ 的消息序列为 $\pmb{u}^L=(u_1,u_2,\cdots,u_K)$，则信源可能输出 $K^L$ 种长度为 $L$ 的不同序列

另一个包含 $D$ 个符号的集合 $\mathcal{B} = \{b_1, b_2, \cdots, b_D\}$，称为编码字符表。现在要用长度为 $N$ 的编码字符序列（称为码字）来表示长度为 $L$ 的信源输出序列。这样的编码称为等长编码（因为所有待编码的消息序列都是等长的，所有码字长度也是一样的）

若这种表示是无损的，也就是说能从码字唯一正确地恢复出信源信息序列，则要求 $D^N\geq K^L\Rightarrow N\geq\frac{L\log K}{\log D}$

整数编码¶

$\mathcal{A}=\{0,1,\cdots,9\},L=1$
- 编码字符表 $\mathcal{B}=\{0,1\}$，则 $N\geq\log 10,N=4$
$\mathcal{A}=\{0,1,\cdots,9\},L=2$，或者 $\mathcal{A}=\{0,1,\cdots,99\},L=1$
- 则 $N\geq\log 100,N=7$，每个字符需要 3.5 个比特
$\mathcal{A}=\{0,1,\cdots,9\},L=\infty$
- $N_0=\frac{N}{L}\geq\log 10=3.322$
信源输出序列越长，编码效率越高，接近 $\log K$
实际实现过程中，编码序列越长，译码时延也越长

香农编码定理¶

问题

码字长度与熵的关系：$N\geq\frac{L\log K}{\log D},H(U)\leq\log K$

有没有可能 $N=\frac{LH(U)}{\log D}$？

香农编码定理：

当 $N>\frac{L(H(U)+\epsilon_L)}{\log D}$ 时，可以实现无损编码
当 $N<\frac{L(H(U)-\epsilon_L)}{\log D}$ 时，不存在无损编码
编码速率：$R=\frac{N}{L}\log D\rightarrow H(U)$
无损编码是指信源编码的错误概率可以任意小, 但并非为零
通常是对非常长的消息序列进行编码，特别当消息序列长度 $L$ 趋于无穷时，才能实现 Shannon 编码

Example

例如，$\mathcal{A}=\{0,1,\cdots,9\},L=1$

若 $p_0\rightarrow 0.5,p_1\rightarrow 0.5,p_i\rightarrow 0,i>2$，则 $H(A)\rightarrow 1$，每个符号的编码长度 $R\rightarrow 1$
若 $p_0\rightarrow 1,p_i\rightarrow 0,i>1$，则 $H(A)\rightarrow 0$，每个符号的编码长度 $N\rightarrow 1,R\rightarrow 0$

直观说明¶

长度为 $L$ 的信源输出序列，个数为 $K^L$ 。当 $L$ 非常大时，根据大数定理，输出序列中符号 $a_i$ 的个数约为 $Lp_i$，具有这样构成成分的序列称为典型列。典型列出现的概率为：

\[ \prod\limits_{i=1}^Kp_i^{Lp_i}=2^{-LH(U)} \]

典型列的个数：

\[ M=\frac{L!}{Lp_1!(L-Lp_1)!}\cdot\frac{(L-Lp_1)!}{Lp_2!(L-Lp_1-Lp_2)!}\cdots=\frac{L!}{\prod\limits_{i=1}^K(Lp_i)!} \]

根据斯特林公式：$x!\approx(\frac{x}{e})^x\sqrt{2\pi x}$，有：

\[ \begin{aligned} \log M&=L(\log L-1)+\frac{1}{2}\log(2\pi L)-\sum\limits_{i=1}^KLp_i(\log L+\log p_i-1)-\sum\limits_{i=1}^K\frac{1}{2}\log(2\pi Lp_i)\\ \frac{\log M}{L}&=H(U)-\frac{1}{2L}((K-1)\log(2\pi L)+\sum\limits_{i=1}^K\log p_i)\\ &\Rightarrow L\rightarrow\infty,M=2^{LH(U)} \end{aligned} \]

上面的证明说明：

典型列几乎等概
当 $L\rightarrow\infty$，输出非典型列的可能性趋于零
对于典型列编码，$R=H(U)$

渐进等分性质¶

长度为 $L$ 的输出序列 $\pmb{u}^L=(u_1,u_2,\cdots,u_L)$，序列发生的概率 $p(\pmb{u}^L)=\prod\limits_{l=1}^Lp(u_l)$，序列的自信息 $I(\pmb{u}^L)=-\log p(\pmb{u}^L)=\sum\limits_{l=1}^LI(u_l)$

定义随机变量：$I_L\stackrel{\Delta}{=}\frac{I(\pmb{u}^L)}{L}=\sum\limits_{l=1}^L\frac{I(u_l)}{L}$，则有：

$$ \begin{aligned}

\end{aligned} $$