PDF《欢迎各位同学拷贝！》

000 001

011 110

010 100

101 111 root

0 1

0 1

0 1

0 1

0 1

0 1

0 1 等长码形成一棵 整树 ,所有的叶子在离根 相同距离n的节点生成,共2n 个. 4.Krafft不等式:(唯一可译的必要条件) ?我们用 剪枝 的方式从n阶整树上剪出一个 最大码长不大于n的变长码的码树来. ?若在第1阶分叉处张出一片码长为1的叶子,相 当于整树被剪掉一半,则因此失去2n-1 片叶子. ?若在第2阶分叉处张出一片码长为2的叶子,相 当于整树被剪掉1/4,则因此失去2n-2 片叶子. ?同理,若在第 l 阶分叉的一枝上张出一片码长 为l 的叶子,则因此失去2n-l 片叶子. 设 m个变长码字的码长分别为l1 , l2 , …… ,lm;

它们是从n阶整树上剪出.必须满足: n m i l n i

2 2

1 ≤ ∑ = ? 才能有足够的枝叶可剪.因此:

1 2

1 ≤ ∑ = ? m i li 叫krafft不等式,是唯一可译码满足的必要条 件. 克拉夫特不等式不能判断是不是即时码. A B C D 码Ⅰ

0 10

11 101 码Ⅱ

1 10

100 1000 码Ⅲ

1 01

001 0001 [例] 用krafft不等式判断下表给出的三种编码是 不是唯一可译码. 解:码Ⅰ: 所以码Ⅰ不是唯一可译码.

1 8

9 2

2 2

2 3

2 2

1 >

= + + + ? ? ? ? Q 而码Ⅱ与码Ⅲ: 所以码Ⅱ与码Ⅲ有可能是唯一可译码.

1 16

15 2

2 2

2 4

3 2

1 <

= + + + ? ? ? ? Q 5.概率匹配原则(Principle of match with probability) 平均码长(Average code length): i m i il p l ∑ = =

1 信息传承要求 log(r)应不小于H(X);

并 尽量接近.即要求: ? l

0 ] log ) log( [ ) log ( ) log( ) ( ) log(

1 1

1 → + = ? ? = ? ∑ ∑ ∑ = = = i i m i i i m i i m i i i p r l p p p r l p X H r l 如果求和中的每一项都为零,或者说如果每一个 i 都满足: (i=1,2,……,m ) 求和必然为零.它等价于:

0 ) log( ) log( = + i i p r l ) (

1 log ) log( ) log( i r i r i i a I p r p l = = ? = 此式表明,只要每一码字的长度都等于它所对应 的信源符号的自信息(以r为底),就能使编码最 短.这个原理叫概率匹配原则. 从信息的荷载能力讲,信息量大的符号用长码, 信息量小的符号用短码,是合理的. 自信息小的符号必然概率大,经常出现,采用较 短的码字表示,必能节省代码长度. 自信息大的符号,虽然采用较长的码字表示,但 由于它的概率小,不常出现,从总体上讲,不会明 显影响平均码长. 概率匹配原则的解释 符号 铅字数 Morse码e12000 ? t

9000 - a

8000 ? - i

8000 ? ? n

8000 - ? o

8000 - - s

8000 ? ? ? h

6400 ? ? ? ? r

6200 ? - ? d

4400 - ? ? l

4000 ? - ? ? u

3400 ? ? - c

3000 - ? - ? 符号 铅字数 Morse码m3000 - - - f

2500 ? ? - ? w

2000 ? - - y

2000 - ? - - g

1700 - - ? p

1700 ? - - ? b

1600 - ? ? ? v

1200 ? ? ? - k

800 - ? - q

500 - - ? - j

400 ? - - - x

400 - ? ? - z

200 - - ? ? 1843年莫尔斯根据当地报馆使用铅字的情况编出Morse码6.Shannon变长码编码定理: 单个信源符号的编码: 考虑到码长只能取整数,概率匹配原则可写为: log r(1/pi ) ≤ l i ≤

1 + log r(1/pi ) 对各符号取统计平均,得到:

1 log ) ( log ) ( + ≤ ≤ r X H r X H l 它给出最小平均码长的一个范围. N个信源符号为分组的编码: 把N个信源符号的序列当作一个符号来编码,其码 字平均码长L满足:

1 log ) ( log ) (

2 1

2 1 + ≤ ≤ r X X X H r X X X H N N L L L N r H r H N N l

1 log log + ≤ ≤ 当N→∞时,就有: →(H∞/log r);