显然费诺要比香农的平均码长小 消息的传输速率大，说明编码效率高。
14
2019/2/16
2.费诺编码方法
费诺编码过程
2019/2/16 15
3.哈夫曼编码方法

编码过程如下：
(1) 将n p(x1)≥p(x2)≥…≥p(xn) (2) 取两个概率最小的字母分别配以0和1两码元，并将这 两个概率相加作为一个新字母的概率，与未分配的二进符 (3) 对重排后的两个概率最小符号重复步骤(2)

l o g 2 p ( xK i ) i l o g 2 p ( x i ) 1
(3) 为了编成唯一可译码，计算第i
pi

i 1
p (k )
(4) 将累加概率Pi (5) 取Pi二进数的小数点后K i位即为该消息符号的二进 2019/2/16 制码字。
k 1
7
1.香农编码方法
A
000 001 010 011 100 0 01
B
0 10
C
0 10
D
0 10
E
0
F
100 101 110 111
011 0111 01111
110 1110 11110
110 1110 1011
1100 1101 1110
1/16
101
011111
111110
1101
1111
011
4
几种编码方法
1.香农编码方法
香农编码过程
2019/2/16 9
1.香农编码方法




各码字之间至少有一位数字不同，故是唯 一可译码； 7个码字都不是延长码，故是即时码 这里L＝1，m＝2 7 平均码长为： K p ( aK 3 . 1 4 码 元 / 符 号 i) i i 1 平均信息传输率为：
2019/2/16
3
练习：有一信源，它有六个可能的输出，其概率分布如下表所示， 表中给出了对应的码A、B、C、D、E和F, (1) 求这些码中哪些是唯一可译码； (2) 求哪些码是即时码； (3) 对所有唯一可译码求出其平均码长
消息 a1 a2 a3 a4 a5 a6
2019/2/16
P(ai)
1/2 1/4 1/16 1/16 1/16
信息论基础
杜春娟 QQ:22282998 Tel:31889581
2019/2/16
1
第三章 数据压缩和信源编码
一．最佳编码 1. 香农码 2. 费诺码 3. 哈夫曼码 二．算术码 1. 香农－费诺码 2. 自适应算术码 三．其他无失真信源编码方法
2019/2/16 2

可能的尾随后缀排列出。而这些尾随后缀又可能是某些码字的前缀，再将由这 些尾随后缀产生的新的尾随后缀列出。然后再观察这些新的尾随后缀是否是某 些码字的前缀，再将产生的尾随后缀列出。这样，首先获得由最短的码字能引 起的所有尾随后缀。接着，按照上述将次短的码字…等等，所有码字可能产生 的尾随后缀全部列出。由此得到码C的所有可能的尾随后缀组成的集合F。

1. 香农编码 2. 费诺编码 3. 哈夫曼编码
2019/2/16
5
最佳编码

最佳码: 定义:能载荷一定的信息量，且码字的 平均长度最短，可分离的变长码的码字 集合.
2019/2/16
6
1.香农编码方法
香农指出，选择每个码字的长度 K i满足下式 I (xi )≤ K i＜I(xi)+1， 就可以得到这种码。这种编码方法称为香农编码。 编码方法如下： (1) p(x1)≥p(x2)≥…≥p (xn) (2) 确定满足下列不等式的整数码长K i
(5) 信源符号所对应的码字即为费诺码
2019/2/16 13
2.费诺编码方法


例 3 对例1的信源进行费诺编码，过程见下 页表 平均码长为： 7
i 1
K p ( aK 2 . 7 4 码 元 / 符 号 i) i

平均信息传输率为：
H ( X ) 2 . 6 1 R ＝ 0 . 9 5 3 b i t / 码 元 K 2 . 7 4
例1：设信源共7个符号消息，其概论和累加 概率如图所示。以i＝4为例， －log0.17≤K4 ≤ －log0.17+1 2.56≤K4 ≤3.56 则K4＝3 则累加概率P4＝0.57, 变换为二进制为：0.1001…… 故第四个消息的编码码字为100 其他码字可类似求出，见下页图

2019/2/16 8Байду номын сангаас
12
2019/2/16
2.费诺编码方法

编码过程如下：
(1) 将信源消息符号按其出现的概率大小依次排列： p(x1)≥p(x2)≥…≥p(xn)
(2) 将依次排列的信源符号按概率值分为两大组，使两个组的概率 之和近于相同，并对各组赋予一个二进制码元“0”和“1”
(3) 将每一大组的信源符号进一步再分成两组，使划分后的两个组 的概率之和近于相同，并又赋予两个组一个二进制符号“0”和 “1” (4)



唯一可译码的判断法 首先观察是否是非奇异码。若是奇异码，肯定不是唯一可 译码； 其次，计算是否满足Kraft不等式。若不满足一定不是唯一 可译码； 然后将码画成一棵树图，观察是否满足异前置码的树图的 构造，若满足则是唯一可译码。 或用Sardinas和Patterson设计的判断法：计算分组码中所 有可能的尾随后缀集合F,观察F中有没有包含任一码字，若 无则为唯一可译码；若有则一定不是唯一可译码。集合F的 构造：首先观察码C中最短的码字是否是其它码字的前缀。若是，将其所有
H ( X ) 2 . 6 1 R ＝ 0 . 8 3 1 b i t / 码 元 K 3 . 1 4
2019/2/16
10
1.香农编码方法

香农码实用性如何？ 例2 设信源有3个符号，概率分布为（0.10.5, 0.4, 0.1）


根据香农编码方法求出各个符号的码长分 别为：？ 码字分别为？
2019/2/16
11
1.香农编码方法


计算得码长分别为（1，2，4） 概率分布分别为（0，10，1110） 但实际上直观可看出（0，10，11）是更短 的码，也是惟一可译码 所以，由此可知，香农编码的冗余度稍大， 实际应用价值不强，但由于它是从编码定 理直接得来，具有理论意义 另外当 l o g 2 p ( xK i ) i l o g 2 p ( x i ) 1 左边等号成立时，编码效率比较高