第3章 无失真信源编码.ppt

《第3章 无失真信源编码.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第3章无失真信源编码理解n次扩展信源的渐近均分性理解香农第一定理理解异前置码的渐近最优性掌握香农码的编码掌握费诺码的编码掌握赫夫曼码的编码教学内容和要求3.1渐近均分性定理1、n次扩展信源的渐进均分性例1二次、三次和四次扩展信源的概率分布特点二次扩展信源的概率概率分布特点三次扩展信源的概率概率分布特点四次扩展信源的概率概率分布特点n次扩展信源的符号序列分为两组，n越大，其中一组的概率之和越接近1，概率相差越小——渐进均分性2、渐进均分性定理任意给定ε>0，当n足够大，n次扩展信源的典型序列满足定理当n足够大由大数定理典型序列的自信息等于熵——典

2、型序列等概率不满足该式的符号序列——非典型序列推论1推论23.2香农第一定理定理信源的熵为H(X)，对n次扩展信源进行二进制信源编码，对任意给定的ε>0，只要码率R≥H(X)+ε，当n足够大，编码无失真如果码率R≤H(X)-2ε，无论n多大，编码一定失真正定理当n足够大，n次扩展信源产生等概率的典型序列，其数量设二进制信源编码的码字数量为2nR，只要保证编码无失真——典型序列有一一对应的编码逆定理必然有部分典型序列没有对应的码字有一一对应码字的这些典型序列的编码无失真，其概率之和为译码正确概率1-Pe如果R≤H(X)-2ε译码错误概率香农第一定

3、理表明了n次扩展信源无失真信源编码的存在性，明确了熵H(X)是无失真信源编码码率R的下界——香农界3.3异前置码定义1、信源编码n次扩展信源消息到码字(二进制码元序列)的映射表示二进制离散型随机变量序列C1C2…Cl2、平均码长n次扩展信源各消息码字长度的数学期望，用L表示定义表示二次扩展信源信源编码及平均码长例1某种信源编码平均码长信源的熵码率3、编码效率定义信源的熵与信源编码的码率之比从提高传输效率的角度，码率越接近熵越好表示4、异前置码定义码表中无任何码字是其它码字的前缀异前置码可以用树图构造二进制异前置码00,10,11和0,10,11

4、各自所对应的二叉树图010101010异前置码——任何码字结束时即可译出例2左移1位=0？=10？输出0Y输出1YNN输出2左移2位结束？YN输入码字串结束3.4渐近最优码定理二进制异前置码的码长l1,l2,…,lNn满足不等式反之，给定满足以上不等式的一组码长，存在相应的二进制异前置码1、克拉夫特不等式记二进制异前置码第k个码字的码长为lk考虑一棵lmax级二叉满树，在第lk级共有2lk个节点根据异前置码的定义，对第k个码字，在第lmax级被用掉或不能用的节点数为2lmax-lk构造二进制异前置码的树图第lmax级总共被用掉或不能用的节点总数

5、第2级被用掉或不能用的节点总数为010100101反之，从树根出发由短及长依次按码长lk生长二叉树枝，即可构造出一颗lmax级二叉树，相应得到二进制异前置码定理2、渐近最优码定理信源的熵为H(X)，对n次扩展信源进行二进制异前置码编码，对任意给定的ε>0，当n足够大，码率满足H(X)≤R

6、,2,3,4按概率降序排列②确定第k个码字的码长③令P(x0)=0，计算第k-1个消息的累加概率④将Pa(xk)用二进制表示，取小数点后lk位作为消息xk的码字ckxkP(xk)lkPa(xk)ckx10.5100x20.320.510x30.1530.8110x40.0550.9511110分别对信源和二次扩展信源编香农码并计算编码效率例2(1)信源编码并计算编码效率xkP(xk)lkPa(xk)ck00.510010.320.51020.230.8110(2)二次扩展信源编码并计算编码效率Pa(00)=0.0=(0.00)2→c1=00Pa

7、(01)=0.25=(0.010)2→c2=010Pa(10)=0.4=(0.011…)2→c3=011Pa(02)=0.55=(0.1000…)2→c4=1000Pa(20)=0.65=(0.1010…)2→c5=1010Pa(11)=0.75=(0.1100)2→c6=1100Pa(12)=0.84=(0.11010…)2→c7=11010Pa(21)=0.9=(0.11100…)2→c8=11100Pa(22)=0.96=(0.11101…)2→c9=11101xkP(xk)lkPa(xk)ck000.252000010.1530.250

8、10100.1530.4011020.140.551000200.140.651010110.0940.751100120.0650.84110102