第5章_无失真信源编码_修改.ppt
第五章：无失真信源编码一、信源编码的相关概念二、定长码及定长信源编码定理三、变长码及变长信源编码定理四、变长码的编码方法五、实用的无失真信源编码方法第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码l 信源编码的作用：信源编码的作用：使信源适合于信道的传输，用信道能传输的符号来代使信源适合于信道的传输，用信道能传输的符号来代表信源发出的消息；表信源发出的消息；在不失真或允许一定失真的条件下，用尽可能少的符在不失真或允许一定失真的条件下，用尽可能少的符号来传递信源消息，提高信息传输率。号来传递信源消息，提高信息传输率。l 以提高通信有效性为目的以提高通信有效性为目的。通常通过。通常通过压缩信源的冗余压缩信源的冗余度度来实现。采用的一般方法是压缩每个信源符号的平均来实现。采用的一般方法是压缩每个信源符号的平均码长。码长。1.信源编码概述一、信源编码的相关概念一、信源编码的相关概念第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码l 信源编码理论是信息论的一个重要分支，其理论基础信源编码理论是信息论的一个重要分支，其理论基础是信源编码的两个定理：是信源编码的两个定理：无失真信源编码定理无失真信源编码定理限失真信源编码定理限失真信源编码定理l 本章主要介绍本章主要介绍无失真信源编码无失真信源编码，它实质上是一种统，它实质上是一种统计匹配编码，根据信源的不同概率分布而选用与之相计匹配编码，根据信源的不同概率分布而选用与之相匹配的码。匹配的码。1.信源编码概述（续1）一、信源编码的相关概念一、信源编码的相关概念第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码l 信源的统计剩余度主要决定于以下两个因素信源的统计剩余度主要决定于以下两个因素：1）无记忆信源中，符号概率分布的非均匀性；）无记忆信源中，符号概率分布的非均匀性；2）有记忆信源中，符号间的相关性及）有记忆信源中，符号间的相关性及符号概率分布符号概率分布的非均匀性的非均匀性。1.信源编码概述（续2）l怎样压缩信源的冗余度？怎样压缩信源的冗余度？1)去除码符号间的相关性。去除码符号间的相关性。2)使码符号等概分布。使码符号等概分布。一、信源编码的相关概念一、信源编码的相关概念第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码2.信源编码器模型信宿信道信源编码器译码器YXSSl 信源编码：将信源符号序列按一定的数学规律映射成码符号序列的过程。图1 信源编码器模型一、信源编码的相关概念一、信源编码的相关概念第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码l 将信源符号集中的符号（或者长为N的信源符号序列）映射成由码符号 组成的长度为 的一一对应的码符号序列 。编码器码字2.信源编码器模型（续1）一、信源编码的相关概念一、信源编码的相关概念信源符号sip(si)码1码2s1p(s1)=1/2000s2p(s2)=1/40101s3p(s3)=1/810001s4p(s4)=1/811111例例:5.1第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码2.信源编码器模型（续2）一、信源编码的相关概念一、信源编码的相关概念第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码3.N次扩展码一、信源编码的相关概念一、信源编码的相关概念第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码3.N次扩展码（续1）二次扩展信源符号 二次扩展码码字一、信源编码的相关概念一、信源编码的相关概念l编码器输出的码符号序列 称为码字码字；长度 称为码字长度，简称码长码长；全体码字的集合C称为码码。l若码符号集合为X=0,1，则所得的码字都是二元序列，称为二元码二元码。第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码4.关于编码的一些术语一、信源编码的相关概念一、信源编码的相关概念l将信源符号集中的每个信源符号 固定的映射成某一个码字 ，这样的码称为分组码分组码。l若一个码中所有码字的码长都相等，则称为定长码定长码；否则为变长码变长码。第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码5.奇异性若一个码中所有码字互不相同，则称为非奇异码非奇异码；否则为奇异码奇异码。信源符号si码1码2s1s2s3s401100110100001一、信源编码的相关概念一、信源编码的相关概念第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码6.唯一可译性l 若任意一串有限长的码符号序列只能被唯一地译为对应的信源符号序列，则称此码为唯一可译码唯一可译码。信源符号si码1码2码3s1s2s3s401100110100001010110111一、信源编码的相关概念一、信源编码的相关概念l 唯一可译码应当满足的条件码字与信源符号一一对应2)不同的信源符号序列对应不同的码字序列1)6.唯一可译性（续1）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码一、信源编码的相关概念一、信源编码的相关概念第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码6.唯一可译性（续2）例1：1)奇异码11译码奇异码一定不是唯一可译码一、信源编码的相关概念一、信源编码的相关概念第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码6.唯一可译性（续3）2)非奇异码0 1 00 00 1 00 10 00 0 1 0译码译码一、信源编码的相关概念一、信源编码的相关概念第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码6.唯一可译性（续4）3)等长码非奇异码0 0 0 1 1 0 1 1唯一可译码译码一、信源编码的相关概念一、信源编码的相关概念第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码6.唯一可译性（续5）4)唯一可译码1 001为非即时码1 1 0 1 0 0 1 0 0 0一、信源编码的相关概念一、信源编码的相关概念第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码6.唯一可译性（续6）5)1 0 1 0 0 1 0 0 0 1唯一可译码0 1即时为即时码任何一个码字不是其它码字的前缀任何一个码字不是其它码字的前缀一、信源编码的相关概念一、信源编码的相关概念第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码7.即时码l 若某个唯一可译码在接收到一个完整的码字时无需参考后续的码符号就能立即译码，则称此码为即时码即时码。l 问题：1)判断下面的码是否即时码？010110111 2)等长码是否即时码？一、信源编码的相关概念一、信源编码的相关概念第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码7.即时码（续1）l 唯一可译码成为即时码的充要条件唯一可译码成为即时码的充要条件：定理定理5.1 一个唯一可译码成为即时码的充要条件是其一个唯一可译码成为即时码的充要条件是其中任何一个码字都不是其他码字的前缀。中任何一个码字都不是其他码字的前缀。一、信源编码的相关概念一、信源编码的相关概念信源概率pi 编 码编 码编 码编 码编 码s11/2000000s21/401011001s31/810100110011s41/811101111101117.即时码（续2）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码一、信源编码的相关概念一、信源编码的相关概念消息000010010000010011100001010110001110011010100100011111101111101011011011100010011101101111001101010111111117.即时码（续3）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码一、信源编码的相关概念一、信源编码的相关概念第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码8.即时码的构造方法l用树图法可以方便地构造即时码。树中每个中间节点都伸出1至r个树枝，将所有的码字都安排在终端将所有的码字都安排在终端节点上节点上就可以得到即时码。一、信源编码的相关概念一、信源编码的相关概念8.即时码的构造方法（续1）0101010100010 011一阶节点二阶节点三阶节点0101100110101111第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码一、信源编码的相关概念一、信源编码的相关概念第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码8.即时码的构造方法（续2）一、信源编码的相关概念一、信源编码的相关概念用树图法可以方便地构造即时码。树中每个中间节点都伸出1至r个树枝，将所有的码字都安排在终端节点上就可以得到即时码。每个中间节点都正好有r个分枝的树称为整树（满整树（满树）。树）。所有终端节点的阶数都相等的树为完全树完全树第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码8.即时码的构造方法（续3）一、信源编码的相关概念一、信源编码的相关概念第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码图2 各类码之间的关系8.即时码的构造方法（续4）一、信源编码的相关概念一、信源编码的相关概念1.唯一可译定长码存在的条件l对于定长码，非奇异码一定是唯一可译码。l所谓非奇异码，即信源符号集中的每一个信源符号与码中的某一个码字 一一对应。l设信源符号集中共有 个符号，码符号集中共有 种码元，定长码码长为 ,则要满足非奇异性必然有该条件是必要条件，而不是充分条件。第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码二、定长码及定长信源编码定理二、定长码及定长信源编码定理1.唯一可译定长码存在的条件（续1）l如果对N次扩展信源 进行定长编码，要满足非奇异性，须满足条件 其中其中当r=2 时，第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码二、定长码及定长信源编码定理二、定长码及定长信源编码定理当N=1时，1.唯一可译定长码存在的条件（续2）例2：英文字母表中，每一字母用定长编码转换成二进制表示，码字的最短长度是多少？解：解：信源符号数信源符号数码符号数码符号数第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码二、定长码及定长信源编码定理二、定长码及定长信源编码定理 p(sj)I(sj)/N s1=s1 s1 1/4 1s2=s1 s2 1/8 1.5s3=s1 s3 1/16 2s4=s1 s4 1/16 2s5=s2 s1 1/8 1.5s6=s2 s2 1/16 2s7=s2 s3 1/32 2.5s8=s2 s4 1/32 2.5 p(sj)I(sj)/Ns9=s3 s1 1/16 2s10=s3 s2 1/32 2.5s11=s3 s3 1/64 3s12=s3 s4 1/64 3s13=s4 s1 1/16 2s14=s4 s2 1/32 2.5s15=s4 s3 1/64 3s16=s4 s4 1/64 3N=2 H(S)=1.75 第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码2.定长信源编码定理二、定长码及定长信源编码定理二、定长码及定长信源编码定理l定理5.3.1 设离散平稳无记忆信源的熵为H(S),若对N次扩展信源 进行定长编码，则对于任意 0，只要满足 则当N足够大时，可实现几乎无失真编码，即译码错误概率 PE 为任意小；反之，则不可能实现无失真编码，如果 当N足够大时，译码错误概率 PE 为1。2.定长信源编码定理（续1）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码l 定长编码定理同样也适用于离散平稳有记忆信源，差别是要将信源熵 改为极限熵 。二、定长码及定长信源编码定理二、定长码及定长信源编码定理l可以验证，对定长信源编码来说，要想实现无失真信源编码，N常常要取非常大的值。这在实际应用中很难实现。2.定长信源编码定理（续2）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码当r=2时二、定长码及定长信源编码定理二、定长码及定长信源编码定理第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码2.定长信源编码定理（续3）定义：为编码信息率编码信息率 定义：为编码效率编码效率。比特/信源符号比特/信源符号比特比特/信源符号信源符号二、定长码及定长信源编码定理二、定长码及定长信源编码定理第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码2.定长信源编码定理（续4）根据编码效率的定义，最佳编码效率为：在已知方差和信源熵的条件下，信源符号序列长度N与最佳编码效率和允许编码错误概率 之间的关系为：二、定长码及定长信源编码定理二、定长码及定长信源编码定理例 5.2如果对信源符号采用定长二元编码，要求编码效率=90%，允许错误概率 ，求所需信源序列长度N。例5.3 设离散无记忆信源 ,要求 求N。第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码2.定长信源编码定理（续5）二、定长码及定长信源编码定理二、定长码及定长信源编码定理1.Kraft不等式和McMillan不等式第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码Kraft定理：即时码存在的充要条件是McMillan定理：唯一可译码存在的充要条件是三、变长码及变长信源编码定理三、变长码及变长信源编码定理1.Kraft不等式和McMillan不等式（续1）l 任何一个唯一可译码均可用一个相同码长的即时码来代替。l 上述定理是存在性定理：当满足Kraft（或McMillan）不等式时，必然可以构造出即时码（或唯一可译码），否则不能构造出即时码（或唯一可译码）。该定理不能作为判断一种码是否是即时码（或唯一可译码）的判断依据。第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码三、变长码及变长信源编码定理三、变长码及变长信源编码定理信源符号si符号出现的概率码1码2码3码4s10011s211101001s30000100001s41101100000011.Kraft不等式和McMillan不等式（续2）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码1/21/41/81/8三、变长码及变长信源编码定理三、变长码及变长信源编码定理2.变长唯一可译码判别方法步骤：步骤：1.构造F1：考考察察 C中中所所有有码码字字，如如果果一一个个码码字字是是另另一一个个码码字字的的前前缀，则将后缀作为缀，则将后缀作为F1 中的元素。中的元素。2.构造 ：将将C 与与 比比较较。如如果果 C 中中有有码码字字是是 中中元元素素的的前前缀缀，则则将将相相应应的的后后缀缀放放入入 中中；同同样样 中中若若有有元元素素是是 C 中码字的前缀，也将相应的后缀放入中码字的前缀，也将相应的后缀放入 中。中。3.检验 ：1)如果如果 是空集，则断定码是空集，则断定码 C 是唯一可译码，退出循环；是唯一可译码，退出循环；2)反反之之，如如果果 中中的的某某个个元元素素与与 C中中的的某某个个元元素素相相同同，则则断断定定码码 不是唯一可译码，退出循环。不是唯一可译码，退出循环。3)如果上述两个条件都不满足，则返回步骤如果上述两个条件都不满足，则返回步骤2。第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码三、变长码及变长信源编码定理三、变长码及变长信源编码定理2.变长唯一可译码判别方法（续）C F1 F2 F3 F4 F5a d eb de b adc bb cde bcdeadabbbaddebbbcde例例5.45.4：结论：结论：F5中包含了中包含了C中的元素，因此该变长码不是唯一可译码。中的元素，因此该变长码不是唯一可译码。第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码问题：判断 C=1,10,100,1000是否是唯一可译码？三、变长码及变长信源编码定理三、变长码及变长信源编码定理3.紧致码平均码长界限定理码符号/信源符号l 平均码长l 对于给定的信源和码符号集，若有一个唯一可译码，其平均长度 小于所有其他唯一可译码，则称这种码为紧致码紧致码或最佳码最佳码。第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码三、变长码及变长信源编码定理三、变长码及变长信源编码定理3.紧致码平均码长界限定理（续1）l 紧致码平均码长界限定理紧致码平均码长界限定理：设离散无记忆信源的熵为设离散无记忆信源的熵为H(S)，用，用r 个码符号进行个码符号进行编码，则总可找到一种无失真信源编码，构成唯一可译编码，则总可找到一种无失真信源编码，构成唯一可译码，使其平均码长满足：码，使其平均码长满足：第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码三、变长码及变长信源编码定理三、变长码及变长信源编码定理定理定理5.6 紧致码平均码长界限定理紧致码平均码长界限定理3.紧致码平均码长界限定理（续2）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码三、变长码及变长信源编码定理三、变长码及变长信源编码定理3.紧致码平均码长界限定理（续3）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码平均码长=下限值时三、变长码及变长信源编码定理三、变长码及变长信源编码定理3.紧致码平均码长界限定理（续4）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码三、变长码及变长信源编码定理三、变长码及变长信源编码定理4.无失真变长信源编码定理l 香农第一定理（变长无失真信源编码定理）：设离散无记忆信源的熵为 H(S)，它的N次扩展信源为 ，对扩展信源 进行编码。总可以找到一种编码方法，构成唯一可译码，使平均码长满足：l 当 时，有第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码三、变长码及变长信源编码定理三、变长码及变长信源编码定理证明：4.无失真变长信源编码定理（续1）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码三、变长码及变长信源编码定理三、变长码及变长信源编码定理l 把香农第一定理推广到一般离散信源，有并且4.无失真变长信源编码定理（续2）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码三、变长码及变长信源编码定理三、变长码及变长信源编码定理bit/信源符号码符号/信源符号=bit/码符号信息传输率(码率)r进制单位/信源符号码符号/信源符号4.无失真变长信源编码定理（续3）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码编码效率三、变长码及变长信源编码定理三、变长码及变长信源编码定理 例5.5 设离散无记忆信源 ,求 R、及扩展信源的R、。4.无失真变长信源编码定理（续4）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码三、变长码及变长信源编码定理三、变长码及变长信源编码定理第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码1.香农码编码步骤如下：编码步骤如下：1.将信源符号按概率从大到小顺序排列，为方便起见，令将信源符号按概率从大到小顺序排列，为方便起见，令 2.按下式计算第按下式计算第i个符号对应的码字的码长（要取整）个符号对应的码字的码长（要取整）3.计算第计算第i个符号的累加概率个符号的累加概率4.将累加概率变换成二进制小数，取小数点后将累加概率变换成二进制小数，取小数点后li位数作为第位数作为第i个符号的码字。个符号的码字。四、变长码的编码方法四、变长码的编码方法1.香农码（续1）例5.6 对如下信源编码:第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法信源符号符号概率累加概率码长码字s10.2002.343000s20.190.22.413001s30.180.392.483011s40.170.572.563100s50.150.742.743101s60.100.593.3441110s70.010.996.66711111101.香农码（续2）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法1.香农码（续3）平均码长平均码长信源熵信源熵结论：结论：1)2)香农码是即时码，但冗余度稍大，不是最佳码。香农码是即时码，但冗余度稍大，不是最佳码。编码效率编码效率第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法2.香农-费诺-埃利斯编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法1、不用对信源符号按概率大小排序。2、直接计算修正的累加概率3、计算码长 2.香农-费诺-埃利斯编码（续1）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法3.Huffman码1.将信源符号按概率从大到小的顺序排列，令将信源符号按概率从大到小的顺序排列，令2.给两个概率最小的信源符号给两个概率最小的信源符号sn-1和和sn各分配一个码元各分配一个码元“0”和和“1”，并将这，并将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含的概率，结果得到一个只包含(n1)个信源符号的新信源。称为个信源符号的新信源。称为信源的第信源的第一次缩减信源一次缩减信源，用，用S1表示。表示。3.将缩减信源将缩减信源S1的符号仍按概率从大到小顺序排列，的符号仍按概率从大到小顺序排列，重复步骤重复步骤2，得到只含，得到只含(n2)个符号的缩减信源个符号的缩减信源S2。4.重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。得到各信源符号所对应的码字。编码步骤如下：编码步骤如下：第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法3.Huffman码（续1）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法010101013.Huffman码（续2）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法01010101码符号/信源符号3.Huffman码（续3）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法01010101码符号/信源符号3.Huffman码（续4）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法讨论：1)两种方法平均码长相等。2)计算两种码的码长方差：第二种方法编出的码码字长度变化较小，便于实现。3.Huffman码（续5）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法3.Huffman码（续6）离散信源如下:解：编码过程略，Huffman编码结果如下：第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法3.Huffman码（续7）l平均码长为平均码长为l信源熵为信源熵为l编码效率为编码效率为第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法3.Huffman码（续8）注意注意：霍夫曼编码后的码字不是惟一的。：霍夫曼编码后的码字不是惟一的。1 1）每次对缩减信源两个概率最小的符号）每次对缩减信源两个概率最小的符号分配分配“0”“0”或或“1”“1”码元码元是任意的是任意的，所以可得到不同的码字。不同的码元分配，得到的，所以可得到不同的码字。不同的码元分配，得到的具体码字不同，但码长具体码字不同，但码长li不变，平均码长也不变，所以没有本不变，平均码长也不变，所以没有本质区别；质区别；2 2）缩减信源时，）缩减信源时，若合并后的概率与其他概率相等，这几个概率若合并后的概率与其他概率相等，这几个概率的次序可任意排列的次序可任意排列，但得到的码字不相同，但得到的码字不相同,对应的码长也不相对应的码长也不相同同,但平均码长也不变。但平均码长也不变。第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法定理5.8 霍夫曼码是紧致码01010101101000001100013.Huffman码（续9）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法假定缩减后信源为 共有m个元素。缩减后信源为 共有m+1个元素。其中第k个元素码长 ,概率为最短则缩减前4.r 元霍夫曼码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法0120120124.r 元霍夫曼码（续1）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法4.r 元霍夫曼码（续2）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法5.Fano码编码步骤如下：1.将概率按从大到小的顺序排列，令2.将依次排列的信源符号按概率分成两组，使每组概率和尽可能接近或相等。3.给每一组分配一位码元“0”或“1”。4.将每一分组再按同样方法划分，重复步骤2和3，直至概率不再可分为止。第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法5.Fano码（续1）例第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法5.Fano码（续2）解：信源信源符号符号符号符号概率概率第一次第一次分组分组第一次第一次分组分组第一次第一次分组分组第一次第一次分组分组码字码字码长码长0.20000020.191001030.18101130.17101020.151011030.1010111040.01111114第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法5.Fano码（续3）l平均码长为平均码长为l信源熵为信源熵为l编码效率为编码效率为第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法5.Fano码（续4）四、变长码的编码方法四、变长码的编码方法香农码、Huffman码、Fano码总结l香农码、费诺码、霍霍夫曼码都考虑了信源的统计特性，使经常出现的信源符号对应较短的码字，使信源的平均码长缩短，从而实现了对信源的压缩。l香农码编码结果唯一，但在很多情况下编码效率不是很高。l费诺码和霍霍夫曼码的编码方法都不唯一。l费诺码比较适合于对分组概率相等或接近的信源编码。l霍霍夫曼码对信源的统计特性没有特殊要求，编码效率比较高，对编码设备的要求也比较简单，因此综合性能优于香农码和费诺码。第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法首先是速率匹配问题其次是差错扩散问题第三是霍霍夫曼码需要查表来进行编译码。信源统计特性未知时，怎么办？可采用所谓通用编码的方法。Huffman码编码应用中的一些问题第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码01 00 00 100 10 00 01 0译码译码四、变长码的编码方法四、变长码的编码方法第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码五、实用的无失真信源编码方法五、实用的无失真信源编码方法游程编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码五、实用的无失真信源编码方法五、实用的无失真信源编码方法游程编码（续1）BBBBBBBBBBXXXXXXXXXAAAAAAUUUUUUUUUUUUU 符号码符号码标识码标识码游程长度游程长度编码：B#10X#9A#6U#13 对于黑、白二值文件:1、黑白游程总是交替出现，可以规定第一游程为白游程。2、不同游程长度出现的概率不同，对游程长度进行编码采用霍夫曼编码，概率大的编长码，概率小的编短码。第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码五、实用的无失真信源编码方法五、实用的无失真信源编码方法游程编码（续2）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码五、实用的无失真信源编码方法五、实用的无失真信源编码方法l73白游程=64+9：1101110100l001101010100101101010110111101100001100110011000000000001 0白1黑15白4黑77白5黑 压缩比=1728/47=36.7:1 结尾码组合基干码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码五、实用的无失真信源编码方法五、实用的无失真信源编码方法算术编码 10001001 第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码五、实用的无失真信源编码方法五、实用的无失真信源编码方法算术编码（续1）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码五、实用的无失真信源编码方法五、实用的无失真信源编码方法算术编码（续2）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码五、实用的无失真信源编码方法五、实用的无失真信源编码方法LZW编码 输入符号序列：输入符号序列：ABCABDABCAAAABBBABCABCA 前缀 尾字符序号0X0000X0410X0FF0X1000X1010X1020X1030X1040X1050X1060X1070X1080X1090X10A0X10B0XFFFQ(FFF)Q(FFF)AQ(FFF)A(041)BB CC AAB DD AAB CCA AA AAA BB BBB AABC A第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码五、实用的无失真信源编码方法五、实用的无失真信源编码方法LZW编码（续1）
