Chapter 6 : 不等长编码

约 586 个字 6 张图片 预计阅读时间 3 分钟

为什么需要不等长编码？

举一个例子：

假设一个无记忆信源 $\{a_1,a_2,a_3\}$，概率密度为$\{0.5,0.25,0.25\}$，$H(U)=1.5\text{ bit}$

• 如果用等长编码, 则 L 很大时才能达到最佳编码的效率
• 如果用不等长编码,将 $\{a_1,a_2,a_3\}$ 分别编码成 $\{1,00,01\}$，译码器在收到 1 时，译码成 $a_1$，收到 00 时译码成 $a_2$，01 时译码成 $a_3$，比如：
• $10001100001101\stackrel{\mathrm{译}}{\Rightarrow }1,00,01,1,00,00,1,1,01=a_1{a}_2{a}_3{a}_1{a}_2{a}_2{a}_1{a}_1{a}_3$，平均码字长度为 $\bar{n}=\sum _{k=1}^K{p}_k{n}_k=1.5\text{ bit}$

DMS 的不等长编码

一个好的不等长编码应该满足以下条件：

• 唯一可译性
• 即时可译性

---

唯一可译性

• 非奇异性：$x_i\ne x_j\Rightarrow C(x_i)\ne C(x_j)$
• 码扩展：$C^{\ast }(x_1{x}_2\cdots x_n)=C(x_1)C(x_2)\cdots C(x_n)$

如果码的任意扩展都是非奇异的, 则称码是唯一可译的

Example

上面的码 A 和码 B 都不是唯一可译的，因为对于 A 来说如果收到 10，可以是 $a_4$，也可以是 $a_3{a}_2$，也可以是 $a_3{a}_1$；对于 B 来说如果收到 11，可以是 $a_4$ 也可以是 $a_2{a}_2$

码 C 和码 D 是唯一可译的

---

Sardinas & Petterson 判据

判据：一个码是唯一可译码的充分必要条件是除 $S_0$ 外没有任何一个后缀分解集中包含码字

• 如果 $S_1=\varphi$ 则该码是即时可译并且唯一可译的
• 如果 $S_n=\varphi ,n\ge 1$，则该码是唯一可译，且译码延时有限

Example

可以看到，上面的这个码的后缀分解集中包含码字，因此不是唯一可译的

---

异字头码

如果一个码中没有任何一个码字是其它码字的前缀, 则称该码是异字头码, 即 $S_1=\varphi$

异字头码的树形表示：所有码字只出现在叶结点上

---

Kraft 不等式

存在长度为 $n_1,n_2,\cdots ,n_K$ 的 D 元异字头码的充要条件为：$\sum _{k=1}^K{D}^{-n_k}\le 1$

Proof

必要性充分性

设 $n_1<n_2<\cdots <n_k$，可将异字头码的所有码字放置在码树的叶节点上，每放置一个长为 $n_k$ 的码字，相当于砍掉其下生长的子树的共 $D^{n_K-n_k}$ 个叶节点。为了保证放置过程可行，必须：

$$\sum _{n_k=1}^{n_K}{D}^{n_K-n_k}\le D^{n_K}\Rightarrow \sum _{n_k=1}^{n_K}{D}^{-n_k}\le 1$$

可将所有码字依次放置在码树的叶节点上, 方法如下：

对长为 $n_k$ 的码字在第 $n_k$ 层任选一个可用的叶节点，砍掉其下生长的子树，相当于砍掉第 $n_K$ 叶节点的 $\frac{1}{D_{n_k}}$，如果 $\sum _{n_k=1}^{n_K}{D}^{-n_k}\le 1$，则上述放置过程一直可以进行下去，即可以构成一个异字头码

• 任意唯一可译码必然满足 Kraft 不等式，即唯一可译码 $\Rightarrow$ Kraft 不等式成立 $\Rightarrow$ 存在一个同样长度的异字头码

Proof

$$\begin{array}{rl}(\sum _{k=1}^K{D}^{-n_k}{)}^r& =(\sum _{k_1=1}^K{D}^{-n_{k_1}})(\sum _{k_2=1}^K{D}^{-n_{k_2}})\cdots (\sum _{k_r=1}^K{D}^{-n_{k_r}})\\ & =\sum _{k_1=1}^K\sum _{k_2=1}^K\cdots \sum _{k_r=1}^K{D}^{-n_{k_1}-n_{k_2}-\cdots -n_{k_r}}\\ & =\sum _{i=1}^{r{n}_{max}}{A}_i{D}^{-i}\end{array}$$

由唯一可译性我们有 $A_i\le D^i$，那么：

$$\sum _{k=1}^K{D}^{-n_k}\le (\sum _{i=1}^{r{n}_{max}}1{)}^{\frac{1}{r}}\le (r{n}_{max}{)}^{\frac{1}{r}}=2^{\frac{1}{r}{\log }_2(r{n}_{max})}\stackrel{r\to \mathrm{\infty }}{\to }1$$

---

不等长编码定理

任何一个唯一可译码的平均码字长度必须满足 $\bar{n}\ge \frac{H(U)}{\log D}$，同时一定存在一个 D 元唯一可译码, 其平均长度满足 $\bar{n}\le \frac{H(U)}{\log D}+1$

Proof

（1）

$$\begin{array}{rl}H(U)-\bar{n}\log D& =-\sum _{k=1}^K(p_k\log p_k+p_k{n}_k\log D)\\ & =-\sum _{k=1}^K{p}_k\log \frac{D^{-n_k}}{p_k}\le -\sum _{k=1}^K{p}_k(\frac{D^{-n_k}}{p_k}-1)\\ & =\sum _{k=1}^K{D}^{-n_k}-1\le 0\end{array}$$

当且仅当 $D^{-n_k}=p_k$ 时，等式成立

（2）选择唯一的 $n_k$，使得 $D^{-n_k}\le p_k\le D^{-(n_k-1)}$

对左边不等式两侧求和，得 $\sum _{k=1}^K{D}^{-n_k}\le \sum _{k=1}^K{p}_k=1$

因此，存在长度为 $n_k$ 的异字头码

对右侧不等式取对数，并求期望值，得：

$$\begin{array}{rl}\sum _{k=1}^K{p}_k\log p_k& <-\sum _{k=1}^K{p}_k(n_k-1)\log D\\ \therefore H(U)& >(\bar{n}-1)\log D,\bar{n}<\frac{H(U)}{\log D}+1\end{array}$$

评论