香农编码、费诺编码、哈弗曼编码

川长思鸟来 2022-07-13 08:42 481阅读 0赞

香农编码

香农编码法冗余度稍大，实用性不大，但有重要的理论意义。

编码步骤如下：

（1） 将信源消息符号按其出现的概率大小依次排列

p（x1）≥p（x2）≥„≥p（xn）

（2） 确定满足下列不等式整数码长Ki：   
           -log2p(xi)≤Ki＜-log2p(xi)+1

（3） 为了编成唯一可译码，计算第i个消息的累加概率

Pi=![Image 1][]p(xk)

（4） 将累加概率Pi变成二进制数。  
（5） 取Pi二进制数的小数点后Ki位即为该消息符号的二进制码字。

费诺编码

编首先,将信源符号以概率递减的次序排列进来，将排列好的信源符号划分为两大组，使两组的概率和近于相同,并各赋于一个二元码符号”0”和”1”.然后，将每一大组的[信源][Link 1]符号再分成两组，使同一组的两个小组的概率和近于相同，并又分别赋予一个二元码符号。依次下去，直至每一个小组只剩下一个信源符号为止。这样，信源符号所对应的码符号序列则为编得的码字。译码原理，按照编码的二叉树从树根开始，按译码序列进行逐个的向其叶子结点走，直到找到相应的信源符号为止。之后再把指示标记回调到树根，按照同样的方式进行下一序列的译码到序列结束。如果整个译码序列能够完整的译出则返回成功，否则则返回译码失败。

编码方法

1.将信源消息符号按其出现的概率大小依次排列。

2.将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近似相同，并对各组赋予一个二进制码元“0”和“1”。

3.将每一大组的信源符号再分为两组，使划分后的两个组的概率之和近似相同，并对各组赋予一个二进制符号“0”和“1”。

4.如此重复，直至每个组只剩下一个信源符号为止。

5.信源符号所对应的码字即为费诺码。

哈弗曼编码

原理：

设某信源产生有五种符号u1、u2、u3、u4和u5，对应概率P1=0.4，P2=0.1，P3=P4=0.2，P5=0.1。首先，将符号按照概率由大到小排队，如图所示。编码时，从最小概率的两个符号开始，可选其中一个支路为0，另一支路为1。这里，我们选上支路为0，下支路为1。再将已编码的两支路的概率合并，并重新排队。多次重复使用上述方法直至合并概率归一时为止。从图（a）和（b）可以看出，两者虽平均码长相等，但同一符号可以有不同的码长，即编码方法并不唯一，其原因是两支路概率合并后重新排队时，可能出现几个支路概率相等，造成排队方法不唯一。一般，若将新合并后的支路排到等概率的最上支路，将有利于缩短码长方差，且编出的码更接近于等长码。这里图（a）的编码比（b）好。

[![图1 赫夫曼编码原理][1]][1 _1] 图1 赫夫曼编码原理

赫夫曼码的码字（各符号的代码是异前置码字，即任一码字不会是另一码字的前面部分，这使各码字可以连在一起传送，中间不需另加隔离符号，只要传送时不出错，收端仍可分离各个码字，不致混淆。

实际应用中，除采用定时清洗以消除误差扩散和采用缓冲存储以解决速率匹配以外，主要问题是解决小符号集合的统计匹配，例如黑（1）、白（0）传真信源的统计匹配，采用0和1不同长度游程组成扩大的符号集合信源。游程，指相同码元的长度（如二进码中连续的一串0或一串1的长度或个数）。按照CCITT标准，需要统计2×1728种游程（长度），这样，实现时的存储量太大。事实上长游程的概率很小，故CCITT还规定：若l表示游程长度，则l=64q+r。其中q称主码，r为基码。编码时，不小于64的游程长度由主码和基码组成。而当l为64的整数倍时，只用主码的代码，已不存在基码的代码。

**编码过程如下 :**  
  
(1)  将信源符号按概率递减顺序排列 ;  
(2)  把两个最小的概率加起来 , 作为新符号的概率 ;  
(3)  重复步骤 (1) 、 (2), 直到概率和达到 1 为止 ;  
(4)  在每次合并消息时，将被合并的消息赋以1和0或0和1；  
(5)  寻找从每个信源符号到概率为1处的路径，记录下路径上的1和0；  
(6)  对每个符号写出"1"、"0"序列（从码数的根到终节点）。

[Image 1]: 
[Link 1]: http://baike.baidu.com/view/497306.htm
[1]: https://imgsa.baidu.com/baike/s%3D220/sign=5b1270565aee3d6d26c680c973176d41/c75c10385343fbf2b83ec5d2b37eca8065388f34.jpg
[1 _1]: /images/20220713/26a4672a19cd4198827af78fcf4f7be1.png