文档介绍：信息论与编码第5章信源编码
香农编码
费诺编码
哈夫曼编码
游程编码
香农编码
设离散无记忆信源为
⎡ X ⎤⎧ x1,L, xn ⎫
⎢⎥= ⎨⎬
⎣P(X )⎦⎩ p(x1),L, p(xn )⎭
则二进制香农编码步骤为 P169
(1)排序:
p(x1) ≥ p(x2 ) ≥ L ≥ p(xn )
(2)计算第i个码字的累加概率:
香农编码
j−1
pa (x j ) = ∑ p(xi ), j = i +1, j =1,2,L,n
i=0
p(x0 ) = 0
(3)确定第i个码字长度 ki
− log2 p(xi ) ≤ ki < −log2 p(xi ) +1
香农编码
(4)将 pa (x j ) 表示成二进制数,并取小数点
后 ki位即为该消息符号的二进制码字。
可以证明,这样得到的编码一定是唯一可译
码,且码长比较短,接近于最佳编码。
香农编码
例题:设信源共有信源消息符号 xi 符号概率 p(xi )
7个符号组成,其 x1
概率如表所示, x2
求其香农码。 x3
x4
x5
x6
x7
香农编码
符号概率累加概率码字长度
xi −log2 p(xi ) 码字
p (x )
p(xi ) a j
ki
x1 0 3 000
x2 3 001
x3 3 011
x4 3 100
x5 3 101
x6 4 1110
x
7 7 1111110
香农编码
以为i = 4 例,
− log 2 ≤ k 4 < − log 2 + 1
≤ k 4 < ,因此 k 4 = 3
累加概率 Pi = 0 .57,变成二进制数,为
…,
Pi
转换的方法是:用乘以2,如果整数部分有进
位,则小数点后第一位为1,否则为0,将其小
数部分再做同样的处理,得到小数点后的第二
位,依此类推,直到得到了满足要求的位数,
或者没有小数部分了为止。
香农编码
例如现在 Pi = 0 .57,,整数部分有
进位,所以小数点后第一位为1,将小数部分即
,,没有整数进位,所以
小数点后第二位为0,依此类推,可得到其对应
…。
可以看出,编码所得的码字,没有相同的,平均
码长为: 7
码元符号
K = ∑ p(xi )ki = /
i=1
香农编码
信息率为 K
R = log m = ,此时L =1,m = 2
L 2
编码效率为
H(X )
η= = = %
R
香农编码的效率不高,实用意义不大,但对其它
编码方法有很好的理论指导意义。
费诺编码
费诺(Fano)编码也不是最佳编码方法,但有时可以得到
最佳编码。
费诺编码步骤: P170
(1)排序:
p(x1) ≥ p(x2 ) ≥ L ≥ p(xn )
(2)“一分为二”,使每一组的概率之和相等或接近。
(3)每组分配一个码元,如二元码符号“0”或者“1”。