资源描述:
《信息论讲义_第十三讲new》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、信息理论基础信息理论基础(第十三讲)(第十三讲)授课教师:于泽电子信息工程学院201教研室第五章无失真信源编码内容提要5.1编码器5.2分组码5.3定长编码5.4变长编码5.5变长编码方法—香农(Shannon)编码—霍夫曼(Huffman)编码—费诺(Fano)编码25.4变长码引入1.变长码无需很长的码长就能实现高效率的无失真信源编码2.变长码必须是唯一可译码,才能实现无失真编码3.变长码是唯一可译码的充要条件:(1)非奇异码(2)任意有限次扩展码是非奇异码4.若想即时译码,变长码必须即时码。35.4.1变长信源主要编码方法1、匹配编码:概率大的信源符号,代码长度短;
2、反之,概率小的信源符号,代码长度长。2、变换编码:从一种空间变换成另一种空间,然后进行编码。3、识别编码:对有标准形状的文字、符号和数据进行编码。*在这里仅介绍匹配编码方法。45.4.1变长信源主要编码方法(续)Morse电报字符A·–K–·–U··–1·––––B–···L·–··V···–2··–––C–·–·M––W·––3···––D–··N–·X–··–4····–E·O–––Y–·––5·····F··–·P·––·Z––··6–····G––·Q––·–,––··–7––···H····R·–·.–8–––··I··S····–·–9––––··–J·–––
3、T–0–––––55.4.2Kraft不等式和McMillan不等式设信源符号集为S=(s,s,…,s),码符号集12q,为X=(x,x,…,x),对信源进行编码,代码组12r为C=(w,w,…,w),相应码长分别l,l,…,l,12q12q即时码存在(唯一可译码存在)的充要条件为:q−li∑r≤1i=1克拉夫特证明不等式为即时码存在的充要条件;麦克米伦证明不等式为唯一可译码存在的充要条件。65.4.2Kraft不等式和McMillan不等式(续)用树的概念可导出唯一可译码存在的充分和必要条件,即各码字的长度K应符合Kraft不等式i满树:–每个节点上都有r个分枝的树——
4、等长码非满树:–变长码75.4.2Kraft不等式和McMillan不等式(续)例:设二进制码树中X=(a1,a2,a3,a4),K1不存在满足这种=1,K2=2,K3=2,K4=3,应用Kraft不等式,得:Ki的唯一可译码4−Ki−1−2−2−39∑2=2+2+2+2=〉1i=18如果将各码字长度改成K=1,K=2,K=3,K=3,则12344−Ki−1−2−3−3∑2=2+2+2+2=1i=111011110这样的码字就存0在唯一可译码01101中间节点0185.4.2Kraft不等式和McMillan不等式(续)¾Kraft不等式是惟一可译码存在的充要条件,其必要
5、性表现在如果码是惟一可译码,则必定满足Kraft不等式;充分性表现在如果满足Kraft不等式,则这种码长的惟一可译码一定存在,但并不表示所有满足Kraft不等式的码一定是惟一可译码。¾因此,克拉夫特不等式是惟一可译码存在的充要条件,而不是惟一可译码的充要条件。¾如码字{0,10,010,111},{1,01,001,0001}95.4.3唯一可译码判别准则1、由原始码集合S,构造集合S,S,…012①S的构造:1若wi∈S0,wj∈S0,且wi=wjA,则后缀A放入S1中,S由所有这样的A构成。1②S(n>1)的构造:将S和S进行比较n0n-1若,W∈S,U∈S且W=UA
6、,则A放入S中,0n−1n若,W'∈Sn−1,U'∈S0且W'=U'A',则A’放入Sn中,S由所有这样的A和A’构成。n105.4.3唯一可译码判别准则(续)2、定理:码集合S是唯一可译码的充要条件是S,S,…012中没有一个含有S的元素。0例如:S={a,c,abb,bad,deb,bbcde}是否唯一可译码0SSSSSSSSS012345678abbcdedebaddebΦcbcdeabbbaddebbbcde115.4.3唯一可译码判别准则(续)例如:S={a,c,ad,abb,bad,deb,bbcde}是否唯一可译码0125.4.4变长信源编码定理1.码平均长
7、度⎡⎤ss?s12q离散无记忆信源为[]SP=⎢⎥p()()sps?p()s⎣⎦12q编码后的码字WW,,,?W12ql,l,?,l码字的长度12q因为是唯一可译码,s和W一一对应iips()=pW()iiqq则码字平均长度为L==∑∑pWl()iipsl()iiii==11135.4.4变长信源编码定理(续)释:(1)l是第i个码字的长度,必须是整数;i(2)是变长编码后,一个信源符号平均所需要的码元个数,可以是L小数;(3)编码后,每个信源符号s平均用L个码符号来表示,平均每个码符号i携带的信息量是信道的信息传输率H(s)