[科普中国]-香农编码

香农(Shannon)编码是一种常见的可变字长编码，与哈夫曼编码相似，当信源符号出现的概率正好为2的负幂次方时，采用香农-范诺编码同样能够达到100%的编码效率。香农编码的理论基础是符号的码字长度Ni完全由该符号出现的概率来决定，即－logDPi≤Ni≤－logDPi+1，式中，D为编码所用的数制。香农编码的步骤如下：(1)将信源符号按其出现概率从大到小排序；(2)计算出各概率对应的码字长度；(3)计算累加概率；(4)把各个累加概率由十进制转化为二进制，取该二进制数的前Ni位作为对应信源符号的码字。二分法香农-范诺编码方法的步骤如下：(1)将信源符号按照其出现概率从大到小排序；(2)从这个概率集合中的某个位置将其分为两个子集合，并尽量使两个子集合的概率和近似相等，给前面一个子集合赋值为0，后面一个子集合赋值为1；(3)重复步骤(2)，直到各个子集合中只有一个元素为止；(4)将每个元素所属的子集合的值依次串起来，即可得到各个元素的香农编码。

基本介绍香农编码严格意义上来说不是最佳码，它是采用信源符号的累计概率分布函数来分配码字。

编码步骤如下：

(1)将信源符号按概率从大到小顺序排列，为方便起见，令 ；

(2)按 计算第i个符号对应的码字的码长(取整)；

(3) 计算第i个符号的累加概率 ；

(4)将累加概率变换成二进制小数，取小数点后 位数作为第i个符号的码字。

香农编码的效率不高，实用性不大，但对其他编码方法有很好的理论指导意义。一般情况下，按照香农编码方法编出来的码，其平均码长不是最短的。即不是紧致码(最佳码)。只有当信源符号的概率分布使不等式左边的等号成立时，编码效率才达到最高1。

例1对如下信源编码：

|| || 表1 例1香农编码

其香农编码如表1所示，以i=4为例， ，即 ，因此 。累加概率 ，变成二进制数，为0.1001...。转换的方法为：用Pi乘以2，如果整数部分有进位，则小数点后第一位为1，否则为0，将其小数部分再做同样的处理，得到小数点后的第二位，依此类推，直到得到了满足要求的位数，或者没有小数部分了为止。

可以看出，编码所得的码字，没有相同的，所以是非奇异码，也没有一个码字是其他码字的前缀，所以是即时码，也是唯一可译码。

平均码长为： 码符号/符号；

平均信息传输效率为： 比特/码符号。

香农编码的效率不高，实用性不大，但对其他编码方法有很好的理论指导意义。一般情况下，按照香农编码方法编出来的码，其平均码长不是最短的，即不是紧致码(最佳码)。只有当信源符号的概率分布使不等式左边的等号成立时，编码效率才达到最高。

最佳码最佳码(optimal code)是信源编码的一种类型，对于某一信源和某一码元集，若有一个惟一可译码，其平均长度 小于等于所有其他惟一可译码的平均长度，则称该码为最佳码或紧致码。无失真信源编码的基本问题就是寻找最佳码。若一个离散无记忆信源 具有熵为 、并有码元集 ，则总可找到一种无失真编码方法，构成惟一可译码，使其平均码长 满足

上式表示最佳码的平均长度的下限值与信源熵 成正比。

相关介绍Huffman编码基本介绍

1952年赫夫曼(D.A. Huffman)提出了一种构造最佳码的方法，称之为Huffman码。Huffman码适用于多元独立信源，对于多元独立信源来说它是最佳码。它充分利用了信源概率分布的特性进行编码，是一种最佳的逐个符号的编码方法2。

二元Huffman编码

二元Huffman码的编码步骤如下：

1) 将 个信源符号按概率递减的次序排列： 。

2) 用0和1码符号分别分配给概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个新符号，并用这两个最小概率之和作为新符号的概率，从而得到由 个符号组成的新信源 ，称 为信源 的缩减信源。

3) 把缩减信源 的信源符号按概率递减的次序排列，将其最后两个概率最小的信源符号合并成一个新符号，并分别用0和1码符号表示，形成 个符号的缩减信源 。

