第五章 信源编码郭里婷

《第五章 信源编码郭里婷》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《信息论与编码》第五章信源编码定理和方法福州大学物理与信息工程学院郭里婷2012-11-5物理与信息工程学院郭里婷1第1节编码的作用和分类一、信源编码的作用1．符号变换2．减小冗余2012-11-5物理与信息工程学院郭里婷2第1节编码的作用和分类二、信息论的主要内容1．无失真编码定理：第一极限定理2．限失真编码定理：第三极限定理3．信道编码定理：第二极限定理2012-11-5物理与信息工程学院郭里婷3第1节编码的作用和分类三、编码的定义和类型（一）编码的模型和定义XYji信源信源编码器信道码表⎧⎪分组码：信源序列，按照一个固

2、定的码表，映射成码字XYij码⎨⎪⎩非分组码：没有码表2012-11-5物理与信息工程学院郭里婷4第1节编码的作用和分类信源序列XiL=∈(,,,)XX12??XX,l{aa12,,,an}信源符号:Xl编码序列(码字)Y=∈(,,,),YY??YY{}bb,,,bjK12Lkm12码集(码)：YYYY={,,,}12?Ln码元:bj码长：K（码元/序列）。Li()⎧⎪定长码：K相同Li()⎨⎪⎩变长码：KLi()不全相同⎧定长码：KKK==⎪LL()iL平均码长：（码元/序列）。KL⎨⎪变长码：KL=∑pK()XiL()i

3、⎩i每个符号的平均码长：（码元/符号）。KK′′=K/LLLL2012-11-5物理与信息工程学院郭里婷5第1节编码的作用和分类例1：XAlk∈∈{},,,,BCDY{0,1}⎧⎧LL==1,定长码1，变长码⎪⎪XY==(),AA(00);XY==(),(0);⎪⎪1111⎪⎪⎨⎨XY==(),BB(01);XY==(),(01);2222⎪⎪XY==(),CC(10);XY==(),(10);⎪⎪3333⎪⎪⎩⎩XY==(),DD(11);XY==(),(111);4444⎧L=2,定长码⎪XYX===(AA),(0000

4、);(AD),Y=(0110);⎪1144⎪⎨XYXY====(AB),(0010);(BA),(0001);2255⎪XYXY====(AC),(0100);(BB),(0011);⎪3366⎪⎩??2012-11-5物理与信息工程学院郭里婷6第1节编码的作用和分类三、编码的定义和类型（二）编码类型1．非奇异码和奇异码信源各符号码1码2码3码4符号概率u1/200111u1/4111010012u1/801001000013u1/811011000000142012-11-5物理与信息工程学院郭里婷7第1节编码的作用和分类

5、2．惟一可译码和非惟一可译码惟一可译码：任意有限长的码元序列，能被唯一地分割成一个个的码字；反之为非惟一可译码例2：码字集合码()0,10,00,01{}码字集合码()01011{}，，2012-11-5物理与信息工程学院郭里婷8第1节编码的作用和分类惟一可译码存在的充要条件：n−Ki各码字的长度为KKi,1满足raft不等式：∑m≤i=1∗注意：Kraft不等式不是判断是否是惟一可译码的充要条件例：判断是否存在码长分别为31KKKK====,2,2,3的二进制惟一可译码。1234解：依题意，m=244−−KKii−−−−1

6、2239又因为∑∑mK==22222+++=>1,不满足raft不等式，ii==118所以不存在符合上述要求的惟一可译码。2012-11-5物理与信息工程学院郭里婷9第1节编码的作用和分类例4：判断是否存在码长分别为KKKK====1,2,3,3的二进制惟一可译码。1234解：依题意，m=244−−KKii−−−−1233又因为∑∑mK==222221+++=,满足raft不等式，ii==11所以存在符合上述要求的惟一可译码。如{0,10,110,111}，但不{0,10,010,100}是2012-11-5物理与信息工程学

7、院郭里婷10第1节编码的作用和分类3．即时码和非即时码即时码（非延长码）：当收到一个完整的码字后，可以立即译码；反之为非即时码例5：如码，，，{}1010010001,如码，，，{}1101001000,！即时码是惟一可译码2012-11-5物理与信息工程学院郭里婷11第1节编码的作用和分类三、编码的定义和类型（三）码分类小结码非分组码分组码奇异码非奇异码惟一可译码非惟一可译码即时码非即时码2012-11-5物理与信息工程学院郭里婷12第1节编码的作用和分类三、编码的定义和类型（四）码树码树：树根、树枝、节点2012-11-

8、5物理与信息工程学院郭里婷13第1节编码的作用和分类000001012012-11-5物理与信息工程学院郭里婷14第1节编码的作用和分类即时码在码树中的特性：若某节点做为码字，则该节点不再延伸2012-11-5物理与信息工程学院郭里婷15第1节编码的作用和分类三、编码的定义和类型（五）各种