55402永利开户注册 > 55402com永利 >

费诺编码

  声明:百科词条人人可编辑,词条创建和修改均免费,绝不存在官方及代理商付费代编,请勿上当受骗。详情

  费诺编码属于统计匹配编码,但它一般不是最佳的编码方法。编码步骤为:(1)将信源消息(符号)按其出现的概率由大到小依次排列;(2)将依次排列的信源符号按概率值分为两大组,使两个组的概率之和近于相同,并对各组分别赋予一个二进制码元“0”和“1”;(3)将每一大组的信源符号进一步再分成两组,使划分后的两个组的概率之和近于相同,并又分别赋予一个二进制符号“0”和“1”;(4)如此重复,直至每个组只剩下一个信源符号为止;(5)信源符号所对应的码字即为费诺码。费诺码考虑了信源的统计特性,使经常出现的信源符号能对应码长短的编码字。显然,费诺码仍然是一种相当好的编码方法。但是,这种编码方法不一定能使短码得到充分利用。尤其当信源符号较多,并有一些符号概率分布很接近时,分两大组的组合方法就很多。可能某种分配结果,会出现后面小组的“概率和”相差较远,因而使平均码长增加,所以费诺码不一定是最佳码。费诺码的编码方法实际上是构造码树的一种方法,所以费诺码是一种即时码。

  1949年费诺(R.M. Fano)提出了一种编码方法,称之为费诺码或Fano码。它属于概率匹配编码,但

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

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

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

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

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

  最佳码(optimal code)是信源编码的一种类型,对于某一信源和某一码元集,若有一个惟一可译码,其平均长度

  。Huffman码适用于多元独立信源,对于多元独立信源来说它是最佳码。它充分利用了信源概率分布的特性进行编码,是一种最佳的逐个符号的编码方法

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

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

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

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

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

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

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

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

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

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

  其香农编码如表1所示,以i=4为例,,即,因此。累加概率,变成二进制数,为0.1001...。转换的方法为:用P

  乘以2,如果整数部分有进位,则小数点后第一位为1,否则为0,将其小数部分再做同样的处理,得到小数点后的第二位,依此类推,直到得到了满足要求的位数,或者没有小数部分了为止。

  可以看出,编码所得的码字,没有相同的,所以是非奇异码,也没有一个码字是其他码字的前缀,所以是

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

上一篇:矿山提升机操作作业人员培训班开班 下一篇:没有了