2022P02014139杨智关于香农编码、哈夫曼编码和费诺编码的比较
发布时间：2023-11-24 14:00
注:以下三种编码比较都是在二进制下讨论的，其它进制下的编码情况可以与二进制下的情况类比。
1香农编码
概念：
香农编码是是采用信源符号的累计概率分布函数来分配字码的。香农编码是根据香农第一定理直接得出的，指出了平均码长与信息之间的关系，同时也指出了可以通过编码使平均码长达到极限值。香农第一定理是将原始信源符号转化为新的码符号，使码符号尽量服从等概分布，从而每个码符号所携带的信息量达到最大，进而可以用尽量少的码符号传输信源信息。
香农编码属于不等长编码，通常将经常出现的消息变成短码，不经常出现的消息编成长码，从而提高通信效率。 香农编码严格意义上来说不是最佳码，它是采用信源符号的累计概率分布函数来分配码字。
编码过程：
（1）、将m个信源符号按照概率大小来进行递减排序。p1>=p2>=…>=pn>=…pm。
（2）、计算出对应符号在排序下的累加概率
。
（3）、按照Ki=⌈-logP(ai) ⌉（其中⌈ ⌉表示向上取整）来确定码字长度Ki。
（4）、将累加概率Pi以二进制数的形式表示。
（5）、取对应Pi的二进制数小数点后Ki位来构成对应信源符号的编码。
例如：
| 信源符号ai |
符号概率p(ai) |
累加概率Pi |
-logp(ai) |
码字长度Ki |
码字 |
| a1 |
0.20 |
0 |
2.32 |
3 |
000 |
| a2 |
0.19 |
0.2 |
2.39 |
3 |
001 |
| a3 |
0.18 |
0.39 |
2.47 |
3 |
011 |
| a4 |
0.17 |
0.57 |
2.56 |
3 |
100 |
| a5 |
0.15 |
0.74 |
2.74 |
3 |
1011 |
| a6 |
0.10 |
0.89 |
3.34 |
4 |
1110 |
| a7 |
0.01 |
0.99 |
6.64 |
7 |
1111110 |
计算编码效率：
先算出平均码字长度K=∑p(ai)*ki=3.14
可得编码效率为:H(X)/K*100%=83.1%。
可见香农码的编码效率是比较低的、多余度较大且实用性不强。但是它依据编码定理编码，故具有重要的理论意义。
2 费诺编码
概念：
1949年费诺(R.M. Fano)提出了一种编码方法，称之为费诺码或Fano码。它属于概率匹配编码，但一般也不是最佳的编码方法，只有当信源的概率分布呈现
P(ai)=s^li(i=1,2,…,r)
分布形式的条件下，才能达到最佳码的性能 。
编码过程：
（1）、将m个信源符号按照概率大小来进行递减排序。p1>=p2>=…>=pn>=…pm。
（2）、将这一组信源符号分成概率之和尽可能相等的两组（两组的概率差尽可能小）。
（3）、将上面一组编码为0，下面一组编码为1（反之亦可）。
（4）、重复（2）、（3）步骤，直到不能分组。
（5）、依次写出所编的码字。
例如：
| 信源符号ai |
符号概率p(ai) |
分组1 |
分组2 |
分组3 |
分组4 |
码字 |
码长 |
| a1 |
0.20 |
0 |
0 |
00 |
2 |
||
| a2 |
0.19 |
0 |
1 |
0 |
010 |
3 |
|
| a3 |
0.18 |
0 |
1 |
1 |
011 |
3 |
|
| a4 |
0.17 |
1 |
0 |
10 |
2 |
||
| a5 |
0.15 |
1 |
1 |
0 |
110 |
3 |
|
| a6 |
0.10 |
1 |
1 |
1 |
0 |
1110 |
4 |
| a7 |
0.01 |
1 |
1 |
1 |
1 |
1111 |
4 |
计算编码效率：
先算出平均码字长度K=∑p(ai)*ki=2.74
可得编码效率为:H(X)/K*100%=95.3%。
可见费诺编码比较适合于对分组概率相等或者比较接近的信源编码，此种编码考虑了信源的统计特性 ，使概率较大的信源符号能对应码长较短的码字，较之香农编码一定提升了编码效率。
但它也有一定的缺点。它不一定是最佳码。当信源符号较多时，有一些符号概率比较接近，使分组变多码长也随之增加。
3 哈夫曼编码
概念：
哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。
编码过程：
（1）、将m个信源符号按照概率大小来进行递减排序。p1>=p2>=…>=pn>=…pm。
（2）、把概率最小的两个信源符号分为一组上面一个编码0，下面一个编码1，之后将这两个概率相加并且与剩下的概率重新排序。
要注意，在重新排序时，如果已编码的概率相加之后发现与一个或多个未编码概率相等，要将相加以后的概率排在这些相等概率的最上面。这样编码虽然不会改变平均码长，但是可以大大降低编码后的码方差，提升编码质量。
（3）、重复（2）步骤，直到所有的信源符号都已经编码完成。
（4）、按照编码路径由左到右返回，得到各码字。
例如：
| 信源符号ai |
符号概率p(ai) |
编码过程 |
码字 |
码长 |
||||||
| a1 |
0.20 |
0.20 |
0.26 |
0.35 |
0.39 |
0.61}0 |
1.0 |
10 |
2 |
|
| a2 |
0.19 |
0.19 |
0.20 |
0.26 |
0.35}0 |
0.39}1 |
11 |
2 |
||
| a3 |
0.18 |
0.18 |
0.19 |
0.20}0 |
0.26}1 |
000 |
3 |
|||
| a4 |
0.17 |
0.17 |
0.18}0 |
0.19}1 |
001 |
3 |
||||
| a5 |
0.15 |
0.15}0 |
0.17}1 |
010 |
3 |
|||||
| a6 |
0.10 |
}0 |
0.11}1 |
0110 |
4 |
|||||
| a7 |
0.01 |
}1 |
0111 |
4 |
||||||
计算编码效率：
先算出平均码字长度K=∑p(ai)*ki=2.72
可得编码效率为:H(X)/K*100%=96.0%。
可见哈夫曼码与香农码相比它的平均码长比较小，编码效率更高，信息传输速率大。并且当信息源各符号出现的概率很不平均的时候，哈夫曼编码的效果才明显。
它也有一定的缺点。当信息源各符号出现的概率较为平均的时候，哈夫曼编码的效果不明显。
并且哈夫曼编码必须精确地统计出原始文件中每个符号的出现频率，如果没有这些精确的统计，将达不到预期的压缩效果。霍夫曼编码通常要经过两遍操作，第一遍进行统计，第二遍产生编码，所以编码速度相对慢。而且由于编码长度不统一，硬件实现有难度。由于编码长度可变。因此译码时间较长，使得霍夫曼编码的压缩与还原相当费时。 哈夫曼所有位都是合在一起的，如果改动其中一位就可以使其数据变得面目全非。
总结
由上述比较可知：
1、香农码的拓展性较好有唯一的编码，虽然效率不高且实用性不大可以对其他编码方法有很好的理论指导意义。
2、费诺码和哈夫曼码的编码方法不唯一。
3、就编码效率而言，哈夫曼码>费诺码>香农码。
4、三种编码都考虑了信源的统计特性，使经常出现的信源符号对应较短的码字，使平均码长缩短，实现了信源压缩。