4) 依次下去，直至缩减信源 只剩两个符号为止。将最后两个新符号分别用0和1码符号表示(最后两个符号的概率和为1)。然后从最后一级缩减信源开始，依编码路径由后向前返回，就得出各信源符号所对应的码符号序列，即得对应的码字。

Huffman编码得到的码并非是唯一的。这是因为以下两点：

1) 每次对缩减信源最后两个概率最小的符号分配0和1码是可以任意的，所以可得到不同的编码。

2) 若当缩减信源中缩减合并后的符号的概率与其他信源符号概率相同时，其不同的概率次序排列导致不同的编码结果，但它们的平均码长相同，方差不同。

通常，在Huffman编码过程中，当缩减信源的概率分布重新排列时，应使合并得来的概率和尽量处于最高的位置，这样可以使合并的元素重复编码次数减少，使短码得到充分利用。

特点

Huffman码具有以下3个特点：

1) Huffman码的编码方法保证了概率大的符号对应短码，概率小的符号对应长码，而且短码得到充分利用。

2) 每次缩减信源的最后两个码字总是最后一位码元不同，前面各位码元相同(二元编码情况)。

3) 每次缩减信源的最长两个码字有相同的码长。

这三个特点保证了所得的Huffman码一定是最佳码。

s元Huffman编码

上面讨论的是二元Huffman码，它的编码方法同样可以推广到s元编码中。不同的只是每次把s个符号(概率最小的)合并成一个新的信源符号，并分别用 等码元。

为了充分利用短码资源使平均码长最短，必须使最后一步的缩减信源有s个信源符号。因此对于s元编码，信源X的符号个数r必须满足

式中， 表示缩减的次数； 为每次缩减所减少的信源符号个数。

若r不满足式(1)，可以增加t个信源符号 ，令其概率为零，即 ，满足 。这样得到的s元Huffman码一定是最佳码。

三元Huffman码的性能不如二元Huffman码的性能好。

Huffman码的最佳性

不失一般性，可以假设信源的概率分布按大小次序排列，即如 ，其对应的码长分别为 。

定理1对于给定分布的任何信源，存在一个最佳二元即时码(其平均码长最短)，此码满足以下性质：

1) 若 ，则 。

2) 两个最小概率的信源符号所对应的码字具有相同的码长。

3) 两个最小概率的信源符号所对应的码字，除最后一位码元不同外，前面各位码元都相同。

定理2二元Huffman码一定是最佳即时码。即若 是Huffman码， 是任意其他即时码，则有 2。

Fano编码1949年费诺(R.M. Fano)提出了一种编码方法，称之为Fano码。它属于概率匹配编码，但一般也不是最佳的编码方法，只有当信源的概率分布呈现 分布形式的条件下，才能达到最佳码的性能。

Fano码的编码步骤如下：

1)将 个信源符号按概率递减的方式进行排列： 。

2)将排列好的信源符号按概率值划分成两大组，使每组的概率之和接近于相等，并对每组各赋予一个二元码符号0和1。

3)将每一大组的信源符号再分成两组，使划分后的两个组的概率之和接近于相等，再分别赋予一个二元码符号0和1。

4)依次下去，直至每个小组只剩一个信源符号为止。

5)将逐次分组过程中得到的码元排列起来就是各信源符号的编码。

Fano码具有以下性质：

1)Fano码的编码方法实际上是一种构造码树的方法，所以Fano码是即时码。

2)Fano码考虑了信源的统计特性，使概率大的信源符号能对应码长较短的码字，从而有效地提高了编码效率。

3)Fano码不一定是最佳码。因为Fano编码方法不一定能使短码得到充分利用。当信源符号较多时，若有一些符号概率分布很接近，分两大组的组合方法就会很多。可能某种分大组的结果，会使后面小组的“概率和”相差较远，从而使平均码长增加。

前面讨论的Fano码是二元Fano码，对于s元Fano码，与二元Fano码的编码方法相同，只是每次分组时应将符号分成概率分布接近的s个组1。

一般Fano编码的平均码长的界限为

本词条内容贡献者为:

王海侠 - 副教授 - 南京理工大学