【通信原理入坑之路】—— 信息论部分离散无记忆信源的不等长编码之霍夫曼编码过程详解

缺乏、安全感 2022-12-18 02:59 173阅读 0赞

> 还记得在上一篇博客中，我们讨论的离散无记忆信源的等长编码吗，我们最后得到的结论是 —— 如果使用等长编码，那么对典型序列编码的编码效率是最高的。然而，要满足较高的编码效率，同时还要保证误码率的情况下，等长编码中要求的  J J J 将会相当大。这显然在实际中是难以实现的，不仅占用的缓存大而且会造成延时。  
> 但换一个思路：在实际信源中，每一个符号出现的概率都不一定相等，如果我们把出现概率高的符号，用更短的码字表示；对出现概率较低的符号用较长的码字表示，这样编码效率不就上去了吗！这就是不等长编码。本文主要介绍霍夫曼编码的具体流程。

--------------------

我们直接以一个例子开始讲解霍夫曼编码：

对于一个离散信源  \[ S i : S 1 S 2 S 3 S 4 S 5 S 6 P ( S i ) : 0.24 0.20 0.18 0.16 0.14 0.08 \] \\begin\{bmatrix\} S\_i: & S\_1 & S\_2 & S\_3 & S\_4 & S\_5 & S\_6 \\\\ P(S\_i): & 0.24 & 0.20 & 0.18 & 0.16 & 0.14 & 0.08 \\end\{bmatrix\} \[Si:P(Si):S10.24S20.20S30.18S40.16S50.14S60.08\]如果我们要用一个三进制（ D = 3 D = 3 D=3）的码元集： \{ C : 0 , 1 , 2 \} \\\{C: 0, 1, 2\\\} \{ C:0,1,2\} 进行编码。

【第一步】我们首先将离散信源的概率降序排列。如下：(本题只是恰好他给出来的就是降序的）  
![在这里插入图片描述][20201025111122288.png_pic_center]  
【第二步】：然后，我们把概率最低的 D 个符号分别记为  C 0 , C 1 , C 2 C\_0, C\_1, C\_2 C0,C1,C2,然后把这最小的 D 个概率相加。如下：  
![在这里插入图片描述][20201025111654283.png_pic_center]  
【第三步】现在因为合并了三个最小的概率，所以我们现在只剩下四个概率值：0.24, 0.20, 0.18和0.38。那么还是按照第一步的办法，继续将这四个概率降序排列。  
![在这里插入图片描述][20201025111859943.png_pic_center]  
【第四步】按照第三步的方法，对概率值最小的 D 个符号分别用  C 0 , C 1 , C 2 C\_0, C\_1,C\_2 C0,C1,C2 表示，然后把这三个最小的概率相加：  
![在这里插入图片描述][20201025112050550.png_pic_center]

【第五步】现在我们发现：最后就只剩下两个概率值了。但是我们一般希望合并到最后能够剩下  D D D 个概率值。也就是现在还差一个概率。这时，我们可以就要回到第一步，首先对信源进行改造—— 给它额外加上一个虚假符号  S 7 ′ S\_7' S7′，这个虚假符号的概率值是 0.如下：

\[ S i : S 1 S 2 S 3 S 4 S 5 S 6 S 7 ′ P ( S i ) : 0.24 0.20 0.18 0.16 0.14 0.08 0 \] \\begin\{bmatrix\} S\_i: & S\_1 & S\_2 & S\_3 & S\_4 & S\_5 & S\_6 & S\_7' \\\\ P(S\_i): & 0.24 & 0.20 & 0.18 & 0.16 & 0.14 & 0.08 & 0 \\end\{bmatrix\} \[Si:P(Si):S10.24S20.20S30.18S40.16S50.14S60.08S7′0\]  
【第六步】：重新执行一开始的【第一步】 至 【第四步】得：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4NjQ3Mw_size_16_color_FFFFFF_t_70_pic_center]

【第七步】回溯，编码。我们先从最后的 0.54, 0.24 和 0.22看起。首先看 0.54，它的编码现在是0对吧。然后我们看 0.54是哪里来的—— 噢！是第二层 0.20 + 0.16 + 0.18 的结果，因此，第二层的 0.20 目前的编码就是 00；0.18的编码就是 01；0.16的编码 02；然后我们看第二层的 0.20是哪里来的 —— 噢！他直接就是第一层  S 2 S\_2 S2 的 0.20，所以  S 2 S\_2 S2 的编码就是 00。以此类推。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4NjQ3Mw_size_16_color_FFFFFF_t_70_pic_center 1]  
 \\quad

--------------------

至此，霍夫曼编码就完成啦！那么大家可能会有疑问—— 为啥霍夫曼编码要加上虚假符号呢？**其实，通过增加虚假符号，可以减少码字的平均字长，从而提高编码性能。因此通过刚刚的流程我们也有了一个直观的认识：概率越小的符号，他被合并的次数越多，从而对他编码的环节也越多，导致概率小的符号所编码出来的码字长度比较长。那么，如果加上了虚假符号，就可以使得大概率的那些符号所经过的编码环节尽可能少，那么大概率符号的码字长度就减小了。从而编码有效性就上去了。**

上例中，增加了虚假符号之后的编码输出的平均码长（**单位是：码字符号/信源符号**）为： 0.24 × 1 + 0.20 × 2 + 0.18 × 2 + 0.16 × 2 + 0.14 × 2 + 0.08 × 2 + 0 × 2 = 1.76 0.24\\times 1 + 0.20\\times 2 + 0.18 \\times 2 + 0.16 \\times 2 + 0.14 \\times 2 + 0.08 \\times 2 + 0 \\times 2 = 1.76 0.24×1\+0.20×2\+0.18×2\+0.16×2\+0.14×2\+0.08×2\+0×2=1.76

而如果不加虚假符号，输出的平均码长是 2（码字符号 / 信源符号）

> 最后需要注意的是：在对合并后的信源进行重新降序排列时，应使合并得到的局部概率和尽量处于相同概率值的最高位置。这样可以使得合并的元素重复编码次数减少，使得码字长度更为均匀。

[20201025111122288.png_pic_center]: /images/20221122/9fd60155579b4bf8927a7e3069acb9c7.png
[20201025111654283.png_pic_center]: /images/20221122/c5c244f30cc84d84b7e01b403a44594b.png
[20201025111859943.png_pic_center]: /images/20221122/fa0a51d1c88541efab0c5edc1211ea3b.png
[20201025112050550.png_pic_center]: /images/20221122/e4a99a72239f4191b5ec09d57db3e4a7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4NjQ3Mw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221122/e92ff934d4a14408b50f5c47b3f6c426.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4NjQ3Mw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221122/e2056a69bbb34c019deea2621c19587b.png