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

P(G) <

1 由此便知:M <

2 N(HN +ε) M占总序列数的比率: ) (log log ) (

2 2

2 ε ε ξ ? ? ? + = = = N N N H m N m H N N m M 一般总有log m =H0>

HN ,使[log m-HN Cε]为正 数, 故当N →∞时:

2 - N[log m-HN -ε] →0 表明典型序列虽然经常出现,但占总序列数目的比 率却很小,并且随着序列变长,比率越来越小. (5)定长码编码定理的得出: ?若码长L取得足够大,使:r L ≥

2 N(HN +ε) >

M, 则所有的典型序列都有唯一的码字可对应. 此时 L?log r ≥ N(HN+ ε);

即: r H N L l N log ε + ≥ = ?反之,若码长L取得不够大,使rL≤2N(HN - 2ε) 即L?log r ≤ N(HN -2ε);

或: 这时就会有一部分典型序列没有码字可对应. r H N L l N log 2ε ? ≤ = ?设有码字可对应的典型序列集合为g,它们应当 是典型序列G的一部分.g出现的概率为: P(g) ≤ rL ・ max[P(s)]≤

2 N(HN -2ε) ・

2 -N(HN -ε) =2 -N ε ?则当N →∞时: P(g) →0 ?于是,无码字对应的典型序列的概率P(G-g)→1 ?表明这种情况下,错误必然存在,不可能是无失 真编码. ?定理得到证明. 3.等长码可行性讨论 这个令人鼓舞的理论结果可行性如何呢? 香农定理给出任意小的错误概率PE满足:

2 )] ( [ ε δ N I D PE x = ≤ 这里任意小量ε来自实际编码码长 l =(HN+ε)/log r 与理论极限码长 l0=HN /log r的接近程度;

这里D[I(X) ]=E[I2(X)]-{E[I(X)]}2是自信息I(X)的方差;

若指定了所要求的错误概率和编码效率η= l0 /l ,由 以上关系式能够求出相应的N值. 不妨以一个实例来讨论: 设:无记忆二元信源概率为: p={3/4,1/4}, 可求出HN =H(X)= (3/4)log(4/3)+(1/4)log4=0.811, D[I(X)]=3/4(log4/3)2+1/4(log4)2-0.8112 =0.4715, 若要求 PE≤ δ=10-5且η= l0 / l =0.96, 则:

7 2

10 13 .

4 )] ( [ ;

0338 .

0 1 * = ≤ = ? = δ ε η η ε X I D N HN 此例表明,定长码定理所讲的 只要N足够大 , 真是太大了,将信源序列以这样大的分组来编码, 显然是无法办到的. 结论:定长码编码不可行. 2.1.4 变长码编码原理 1.唯一可译性: 首先要解决 断字 问题.如何将连在一起的 编码按原来的分组拆分开呢? 例如,当信宿收到的码流为10101011时,按 照表中给出的三种编码各应如何翻译呢? A B C D 码Ⅰ

0 10

11 101 码Ⅱ

1 10

100 1000 码Ⅲ

1 01

001 0001 翻译结果 BBBC,DABC,BDAC BBBAA ABBBA 按码Ⅰ编码,译为 BBBC , DABC 还是 BDAC 都对!译码失去唯一性. 按码Ⅱ编码,唯一地只能译为BBBAA.码Ⅱ的特 点是1打头,凡是见到1就是新码字头. 按码Ⅲ编码,唯一地只能译为ABBBA.码Ⅲ的特 点是1结尾,凡是见到1就是码字尾. 码Ⅱ与码Ⅲ都是唯一可译码. 码Ⅰ不能唯一可译. 2.即时性: ?码Ⅲ在码字一结束就能进行翻译,而码Ⅱ必须等收到下 一个码字开头时才能进行翻译.因此码Ⅲ是即时码,码Ⅱ 是非即时码. ?即时码在结构上有两个典型特征: (1)异前缀性:任一码字都不会是另一码字的前缀.因 此不会出现一个码字没收完却被判为其它码字的情况. (2)非延长性:任一码字都不会是另一码字的延长.因 此不会出现一个码字已收完却还需要等待其它码字的情 况. ?我们希望的变长码应当是唯一可译的即时码.

0 1

0 1

0 1

0 1

1100 1101

01 10

111 00

0 1 root 3.码树: ?码树是设计唯一可译即时码的一个好办法. 码树的构造方法: ?二元码应分布在一棵二叉树上.每枝分两叉, 每个分叉的左右两枝分别标记为0与1. ?生了叶的枝便不再分叉 ――非延长性. ?从根到叶的路径只能有唯一的一条,这条路径 就给出了树叶所代表的码字 ――异前缀性. ?只要改变每个结点处分叉的个数,就能推广到多元码 树.