Fano编码：提高数据传输效率的方法

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

Fano码的编码步骤如下：

1）将r个信源符号按概率递减的方式进行排列：P（a₁）≥P（a₂）≥…≥P（a_r）。

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

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

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

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

下面给出两个具体的例子来说明这种编码方法。

【例4.13】

设8个符号的离散无记忆信源为

试对该信源进行Fano编码。

解 该信源的Fano编码过程见表4.5。其信源的熵为

表4.5 例4.13的Fano编码

码的平均长度为

显然，该码是最佳码，其编码效率为(www.xing528.com)

例4.13的编码之所以能达到最佳，是因为信源符号的概率分布正好满足式；否则，在一般情况下是无法达到编码效率等于1的。

【例4.14】（续例4.11）

对例4.11的信源进行Fano编码。其Fano编码过程见表4.6。平均码长为

表4.6 例4.14的Fano编码

编码效率为

比较例4.14和例4.11可见，Fano编码的平均码长比Shannon编码的平均码长小，编码效率较高。

Fano码具有以下性质：

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

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

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

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

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

L≤H_s（X）+2 （4.37）