当前位置: 首页 > >

《信息论与编码》之香农编码、费诺编码、赫夫曼编码

发布时间:



信息论与编码
1.香农编码编码步骤
2.费诺编码编码步骤
3.赫夫曼编码编码步骤二进制赫夫曼编码m进制赫夫曼编码
解题步骤



1.香农编码

香农编码的过程,其实很简单,只是一开始没有记清楚导致记混了。我们以例题为例进行介绍。


编码步骤

1.概率由大到小排列,
2.计算第i个码字的码长ki( ki为整数)
3.为了编成唯一可译码,计算第i个码字的累加概率
4. 用二进制表示,取小数点后ki 位作为符号ai 的编码


我们在这里只写第二问,即编码部分。下面分享手写版本,注意,香农编码与本信息的概率(对应码长)和累加概率(对应码字)均有关系。


2.费诺编码

我们仍然以这道题为例写费诺编码的解法。


编码步骤

1.概率由大到小排列,
2.按编码进制数将概率分组,使每组概率尽可能接*或相等。
3.给每组分配一位码元。
4.将每一分组再按同样原则划分,重复步骤2、3,直至概率不再
可分为止。


解题步骤如下:


3.赫夫曼编码

我们仍然以这道题为例写赫夫曼编码的解法。


编码步骤
二进制赫夫曼编码

1.概率由大到小排列,
2.用0和1分别表示概率最小的两个信源符号,并将它们合并成一
个符号,得到只包含(n-1)个符号的新信源X1(缩减信源)。
3.将缩减信源X1按概率递减排列,重复步骤2,得到只包含(n-2)
个符号的缩减信源X2。
4.重复上述步骤,直到缩减信源只剩两个符号为止,此时所剩两
个符号的概率之和必为1,并用0和1分别表示。
5.从最后一级缩减信源开始,向前返回,就得到各信源符号所对
应的码字。


m进制赫夫曼编码

每次把m个概率最小的信源符号分别用0,1, …,m-1码元来表示,然后再将它们合并成一个新的符号,得到缩减信源。为了充分利用短码,使*均码长最短,必须使最后一步缩减信源有m个信源符号。
信源符号个数n必须满足 n = k(m ? 1)+m (k:信源缩减次数)。
若n不满足,增补s个概率为零的信源符号,使之满足。
即:第一次编码取m-s个实际信源符号。


解题步骤



友情链接: