第五章：无失真编码2.ppt

无失真信源编码,无失真信源编码,无失真编码概述定长信源编码变长信源编码实用的无失真信源编码方法举例,5.1无失真编码器1,离散、无失真、无记忆信源编码的一般模型：,总码组合数：,总组合数：,入,出,有q个源字母,有r个码字母,5.1无失真编码器2,问题：能否进行无失真编码，怎样进行无失真编码若：不考虑信源统计特性：应满足条件：相互矛盾！,由,结论：当q=r时，lN不有效。当l=N时，rq，亦不满足有效性,解决办法：引入信源统计特性。,5.1无失真编码器3,考察无失真条件：分别表示等概条件下的消息熵与码字熵之比，考虑信源的实际统计特性（非等概），实际消息熵为：代入无失真条件得：此时：即使q=r,只要就有可能实现l0,0，只要满足：(l/N)logrH(S)+则：当N足够大时，可使译码差错小于，反之，当(l/N)logrH(S)-2时，译码一定出错。解释：定长编码定理给出了信源进行等长编码所需码长的理论极限值。,5.3定长编码定理2-进一步理解,若要求变得的等长码是唯一可译的，则必须：若N1，则：结论：对于唯一可译码，每个信源符号至少需要用个码符号来变换。当采用二元码编码时，r2，则：结论：对信源进行二元等长编码时，每个信源符号所需码长的极限值为,例1：英文电报有32个符号（266），即q=32，若r=2，N1（即对信源的逐个符号进行二元编码），则：解释：每个英文电报符号至少需要用5位二元符号编码问题：第三章：在考虑符号出现的概率和符号间相关性前提下,每个英文符号平均携带的信息量是1.4bit/符号（），5bit/符号，等长编码效率极低，如何提高效率？如何体现有效性？,Bit/符号,解决方法：考察：字母个数为n，字母出现非等概，且字母之间相关长度为L的英文信源，其可能的字母序列总数为；但其中大部分字母序列是无意义的字母组合，而且随着N的增加，这种无意义序列的总数越来越大。方法：进行联合编码，即对字母序列编码，且只对哪些有意义的字母序列编码，即需编码的字母序列的总数,则平均每个信源符号所需的码符号个数可以大大减少，从而提高了传输效率。问题：会引入一定的误差，当N足够长后，误差可以任意小。,5.3定长编码定理3证明,考察离散、随机序列信源的统计特性渐进等分割性（AEP）AEP描述：渐进等分割定理：（熵定理，遍历性定理）设是离散无记忆信源输出的一个特定序列，则任给和，总可以找到一个整数，使当时，有：,引入：渐进等分割性（AEP）,5.3定长编码定理4AEP物理意义,任何一个离散随机序列信源当序列长度时,信源序列会产生两极分化.大概率事件集合与小概率事件集合对于有性质:(信源熵)(大概率事件熵)(等概率)对于有性质:由此可见，信源编码只需对信源中少数落入典型大概率事件的集合的符号进行编码即可。而对大多数属于非典型小概率事件集合中的信源符号无需编码,且。,5.3定长编码定理5AEP证明,集合和中的序列分别称为典型序列和非典型序列可以证明：对于任意小的正数，当N足够大时，表示中所有典型序列的集合表示集合中序列的个数还可以证明：对于任意小的正数，当N足够大时，表示序列出现的概率由切比雪夫不等式可得：表示S中每个符号携带的信息量的方差,AEP结论：当L足够大时，所有典型序列出现的概率近似相等，即典型序列为渐进等概序列可粗略认为典型序列出现的概率为所有典型序列的概率和接近为1，即AEP应用：提出、证明都是基于离散无记忆序列信源平稳遍历信源有类似结果体现信源统计特性用以证明定长编码定理,5.3定长编码定理5证明,定长编码定理证明思路：将取自S，长为N的信源符号序列分为集合和只对集合中的序列进行一一对应的等长编码此时的误差为，计算误差可见当，且(K/L)logmH(S)+时，几个概念：编码信息率：（编码后平均每个信源符号能载荷的最大信息率）编码效率：（编码前后平均每个信源符号能载荷的最大信息率之比）,5.3定长编码定理6（物理意义）,结论：可推广至离散、非平稳无记忆信源和有记忆信源情况只要码字传输的信息量大于信源序列携带的信息量，总可以实现几乎无失真编码,(l/N)logrH(S)+,二元码时，r2：,最佳等长码时：,5.3定长编码定理7（实际应用问题）,编译码同步问题问题：如何使译码端知道码字起点解决办法：1、每个码字加短同步前缀2、每若干码字加较长同步前缀分组长度与编译码复杂性、编译码延时等等关系问题：要实现有效，源序列分组很长，使得编译码复杂性和延时增加解决办法：目前没有理想到解决办法定长信源编码的理论意义远大于其实用价值,5.3定长编码定理8（举例),例2：设有一简单离散信源：q=2对其进行近似于无失真的等长编码，若要求其编码效率为96%，差错率低于10-5，试求符号联合编码长度N=？解：由编码效率：即：再由:可见,信源序列长度需要4100万个符号,才能达到上述要求,这显然是不现实的.一般来说：当N有限时，高传输效率的等长码往往要引入一定的失真和错误，它不能象变长编码那样可以实现真正的无失真编码,5.4变长信源编码,几个码类的概念(4)非奇异码（奇异码、单义码）唯一可译码前缀码（即时码、非延长码、异前置码）最佳码（紧致码）Kraft定理唯一可译码存在定理变长编码定理（香农第一定理）,5.4变长信源编码-1(Kraft定理),引出码树Kraft定理描述Kraft定理证明略,5.4变长信源编码-2(Kraft定理引出),问题：寻求实时唯一可译码方法：研究实时唯一可译码的码字可分离条件引入：“码树”概念（直观）结论：通过Kraft定理给出实时唯一可译码（前缀码）存在的条件,码树变长码的树图表示,将变长码与码树建立“一一对应”关系：树根码字起点树枝数码的进制数节点码字或码字的一部分终止节点码字节数码长非满树变长码满树等长码,5.4变长信源编码-3(Kraft定理),问题：比较简单信源，码树方法可直接且直观构造前缀码较复杂信源，直接画码树复杂且困难解决方法：为分析起来特别对含有很多符号种类的复杂信源更方便寻找一种与上述“树图”等效的解析式表达式-Kraft不等式。结论：Kraft定理给出码字可分离或前缀码存在的充要条件,5.4变长信源编码-4(Kraft定理),定理：长度为li（i=1,2,n）的r（码字母表长度）进制前缀码存在的充要条件为：证明：略物理意义：给定信源个数q和码字数r，只要允许码字长度可以足够长，就总可以满足Kraft不等式，从而得到前缀码,5.4变长信源编码-5(唯一可译码定理),Kraft不等式给出的限制也是所有唯一可译码都必须满足的。定理描述：任何唯一可译码均满足Kraft不等式。结论：对任何唯一可译码均可在不改变码字长度的条件下得到相应的前缀码,5.4变长编码定理6,问题：对于已知信源S可用码符号X进行变长编码，而且对同一信源编成同一码符号的前缀码或惟一可译码可有许多种。究竟哪一种最好呢?从高速度传输信息的观点来考虑，当然希望选择由短的码符号组成的码字，就是用码长作为选择准则。引入：码的平均长度。离散无记忆平稳信源信源熵率为码字母表个数为r，则前缀码平均码长：,5.4变长编码定理7,无失真变长信源编码定理(即香农第一定理)：离散无记忆平稳信源S，其熵率为，并有码符号X=x1,xr。对信源S进行编码,总可以找到一种编码方法，构成惟一可译码，使信源S中每个信源符号所需的平均码长满足:另一方面,必可以找到前缀码，使其平均码长满足,5.4变长编码定理8,定理证明略物理意义：又称无噪信道编码定理编码后的码符号信源尽可能为等概分布，使每个码符号平均所含的信息量达到最大要做到无失真编码，变换每个信源符号平均所需最少的r元码元数就是信源的熵率（以r进制信息量单位测度）信源的熵率是描述信源每个符号平均所需最少的比特数定理说明：是存在性定理具有理论指导意义是构造性定理设计出多种具体编码方法,5.4变长编码定理9编码效率,变长码编码效率：衡量各种编码方法的优略，判断是否最佳码。编码前平均每个信源符号携带的信息量为：编码后平均每个信源符号携带的最大的信息量为：定义变长码编码效率为：另一种理解：最佳码（极限时）每个信源符号的平均码长为：某一方法得到的每个信源符号的平均码长为：定义变长码编码效率为：,比较：定长编码的编码效率：变长编码的编码效率：注意到：是指每个信源符号所需的平均码长，而也是平均到每个信源符号的码长，所以它们是一致的，均表示无失真信源编码的效率。,例4：p160例4.4一离散无记忆信源,其熵为：,用二元符号（0，1；r=2）构造一个前缀码：,此时每个信源符号平均码长为：,编码效率为：,为提高编码效率，对S的2次扩展信源进行2维联合编码：,构造一个扩展信源S2的前缀码：,此时平均码长为：,此时信源S中每个符号对应的平均码长为：,编码效率为：,同样可得：,定长编码与变长编码效率比较：,例4与例2相比：同一个信源，当要求编码效率达到96时，等长码需要4100万个信源符号联合编码；变长码只需2个符号（二次扩展信源）联合编码；结论：采用变长编码，N不需要很大就可以达到相当高的编码效率，而且可以实现无失真编码。且随着N的增大，编码效率越来越接近于1。,5.5实用的无失真信源编码方法举例1（huffman编码）,Huffman编码编码方法特点应用问题,5.5实用的无失真信源编码方法举例2（huffman编码）,编码方法：例：=消息U概率pi编码CU11/2001U21/40101/21U31/801101/41U41/81111,5.5实用的无失真信源编码方法举例3（huffman编码）,编码规则：1)将信源消息U按概率大小排序（由大至小）。2)从最小两个概率开始编码，并赋予一定规则，如下支路小概率为“1”，上支路大概率为“0”。若两支路概率相等，仍为下支为“1”上支为“0”。3)将已编码两支路概率合并，重新排队，编码。4)重复步骤3）直至合并概率归一时为止。5)从概率归一端沿树图路线逆行至对应消息编码，如U3为“110”。,5.5实用的无失真信源编码方法举例4（huffman编码）,例2：,5.5实用的无失真信源编码方法举例5（huffman编码）,特点：编码不是唯一的保证了概率大的符号对应于短码，概率小的符号对应于长码，而且短码得到充分利用每次缩减信源的最后二个码字总是最后一位码元不同，前面各位码元相同（二元码情况）每次缩减信源的最长两个码字具有相同码长这三个特点保证了所得到huffman码一定是最佳码,5.5实用的无失真信源编码方法举例6（huffman编码）,应用:在不同领域得到广泛应用。例：Internationaldigitalfacsimilecodingstandard(1980)USHDTV(19