七讲-变长信源编码定理.ppt

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,变长信源编码定理,71 变长信源编码定理,72 Huffman编码,第七讲,对信源输出的消息（一个符号或者一串符号）采用不同长度的码字表示，则这种编码方法叫做,变长编码,。一般应使出现概率大的消息用较短的码字表示，出现概率小的消息用较长的码字表示，这样将会提高编码效率。,设信源有,q,个符号，第,i,个消息以长为,l,i,的,r,元码表示，当信源为无记忆时，平均每个信源号所需的码长为,平均码长,：,71,变长信源,编码定理,1、基本概念,信源符号集,概率,码A,码B,码C,码D,a1,a2,a3,a4,0.5,0.25,0.125,0.125,0,0,1,10,0,1,00,11,0,10,110,111,0,01,011,0111,码A于信源字母集不是一一对应的；,码B虽然与信源字母集一一对应，但仍不是唯一可译的；,码,C,和码,D,是唯一可译的。,变长码与定长码的优缺点：同步、译码延时、效率方面。,唯一可译,：,对每个有限长的信源序列，相应的码字序,列彼此都可无疑义地区分开。,逗点码,：码中各码字都有一特定符号或符号组用以,指示码字地起始点。否则为无逗点码。,上表中码D是一种逗点码，码C是无逗点码。,字头（前缀）,：对于码字为码字的字头或前缀。,异字头码,：,码中任何一个码字都不是另一个码字的字头。,（即时码）,或称异前缀码。码,C,是异字头码，码,D,不是。,异字头条件保证这类码的唯一可译性。并且还有即时性，收到哪个码就可译码，无译码延时。而对于码,D,译码时必须在观察到下一个逗点时才能译码。,各类码的包含关系,：,即时码,非奇异码,（码字都不同）,所有的码,唯一可译码,2、Shannon-Fano,编码方法：（异字头条件码树码）,对于 r 元树，最顶部的起始点为树根，自树根向下有 r 个分支，各个分支的端点为,一级节点，二级节点最多可能有,r,2,，一般,l,级节点有,r,l,个。若将从每个节点出发的,r,个分支分别标以,0,，,1,，,2,，,，,r,1,，则每个,l,级节点需要用,l,个 r元数字表示（也即从树根到该节点的路径）。,根,分支,C1=0,C4=12,C5=20,C6=21,C7=220,C8=221,C9=222,C2=10,C3=11,若指定某个,l,级节点表示一个消息，则该节点不再向下延伸，其长度为,l,，此节点称为,端节点,。这样的得到的码就能保证异字头条件。如果有,K,个消息，就在树上选择,K,个端节点，相应的,r,元数字即为码字。这样输出的码称作,树码,，相应的图称作,码树,，如果码树的各分支都延伸到最高级端点，就称为,满树,。否则为非满树。,我们希望选出的码集合平均长度最小。为此希望码序列的任一符号承载的信息量最大，我们可使从每个节点的,r,种可能的分支出现的概率近似相等，这将给出一种近似最佳的编码方法。,消息,概率,第一次划分,第二次划分,第三次划分,指定,码组,码长,a1,a2,a3,a4,a5,a6,a7,a8,a9,1/3,1/9,1/9,1/9,1/9,1/9,1/27,1/27,1/27,0(1/3),1(1/3),2(1/3),0(1/9),1(1/9),2(1/9),0(1/9),1(1/9),2(1/9),0(1/27),1(1/27),2(1/27),0,10,11,12,20,21,220,221,222,1,2,2,2,2,2,3,3,3,Kraft不等式：,（异字头条件码存在的充分必要条件）：,长度为 的 r 元异字头码存在的,充要条件,是：,证明,：（1）必要性：即时码满足上式。,最低层 N 阶的分支数为,第 i 阶节点作为码字后，不能伸出分支数,共 q 个码字，总不能伸出的分支数,（2）充分性：不等式意味着存在即时码,构造码树：,码字最后节点的阶的节点数,码树分配 长 码字,，阶中剩下的节点,依次类推。分配完 阶后还剩余的节点为,码树再分配 码字,，阶中剩下的节点,定理,：唯一可译码必满足,Kraft,不等式。,推论,：任一唯一可译码可用各相应码长度一样的异字头码,代替。,平均码长界定,定理,（-定理5.7）,：,此为单符号情况！,任一唯一可译码满足,存在,有r元唯一可译码，其平均长度,下界证明：利用Jensen不等式,存在上界证明：构造即时码：,右面对概率求和，可得结论：,左边整理，并对,i,求和：,即为kraft不等式，说明存在唯一可译码；,最佳的。,码树分配 长 码字,可对 的码字的最后一位指定为 1 和 0，,第七讲 变长信源编码定理,如果未知统计特性，则还没有很好办法；,这样的得到的码就能保证异字头条件。,最佳的。,同一空间，可以引入不同种类的范数,存在有r元唯一可译码，其平均长度,3、香农第一定理：（又称为变长编码定理）,设离散无记忆信源S包含r个符号，信源发出N重符号序列 ，则此信源可发出 个不同的符号序列消息，其中第 j 个符号序列消息的出现概率为 ，其信源编码后所得的二进制代码组长度为 ，代码组的平均长度为,它满足：,多余度（冗余度,）定义,为：,当 N 趋于无限大时，和 H(S)之间的关系为,编码效率：,例：书中例5.4,最佳的。,72 Huffman编码,例如 R2 空间中可定义范数：,算子：将一个空间 X 的元素变换到另一个空间 Y 的映射。,最低层 N 阶的分支数为,Huffman提出的一种异字头编码方法，其平均长度最短，是一种最佳编码。,码C和码D是唯一可译的。,下面对正交变换略作解释：,如果有K个消息，就在树上选择K个端节点，相应的r元数字即为码字。,若指定某个 l 级节点表示一个消息，则该节点不再向下延伸，其长度为 l，此节点称为端节点。,有了距离的概念，就可以引入极限的概念。,可对 的码字的最后一位指定为 1 和 0，,线性空间：在集合中引入线性运算（加法和数乘）,给定信源 ，不失一般性可将各消息按概率由小到大进行如下排列：，相应的概率为 。,然后作一个辅助集,72 Huffman编码（最佳编码方法）,通常称具有最短的代码组平均长度或编码效率接近于1的信源编码为,最佳编码,。香农编码方法对于某些信源编码效率高，但对有些编码效率低，因此不是最佳的。,Huffman,提出的一种异字头编码方法，其平均长度最短，是一种最佳编码。,给定信源 ，不失一般性可将各消息按概率由小到大进行如下排列：，相应的概率为 。设二元码字为 ，,相应的长度为 。,定理,：对于给定信源，存在有最佳唯一可译二元码，其,最小概率的两个码字C,K-1,和C,K,的长度最长且相等，,它们之间仅最后一位码元取值不同（一个为0，,一个为1）。,这一定理暗示了一种编码方法：,即对于给定信源,可对 的码字的最后一位指定为 1 和 0，,然后作一个辅助集,其中：,对于新的辅助集合，首先将它按 的大小重新排序，而后将概率最小的两个消息的码字随后一位分别赋予1和0。再构造新的辅助集，如此重复，直到最后的辅助集只有两个消息位置。,这样由原来每个消息 在各辅助集中所参与的最后两个元素相应的码元，就可以得到各消息 所对应的码字。,定理,：对于辅助集U为最佳的码，对原始消息集U也是,最佳的。,例：,0,1,1,0,0,0,1,1,可以用码树；,码不唯一！,实用无失真信源编码方法,M H 编码（）,算术编码（对二元序列编码，一般方法，未知分布）,I Z 编码 （LZW）,压缩编码的码率，就是压缩每个符号平均 bit 数；,如果,未知统计特性,，则还没有很好办法；,连续信源必然有失真，依据,限失真信源编码,定理,多媒体信源编码压缩编码：,文本、音频、图象、视频等。,关于信源编码，可参见：,周炯槃，丁晓明编著信源编码原理，,1996，北京邮电大学出版社。,对于相关信源，条件熵一般远小于无条件熵。,通过预测和正交变换的编码方法，去除符号之间,的相关性，达到进一步压缩码率的目的。,（集中到少量码字，用少的表示多的。）,下面对,正交变换,略作解释：,空间：赋予某些数学结构的集合,线性空间：在集合中引入,线性运算,（加法和数乘）,线性赋范空间：线性空间中引入元素长度（,范数,）,内积空间：线性空间中引入,内积,的概念,线性空间是线性代数研究的内容；,线性赋范空间和内积空间是泛函分析研究的内容。,范数（Norm）：,实数域上的线性空间X，其中任意元素,对应一个实数（函数），称为范数，满足下列条件：,同一空间，可以引入不同种类的范数,有了距离的概念，就可以引入极限的概念。,例如 R,2,空间中可定义范数：,内积,：（两向量之间的关系，数量积概念的推广）,设X为实线性空间，若对应 X 中两个元素 x 和 y,都有一个实数，（x,y）即x和y的内积，满足：,（内积的几何意义是两向量的夹角，也叫,标量积,）,例如：,内积空间必是赋范空间，只要令,元素的正交,：只要它们的内积为 0。,内积可以表示元素（信号）的相似程度。,一个元素可以按一个正交系展开。,算子,：将一个空间 X 的元素变换到另一个空间 Y 的映射。,泛函,：值域是数域的算子。（定义域是函数空间）,正交变换：,保持范数不变的线性算子（正交算子）。,信号处理中常用的,有限正交变换,：,N维空间,N 空间的正交变换,正交变换可用矩阵表示，且这个矩阵是正交的。,离散傅立叶变换（DCT）：,离散沃尔什变换(DWT：descrete Walsh transform),离散哈达玛变换（DWHT）：WalshHadamard）,（不是表示为正弦波，而是方波的线性组合形式！）,卡亨南洛厄维变换（KarhunenLoeve）：独立分量,离散小波变换（Wavelet transform）,第七讲 变长信源编码定理,结 束,