信息论无失真信源编码

1、无失真信源编码：解码之后可以得到原始jlll信息，例如霍夫曼编码。它相对简单，是 本章的重点。有失真信源编码：解码之后的信息与原始jlll信息有一定的差别，例如JPEG、MPEG5.1编码器编码器C=(W1,W2,W几信源编码器表示为:X=(QK2,对例如:S=(ACD) r A B C D C=(OOJOJl)r00,01,10,11rX=(o，l)S=(A，CQ) AB C D C=(0,001,lip* 0,01,001,111X=(0J)其中X称为码符号集，X中的元素“称为码元或者 码符号。输岀符号叱称为码字，植字的集合C称 为代码组或者码。码字比的长度厶称为码字长度, 简称码长。要实

2、现无失真编码，编码器的映射必须是一一对 应、可逆的。码的分类根据码长固定长度码（定长码）：所有码字的长度相同。可变长度码（变长码）：码字长短不一。码字是否相同非奇异码：所有码字都不相同。奇异码：存在相同的码字。5.2分组码象稱蛊轟凋11映射通常在接收端收到的码字之间并没有明显的间隔, 表现为皿叫巴的形式，把这种形式称为g阶扩 展码。例如前面的两个例子，ACD编码成另 001011/0001111的形式，均为3阶扩展码。码字之间缺少间隔，给译码造成了一定的困难 定长码：不存在困难，001011必定译码成为ACD 变长码：存在困难，0001111可以译码成为ACD(0 001 111),也可以译码

3、成为AABD(0 0 01 lll)oABcD00011011ABcD001001111唯一可译性定义524 个分组码若对于任意有限的整 数N,其N阶扩展码均为非奇异的，则称之 为唯一可译码。含义：无论码由多少个码字组成，总是能 够正确译码，不存在二义性。即时码ABCD1101001000ABcD101001000110110 010 BACB10110 0 OlABAD无需知道下一个码字的码符号，即可译码, 这样的唯一可译码成为即时码。命题521 个唯一可译码成为即时码的充 要条件是其中任何一个码字都不是其他码 字的前缀。5.3定长码编码速率:1T，其中/是码字长度，厂是码符号的个数，N代表

4、N次扩展信源。编码效率：rj=H(S)R 其中H(S)是扩展之前信源的爛。例如：S=ABC,等概率出现，N=2，SN=AA,CC,对 SN进行二元编码，则心2,编码方式如下，则上4。AAABACBABBBCCACBcc000000010010010001010110100010011010那么，S的编码速率为R=(41og2)/2=2, S的编码效率为7=H(S)/?=log3/2=0.79255.4变长码匹配编码：根据概率进 行编码，概率大的所给 的代码短，概率小的所 给的代码长。例如哈夫 曼编码。变换编码：将信号从一 个空间变换到另一个空 间，在新的空间里对信 号进行编码。例如JPEG识别

5、编码：主要用于印 刷或奢打字机等有标准 形状的符号的编码。024681012141618205.4.2两个不等式定理5.4.1即时码爭在的充要条件是 茁aZ = 1克拉夫特（Kraft）不等式。定理5.4.2唯一可译码存在的充要条件是qy麦克米伦（McMillanS不等式。5.4.3唯一可译码判别准则S。SiS2S3S4SS6S7a c abb bad deb bbcdebbcdedebadbcdedeb命题541 种码是唯一可译码的充要条件 是S, S”中没有一个含有So中的码字。5.4.4码平均长度;定义5.4.1设信源编码后的码字分别为WW?巴，各码字相应的码 长分别为仏丿 均长度为/八一么0g。对唯一可译桐，则这个码的平 q厶二卩（训i=l定义5.4.2对应一给定的信源和一给定的码符号集，若有一种唯一可译码，其平均长度小于所有 其他的唯一可译码，则称这种码为紧致码，或最 佳码。精品课件V1 r精品课件V1 r5.4.5变长码的编码方法：霍夫曼编码 5.