费诺编码

统计匹配编码

费诺编码属于统计匹配编码，但它一般不是最佳的编码方法。编码步骤为：(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)是信源编码的一种类型，对于某一信源和某一码元集，若有一个惟一可译码，其平均长度小于等于所有其他惟一可译码的平均长度，则称该码为最佳码或紧致码。无失真信源编码的基本问题就是寻找最佳码。若一个离散无记忆信源具有熵为、并有码元集，则总可找到一种无失真编码方法，构成惟一可译码，使其平均码长满足

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