更新时间：2022-08-25 15:48
费诺编码属于统计匹配编码，但它一般不是最佳的编码方法。编码步骤为：(1)将信源消息(符号)按其出现的概率由大到小依次排列；(2)将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近于相同，并对各组分别赋予一个二进制码元“0”和“1”；(3)将每一大组的信源符号进一步再分成两组，使划分后的两个组的概率之和近于相同，并又分别赋予一个二进制符号“0”和“1”；(4)如此重复，直至每个组只剩下一个信源符号为止；(5)信源符号所对应的码字即为费诺码。费诺码考虑了信源的统计特性，使经常出现的信源符号能对应码长短的编码字。显然，费诺码仍然是一种相当好的编码方法。但是，这种编码方法不一定能使短码得到充分利用。尤其当信源符号较多，并有一些符号概率分布很接近时，分两大组的组合方法就很多。可能某种分配结果，会出现后面小组的“概率和”相差较远，因而使平均码长增加，所以费诺码不一定是最佳码。费诺码的编码方法实际上是构造码树的一种方法，所以费诺码是一种即时码。
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个组。
一般Fano编码的平均码长的界限为
最佳码
最佳码(optimal code)是信源编码的一种类型，对于某一信源和某一码元集，若有一个惟一可译码，其平均长度小于等于所有其他惟一可译码的平均长度，则称该码为最佳码或紧致码。无失真信源编码的基本问题就是寻找最佳码。若一个离散无记忆信源具有熵为、并有码元集，则总可找到一种无失真编码方法，构成惟一可译码，使其平均码长满足
上式表示最佳码的平均长度的下限值与信源熵成正比。
Huffman编码
基本介绍
1952年赫夫曼(D.A. Huffman)提出了一种构造最佳码的方法，称之为Huffman码。Huffman码适用于多元独立信源，对于多元独立信源来说它是最佳码。它充分利用了信源概率分布的特性进行编码，是一种最佳的逐个符号的编码方法。
二元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码，是任意其他即时码，则有。
香农编码
香农编码严格意义上来说不是最佳码，它是采用信源符号的累计概率分布函数来分配码字。
编码步骤如下：
(1)将信源符号按概率从大到小顺序排列，为方便起见，令；
(2)按计算第i个符号对应的码字的码长(取整)；
(3) 计算第i个符号的累加概率；
(4)将累加概率变换成二进制小数，取小数点后位数作为第i个符号的码字。
香农编码的效率不高，实用性不大，但对其他编码方法有很好的理论指导意义。一般情况下，按照香农编码方法编出来的码，其平均码长不是最短的。即不是紧致码(最佳码)。只有当信源符号的概率分布使不等式左边的等号成立时，编码效率才达到最高。
例1对如下信源编码：
其香农编码如表1所示，以i=4为例，，即，因此。累加概率，变成二进制数，为0.1001...。转换的方法为：用Pi乘以2，如果整数部分有进位，则小数点后第一位为1，否则为0，将其小数部分再做同样的处理，得到小数点后的第二位，依此类推，直到得到了满足要求的位数，或者没有小数部分了为止。
可以看出，编码所得的码字，没有相同的，所以是非奇异码，也没有一个码字是其他码字的前缀，所以是即时码，也是唯一可译码。
平均码长为：码符号/符号；
平均信息传输效率为：比特/码符号。
香农编码的效率不高，实用性不大，但对其他编码方法有很好的理论指导意义。一般情况下，按照香农编码方法编出来的码，其平均码长不是最短的，即不是紧致码(最佳码)。只有当信源符号的概率分布使不等式左边的等号成立时，编码效率才达到最高。