2.48
3
011
a4
0.17
0.57
2.56
3
100
a5
0.15
0.74
2.743101 Nhomakorabeaa6
0.10
0.89
3.34
4
1110
a7
0.01
0.99
6.66
7
1111110
10
香农编码
• 由上表可以看出，一共有5个三位的代码组，各代 码组之间至少有一位数字不相同，故是唯一可译码。 还可以判断出，这7个代码组都属于即时码。
相等。如编二进制码就分成两组,编m进制码就分成 m组。 给每一组分配一位码元。 将每一分组再按同样原则划分,重复步骤2和3,直至概 率不再可分为止。
13
费诺编码
xi
符号概 率
x1
0.32
0
编码 0
码字 00
码长 2
x2
0.22
1
01
2
x3
0.18
0
10
2
x4
0.16
1
0
110
3
x5
0.08
1
0
的码字总是0、00、000、0…0的式样； ✓ 码字集合是唯一的，且为即时码； ✓ 先有码长再有码字； ✓ 对于一些信源，编码效率不高，冗余度稍大，因此
其实用性受到较大限制。
12
费诺编码
费诺编码属于概率匹配编码 。
编码步骤如下： 将概率按从大到小的顺序排列,令
p(x1)≥ p(x2)≥…≥ p(xn) 按编码进制数将概率分组,使每组概率尽可能接近或
15
哈夫曼编码
哈夫曼编码也是用码树来分配各符号的码字。 哈夫曼(Huffman)编码是一种效率比较高的变长无失
真信源编码方法。 霍夫曼编码及其变种，在压缩编码领域中应用的非常广泛
数字图像：JPEG 运动图像：MPEG2、H.261、H.263
16
哈夫曼编码
哈夫曼编码的步骤如下：
1110
4
x6
0.04
1
1
1111
4
14
结论
➢ 费诺编码特点： ✓ 概率大，则分解的次数小；概率小, 则分解的次数多。
这符合最佳编码原则。 ✓ 码字集合是唯一的。 ✓ 分解完了，码字出来了，码长也有了。 ✓ 因此，费诺编码方法又称为子集分解法。 ✓ 费诺编码方法比较适合于每次分组概率都很接近的信
源，特别是对每次分组概率都相等的信源进行编码时， 可达到理想的编码效率。 ➢r 元费诺码: 前面讨论的费诺码是二元费诺码，对r元费诺码， 与二元费诺码编码方法相同，只是每次分组时应将符号分成概 率分布接近的r个组。
信源编码
1
无失真信源编码
X
Y
信源
信源编码器
信道
L长序列
码表
K长码字
实现无失真的信源编码,要求: 信源符号X1 X2…Xl …XL 是一一对应的
码字Y1 Y2…Yk… YK
能够无失真或无差错地从Y恢复X,也就是能正确地进行反 变换或译码 ; 传送Y时所需要的信息率最小
信息率最小就是找到一种编码方式使
_
K
KL
log m
1 log M
最小
L
L
2
定长编码定理
定长编码定理：
由L个符号组成的、每个符号的熵为HL(X)的无记忆 平稳信源符号序列X1…Xl…XL,可用 KL个符号 Y1…Yk…YKL(每个符号有m种可能值)进行定长编码。
KL L
log
m
H L (X)
则当L足够大时,必可使译码差错小于δ;反之,当
香农第一定理指出,选择每个码字的长度Ki满足下式：
或: －log2 p(xi)≤ Ki <－log2 p(xi)+1 就可以得到这种码。 这种编码方法称为香农编码
8
香农编码
二进制香农码的编码步骤如下： ⑴将信源符号按概率从大到小的顺序排列, p1≥ p2≥…≥ pn ⑵确定满足下列不等式的整数Ki, －log2 pi ≤ Ki <－log2 pi+1 ⑶计算第i个码字的累加概率，
2 (X)
L
2
信源序列的自信息方差
2(X) E{[I(xi) H(X)]2}
5
变长编码定理
单个符号变长编码定理：
若一离散无记忆信源的符号熵为H(X),每个信源符号用m进 制码元进行变长编码,一定存在一种无失真编码方法,其码
字平均长度满足下列不等式: H(X) K H(X) 1
log m
⑷将Pi用二进制表示,并取小数点后Ki位作为符号ai的编 码。
9
香农编码
例 有一个信源共有7个符号，其概率及其累加和如下表所示：
信源消息 符号概率 累加概率 logP(ai) 码字长
符号ai P(ai)
Pi
度Ki
码字
a1
0.20
0
2.34
3
000
a2
0.19
0.20
2.41
3
001
a3
0.18
0.39
⑵将定理的条件改写成
KL logm > LHL(X) H(X)
其中：左边：KL长码字所能携带的最大信息， 右边：L长信源序列携带的信息量。
4
定长编码定理
为了衡量编码效果,定义编码效率：
最佳编码效率： HL(X) , >0 HL(X)
对定长编码,若要实现几乎无失真编码,则信源长度
必须满足:
方法：将概率大的信源符号编以短的码字。概率小 的符号编以长的码字，这样使得平均码字长度最短。 主要有：
香农（Shannon） 费诺（Fano） 哈夫曼（Huffma ）
7
香农编码
香农第一定理指出了平均码长与信源之间的关系,同 时也指出了可以通过编码使平均码长达到极限值,这 是一个很重要的极限定理。
• 平均码长 n K p(xi )ki 3.14 码元/符号 i 1
• 平均信息传输速率
R H (X ) 2.61 0.831 比特 / 码元 K 3.14
11
结论
➢ 香农编码方法特点： ✓ 由于ki总是进一取整，香农编码方法不一定是最佳的； ✓ 由于第一个消息符号的累加概率总是为0，故它对应
KL L
log
m
H L (X)
2
时,译码差错一定是有限值,而当L足够大时,译码几乎 必定出错
3
定长编码定理
⑴当编码器容许的输出信息率,也就是当每个信源符号所必须 输出的码长是
时,只要 K HL(X) ,这种编码器一定可以做到几乎无失真, 也就是收端的译码差错概率接近于零,条件是所取的符号数 L足够大。
log m
离散平稳无记忆序列变长编码定理 对于平均符号熵为HL(X)的离散平稳无记忆信源,必存在一种
无失真编码方法,使平均信息率 K 满足不等式
HL(X) K HL(X)
编码效率的下界： H L(X)
H L(X)
K
H L(X) log m
L
6
5.2.3最佳变长编码
最佳码： 对于某一信源和某一码符号集来说,若有一唯一可 译码,其平均码长小于所有其他唯一可译码的平均 长度。