香农编码,哈夫曼编码与费诺编码的比较 |
您所在的位置:网站首页 › 编码效率是什么比上什么 › 香农编码,哈夫曼编码与费诺编码的比较 |
一、香农编码
概念: 香农编码是是采用信源符号的累计概率分布函数来分配字码的。香农编码是根据香农第一定理直接得出的,指出了平均码长与信息之间的关系,同时也指出了可以通过编码使平均码长达到极限值。香农第一定理是将原始信源符号转化为新的码符号,使码符号尽量服从等概分布,从而每个码符号所携带的信息量达到最大,进而可以用尽量少的码符号传输信源信息。 香农编码属于不等长编码,通常将经常出现的消息变成短码,不经常出现的消息编成长码,从而提高通信效率。 香农编码严格意义上来说不是最佳码,它是采用信源符号的累计概率分布函数来分配码字。 编码步骤如下: (1)将信源符号按概率从大到小顺序排列,为方便起见,令 ** 二、哈夫曼编码** 概念: 哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式,哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般就叫做Huffman编码(有时也称为霍夫曼编码)。 哈夫曼编码的具体步骤如下: 1)将信源符号的概率按减小的顺序排队。 2)把两个最小的概率相加,并继续这一步骤,始终将较高的概率分支放在右边,直到 最后变成概率1。 3)画出由概率1处到每个信源符号的路径,顺序记下沿路径的0和1,所得就是该符号的霍夫曼码字。 4)将每对组合的左边一个指定为0,右边一个指定为1(或相反)。 例1对如下信源编码: 概念: 1949年费诺(R.M. Fano)提出了一种编码方法,称之为费诺码或Fano码。它属于概率匹配编码,但一般也不是最佳的编码方法,只有当信源的概率分布呈现 Fano码的编码步骤如下: 1)将 r 个信源符号按概率递减的方式进行排列 。 2)将排列好的信源符号按概率值划分成两大组,使每组的概率之和接近于相等,并对每组各赋予一个二元码符号0和1。 3)将每一大组的信源符号再分成两组,使划分后的两个组的概率之和接近于相等,再分别赋予一个二元码符号0和1。 4)依次下去,直至每个小组只剩一个信源符号为止。 5)将逐次分组过程中得到的码元排列起来就是各信源符号的编码。 例1对如下信源编码: 这样就把两组的差别降到最小。通过这样的分割, S1,S2与S3同时拥有了一个以0为开头的码字, S4,S5,S6,S7的码子则为1, 随后, 在树的左半边,于S1,S2,S3间建立新的分割线,S1为一组,S2,S3为一组这样S1就成为了码字为00的叶子节点,S2,S3的开头为01;然后S2,S3间再分组得到S2的编码为010,S3的编码为011.以此类推最后得到编码为下图: Fano码具有以下性质: 1)Fano码的编码方法实际上是一种构造码树的方法,所以Fano码是即时码。 2)Fano码考虑了信源的统计特性,使概率大的信源符号能对应码长较短的码字,从而有效地提高了编码效率。 3)Fano码不一定是最佳码。因为Fano编码方法不一定能使短码得到充分利用。当信源符号较多时,若有一些符号概率分布很接近,分两大组的组合方法就会很多。可能某种分大组的结果,会使后面小组的“概率和”相差较远,从而使平均码长增加。 前面讨论的Fano码是二元Fano码,对于s元Fano码,与二元Fano码的编码方法相同,只是每次分组时应将符号分成概率分布接近的s个组。 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |