第9讲——最佳不等长编码
- 格式：pdf
- 大小：1.13 MB
- 文档页数：36
0.20 0.19 0.18 0.17 0.15 0.10 0.01
2.34 2.41 2.48
0.39
0.57 0.17 0.89 0.99
2.56
2.74 3.34
3
3 4
0.1011
0.1110 0.1111110
6.66
7
信源符号 s1 s2 s3 s4 s5
码字 000 001
lK最大 存在另外一个码字其长度也为lK， 并且与cK仅最后一位码元取值不 同(一个为0，另一个为1) s1, s2,…,sK-1, sK p1,p2,…,pK-1, pK c1, c2,…,cK-1, cK
满足 的码字为cK－1
l1, l2,…,lK-1, lK
反证法
唯一可译码 (最佳) 异字头码 (最佳)
1
s4
s5 s6
0.17
0.15 0.10
10
110 1110
s7
0.01
1111
0 0 1
0 1
s1 s2
0 1
0
s1
0 1
1
0 1
s2 （P2=0.19） 4 s3
1 0 1
1
s3 s4
0
0 1
s5
1
s6
1 1
s2 （ 4 4 P4=0.17） s5 1s7
Shannon码
s1, s2, … sk …., sK p1, p2,… pk ….,pK pk >pK c1, c2, … ck …., cK l1, l2, … lk …., lK
c1, c2, …, cK, …., ck
l1, l2, …, lK, …., lk
' p l p l p l L 11 k k K K L p1l1 pk l K pK lk
2
12 21
22 200 201
0.06
0.05 0 0.04 1 2 0
思考: r元Huffman编码？
q (r 1) r
?
Y
进行编码
N
增加0概率 符号
进行编码
Huffman编码实际应用中的问题
例： 设离散无记忆信源
S s1 , s2 , s3 , s4 , s5 P( S ) 0.4 0.2 0.2 0.1 0.1
0 1 0
0 1
s1 s2
1
0 1
1 0 1
1
011
100 101 1110 1111110
s3 s4
0
s5
1
s6
s6 s7
s1 7
1
0
s7
1 当满足nk log k 时最佳 pk
Fano编码
信源 符号 s1 s2 s3 概率 第一次 第二次 pk 分组 分组 0.20 0.19 0.18 0 0 0 1 1 0 1 0 1 1 0 1 0 0 第三次 分组 第四次 码字 分组 00 010 011
试对其进行二元Huffman编码。
编法一
码字 S p(sk) 1 01 s1 0.4 s2 0.2 0 0.4 0 1
0.6 0
1
编法二
1 码字S p(sk) 00 s1 0.4 10 s2 0.2 11 s3 0.2 010 s4 0.1 0 011 s 0.11
5
0.6 0.4 0 0.2 1 0 1
0.15
0.10 0 1 0.11 0.01 1
信源符号 s1 s2 s3 s4 s5 s6 s7
码字
10
11 000 001 010 0110 0111
0 1 0 1
0 1 1
s3
s4 0 s5
0 1
s6 s7
0 s1 1
s2
编码效率比较
编码方式
Shannon编码 Fano编码
平均码长 n
3.14 2.74
Pi pk i 1
P 1 0
k 1
Shannon编码
例1： 设离散无记忆信源
s2 s3 s4 s5 s6 s7 S s1 p 0.20 0.19 0.18 0.17 0.15 0.10 0.01 i
试对其进行二元Shannon编码。
Shannon编码
lK最大 存在另外一个码字其长度也为lK，
并且与cK仅最后一位码元取值不 同(一个为0，另一个为1) 满足 的码字为cK－1
s1, s2,…,sK-1, sK p1,p2,…,pK-1, pK
c1, c2,…,cK-1, cK l1, l2,…,lK-1, lK
回顾Huffman 编码过程 如果 对缩减信源 为最佳码，则 对原始信源也 是最佳码。
0 1 1
000 s3 0.2
0010 s4 0.1 0 1 0.2 0011 s 0.1 1
5
0.2
平均码长
编法一：
S p(sk) 编法一编法二 1 00
s1 0.4 5 n1 p(sk )nk 0.4 1 0.2 2 0.2 3 0.1 4 2 2.2 s2 0.2 k 1 s3 0.2 编码效率相同 编法二： s4 0.1 5 n2 p(sk )nk 0.4 2 0.2 2 2 0.1 3 2 2.2 s 5 0.1
1 信源 概率pk log 符号 pk
码长nk 3 3 3
累加 累加概率对应 概率 的二进制数 0 0.20 0.000 000 0.0011 001 0.0110 0.1001
码字 000 001
011 100 101 1110 1111110
s1 s2 s3 s4 s5 s6 s7
Fano码
Fano编码
信源 符号 s1 s2 s3 s4 概率 第一次 第二次 pk 分组 分组 0.20 0.19 0 0 1 0 1 0 1
nk
第三次 分组
第四次 码字 分组 00
0 1
010 011
0.18
0.17 0.15 0.10 0.01
10 110
0 1110 1111
s5
s6 s7
假设不成立
0 1 1 0 1 1 0 1 1
存在另外一个码字其长度也为lK， 并且与cK仅最后一位码元取值不 同(一个为0，另一个为1)
0 1
s1 s2 s3 s4
0
0
s5
1
s6 s1 7 s7
Huffman编码最佳性证明
【定理1】
对于给定的信源，存在最佳唯一可译二元码，其最 小概率的两个码字的长度最长且相等，它们之间仅最后 一位码元取值不同（一个为0，另一个为1）。
编码效率
0.831 0.953
Huffman编码
2.72
0.96
是否最佳？
Huffman编码最佳性证明
【定理1】 对于给定的信源，存在最佳唯一可译二元码， 其最小概率的两个码字的长度最长且相等，它们 之间仅最后一位码元取值不同（一个为0，另一 个为1）。
lK K最大 存在另外一个码字其长度也为lK， s1, s2,…,sK-1, sK p1,p2,…,pK-1, pK
第九讲 最佳不等长编码
Review
不等长编码定理
若一离散无记忆信源的熵为 H(U),每个信源符 号用 D 进制码元进行不等长编码 , 则一定存在 一种无失真编码方法 ,构成唯一可译码，其平 均码长满足
H (U ) H (U ) n 1 log D log D
Review
不等长编码定理
对于平均符号熵为HL(U)的离散平稳无记忆信
并且与cK仅最后一位码元取值不 p p p p 1 2 K 1 K 同(一个为0，另一个为1) c1, c2,…,cK-1, cK 满足 的码字为cK－1 l1, l2,…,lK-1, lK
假设
lk >lK
反证法
s1, s2, …, sk ,…., sK p1, p2,…, pk ,….,pK
'' K 2 2 K '' K K 1 1
' ' ' ' c c2 pKc pK 1 2 K 2 1 ' ' ' ' pK p 1pK 1 l l l 1 11 2 K K
【定理2】
对缩减信源为最佳码，则对原始信源也是最佳码。
Huffman编码最佳
思考: 试对下述离散无记忆信源S进行三元
1
1
当满足 pk 2
k 时最佳
Huffman编码
信源 概率p k 符号 s1 s2 s3 s4 0.20 0.19 0.18 0.17 0 0.26 0.35 0.26 0 0.39 0 1 0.61 0 1 1.00
码字 10
11 000 001 010 0110 0111
1 0
1
s5
s6 s7
0 0.60 1 2 0 1 2 1.00
最佳?
【提示】 增加1个概率为0的信源符号
思考: r元Huffman编码？
信源符号 概率pk s1 0.40 s2 s3 0.18 0.10 0.10 0.07 0.22 0 0 0.38 1 2 码字 0 1.00
10
11
1 0.09
0 1 2
s4
s5 s6 s7 s8 s9
pk lK pK lk ( pk lk pK lK ) ( pk pK )(lK lk ) 0
L L
'
矛盾
Huffman编码最佳性证明
【定理1】 对于给定的信源，存在最佳唯一可译二元码， 其最小概率的两个码字的长度最长且相等，它们 之间仅最后一位码元取值不同（一个为0，另一 个为1）。
