[理学]第5章信源编码.ppt

1,第5章 信源编码,由于信源符号之间存在分布不均匀和相关性，使得信源存在冗余度，信源编码的主要任务就是减少冗余，提高编码效率。,2,第5章 信源编码,编码分为信源编码和信道编码，其中信源编码又分为无失真和限失真。 一般称 无失真信源编码定理为第一极限定理； 信道编码定理（包括离散和连续信道）称为第 二极限定理； 限失真信源编码定理称为第三极限定理。,3,第5章 信源编码,信源编码的基本途径有两个： 使序列中的各个符号尽可能地互相独立，即解除相关性； 使编码中各个符号出现的概率尽可能地相等，即概率均匀化。,4,第5章 信源编码,信源编码的基础是信息论中的两个编码定理： 无失真编码定理 限失真编码定理 无失真编码只适用于离散信源 对于连续信源，只能在失真受限制的情况下进行限失真编码,5,第5章 信源编码,本章讨论离散信源编码，首先从无失真编码定理出发，重点讨论以香农码、费诺码和霍夫曼码为代表的最佳无失真码。然后介绍了限失真编码定理。最后简单介绍了一些其它常用的信源编码方法。,6,5.1 编码的定义,信源编码是指信源输出符号经信源编码器编码后转换成另外的压缩符号 无失真信源编码：可精确无失真地复制信源输出地消息,7,5.1 编码的定义,将信源消息分成若干组，即符号序列xi， xi(xi1xi2xilxiL)， xilA=a1，a2，ai，an 每个符号序列xi依照固定码表映射成一个码字yi， yi(yi1yi2yilyiL)， yilB=b1，b2，bi，bm 这样的码称为分组码，有时也叫块码。只有分组码才有对应的码表，而非分组码中则不存在码表。,8,5.1 编码的定义,如果信源输出符号序列长度L1，信源符号集A(a1，a2，an) 信源概率空间为,若将信源X通过二元信道传输，就必须把信源符号ai变换成由0，1符号组成的码符号序列，这个过程就是信源编码,9,编码器输入：信源符号M=m1,m2,mn,码符号（码元）：符号集A=a1,a2,ar，一般元素ai是适合信道传输的；,这种码符号序列Ci称为码字，其长度li称为码字长度（码长），所有这些码字的集合C称为码。,10,5.1 编码的定义,码可分为两类： 一、固定长度的码，码中所有码字的长度 都相同，如表5-1中的码1就是定长码 二、可变长度码，码中的码字长短不一，如表中码2就是变长码。,11,5.1 编码的定义,（1）奇异码和非奇异码 若信源符号和码字是一一对应的，则该码为非奇异码。反之为奇异码。,12,5.1 编码的定义,表5-2 码的不同属性,13,5.1 编码的定义,（2）唯一可译码 任意有限长的码元序列，只能被唯一地分割成一个个的码字，便称为唯一可译码,14,例:W1=(1,01,00) ,如码字序列10001101 只可唯一划分为1,00,01,1,01; 反之,W2=(0,10,01) 如序列01001可划分为 0,10,01或01,0,01.,15,5.1 编码的定义,唯一可译码中又分为非即时码和即时码：如果接收端收到一个完整的码字后，不能立即译码，还需等下一个码字开始接收后才能判断是否可以译码，这样的码叫做非即时码。,16,5.1 编码的定义,即时码：只要收到符号就表示该码字已完整，可以立即译码。 即时码又称为非延长码，任意一个码字都不是其它码字的前缀部分，有时叫做异前缀码。,17,非即时码和即时码,18,5.1 编码的定义,19,5.1 编码的定义-码树,通常可用码树来表示各码字的构成,二进制码树,20,码树,0 1 2,0 1 2 0 1 2 0 1 2,0 1 2,0 1 2,三进制码树,21,5.1 编码的定义-克劳夫特不等式,唯一可译码存在的充分和必要条件 各码字的长度Ki 应符合克劳夫特不等式：,22,唯一可译码的判断法 首先观察是否是非奇异码.若是奇异码,肯定不是唯一可译码; 其次,计算是否满足Kraft不等式.若不满足一定不是唯一可译码;然后将码画成一棵树图,观察是否满足异前置码的树图的构造,若满足则是唯一可译码.,23,5.1 编码的定义,例：设二进制码树中X (a1， a2 ， a3 ， a4 )，K11，K22，K32，K43，应用上述判断定理：,因此不存在满足这种Ki的唯一可译码。,24,5.1 编码的定义,1，01，001，000 惟一可译码； 1，01，101，000 不是惟一可译码； 均满足克劳夫特不等式,25,5.1 编码的定义,克劳夫特不等式只是用来说明唯一可译码是否存在，并不能作为唯一可译码的判据。,26,A.A.Sardinas和G.W.Patterson算法步骤 计算分组码中所有可能的尾随后缀集合A,观察A中有没有包含任一码字，若无则为唯一可译码；若有则一定不是唯一可译码。 集合A的构造： 首先观察码C中最短的码字是否是其它码字的前缀。若是，将其所有可能的尾随后缀排列出。而这些尾随后缀又可能是某些码字的前缀，再将由这些尾随后缀产生的新的尾随后缀列出。 然后再观察这些新的尾随后缀是否是某些码字的前缀，再将产生的尾随后缀列出。这样，首先获得由最短的码字能引起的所有尾随后缀。 接着，按照上述将次短的码字等等，所有码字可能产生的尾随后缀全部列出。由此得到码C的所有可能的尾随后缀组成的集合A。,27,例：现设C=0，10，1100，1110，1011，1101，来判断是否是惟一可译码。 解法一（根据异前置码是惟一可译码）： 首先码字C是非奇异码，又由题知，信源符号数为q=6，输出信源的码符号数为r=2，根据kraft不等式得， 满足kraft不等式。 最后画出树图，如下图所示。又图知，该码是非异前置码，所以还无法判断是否是惟一可译码。,28,解法二（根据A.A.Sardinas和G.W.Patterson算法）：因为最短码字为“0”，不是其他码字的前缀，所以它没有尾随后缀。观察码字“10”，它是码字“1011”的前缀，所以有 尾随后缀。根据下图可得，A=11，00，10，01，0，1，100，110，011，101。可见，A集中“10”和“0”都是码字，故码C不是惟一可译码。,29,5.2 无失真信源编码,信源输出 X(X1X2XlXL)， Xla1，a2，ai，an 编码为 Y(Y1Y2Yk YkL)， Ykb1，b2，bj，bm。 要求能够无失真或无差错地译码，同时传送Y时所需要的信息率最小,30,5.2 无失真信源编码,Yk平均每个符号的最大信息量为log m KL长码字的最大信息量为KLlog m 则传送一个信源符号需要的信息率平均为,31,5.2 无失真信源编码,所谓信息率最小，就是找到一种编码方式使 最小。 无失真信源编码定理研究的内容: 最小信息率为多少时，才能得到无失真的译码？若小于这个信息率是否还能无失真地译码,32,5.2 无失真信源编码,无失真的信源编码定理 定长编码定理 变长编码定理,定长编码定理 K是定值 且惟一可译码,33,5.2 无失真信源编码,由L个符号组成的、每个符号的熵为HL(X)的无记忆平稳信源符号序列X1X2XlXL，可用KL个符号Y1，Y2，Yk，（每个符号有m种可能值）进行定长编码。对任意0，0，只要 则当L足够大时，必可使译码差错小于； 反之，当 时，译码差错一 定是有限值，而L足够大时，译码几乎必定出错,34,5.2 无失真信源编码,定长编码定理说明，,码字所能携带的信息量大于信源序列输出的信息量，则可以使传输几乎无失真，条件是L足够大。,35,5.2 无失真信源编码,反之，当 时，不可能构成无失真的编码，使收端译码时差错概率趋于零。 时，则为临界状态，可能无失真，也可能有失真。,36,5.2 无失真信源编码,信源有八种等概率符号，L=1 H（X）=3bit 设离散无记忆信源概率空间为 比特/符号,37,5.2 无失真信源编码,式中 为自信息方差。当 和 均为定值时，只要L足够大，Pe可以小于任一正数。即，,38,5.2 无失真信源编码,当信源序列长度L满足 时， 式中 为自信息方差, 为一正数,39,5.2 无失真信源编码,在连续信源的情况下，由于信源的信息量趋于无限，显然不能用离散符号序列Y来完成无失真编码，而只能进行限失真编码。,40,5.2 无失真信源编码-编码效率,定义 为编码效率，即信源的平均符号熵为H(X)，采用平均符号码长为 来编码，所得的效率。 编码效率总是小于1，且最佳编码效率为,41,5.2 无失真信源编码,编码定理从理论上阐明了编码效率接近1的理想编码器的存在性，它使输出符号的信息率与信源熵之比接近于1，即 L取无限长,42,5.2 无失真信源编码,例 设离散无记忆信源概率空间为 比特/符号,43,5.2 无失真信源编码,对信源符号采用定长二元编码，要求编码效率为 90，若取L1，则可算出 2.55 90%=2.8比特/符号,44,5.2 无失真信源编码,若要求译码错误概率,45,5.2 无失真信源编码,变长编码定理 在变长编码中，码长K是变化的 根据信源各个符号的统计特性，如概率大的符号用短码，概率小的用较长的码，使得编码后平均码长降低，从而提高编码效率。（统计匹配）,46,5.2 无失真信源编码,单个符号变长编码定理：若离散无记忆信源的符号熵为H(X)，每个信源符号用m进制码元进行变长编码，一定存在一种无失真编码方法，其码字平均长度满足下列不等式,47,5.2 无失真信源编码,离散平稳无记忆序列变长编码定理：对于平均符号熵为HL(X)的离散平稳无记忆信源，必存在一种无失真编码方法，使平均信息率满足不等式 其中为任意小正数。,48,5.2 无失真信源编码,用变长编码来达到相当高的编码效率，一般所要求的符号长度L可以比定长编码小得多。,49,5.2 无失真信源编码,编码效率总是小于1，可以用它来衡量各种编码方法的优劣。 为了衡量各种编码方法与最佳码的差距，定义码的剩余度为,50,5.2 无失真信源编码,例 设离散无记忆信源的概率空间为,51,5.2 无失真信源编码,若用二元定长编码(0，1)来构造一个即时码： 。 平均码长 1二元码符号/信源符号,52,5.2 无失真信源编码,编码效率为,输出的信息效率为 R0.811比特/二元码符号,53,5.2 无失真信源编码,长度为2的信源序列进行变长编码（编码方法后面介绍），其即时码如下表,54,5.2 无失真信源编码,二元码符号/信源序列,二元码符号/信源符号,55,5.2 无失真信源编码,编码效率,信息效率 R20.961比特/二元码符号,56,5.2 无失真信源编码,L3 R30.985比特/二元码符号 L4 R40.991比特/二元码符号,57,5.2 无失真信源编码,定长二元码编码，要求编码效率达到96时，允许译码错误概率,58,5.2 无失真信源编码,最佳变长编码 凡是能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字集合称为最佳变长码。,59,5.2 无失真信源编码,能获得最佳码的编码方法主要有： 香农（Shannon） 费诺（Fano） 哈夫曼（Huffman）等,60,5.2 无失真信源编码,香农（Shannon）编码 将信源消息符号按其出现的概率大小依次排列 确定满足下列不等式的整数码长Ki。,61,5.2 无失真信源编码,为了编成唯一可译码，计算第i个消息的累加概率 将累加概率Pi变换成二进制数。 取Pi二进数的小数点后Ki位即为该消息符号的二进制码字。,62,63,5.2 无失真信源编码,例 设信源共7个符号消息，其概率和累加概率如下表所示。,64,5.2 无失真信源编码,码元/符号,比特/码元,65,5.2 无失真信源编码,费诺编码方法 费诺编码属于概率匹配编码 (1)将信源消息符号按其出现的概率大小依次排列： 。 (2)将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近于相同，并对各组赋予一个二进制码元“0”和“1”。,66,5.2 无失真信源编码,(3)将每一大组的信源符号进一步再分成两组，使划分后的两个组的概率之和近于相同，并又赋予两个组一个二进制符号“0”和“1”。 (4)如此重复，直至每个组只剩下一个信源符号为止。 (5)信源符号所对应的码字即为费诺码。,67,5.2 无失真信源编码,例 对以下信源进行费诺编码。,68,5.2 无失真信源编码,码元/符号,bit/符号,69,5.2 无失真信源编码,哈夫曼编码方法 (1)将信源消息符号按其出现的概率大小依次排列， (2)取两个概率最小的字母分别配以0和1两个码元，并将这两个概率相加作为一个新字母的概率，与未分配的二进符号的字母重新排队。,70,5.2 无失真信源编码,(3)对重排后的两个概率最小符号重复步骤(2)的过程。 (4)不断继续上述过程，直到最后两个符号配以0和1为止。 (5)从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。,71,5.2 无失真信源编码,例 对以下信源进行哈夫曼编码,72,X1 0.20 x2 0.19 x3 0.18 x4 0.17 x5 0.15 x6 0.10 x7 0.01,S,S1,S2,S3,S4,S5,11 10 011 010 001 0001 0000,73,5.2 无失真信源编码,0.20 0.20 0.26 0.35 0.39 0.61 1.0 0.19 0.19 0.20 0.26 0.35 0.39 0.18 0.18 0.19 0.20 0.26 0.17 0.17 0.18 0.19 0.15 0.15 0.17 0.10 0.11 0.01,74,5.2 无失真信源编码,码元/符号,bit/符号,75,5.2 无失真信源编码,哈夫曼编码方法得到的码并非唯一的 每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和1是可以任意的，所以可以得到不同的哈夫曼码，但不会影响码字的长度。,76,5.2 无失真信源编码,对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将合并的概率放在上面，这样可获得较小的码方差。,77,5.2 无失真信源编码,例 设有离散无记忆信源,78,5.2 无失真信源编码,79,5.2 无失真信源编码,0.4 0.4 0.4 0.6 1.0 0.2 0.2 0.4 0.4 0.2 0.2 0.2 0.1 0.2 0.1,0.4 0.4 0.4 0.6 1.0 0.2 0.2 0.4 0.4 0.2 0.2 0.2 0.1 0.2 0.1,80,5.2 无失真信源编码,码元/符号,81,5.2 无失真信源编码,进行哈夫曼编码时，为得到码方差最小的码，应使合并的信源符号位于缩减信源序列尽可能高的位置上，以减少再次合并的次数，充分利用短码。,82,5.2 无失真信源编码,83,5.2 无失真信源编码,哈夫曼码是用概率匹配方法进行信源编码。 哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码； 缩减信源的最后二个码字总是最后一位不同，从而保证了哈夫曼码是即时码。,84,David Huffman 戴维 哈夫曼 David Huffman教授1999年10月7日逝世。在他的一 生中，他对于有限状态自动机，开关电路，异步过程 和信号设计有杰出的贡献。但是我们只是通过数据结 构中的哈夫曼编码才了解这位杰出的科学家的。 他发明的哈夫曼编码能够使我们通常的数据传输数量减少到最小。这个编码的发明和这个算法一样十分引人入胜。 1950年，哈夫曼在MIT的信息理论与编码研究生班学习。Robert Fano教授让学生们自己决定是参加期未考试还是做一个大作业。而哈夫曼选择了后者，原因很简单，因为解决一个大作业可能比期未考试更容易通过。这个大作业促使了哈夫曼以后算法的诞生。 离开MIT后，哈夫曼来到加利福尼亚大学的计算机系任教，并为此系的学术做出了许多杰出的工作。而他的算法也广泛应用于传真机，图象压缩和计算机安全领域。但是哈夫曼却从未为此算法申请过专利或其它相关能够为他带来经济利益的东西，他将他全部的精力放在教学上，以他自己的话来说，“我所要带来的就是我的学生。” Huffman编码至少可以减少20%的数据量。,85,5.3 限失真信源编码定理,信息率失真函数给出了失真小于D时所必须具有的最小信息率R(D)； 只要信息率大于R(D)，一定可以找到一种编码，使译码后的失真小于D。,86,5.3 限失真信源编码定理,限失真信源编码定理： 设离散无记忆信源X的信息率失真函数R(D)，则当信息率RR(D)，只要信源序列长度L足够长，一定存在一种编码方法，其译码失真小于或等于D，为任意小的正数。反之，若RR(D)，则无论采用什么样的编码方法，其译码失真必大于D。,87,5.3 限失真信源编码定理,限失真信源编码定理只能说明最佳编码是存在的，而具体构造编码方法却一无所知。因而就不能象无损编码那样从证明过程中引出概率匹配的编码方法。一般只能从优化的思路去求最佳编码。实际上迄今尚无合适的可实现的编码方法可接近R(D)这个界。,88,5.4 常用信源编码方法简介,游程编码 在二元序列中，连0段称为0游程 连1段称为1游程 000101110010001 可变换成下列游程序列：3113213,89,5.4 常用信源编码方法简介,若已知二元序列以0起始，从游程序列很容易恢复成原来的二元序列 游程序列是多元序列，各长度可按霍夫曼编码或其它方法处理以达到压缩码率的目的。,90,5.4 常用信源编码方法简介,多元序列也存在相应的游程序列 多元序列变换成游程序列再进行压缩编码没有多大意义 游程编码只适用于二元序列，对于多元信源，一般不能直接利用游程编码,91,视频压缩,1.统计冗余度的压缩：对于一串由许多数值构成的数据来说，如果其中某些值经常出现，而另外一些值很少出现，则这种由取值上的统计不均匀性就构成了统计冗余度，可以对之进行压缩。 目前用于图像压缩的具体的熵编码方法主要是霍夫曼编码，即一个数值的编码长度与此数值出现的概率尽可能地成反比。 霍夫曼编码虽然压缩比不高，约为1.6：1，但好处是无损压缩，目前在图像压缩编码中被广泛采用。,92,视频压缩,空间冗余度的压缩：一幅视频图像相邻各点的取值往往相近或相同，具有空间相关性，这就是空间冗余度。图像的空间相关性表示相邻象素点取值变化缓慢。从频域的观点看，意味着图像信号的能量主要集中在低频附近，高频信号的能量随频率的增加而迅速衰减。通过频域变换，可以将原图像信号用直流分量及少数低频交流分量的系数来表示，这就是变换编码中的正交余弦变换DCT的方法。DCT是JPEG和MPEG压缩编码的基础，可对图像的空间冗余度进行有效的压缩。 视频图像中经常出现一连串连续的象素点具有相同值的情况，典型的如彩条，彩场信号等。只传送起始象素点的值及随后取相同值的象素点的个数，也能有效地压缩码率，这就是行游程编码。目前在图像压缩编码中，行游程编码并不直接对图像数据进行编码，主要用于对量化后的DCT系数进行编码。,93,视频压缩,时间冗余度的压缩：时间冗余度表现在画面中相继各帧对应象素点的值往往相近或相同，具有时间相关性。在知道了一个象素点的值后，利用此象素点的值及其与后一象素点的值的差值就可求出后一象素点的值。因此，不传送象素点本身的值而传送其与前一帧对应象素点的差值，也能有效地压缩码率，这就是差分编码DPCM。在实际的压缩编码中，DPCM主要用于各图像子块在DCT变换后的直流系数的传送。 由差分编码进一步发展起来的预测编码，是根据一定的规则先预测出下一个象素点或图像子块的值，然后将此预测值与实际值的差值传送给接收端。目前图像压缩中的预测编码主要用于帧间压缩编码，方法是先根据一个子块的运动矢量求出下一帧对应子块的预测值及其与实际值的差值，接收端根据运动矢量及差值恢复出原图像。由于运动矢量及差值的数据量低于原图像的数据量，因而也能达到图像数据压缩的目的。,94,视频压缩,视觉冗余度的压缩：视觉冗余度是相对于人眼的视觉特性而言的。人眼对于图像的视觉特性包括：对亮度信号比对色度信号敏感，对低频信号比对高频信号敏感，对静止图像比对运动图像敏感，以及对图像水平线条和垂直线条比对斜线敏感等。因此，包含在色度信号，图像高频信号和运动图像中的一些数据并不能对增加图像相对于人眼的清晰度作出贡献，而被认为是多余的，这就是视觉冗余度。 压缩视觉冗余度的核心思想是去掉那些相对人眼而言是看不到的或可有可无的图像数据。对视觉冗余度的压缩通常已反映在各种具体的压缩编码过程中。如对于DCT系数的直流与低频部分采取细量化，而对高频部分采取粗量化，使得DCT变换能借此压缩码率，并能有效地进行行游程编码。在帧间预测编码中，大码率压缩的预测帧及双向预测帧的采用，也是利用了人眼对运动图像细节不敏感的特性。 图像压缩编码的具体方法虽然还有多种，但大都是建立在上述基本思想之上的。DCT变换，行游程编码，DPCM，帧间预测编码及霍夫曼编码等编码方法，因技术上的成熟，已被有关国际组织定为压缩编码的主要方法。,95,96,5.4 常用信源编码方法简介,算术编码 非分组码的编码方法之一算术码,97,5.4 常用信源编码方法简介,符号概率与积累概率的递推关系,98,5.4 常用信源编码方法简介,采用累积概率P(S)表示码字C(S)，符号概率p(S)表示状态区间A(S),99,5.4 常用信源编码方法简介,P(S)把区间0，1)分割成许多小区间，每个小区间的长度等于各序列的概率p(S)，小区间内的任一点可用来代表这序列,100,5.4 常用信源编码方法简介,代表大于或等于的最