信息论——Kraft不等式以及变长编码定理

Posted on 2018-11-14 Edited on 2023-10-21 In 信息论

上次介绍了香农无损编码定理以及一些不同类别的编码。这次介绍kraft不等式以及huffman编码，并且说明霍夫曼编码的最优性。

Kraft不等式为前缀码约束条件。在前缀码中，显然不能使用所有的最短的码字，这样的话前缀码的条件就无法满足。就用二叉树来编码（二进制编码）的时候，如果一个节点被作为码字，则它的子树结点都无法作为码字。

Kraft不等式

kraft不等式定义如下：

任意D-进制码前缀码其码长$l_1,l_2,...,l_m$，满足 \[ \sum_{i} D^{-l_i} \leq 1 \]

反之，如果码长约束满足上述不等式，则必然可以构造出具有此码长的前缀码。

Kraft不等式的证明是非常直接的：

必要性：

我们依然从D叉树来考虑这个问题。假如码字最长为$l_{max}$.当一个结点被选做码字的时候，假设这个结点的深度为$l_i$，也就是码长为$l_i$.那么因为它的存在，它子树的结点都不能再次作为码字。因此我们就损失了D^{l_{max} - l_i}个叶子结点（注意，这里说的是叶子结点）。

这棵树的所有叶子结点数目为：$D^{l_max}$.我们最多把所有的叶子结点都给剪掉。

现在假设一共有m个码字，则： \[ \sum_{i=1}^m D^{l_{max} - l_i} \leq D^{l_{max} } \]

两侧同时除以$D^{l_{max} }$,就得到了kraft不等式。

充分性

充分性更好证明。我们只要在树上就可以很容易构造出来这样的编码。

Kraft不等式给出了即时码的充要条件，但是和最优码长无关。

任意前缀码码长约束

对随机变量X进行D进制前缀码编码，得到的码长满足： \[ L \ge H_D(X) \]

等号当且仅当$D^{-l_i} = p_i$时候成立。这个L为平均码长。

证明如下： \[ \begin{aligned} L - H_D(X) &= \sum P_i l_i - \sum P_i \log_D \frac 1 {P_i}\\ &= \sum P_i \log_D D^{l_i} +\sum P_i \log_D P_i\\ &= \sum P_i \log_D P_i - \sum P_i \log _D D^{-l_i}\\ &= \sum P_i \log_D \frac{P_i}{D^{-l_i} } ----(1)\\ \end{aligned} \]

也许大家会觉得从（1）可以直接得到:D(PD^{-l})，然后由互信息大于0从而完成证明。但这样是不严谨的，因为我们无法保证$\sum D^{-l_i} = 1$.

因此这里需要做一个归一化处理：令：$r_i = \frac{D^{-l_i} }{\Delta}，\Delta = \sum D^{-l_i}$ (这个地方真是不容易想到啊，很容易就不严谨了)

则（1）可以写为： $$ \begin{aligned} P_i _D \ &=P_i _D {}\ &=P_i _D - _D P_i\ &=D(Pr) + 码长码长码长而$D(P\Vert r) + \log \frac 1 \Delta \ge 0$（由对数性质，鉴别信息性质以及Kraft不等式决定）.

所以，我们完成了对上述定理的证明。

最优前缀码定理（香农第一定理）

该定理描述如下：

对随机变量X进行D进制前缀编码，得到的最优码长满足下列不等式： \[ H_D(X) \leq L^* < H_D(X)+1 \]

左侧是不用证明的，因为上个定理已经证明了。我们主要需要证明的是右侧。

香农通过构造香农码来证明右侧：

取$\lceil \log_D \frac 1{P_i} \rceil$为码字长度，这样的编码是满足kraft不等式的： \[ \sum D^{-\rceil \log_D \frac 1 {P_i} } \leq \sum D^{-\log_D \frac 1 {P_i} } = \sum P_i = 1 \] 因此我们可以根据这个码长来构造出相应的前缀码。

我们知道： \[ \log _D \frac 1 {P_i} \leq l_i \leq \log_D \frac 1 {P_i}+1 \]

如果对上述不等式的所有side求期望，得到： \[ H_D(X) \leq \sum p_il_i \leq H_D(X) + 1 \]

这就是香农码。它不一定是最优，因此我们就完成了香农第一定理的证明。

分组前缀码

定长编码定理告诉我们，$\epsilon$可以任意小，而变长编码告诉我们，我们付出的代价小于1。能不能让这个代价能保证比1更小呢？这就是分组编码。

对于信源X进行分组前缀编码，得到的每消息符号数$L_n^*$满足不等式： \[ \frac{H(X_1,X_2,...,X_n)}{n} \leq L_n^* \leq \frac{H(X_1,X_2,...,X_n)}{n} + \frac 1 n \]

如果信源稳恒，则$L_n^* \rightarrow H(X)$.

这要求我们对X进行分组，因此会有解码延迟，也需要缓冲区。但是通过这个，可以使得平均码长代价更小。天下没有免费的午餐。

编码效率与互信息

最优前缀码的编码与信源的分布密切相关，但是我们不一定能准确知道信源的分布。如果信源分布估计出现偏差，则平均码长就会受到惩罚。

Penalty分析：

可以证明，对于服从p(x)信源X进行前缀编码，如果码字长度取$l(x) = \lceil \log \frac 1 {q(x)}\rceil$，则平均码长满足： \[ H(p) + D(p\Vert q) \leq E_{p}l(X) < H(p) + D(p\Vert q) +1 \]

受到的惩罚中，互信息出来了。