信息论无失真信源编码.ppt

第5章 无失真信源编码n无失真信源编码：解码之后可以得到原始信息，例如霍夫曼编码。它相对简单，是本章的重点。n有失真信源编码：解码之后的信息与原始信息有一定的差别，例如JPEG、MPEG5.1 编码器n信源编码器表示为：n例如：n其中X称为码符号集，X中的元素xi称为码元或者码符号。输出符号Wi称为码字，码字的集合C称为代码组或者码。码字Wi的长度li称为码字长度，简称码长。n要实现无失真编码，编码器的映射必须是一一对应、可逆的。码的分类n根据码长固定长度码（定长码）：所有码字的长度相同。可变长度码（变长码）：码字长短不一。n码字是否相同非奇异码：所有码字都不相同。奇异码：存在相同的码字。5.2 分组码n定义5.2.1 将信源符号集中的每个信源符号si映射成一个固定固定的码字Wi，这样的码称为分组码。n通常在接收端收到的码字之间并没有明显的间隔，表现为W1W2Wq的形式，把这种形式称为q阶扩展码。例如前面的两个例子，ACD编码成为001011/0001111的形式，均为3阶扩展码。n码字之间缺少间隔，给译码造成了一定的困难定长码：不存在困难，001011必定译码成为ACD变长码：存在困难，0001111可以译码成为ACD(0 001 111)，也可以译码成为AABD(0 0 01 111)。ABCD00011011ABCD001001111唯一可译性n定义5.2.4 一个分组码若对于任意有限的整数N，其N阶扩展码均为非奇异的，则称之为唯一可译码。n含义：无论码由多少个码字组成，总是能够正确译码，不存在二义性。即时码n无需知道下一个码字的码符号，即可译码，这样的唯一可译码成为即时码。n命题5.2.1 一个唯一可译码成为即时码的充要条件是其中任何一个码字都不是其他码字的前缀。ABCD1101001000ABCD101001000110110010BACB10110001ABAD5.3 定长码n编码速率：，其中l是码字长度，r是码符号的个数，N代表N次扩展信源。n编码效率：=H(S)/R，其中H(S)是扩展之前信源的熵。n例如：S=A,B,C,等概率出现，N=2,SN=AA,CC，对SN进行二元编码，则r=2，编码方式如下，则l=4。n那么，SN的编码速率为R=(4log2)/2=2，SN的编码效率为=H(S)/R=log3/2=0.7925AAABACBABBBCCACBCC0000000100100100010101101000100110105.4 变长码n匹配编码：根据概率进行编码，概率大的所给的代码短，概率小的所给的代码长。例如哈夫曼编码。n变换编码：将信号从一个空间变换到另一个空间，在新的空间里对信号进行编码。例如JPEG。n识别编码：主要用于印刷或者打字机等有标准形状的符号的编码。5.4.2 两个不等式n定理5.4.1 即时码存在的充要条件是克拉夫特（Kraft）不等式。n定理5.4.2 唯一可译码存在的充要条件是麦克米伦（McMillan）不等式。5.4.3 唯一可译码判别准则n命题5.4.1 一种码是唯一可译码的充要条件是S1,S2,中没有一个含有S0中的码字。S0S1S2S3S4S5S6S7abbcdedebaddebcbcdeabbbaddebbbcde5.4.4 码平均长度n定义5.4.1 设信源 编码后的码字分别为W1W2Wq，各码字相应的码长分别为l1l2lq。对唯一可译码，则这个码的平均长度为n定义5.4.2 对应一给定的信源和一给定的码符号集，若有一种唯一可译码，其平均长度小于所有其他的唯一可译码，则称这种码为紧致码，或最佳码。5.4.5 变长码的编码方法：霍夫曼编码n例5.4.4n定理5.4.6 霍夫曼码是紧致码。s1s2s3s4s5101101001 000