香农编码
? 设离散无记忆信源
? 二进制香农码的编码步骤如下：
? 将信源符号按概率从大到小的顺序排列，为方便起见，令
p(x1)≥ p(x2)≥…≥ p(xn)
? 令 p(x0)=0，用 pa(xj),j=i+1表示第 i个码字的累加概率，则：
? 确定满足下列不等式的整数 ki,并令 ki为第 i个码字的长度
? － log2 p(xn)≤ki<－ log2 p(xn)+1
? 将 pa(xj) 用二进制表示，并取小数点后 ki 位作为符号 xi的编码。
1
0
( ) ( ),1,2,,ja j i
i
p x p x j n?
?
???
12
112
,,,,,,( ) 1
( ),( ),,( ),,( )()
nin
i
iin
x x x xX px
p x p x p x p xPX ?
???? ????
???? ?? ?
香农编码
例 有一单符号离散无记忆信源
对该信源编二进制香农码。其编码过程如下表所示。
二 进制香农编码
x i p ( x i ) p a ( x j ) k i 码字
x 1 0, 2 5 0, 0 0 0 2 0 0 (0, 0 0 0 ) 2
x 2 0, 2 5 0, 2 5 0 2 0 1 (0, 0 1 0 ) 2
x 3 0, 2 0 0, 5 0 0 3 1 0 0 (0, 1 0 0 ) 2
x 4 0, 1 5 0, 7 0 0 3 1 0 1 (0, 1 0 1 ) 2
x 5 0, 1 0 0, 8 5 0 4 1 1 0 1 (0, 1 1 0 1 ) 2
x 6 0, 0 5 0, 9 5 0 5 1 1 1 1 1 0 (0, 1 1 1 1 0 ) 2
1 2 3 4 5 6,,,,,
( ) 0, 2 5 0, 2 5 0, 2 0 0, 1 5 0, 1 0 0, 0 5
X x x x x x x
PX
? ? ? ?? ????
? ? ? ?
香农编码
? 计算出给定信源香农码的平均码长
? 若对上述信源采用等长编码，要做到无失真译码，每个符号至少要用 3
个比特表示。相比较，香农编码对信源进行了压缩。
? 由离散无记忆信源熵定义，可计算出：
? 对上述信源采用香农编码的信息率为
? 编码效率为信源熵和信息率之比。则
? 可以看出，编码效率并不是很高。
0.25 2 2 ( 0.2 0.15 ) 3 0.10 4 0.05 5 2.7 ( / )K ? ? ? ? ? ? ? ? ? ? ? 比特 符号
22
2, 7l o g l o g 2 2, 7 1,2
1
KR m L m
L? ? ? ? ?这里
( ) 2, 4 2 8 9, 6 3 %
2, 7
HX
R? ? ? ?
6
21( ) ( ) l o g ( ) 2,4 2 ( / )iiiH X p x p x?? ? ?? 比特 符号
费诺编码
费诺编码也是一种常见的信源编码方法。
编码步骤如下：
? 将概率按从大到小的顺序排列，令
p(x1)≥ p(x2)≥…≥ p(xn)
? 按编码进制数将概率分组，使每组概率尽可能接近或相等。如
编二进制码就分成两组，编 m进制码就分成 m组。
? 给每一组分配一位码元。
? 将每一分组再按同样原则划分，重复步骤 2和 3，直至概率不再
可分为止。
费诺编码
例 设有一单符号离散信源
? 对该信源编二进制费诺码。编码过程如下表。
二进制费诺编码
信源符号 概率 编码 码字 码长
x 1 0, 3 2 0 00 2
x 2 0, 2 2
0
1 01 2
x 3 0, 1 8 0
10 2
x 4 0, 1 6 0 1 1 0 3
x 5 0, 0 8 0 1 1 1 0 4
x 6 0, 0 4
1
1
1
1 1111 4
1 2 3 4 5 6,,,,,
( ) 0, 3 2 0, 2 2 0, 1 8 0, 1 6 0, 0 8 0, 0 4
X x x x x x x
PX
? ? ? ?? ????
? ? ? ?
费诺编码
? 该信源的熵为
? 平均码长为
? 编码效率为
? 本例中费诺编码有较高的编码效率。费诺码比较适合于
每次分组概率都很接近 的信源。特别是对每次 分组概率
都相等 的信源进行编码时，可达到理想的编码效率。
6
2
1
( ) ( ) l o g ( ) 2,3 5 ( / )ii
i
H X p x p x
?
? ? ?? 比特 符号
6
1
( ) 2.4( / )ii
i
K p x k
?
??? 比特 符号
2.422 1
( ) 2,3 5 2,3 5 9 7,9 2 % 1,2
l o g l o g 2 2,4KL
HX Lm
m? ? ? ? ? ? ?这里
费诺编码
? 题中码字还可用码树来表示，如图所示。
霍夫曼编码
霍夫曼 (Huffman)编码是一种效率比较高的变长
无失真信源编码方法。
? 编码步骤
? 二进制哈夫曼编码
? m进制哈夫曼编码
霍夫曼编码 —— 编码步骤
? 将信源符号按概率从大到小的顺序排列，令
p(x1)≥ p(x2)≥…≥ p(xn)
? 给两个概率最小的信源符号 p(xn-1)和 p(xn)各分配一个码位,0”和,1”，
将这两个信源符号合并成一个新符号，并用这两个最小的概率之和
作为新符号的概率，结果得到一个只包含 (n－ 1)个信源符号的新信源。
称为 信源的第一次缩减信源,用 S1表示。
? 将缩减信源 S1的符号仍按概率从大到小顺序排列，重复步骤 2，得到
只含 (n－ 2)个符号的缩减信源 S2。
? 重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符
号的概率之和必为 1。然后从最后一级缩减信源开始，依编码路径向
前返回，就得到各信源符号所对应的码字。
霍夫曼编码 —— 二进制哈夫曼编码
例 设单符号离散无记忆信源如下，要求对信源编二进制
霍夫曼码。编码过程如下图（后页）。
1 2 3 4 5 6 7 8,,,,,
( ) 0, 4 0, 1 8 0, 1 0, 1 0, 0 7 0, 0 6 0, 0 5 0, 0 4
X x x x x x x x x
PX
? ? ? ?? ????
? ? ? ?
? 在图中读取码字的时候，一定要从后向前读，此时编出
来的码字才是可分离的异前置码。若从前向后读取码字，
则码字不可分离。
霍夫曼编码 —— 二进制哈夫曼编码
霍夫曼编码 —— 二进制哈夫曼编码
? 将上图左右颠倒过来重画一下，即可得到二进制哈夫曼码的码树。
? 信源熵为：
? 平均码长为
? 编码效率为
? 若采用定长编码，码长 K=3，则编码效率
? 可见哈夫曼的编码效率提高了 12.7%。
霍夫曼编码 —— 二进制哈夫曼编码
8
2
1
( ) ( ) l o g ( ) 2,5 5 ( / )ii
i
H X p x p x
?
? ? ?? 比特 符号
8
1
( ) 0,4 1 ( 0,1 8 0,1 ) 3 ( 0,1 0 0,0 7 0,0 6 ) 4 ( 0,0 5 0,0 4 ) 5 2,6 1 ( / )ii
i
K p x k
?
? ? ? ? ? ? ? ? ? ? ? ? ? ?? 比特 符号
( ) ( ) 2, 5 52, 6 1 9 7, 7 %H X H XR K? ? ? ? ?
2.553 85%? ??
霍夫曼编码 —— 二进制哈夫曼编码
注意, 哈夫曼的编法并不惟一 。
? 每次对缩减信源两个概率最小的符号分配,0”和,1”码元是任意的，
所以可得到不同的码字。只要 在各次缩减信源中保持码元分配的一致
性, 即能得到可分离码字。
? 不同的码元分配，得到的具体码字不同，但码长 ki不变，平均码长
也不变，所以没有本质区别；
? 缩减信源时，若合并后的新符号概率与其他符号概率相等，从编码方
法上来说,这几个符号的次序可任意排列，编出的码都是正确的，但
得到的 码字不相同 。 不同的编法得到的 码字长度 ki也不尽相同 。
K
例,单符号离散无记忆信源,用
两种不同的方法对其编二进制哈夫曼码。
si li Wi 概率
s1
s2
s3
s4
s5
1
2
3
4
4
1
01
000
0010
0011
0.4
0.2
0.2
0.1
0.1
0.4
0.2
0.2
0.2
0.4
0.4
0.2
0.6
0.4
0
1
0
1
0
1
方法一,合并后的新符号排在其它相同概率符号的后面。
1 2 3 4 5,,,,,
( ) 0, 4 0, 2 0, 2 0, 1 0, 1
X x x x x x
PX
? ? ? ?? ????
? ? ? ?
霍夫曼编码 —— 二进制哈夫曼编码
si li Wi 概率
s1
s2
s3
s4
s5
1
2
3
4
4
1
01
000
0010
0011
0.4
0.2
0.2
0.1
0.1
0.4
0.2
0.2
0.2
0.4
0.4
0.2
0.6
0.4
0
1
0
1
0
1
这两种编码哪一种更好呢，我们来计算一下二者的码长。
方法二,合并后的新符号排在其它相同概率符号的前面。
霍夫曼编码 —— 二进制哈夫曼编码
两种编码的平均码长是一样的，都是 2.2，那一种更好呢，
我们可以计算一下平均码长的方差。
5
1
1
( ) 0.4 1 0.2 2 0.2 3 0.1 4 0.1 4 2.2ii
i
L P s l
?
? ? ? ? ? ? ? ? ? ? ? ??
5
2
1
( ) 0.4 2 0.2 2 0.2 2 0.1 3 0.1 3 2.2ii
i
L P s l
?
? ? ? ? ? ? ? ? ? ? ? ??
2 2 2
1
[ ( ) ] ( ) ( )qi i i
i
E l L P s l L?
?
? ? ? ??
522
11
1
( ) ( ) 1.36ii
i
P s l L?
?
? ? ??
522
1
( ) ( ) 0,1 6ii
i
P s l L?
?
? ? ??
定义码字长度的方差 σ2：
霍夫曼编码 —— 二进制哈夫曼编码
霍夫曼编码 —— 二进制哈夫曼编码
? 可见：第二种编码方法的码长方差要小许多。意味着第二种
编码方法的码长变化较小，比较接近于平均码长。
? 第一种方法编出的 5个码字有 4种不同的码长；
? 第二种方法编出的码长只有两种不同的码长；
? 显然,第二种编码方法更简单、更容易实现，所以更好 。
结论, 在哈夫曼编码过程中，对缩减信源符号按概率由大到小
的顺序重新排列时，应 使合并后的新符号尽可能排在靠前的
位置,这样可使合并后的新符号重复编码次数减少，使短码
得到充分利用。
霍夫曼编码 —— m进制哈夫曼编码
“全树”概念
? 定义：码树图中每个中间节点后续的枝数为 m时称为 全树 ；若
有些节点的后续枝数不足 m，就称为 非全树 。
? 二进制码不存在非全树的情况，因为后续枝数是一时，这个枝
就可以去掉使码字长度缩短。
? 对 m进制编码：若所有码字构成全树，可分离的码字数（信源
个数）必为 m+k(m－ 1)。 k为信源缩减次数。
? 若信源所含的符号数 n不能构成 m进制全树，必须增加 s个不用
的码字形成全树。显然 s<m－ 1，若 s=m－ 1，意味着某个中间
节点之后只有一个分枝，为了节约码长，这一分枝可以省略。
霍夫曼编码 —— m进制哈夫曼编码
? 在编 m进制哈夫曼码时为了使平均码长最短，必须使最
后一步缩减信源有 m个信源符号。非全树时，有 s个码字
不用：
? 第一次对最小概率符号分配码元时就只取 (m－ s)个，
分别配以 0,1,…,m－ s－ 1，把这些符号的概率相加作
为一个新符号的概率，与其它符号一起重新排列。
? 以后每次就可以取 m个符号，分别配以 0,1,…,m－
1； … ；如此下去，直至所有概率相加得 1为止，即得
到各符号的 m进制码字。
霍夫曼编码 —— m进制哈夫曼编码
例：对如下单符号离散无记忆信源 (例 5.4.1)编三进制哈夫
曼码。
这里,m=3,n=8
? 令 k=3,m+k(m－ 1)=9，则 s=9－ n=9－ 8=1
? 所以第一次取 m－ s=2个符号进行编码。
1 2 3 4 5 6 7 8,,,,,
( ) 0, 4 0, 1 8 0, 1 0, 1 0, 0 7 0, 0 6 0, 0 5 0, 0 4
X x x x x x x x x
PX
? ? ? ?? ????
? ? ? ?
霍夫曼编码 —— m进制哈夫曼编码
霍夫曼编码 —— m进制哈夫曼编码
? 平均码长为：
? 信息率为：
? 编码效率为：
? 可见：哈夫曼的编码效率相当高，对编码器的要求也简单得多。
5
1
1
( ) 0.4 1 ( 0.1 8 0.1 0.0 7 0.0 6) 2 ( 0.0 5 0.0 4) 3 1.6 9( /)ii
i
K p x k
?
? ? ? ? ? ? ? ? ? ? ? ?? 比特 符号
22
1, 6 9l o g 3 l o g 3 2, 6 8 ( / )
1
KR
L? ? ? 比特 符号
( ) 2, 5 5 9 5, 2 %
2, 6 8
HX
R? ? ? ?
哈夫曼编码
? 哈夫曼 (Huffman)编码是一种常用的压缩
编码方法，是 Huffman于 1952年为压缩
文本文件建立的。 它的基本原理是频繁
使用的数据用较短的代码代替，较少使
用的数据用较长的代码代替，每个数据
的代码各不相同 。这些代码都是二进制
码，且码的长度是可变的。。
? 举个例子：假设一个文件中出现了 8种符
号 S0,S1,S2,S3,S4,S5,S6,S7，那么每种
符号要编码，至少需要 3比特。假设编码
成 000,001,010,011,100,101,110,111(称
做码字 )。那么符号序列
S0S1S7S0S1S6S2S2S3S4S5S0S0S1编码
后变成
00000111100000111001001001110010
1000000001，共用了 42比特。
? 我们发现 S0,S1,S2这三个符号出现的频率比
较大，其它符号出现的频率比较小，如果我们
采用一种编码方案使得 S0,S1,S2的码字短，
其它符号的码字长，这样就能够减少占用的比
特数。例如，我们采用这样的编码方案,S0到
S7的码字分别
01,11,101,0000,0001,0010,0011,100，那么上
述符号序列变成
0111100011100111011010000000100100101
11，共用了 39比特，
? 尽管有些码字如 S3,S4,S5,S6变长了
(由 3位变成 4位 )，但使用频繁的几个码
字如 S0,S1变短了，所以实现了压缩。
? 上述的编码是如何得到的呢？随意乱写
是不行的。编码必须保证不能出现一个
码字和另一个的前几位相同的情况，比
如说，如果 S0的码字为 01,S2的码字为
011，那么当序列中出现 011时，你不知
道是 S0的码字后面跟了个 1，还是完整的
一个 S2的码字。我们给出的编码能够保
证这一点
? 下面给出具体的 Huffman编码算法。
? (1) 首先统计出每个符号出现的频率，
上例 S0到 S7的出现频率分别为 4/14,3/14，
2/14,1/14,1/14,1/14,1/14,1/14。
? (2) 从左到右把上述频率按从小到大的
顺序排列。
? (3) 每一次选出最小的两个值，作为二
叉树的两个叶子节点，将和作为它们的根节点，
这两个叶子节点不再参与比较，新的根节点参
与比较。
? (4) 重复 (3)，直到最后得到和为 1的根
节点。
? (5) 将形成的二叉树的左节点标 0，右节
点标 1。把从最上面的根节点到最下面的叶子
节点途中遇到的 0,1序列串起来，就得到了各
个符号的编码。
? 上面的例子用 Huffman编码的过程如图所示，
其中圆圈中的数字是新节点产生的顺序。可见，
我们上面给出的编码就是这么得到的。
?
? Huffman编码的示意图
一些结论
? 香农码、费诺码、哈夫曼码都考虑了信源的统计特性，使经常出
现的信源符号对应较短的码字，使信源的平均码长缩短，从而实
现了对信源的压缩；
? 香农码有系统的、惟一的编码方法，但在很多情况下编码效率不
是很高；
? 费诺码和哈夫曼码的编码方法都不惟一；
? 费诺码比较适合于对分组概率相等或接近的信源编码；
? 哈夫曼码对信源的统计特性没有特殊要求，编码效率比较高，对
编码设备的要求也比较简单，因此综合性能优于香农码和费诺码 。
Huffman码在具体实用时，设备较复杂。
在编码器中需要增加缓冲寄存器，因为
每个信源符号所对应的码符号长度不一，
负责会造成输入和输出不能保持平衡。
? 本章介绍的都是离散信源变长编码。
? 优点,提高编码效率 ；
? 缺点,需要大量缓冲设备来存储这些变长码，然后再以恒定的
码率进行传送；在传输的过程中如果出现了误码，容易引起错
误扩散，所以要求有优质的信道。
信
源
编
码
总
结
? 设离散无记忆信源
? 二进制香农码的编码步骤如下：
? 将信源符号按概率从大到小的顺序排列，为方便起见，令
p(x1)≥ p(x2)≥…≥ p(xn)
? 令 p(x0)=0，用 pa(xj),j=i+1表示第 i个码字的累加概率，则：
? 确定满足下列不等式的整数 ki,并令 ki为第 i个码字的长度
? － log2 p(xn)≤ki<－ log2 p(xn)+1
? 将 pa(xj) 用二进制表示，并取小数点后 ki 位作为符号 xi的编码。
1
0
( ) ( ),1,2,,ja j i
i
p x p x j n?
?
???
12
112
,,,,,,( ) 1
( ),( ),,( ),,( )()
nin
i
iin
x x x xX px
p x p x p x p xPX ?
???? ????
???? ?? ?
香农编码
例 有一单符号离散无记忆信源
对该信源编二进制香农码。其编码过程如下表所示。
二 进制香农编码
x i p ( x i ) p a ( x j ) k i 码字
x 1 0, 2 5 0, 0 0 0 2 0 0 (0, 0 0 0 ) 2
x 2 0, 2 5 0, 2 5 0 2 0 1 (0, 0 1 0 ) 2
x 3 0, 2 0 0, 5 0 0 3 1 0 0 (0, 1 0 0 ) 2
x 4 0, 1 5 0, 7 0 0 3 1 0 1 (0, 1 0 1 ) 2
x 5 0, 1 0 0, 8 5 0 4 1 1 0 1 (0, 1 1 0 1 ) 2
x 6 0, 0 5 0, 9 5 0 5 1 1 1 1 1 0 (0, 1 1 1 1 0 ) 2
1 2 3 4 5 6,,,,,
( ) 0, 2 5 0, 2 5 0, 2 0 0, 1 5 0, 1 0 0, 0 5
X x x x x x x
PX
? ? ? ?? ????
? ? ? ?
香农编码
? 计算出给定信源香农码的平均码长
? 若对上述信源采用等长编码，要做到无失真译码，每个符号至少要用 3
个比特表示。相比较，香农编码对信源进行了压缩。
? 由离散无记忆信源熵定义，可计算出：
? 对上述信源采用香农编码的信息率为
? 编码效率为信源熵和信息率之比。则
? 可以看出，编码效率并不是很高。
0.25 2 2 ( 0.2 0.15 ) 3 0.10 4 0.05 5 2.7 ( / )K ? ? ? ? ? ? ? ? ? ? ? 比特 符号
22
2, 7l o g l o g 2 2, 7 1,2
1
KR m L m
L? ? ? ? ?这里
( ) 2, 4 2 8 9, 6 3 %
2, 7
HX
R? ? ? ?
6
21( ) ( ) l o g ( ) 2,4 2 ( / )iiiH X p x p x?? ? ?? 比特 符号
费诺编码
费诺编码也是一种常见的信源编码方法。
编码步骤如下：
? 将概率按从大到小的顺序排列，令
p(x1)≥ p(x2)≥…≥ p(xn)
? 按编码进制数将概率分组，使每组概率尽可能接近或相等。如
编二进制码就分成两组，编 m进制码就分成 m组。
? 给每一组分配一位码元。
? 将每一分组再按同样原则划分，重复步骤 2和 3，直至概率不再
可分为止。
费诺编码
例 设有一单符号离散信源
? 对该信源编二进制费诺码。编码过程如下表。
二进制费诺编码
信源符号 概率 编码 码字 码长
x 1 0, 3 2 0 00 2
x 2 0, 2 2
0
1 01 2
x 3 0, 1 8 0
10 2
x 4 0, 1 6 0 1 1 0 3
x 5 0, 0 8 0 1 1 1 0 4
x 6 0, 0 4
1
1
1
1 1111 4
1 2 3 4 5 6,,,,,
( ) 0, 3 2 0, 2 2 0, 1 8 0, 1 6 0, 0 8 0, 0 4
X x x x x x x
PX
? ? ? ?? ????
? ? ? ?
费诺编码
? 该信源的熵为
? 平均码长为
? 编码效率为
? 本例中费诺编码有较高的编码效率。费诺码比较适合于
每次分组概率都很接近 的信源。特别是对每次 分组概率
都相等 的信源进行编码时，可达到理想的编码效率。
6
2
1
( ) ( ) l o g ( ) 2,3 5 ( / )ii
i
H X p x p x
?
? ? ?? 比特 符号
6
1
( ) 2.4( / )ii
i
K p x k
?
??? 比特 符号
2.422 1
( ) 2,3 5 2,3 5 9 7,9 2 % 1,2
l o g l o g 2 2,4KL
HX Lm
m? ? ? ? ? ? ?这里
费诺编码
? 题中码字还可用码树来表示，如图所示。
霍夫曼编码
霍夫曼 (Huffman)编码是一种效率比较高的变长
无失真信源编码方法。
? 编码步骤
? 二进制哈夫曼编码
? m进制哈夫曼编码
霍夫曼编码 —— 编码步骤
? 将信源符号按概率从大到小的顺序排列，令
p(x1)≥ p(x2)≥…≥ p(xn)
? 给两个概率最小的信源符号 p(xn-1)和 p(xn)各分配一个码位,0”和,1”，
将这两个信源符号合并成一个新符号，并用这两个最小的概率之和
作为新符号的概率，结果得到一个只包含 (n－ 1)个信源符号的新信源。
称为 信源的第一次缩减信源,用 S1表示。
? 将缩减信源 S1的符号仍按概率从大到小顺序排列，重复步骤 2，得到
只含 (n－ 2)个符号的缩减信源 S2。
? 重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符
号的概率之和必为 1。然后从最后一级缩减信源开始，依编码路径向
前返回，就得到各信源符号所对应的码字。
霍夫曼编码 —— 二进制哈夫曼编码
例 设单符号离散无记忆信源如下，要求对信源编二进制
霍夫曼码。编码过程如下图（后页）。
1 2 3 4 5 6 7 8,,,,,
( ) 0, 4 0, 1 8 0, 1 0, 1 0, 0 7 0, 0 6 0, 0 5 0, 0 4
X x x x x x x x x
PX
? ? ? ?? ????
? ? ? ?
? 在图中读取码字的时候，一定要从后向前读，此时编出
来的码字才是可分离的异前置码。若从前向后读取码字，
则码字不可分离。
霍夫曼编码 —— 二进制哈夫曼编码
霍夫曼编码 —— 二进制哈夫曼编码
? 将上图左右颠倒过来重画一下，即可得到二进制哈夫曼码的码树。
? 信源熵为：
? 平均码长为
? 编码效率为
? 若采用定长编码，码长 K=3，则编码效率
? 可见哈夫曼的编码效率提高了 12.7%。
霍夫曼编码 —— 二进制哈夫曼编码
8
2
1
( ) ( ) l o g ( ) 2,5 5 ( / )ii
i
H X p x p x
?
? ? ?? 比特 符号
8
1
( ) 0,4 1 ( 0,1 8 0,1 ) 3 ( 0,1 0 0,0 7 0,0 6 ) 4 ( 0,0 5 0,0 4 ) 5 2,6 1 ( / )ii
i
K p x k
?
? ? ? ? ? ? ? ? ? ? ? ? ? ?? 比特 符号
( ) ( ) 2, 5 52, 6 1 9 7, 7 %H X H XR K? ? ? ? ?
2.553 85%? ??
霍夫曼编码 —— 二进制哈夫曼编码
注意, 哈夫曼的编法并不惟一 。
? 每次对缩减信源两个概率最小的符号分配,0”和,1”码元是任意的，
所以可得到不同的码字。只要 在各次缩减信源中保持码元分配的一致
性, 即能得到可分离码字。
? 不同的码元分配，得到的具体码字不同，但码长 ki不变，平均码长
也不变，所以没有本质区别；
? 缩减信源时，若合并后的新符号概率与其他符号概率相等，从编码方
法上来说,这几个符号的次序可任意排列，编出的码都是正确的，但
得到的 码字不相同 。 不同的编法得到的 码字长度 ki也不尽相同 。
K
例,单符号离散无记忆信源,用
两种不同的方法对其编二进制哈夫曼码。
si li Wi 概率
s1
s2
s3
s4
s5
1
2
3
4
4
1
01
000
0010
0011
0.4
0.2
0.2
0.1
0.1
0.4
0.2
0.2
0.2
0.4
0.4
0.2
0.6
0.4
0
1
0
1
0
1
方法一,合并后的新符号排在其它相同概率符号的后面。
1 2 3 4 5,,,,,
( ) 0, 4 0, 2 0, 2 0, 1 0, 1
X x x x x x
PX
? ? ? ?? ????
? ? ? ?
霍夫曼编码 —— 二进制哈夫曼编码
si li Wi 概率
s1
s2
s3
s4
s5
1
2
3
4
4
1
01
000
0010
0011
0.4
0.2
0.2
0.1
0.1
0.4
0.2
0.2
0.2
0.4
0.4
0.2
0.6
0.4
0
1
0
1
0
1
这两种编码哪一种更好呢，我们来计算一下二者的码长。
方法二,合并后的新符号排在其它相同概率符号的前面。
霍夫曼编码 —— 二进制哈夫曼编码
两种编码的平均码长是一样的，都是 2.2，那一种更好呢，
我们可以计算一下平均码长的方差。
5
1
1
( ) 0.4 1 0.2 2 0.2 3 0.1 4 0.1 4 2.2ii
i
L P s l
?
? ? ? ? ? ? ? ? ? ? ? ??
5
2
1
( ) 0.4 2 0.2 2 0.2 2 0.1 3 0.1 3 2.2ii
i
L P s l
?
? ? ? ? ? ? ? ? ? ? ? ??
2 2 2
1
[ ( ) ] ( ) ( )qi i i
i
E l L P s l L?
?
? ? ? ??
522
11
1
( ) ( ) 1.36ii
i
P s l L?
?
? ? ??
522
1
( ) ( ) 0,1 6ii
i
P s l L?
?
? ? ??
定义码字长度的方差 σ2：
霍夫曼编码 —— 二进制哈夫曼编码
霍夫曼编码 —— 二进制哈夫曼编码
? 可见：第二种编码方法的码长方差要小许多。意味着第二种
编码方法的码长变化较小，比较接近于平均码长。
? 第一种方法编出的 5个码字有 4种不同的码长；
? 第二种方法编出的码长只有两种不同的码长；
? 显然,第二种编码方法更简单、更容易实现，所以更好 。
结论, 在哈夫曼编码过程中，对缩减信源符号按概率由大到小
的顺序重新排列时，应 使合并后的新符号尽可能排在靠前的
位置,这样可使合并后的新符号重复编码次数减少，使短码
得到充分利用。
霍夫曼编码 —— m进制哈夫曼编码
“全树”概念
? 定义：码树图中每个中间节点后续的枝数为 m时称为 全树 ；若
有些节点的后续枝数不足 m，就称为 非全树 。
? 二进制码不存在非全树的情况，因为后续枝数是一时，这个枝
就可以去掉使码字长度缩短。
? 对 m进制编码：若所有码字构成全树，可分离的码字数（信源
个数）必为 m+k(m－ 1)。 k为信源缩减次数。
? 若信源所含的符号数 n不能构成 m进制全树，必须增加 s个不用
的码字形成全树。显然 s<m－ 1，若 s=m－ 1，意味着某个中间
节点之后只有一个分枝，为了节约码长，这一分枝可以省略。
霍夫曼编码 —— m进制哈夫曼编码
? 在编 m进制哈夫曼码时为了使平均码长最短，必须使最
后一步缩减信源有 m个信源符号。非全树时，有 s个码字
不用：
? 第一次对最小概率符号分配码元时就只取 (m－ s)个，
分别配以 0,1,…,m－ s－ 1，把这些符号的概率相加作
为一个新符号的概率，与其它符号一起重新排列。
? 以后每次就可以取 m个符号，分别配以 0,1,…,m－
1； … ；如此下去，直至所有概率相加得 1为止，即得
到各符号的 m进制码字。
霍夫曼编码 —— m进制哈夫曼编码
例：对如下单符号离散无记忆信源 (例 5.4.1)编三进制哈夫
曼码。
这里,m=3,n=8
? 令 k=3,m+k(m－ 1)=9，则 s=9－ n=9－ 8=1
? 所以第一次取 m－ s=2个符号进行编码。
1 2 3 4 5 6 7 8,,,,,
( ) 0, 4 0, 1 8 0, 1 0, 1 0, 0 7 0, 0 6 0, 0 5 0, 0 4
X x x x x x x x x
PX
? ? ? ?? ????
? ? ? ?
霍夫曼编码 —— m进制哈夫曼编码
霍夫曼编码 —— m进制哈夫曼编码
? 平均码长为：
? 信息率为：
? 编码效率为：
? 可见：哈夫曼的编码效率相当高，对编码器的要求也简单得多。
5
1
1
( ) 0.4 1 ( 0.1 8 0.1 0.0 7 0.0 6) 2 ( 0.0 5 0.0 4) 3 1.6 9( /)ii
i
K p x k
?
? ? ? ? ? ? ? ? ? ? ? ?? 比特 符号
22
1, 6 9l o g 3 l o g 3 2, 6 8 ( / )
1
KR
L? ? ? 比特 符号
( ) 2, 5 5 9 5, 2 %
2, 6 8
HX
R? ? ? ?
哈夫曼编码
? 哈夫曼 (Huffman)编码是一种常用的压缩
编码方法，是 Huffman于 1952年为压缩
文本文件建立的。 它的基本原理是频繁
使用的数据用较短的代码代替，较少使
用的数据用较长的代码代替，每个数据
的代码各不相同 。这些代码都是二进制
码，且码的长度是可变的。。
? 举个例子：假设一个文件中出现了 8种符
号 S0,S1,S2,S3,S4,S5,S6,S7，那么每种
符号要编码，至少需要 3比特。假设编码
成 000,001,010,011,100,101,110,111(称
做码字 )。那么符号序列
S0S1S7S0S1S6S2S2S3S4S5S0S0S1编码
后变成
00000111100000111001001001110010
1000000001，共用了 42比特。
? 我们发现 S0,S1,S2这三个符号出现的频率比
较大，其它符号出现的频率比较小，如果我们
采用一种编码方案使得 S0,S1,S2的码字短，
其它符号的码字长，这样就能够减少占用的比
特数。例如，我们采用这样的编码方案,S0到
S7的码字分别
01,11,101,0000,0001,0010,0011,100，那么上
述符号序列变成
0111100011100111011010000000100100101
11，共用了 39比特，
? 尽管有些码字如 S3,S4,S5,S6变长了
(由 3位变成 4位 )，但使用频繁的几个码
字如 S0,S1变短了，所以实现了压缩。
? 上述的编码是如何得到的呢？随意乱写
是不行的。编码必须保证不能出现一个
码字和另一个的前几位相同的情况，比
如说，如果 S0的码字为 01,S2的码字为
011，那么当序列中出现 011时，你不知
道是 S0的码字后面跟了个 1，还是完整的
一个 S2的码字。我们给出的编码能够保
证这一点
? 下面给出具体的 Huffman编码算法。
? (1) 首先统计出每个符号出现的频率，
上例 S0到 S7的出现频率分别为 4/14,3/14，
2/14,1/14,1/14,1/14,1/14,1/14。
? (2) 从左到右把上述频率按从小到大的
顺序排列。
? (3) 每一次选出最小的两个值，作为二
叉树的两个叶子节点，将和作为它们的根节点，
这两个叶子节点不再参与比较，新的根节点参
与比较。
? (4) 重复 (3)，直到最后得到和为 1的根
节点。
? (5) 将形成的二叉树的左节点标 0，右节
点标 1。把从最上面的根节点到最下面的叶子
节点途中遇到的 0,1序列串起来，就得到了各
个符号的编码。
? 上面的例子用 Huffman编码的过程如图所示，
其中圆圈中的数字是新节点产生的顺序。可见，
我们上面给出的编码就是这么得到的。
?
? Huffman编码的示意图
一些结论
? 香农码、费诺码、哈夫曼码都考虑了信源的统计特性，使经常出
现的信源符号对应较短的码字，使信源的平均码长缩短，从而实
现了对信源的压缩；
? 香农码有系统的、惟一的编码方法，但在很多情况下编码效率不
是很高；
? 费诺码和哈夫曼码的编码方法都不惟一；
? 费诺码比较适合于对分组概率相等或接近的信源编码；
? 哈夫曼码对信源的统计特性没有特殊要求，编码效率比较高，对
编码设备的要求也比较简单，因此综合性能优于香农码和费诺码 。
Huffman码在具体实用时，设备较复杂。
在编码器中需要增加缓冲寄存器，因为
每个信源符号所对应的码符号长度不一，
负责会造成输入和输出不能保持平衡。
? 本章介绍的都是离散信源变长编码。
? 优点,提高编码效率 ；
? 缺点,需要大量缓冲设备来存储这些变长码，然后再以恒定的
码率进行传送；在传输的过程中如果出现了误码，容易引起错
误扩散，所以要求有优质的信道。
信
源
编
码
总
结
