香农编码

数学术语

香农(Shannon)编码是一种常见的可变字长编码，与哈夫曼编码相似，当信源符号出现的概率正好为2的负幂次方时，采用香农-范诺编码同样能够达到100%的编码效率。香农编码的理论基础是符号的码字长度Ni完全由该符号出现的概率来决定，即－logDPi≤Ni≤－logDPi+1，式中，D为编码所用的数制。香农编码的步骤如下：(1)将信源符号按其出现概率从大到小排序；(2)计算出各概率对应的码字长度；(3)计算累加概率；(4)把各个累加概率由十进制转化为二进制，取该二进制数的前Ni位作为对应信源符号的码字。二分法香农-范诺编码方法的步骤如下：(1)将信源符号按照其出现概率从大到小排序；(2)从这个概率集合中的某个位置将其分为两个子集合，并尽量使两个子集合的概率和近似相等，给前面一个子集合赋值为0，后面一个子集合赋值为1；(3)重复步骤(2)，直到各个子集合中只有一个元素为止；(4)将每个元素所属的子集合的值依次串起来，即可得到各个元素的香农编码。

基本介绍

香农编码严格意义上来说不是最佳码，它是采用信源符号的累计概率分布函数来分配码字。

编码步骤如下：

(1)将信源符号按概率从大到小顺序排列，为方便起见，令；

(2)按计算第i个符号对应的码字的码长(取整)；

(3) 计算第i个符号的累加概率；

(4)将累加概率变换成二进制小数，取小数点后位数作为第i个符号的码字。

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

例1对如下信源编码：

其香农编码如表1所示，以i=4为例，，即，因此。累加概率，变成二进制数，为0.1001...。转换的方法为：用Pi乘以2，如果整数部分有进位，则小数点后第一位为1，否则为0，将其小数部分再做同样的处理，得到小数点后的第二位，依此类推，直到得到了满足要求的位数，或者没有小数部分了为止。

可以看出，编码所得的码字，没有相同的，所以是非奇异码，也没有一个码字是其他码字的前缀，所以是即时码，也是唯一可译码。

平均码长为：码符号/符号；

平均信息传输效率为：比特/码符号。

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

最佳码

最佳码(optimal code)是信源编码的一种类型，对于某一信源和某一码元集，若有一个惟一可译码，其平均长度小于等于所有其他惟一可译码的平均长度，则称该码为最佳码或紧致码。无失真信源编码的基本问题就是寻找最佳码。若一个离散无记忆信源具有熵为、并有码元集，则总可找到一种无失真编码方法，构成惟一可译码，使其平均码长满足

上式表示最佳码的平均长度的下限值与信源熵成正比。