香农第一定理的证明过程给出了一种编码方法,称为香农编码。其编码方法是选择每个码字长度Li满足

可以证明,这样的码长一定满足Kraft不等式,所以一定存在这样码长的唯一可译码和即时码。

香农编码的基本思想是概率匹配原则,即概率大的信源符号用短码,概率小的信源符号用长码,以使减小平均码长,提高编码效率。

香农编码的步骤如下:

(1)将信源发出的q个消息,按出现概率递减顺序进行排列;

(2)计算各消息的-log(pi);

(3)确定满足式(7.1)的整数码长Li;

(4)计算第i个消息的累积分布函数(www.daowen.com)

(5)将累积分布函数Fi变换成二进制数;

(6)取Fi二进制数的小数点后Li位作为第i个符号的二进制码字Wi。

【例7.4】已知信源共6个符号,其概率空间为

试进行香农编码。

解:以消息s5为例来介绍。计算-log(p5)=-log0.15=2.74,取整数L5=3作为s5的码长。计算s1,s2,s3,s4的累积分布函数

将0.74变换成二进制小数(0.74)10=(0.1011110)2,取小数点后面三位101作为s5的代码。

香农编码是依据香农第一编码定理而来的,有着重要的理论意义。但香农编码的冗余度稍大,实用性不强。比如信源有3个符号,概率分布为(0.5,0.4,0.1),根据香农编码方法求出各个符号的码长对应为1,2,4,码字为(0,10,1110)。下面将看到如果采用霍夫曼编码,可以构造出平均码长更短的即时码(0,10,11)。