第四章课件《无失真信源编码》

第四章无失真信源编码,1 冗余度的概念；2 数据压缩的概念3 数据压缩的基本途径4 编码器5 等长码及等长信源编码定理6 变长码及变长信源编码定理7 霍夫曼码和其他编码方法,信息论面对通信系统回答了以下两个问题：,在不失真或者允许一定失真条件下，如何用尽可能少的符号来传送信源信息，以提高信息传输率-信源编码在信道受干扰的情况下，如何增加信道的抗干扰能力，同时使信息传输率最大-信道编码,冗余度的概念,冗余度的概念,冗余度的概念,4.1,冗余度的概念,冗余度的概念,冗余度的概念,冗余度,计算机文件表现为字符集合或者是二进制集合，当然二者最终存储形式都是“0”、“1”代码。有一类逻辑压缩方法，就是从分析数据入手，看那些数据可以省去，又如何以最少的符号来代替必不可少的数据。这实际上只是一种由数据自身特点及设计者技巧来决定的压缩表示法。本节讨论的是减少计算机文件内部冗余度的办法的统计编码方法。文件的冗余类型 字符分布 字符重复 位置冗余 高使用模式,4.2 数据压缩的概念,信源编码：主要解决有效性问题。通过对信源的压缩、扰乱、加密等一系列处理，力求用最少的数码传递最大的信息量，使信号更适宜传输。信道编码：主要解决可靠性问题。即尽量使处理过的信号在传输过程中不出错或少出错，即使出了出了错也要能自动检错和尽量纠错。 因此，从信息论的角度看，信源编码的一个最主要的目的，就是要解决数据的压缩的问题，它构成了数据压缩的理论基础。数据压缩，就是以最少的数码表示信源所发出的信号，减少容纳给定消息集合或数据采样集合的信号空间。,数据压缩的概念,所谓信号空间亦即被压缩的对象是指：物理空间：如存储器、磁盘、磁带、光盘等数据存储介质；时间区间：如传递给定信号所需要的时间；电磁频谱区域：如为传递给定消息所要求的带宽。,数据压缩的概念,解决方法减小数据存储空间；提高传输速度时域压缩；提高频带利用率（在通信干线上开通更多的并行业务（电视、传真、电话、可视图文等）。数据压缩技术分类可逆压缩;不可逆压缩,可逆压缩,可逆压缩： 亦称无失真、无差错编码(Error Free Coding)或（Noiseless Coding），不同专业的文献作者还采用了另外些术语，如冗余度压缩（Redundancy Reduction）,熵编码（Entropy Coding）、数据紧缩(Data Compaction)等等。理论依据： 香农在创立信息论时，提出把数据看作是信息与冗余度的结合。,可逆压缩,【例4-1】在一个数据采集系统，如信号在一段长时间内不变，则许多连续采样值是重复不变的。 显而易见的方法就是计算两个不同采样值间的重复采样数目,然后将变化的采样值和重复数目一起发送,即压缩又无失真(compression）【例4-2】12位A/D转换器采样数据。为了便于处理，常用一个2个8 位的寄存器来存一个样值，这就使每一样值额外增加了4位冗余度. 若改用6个字（48bit）存4个数据，即可消除冗余度（Compaction）,不可逆压缩,不可逆压缩 ： 有失真编码（LossyCoding），亦称熵压缩（Entropy Compressing）【例4-3】为了简单地实现熵编码，我们在监督采样时设置某个门限；只有当采样值过该门限时才传数据。丢失了信息。,数据压缩的类比,【例4-4】设想我们将菜叶（数据）倒入一个铁桶（存储器）的情形，为了使铁桶装得尽可能多的茶叶。 有以下几种可行的途径：将茶叶罐颠一颠、摇一摇，使茶叶排列更紧密，挤掉外在的一些外在的“冗余度（ Compaction）”。无失真压缩将茶叶烤干，去除茶叶的水分，减小自身体积消除“内在的冗余度”（compression）。无失真压缩将干菜叶压成末，此时装的最多（压缩最大）， 但“ 叶”已变“粉”，不可逆压缩。茶叶已无法复原。 有失真信源编码。 由此我们已建立了一个初步的概念，即：有冗余度就可以压缩（罐中有空气，茶叶中有水分）压缩只能在一定限度内可逆（菜叶倒出来仍然完整）超过此限度（信息熵）必然带来失真（茶叶会破碎）允许的失真越大，压缩比也可以越大（茶叶压得余额碎，罐可装得越多）,3 数据压缩的基本途径, 基本途径之一概率匹配 基本途径之二对独立分量进行编码 基本途径之三利用条件概率,基本途径之一概率匹配,基本途径之一概率匹配,基本途径之一概率匹配,基本途径之一概率匹配,基本途径之二对独立分量进行编码,不考虑相关性时信源熵为H(X)+H(Y),考虑相关性时信源熵为H(X)+H(Y)-I(X,Y),基本途径之三利用条件概率,基本途径之三利用条件概率,基本途径之三利用条件概率,4、编码器,编码实质是对信源的原始符号按一定的数学规则进行的一种变换，如下图所示,图4.1 无记忆信源编码器,编码器,编码器,无失真信源编码,无失真编码概述定长信源编码变长信源编码无失真信源编码方法举例,4.1无失真编码概述1,离散、无失真、无记忆信源编码的一般模型：,总码组合数：,总组合数：,入,出,4.1无失真编码概述2,问题：能否进行无失真编码，怎样进行无失真编码若：不考虑信源统计特性：应满足条件： 相互矛盾！,由,结论：当 q = r 时，lN 不有效。 当l=N 时，rq，亦不满足有效性,解决办法： 引入信源统计特性。,4.1无失真编码概述3,考察无失真条件： 分别表示等概条件下的消息熵 与码字熵 之比， 考虑信源的实际统计特性（非等概），实际消息熵为： 代入无失真条件得： 此时：即使q=r,只要 就有可能实现N0,0，只要满足： (l/N)logrH(S)+ 则：当N足够大时，可使译码差错小于， 反之，当 (l/N)logrH(S)-2 时，译码一定出错。解释：定长编码定理给出了信源进行等长编码所需码长的理论极限值。,4.2定长编码定理2-进一步理解,若要求变得的等长码是唯一可译的，则必须：若N1，则：结论：对于唯一可译码，每个信源符号至少需要用 个码符号来变换。当采用二元码编码时，r2，则：结论：对信源进行二元等长编码时，每个信源符号所需码长的极限值为,例1：英文电报有32个符号（266），即n=32， 若m=2，L1（即对信源的逐个符号进行二元编码）， 则：解释：每个英文电报符号至少需要用5位二元符号编码问题：在考虑符号出现的概率和符号间相关性前提下,每个英文符 号平均携带的信息量是1.4bit/符号（ ），5bit/符号， 等长编码效率极低，如何提高效率？如何体现有效性？,Bit/符号,解决方法：考察：字母个数为q，字母出现非等概，且字母之间相关长度为N的英文信源，其可能的字母序列总数为 ；但其中大部分字母序列是无意义的字母组合，而且随着N的增加，这种无意义序列的总数越来越大。方法：进行联合编码，即对字母序列编码，且只对哪些有意义的字母序列编码，即需编码的字母序列的总数 ,则平均每个信源符号所需的码符号个数可以大大减少，从而提高了传输效率。问题：会引入一定的误差，当N足够长后，误差可以任意小。,4.2定长编码定理5（物理意义）,结论：可推广至离散、非平稳无记忆信源和有记忆信源情况只要编码信息率大于信源序列携带的信息量（熵)，总可以实现几乎无失真编码,(l/N)log rH(S)+,二元码时，r2：,最佳等长码时：,4.2定长编码定理6（实际应用问题）,编译码同步问题问题：如何使译码端知道码字起点解决办法：1、每个码字加短同步前缀 2、每若干码字加较长同步前缀分组长度与编译码复杂性、编译码延时等等关系问题：要实现有效，源序列分组很长，使得编译码 复杂性和延时增加解决办法：目前没有理想到解决办法定长信源编码的理论意义远大于其实用价值,4.2定长编码定理7（举例),例2：设有一简单离散信源：L=1,n=2对其进行近似于无失真的等长编码，若要求其编码效率为96%，差错率低于10-5，试求符号联合编码长度L=？解： 由编码效率：即： 再由:可见,需要4100万个信源符号联合编码,才能达到上述要求,这显然是不现实的.一般来说：当N有限时，高传输效率的等长码往往要引入一定的失真和错误，它不能象变长编码那样可以实现真正的无失真编码,4.5 变长码,变长码,可见变长码的编码思想就是，用短码表示高概率的符号，用长码表示低概率符号，编码后使平均码长接近于信源的信息熵。缺点是：解码远比等长码复杂，并且还存在唯一可译性、译码实时性、均匀输入输出的缓存问题,4.6 变长信源编码-1,几个码类的概念非奇异码（奇异码、单义码）唯一可译码前缀码（即时码、非延长码、异前置码）最佳码（紧致码）Kraft定理唯一可译码存在定理变长编码定理（香农第一定理）,4.6变长信源编码-2(几个码类的概念),非奇异码：每一个码字仅对应信源中的一个信源符号（序列）。编码是单义的。反之为奇异码或非单义码。,4.6变长信源编码-3(几个码类的概念),唯一可译码编码单义、译码单义对任何一个有限长度的信源字母序列，如果编码得到的码字母序列不与其他任何信源字母序列所对应的码字母序列相同。,4.6变长信源编码-4(几个码类的概念),即时码是一类唯一可译码在一个变长码中，没有任何一个码字是其他码字的前缀。译码时无需参考后续的码符号就能立即作出判断，进行无延时译码。又称即时码、非延时码,4.6变长信源编码-5(几个码类的概念),最佳码唯一可译码的一类其平均码长小于其他唯一可译码的平均长度,所有的码,非奇异码,唯一可译码,即时码,4.6变长信源编码-6（几种类型的信源编码 举例）例3：,定理4.4：对于码符号为X：x1,x2,xq的任意即时码，其码字为W1，W2 , Wq 符号，所对应码长分别为l1,l2,lq。则必定满足Kraft不等式，即：反之，若码长满足Kraft不等式，则一定存在这样码长的即时码,定理4.5：对于码符号为X：x1,x2,xq的任一唯一可译码，其码字为W1，W2 , Wq 符号，所对应码长分别为l1,l2,lq。则必定满足Kraft不等式，即：反之，若码长满足Kraft不等式，则一定存在这样码长的唯一可译码,定理4.6：若存在码长分别为l1,l2,lq的唯一可译码。则一定存在具有相同码长的即时码,码树变长码的树图表示,将变长码与码树建立“一一对应”关系：树根码字起点树枝数码的进制数节点码字或码字的一部分终止节点码字节数码长非满树变长码满树等长码,变长码,变长码,变长码,唯一可译变长码的判断法,将码C所有可能的尾随后缀组成一个集合F，当且仅当集合F中没有包含任意码字，则可判断此码C为唯一可译变长码,例4.2 现设码C=0,10,1100,1110,1011,1101, 判断码C是否为唯一可译码F=11，00，10，01，0，1，100，110，011，101，而10，0都是C中的码字，所以码C不是唯一可译码,例4.1 设码C=110,11,100,00,10, 判断码C是否为唯一可译码 F=0，F集中没有元素是码C的码字，所以码C是唯一可译,4.6变长编码定理,问题：对于已知信源S可用码符号X进行变长编码，而且对同一信源编成同一码符号的前缀码或惟一可译码可有许多种。究竟哪一种最好呢?从高速度传输信息的观点来考虑，当然希望选择由短的码符号组成的码字，就是用码长作为选择准则。引入：码的平均长度。 离散无记忆平稳信源 信源熵率为 码字母表个数为M， 则即时码平均码长：,4.6变长编码定理,定理4.7 无失真变长信源编码定理(即香农第一定理) ： 离散无记忆平稳信源S，其熵率为 ，并有码符号X=x1,xm。对信源S进行编码,总可以找到一种编码方法，构成惟一可译码，使信源S中每个信源符号所需的平均码长满足:,下界证明,上界证明,4.6变长编码定理,物理意义：又称无噪信道编码定理编码后的码符号信源尽可能为等概分布，使每个码符号平均所含的信息量达到最大要做到无失真编码，变换每个信源符号平均所需最少的r元码元数就是信源的熵率（以r进制信息量单位测度）信源的熵率是描述信源每个符号平均所需最少的比特数定理说明：是存在性定理具有理论指导意义是构造性定理设计出多种具体编码方法,4.6变长编码定理15编码效率,变长码编码效率：衡量各种编码方法的优略，判断是否最佳码。 编码前平均每个信源符号携带的信息量为： 编码后平均每个信源符号携带的最大的信息量为： 定义变长码编码效率为：另一种理解： 最佳码（极限时）每个信源符号的平均码长为： 某一方法得到的每个信源符号的平均码长为： 定义变长码编码效率为：,比较：定长编码的编码效率：变长编码的编码效率：,例4：p145例4.1一离散无记忆信源,其熵为：,用二元符号（0，1；m=2）构造一个前缀码：,此时每个信源符号平均码长为：,编码效率为：,为提高编码效率，对S的2次扩展信源进行2维联合编码：,构造一个扩展信源S2的前缀码：,此时平均码长为：,此时信源S中每个符号对应的平均码长为：,编码效率为：,同样可得：,定长编码与变长编码效率比较：,例4.4与例4.1相比： 同一个信源，当要求编码效率达到96时， 等长码需要4100万个信源符号联合编码； 变长码只需2个符号（二次扩展信源）联合编码；结论：采用变长编码，N不需要很大就可以达到相当高的编码效率，而且可以实现无失真编码。且随着N的增大，编码效率越来越接近于1。,无失真编码的实质,无失真编码的实质就是：对离散信源进行适当的变换，使变换后新的码符号信源尽可能的为等概率分布，以使新信源的每个码符号平均所含的信息量达到最大,信源编码,针对信源的编码，能更加有效地传输、存储信息。编码后尽可能减少所需信息的损失，提高编码后携带信息的效率,4.7 霍夫曼码和其他编码方法,本节介绍霍夫曼(Huffman)码、费诺(Fano)码和香农 -费诺-埃利斯(Shannon-Fano-Elias)码。 香农第一定理指出了平均码长与信源熵之间的关系，同时也指出了通过编码可使平均码长达到极限值。 但如何编码呢？ 本节将阐述如何构造一个紧致码(最佳码)的方法。首先讨论霍夫曼码的编码方法，再证明它的最佳性，然后再讨论其他次优的接近下界的编码方法。 最佳码：对于某一个信源和某一码符号集来说，若有唯一可译码，其平均编码长度不大于所有其他唯一可译码的平均编码长度，则该码为最佳码。,4.7.1 霍夫曼（Huffman）码,1952年，霍夫曼提出了一种构造最佳码的方法。 这是一种最佳的逐个符号的编码方法。编码对象为离散信源：,编码步骤（对二元系统）：,将q个信源符号按概率递减的方式排列起来； 用“0”,“1”码符号分别表示概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个符号，从而得到只包含 q-1个符号的新信源，称之为S信源的缩减信源S1； 将缩减信源S1的符号仍按概率大小以递减次序排列，再将其最后两个概率最小的符号合并成一个符号，并分别用“0”，“1”码符号表示，这样又形成了q-2个符号的缩减信源S2； 依次继续下去，直到信源最后只剩下两个符号为止，将这最后两个符号分别用“0”，“1” 码符号表示，然后从最后一级缩减信源开始，向前返回，得出各信源符号所对应的码符号序列，即得出对应的码字。,按霍夫曼的编码方法，可知这种码有以下特点：它是一种分组码它是一种即时码它是一种唯一可译码解码：霍夫曼码串可通过从左到右检查各个符号进行解码。本例中00011011010011a3 a2 a5 a2 a6,a511 l=2a210 l=2a6011 l=3a4010 l=3a1001 l=3a30001 l=4a70000 l=4,（huffman编码）,编码方法：例 ： =消息U 概率pi 编码C U1 1/2 0 0 1 0 U2 1/4 0 10 1/2 1 U3 1/8 0 110 1/4 1 U4 1/8 1 111,（huffman编码）,编码规则： 1)将信源消息U按概率大小排序（由大至小）。 2)从最小两个概率开始编码，并赋予一定规则，如下支路小概率为“1”，上支路大概率为“0”。若两支路概率相等，仍为下支为“1”上支为“0”。 3) 将已编码两支路概率合并，重新排队，编码。 4) 重复步骤3）直至合并概率归一时为止。 5) 从概率归一端沿树图路线逆行至对应消息编码，如U3为“