不等长编码
约 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