不等长编码

约 597 个字 9 张图片 预计阅读时间 2 分钟

我们之前用过霍夫曼编码。

a	0.5	0
b	0.25	10
c	0.125	110
d	0.125	111
此时的$R$: $0.5\cdot 1+0.25 \cdot 2+0.125 \cdot 3+0.125 \cdot 3=1.75 \ bit = H(U)$
刚刚我们讨论的香农定理中，前提条件是$L \rightarrow \infty$ , 这只能在理论中推导，不能在现实中实现。而对于上面这个案例，刚好有一种很简单的方式达到这个$H(U)$值。

这就是实现该性质的方法——不等长编码。

一、定义

平均码长 $\overline{n}=\sum_{k=1}^K p_kn_k$

码A和码B有错误；
码C唯一可译码，但延迟。
码D唯一可译，且无延迟。

观察：

A:
$2^{-1}+2^{-1}+2^{-1}+2^{-2}\geq 1$ ×
B:
$2^{-1}+2^{-1}+2^{-2}+2^{-2}\geq 1$ ×
C/D:
$2^{-1}+2^{-2}+2^{-3}+2^{-4}\leq 1$ √
其实$a_4$还可以是111, 那么该式$2^{-1}+2^{-2}+2^{-3}+2^{-3}\leq 1$， 这里恰好取等。

二、唯一可译性

1. 定义

2. Sardinas & Petterson 判据

3. 异字头码

$S_1$ 是 $\emptyset$

00/001，000， 则若取了00，该节点就是下面叶子的前缀，叶子就不能取。所以所有码字只出现在叶结点上。

4. Kraft不等式

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

证明：
~~（这很离散XD）~~

任何唯一可译码必然满足Kraft不等式。

唯一可译码：
$\Rightarrow$ Kraft不等式成立
$\Rightarrow$ 存在一个同样长度的异字头码

（我们得出码C是唯一可译码，那么我们一定能够构造出一个码D，它是异字头码，传输没有延时）

5. 不等长编码定理

和香农定理联系起来（香农定理是针对等长编码的，不等长编码是否突破极限？）

（最后一步是由于Kraft不等式，$\leq 0$）

取等1：$p_k=D^{-n_k}$， （概率刚好是$2^{-n}$）
取等2：刚好取到所有叶子节点，没有浪费

对于概率分布没有这么好的序列：

因此这个定理让$H(U)\leq \overline{n} \leq H(U)+1$

是否能推广到$\overline{n}\leq H(U)+\epsilon$, 这就是不等长编码定理的扩展

$u\rightarrow \mathbf{u}^L$， 则$1 \rightarrow \frac{1}{L}$
因此目前的编码大多数是不等长编码

实际处理中，不一定需要$\epsilon$, 即$\eta$ 不一定是1

Comments