资源描述：
《信息论讲义_第十三讲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)
