《第五章无失真信源编码精选文档.ppt》由会员分享，可在线阅读，更多相关《第五章无失真信源编码精选文档.ppt（86页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第五章无失真信源编码本讲稿第一页，共八十六页第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码l 信源编码的作用：信源编码的作用：使信源适合于信道的传输，用信道能传输的符号来代表信源发出使信源适合于信道的传输，用信道能传输的符号来代表信源发出的消息；的消息；在不失真或允许一定失真的条件下，用尽可能少的符号在不失真或允许一定失真的条件下，用尽可能少的符号来传递信源消息，提高信息传输率。来传递信源消息，提高信息传输率。l 以提高通信有效性为目的以提高通信有效性为目的。通常通过。通常通过压缩信源的冗余度压缩信源的冗余度来实来实现。采用的一般方法是压缩每个信源符号
2、的平均码长。现。采用的一般方法是压缩每个信源符号的平均码长。1.信源编码概述一、信源编码的相关概念一、信源编码的相关概念本讲稿第二页，共八十六页第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码l 信源编码理论是信息论的一个重要分支，其理论基础是信信源编码理论是信息论的一个重要分支，其理论基础是信源编码的两个定理：源编码的两个定理：无失真信源编码定理无失真信源编码定理限失真信源编码定理限失真信源编码定理l 本章主要介绍本章主要介绍无失真信源编码无失真信源编码，它实质上是一种统计匹配，它实质上是一种统计匹配编码，根据信源的不同概率分布而选用与之相匹配的码。编
3、码，根据信源的不同概率分布而选用与之相匹配的码。1.信源编码概述（续1）一、信源编码的相关概念一、信源编码的相关概念本讲稿第三页，共八十六页第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码l 信源的统计剩余度主要决定于以下两个因素信源的统计剩余度主要决定于以下两个因素：1）无记忆信源中，符号概率分布的非均匀性；）无记忆信源中，符号概率分布的非均匀性；2）有记忆信源中，符号间的相关性及）有记忆信源中，符号间的相关性及符号概率分布的非均符号概率分布的非均匀性匀性。1.信源编码概述（续2）l怎样压缩信源的冗余度？怎样压缩信源的冗余度？1)去除码符号间的相关性。
4、去除码符号间的相关性。2)使码符号等概分布。使码符号等概分布。一、信源编码的相关概念一、信源编码的相关概念本讲稿第四页，共八十六页第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码2.信源编码器模型信宿信道信源编码器译码器YXSSl 信源编码：将信源符号序列按一定的数学规律映射成码符号序列的过程。图1 信源编码器模型一、信源编码的相关概念一、信源编码的相关概念本讲稿第五页，共八十六页第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码l 将信源符号集中的符号（或者长为N的信源符号序列）映射成由码符号 组成的长度为 的一一
5、对应的码符号序列 。编码器码字2.信源编码器模型（续1）一、信源编码的相关概念一、信源编码的相关概念本讲稿第六页，共八十六页信源符号sip(si)码1码2s1p(s1)=1/2000s2p(s2)=1/40101s3p(s3)=1/810001s4p(s4)=1/811111例例:5.1第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码2.信源编码器模型（续2）一、信源编码的相关概念一、信源编码的相关概念本讲稿第七页，共八十六页第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码3.N次扩展码一、信源编码的相关概念一、信
6、源编码的相关概念本讲稿第八页，共八十六页第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码3.N次扩展码（续1）二次扩展信源符号 二次扩展码码字一、信源编码的相关概念一、信源编码的相关概念本讲稿第九页，共八十六页l编码器输出的码符号序列 称为码字码字；长度 称为码字长度，简称码长码长；全体码字的集合C称为码码。l若码符号集合为X=0,1，则所得的码字都是二元序列，称为二元码二元码。第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码4.关于编码的一些术语一、信源编码的相关概念一、信源编码的相关概念l将信源符号集中的每个信
7、源符号 固定的映射成某一个码字 ，这样的码称为分组码分组码。l若一个码中所有码字的码长都相等，则称为定长码定长码；否则为变长码变长码。本讲稿第十页，共八十六页第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码5.奇异性若一个码中所有码字互不相同，则称为非奇异码非奇异码；否则为奇异码奇异码。信源符号si码1码2s1s2s3s401100110100001一、信源编码的相关概念一、信源编码的相关概念本讲稿第十一页，共八十六页第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码6.唯一可译性l 若任意一串有限长的码符号序列只能
8、被唯一地译为对应的信源符号序列，则称此码为唯一可译码唯一可译码。信源符号si码1码2码3s1s2s3s401100110100001010110111一、信源编码的相关概念一、信源编码的相关概念本讲稿第十二页，共八十六页l 唯一可译码应当满足的条件码字与信源符号一一对应2)不同的信源符号序列对应不同的码字序列1)6.唯一可译性（续1）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码一、信源编码的相关概念一、信源编码的相关概念本讲稿第十三页，共八十六页第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码6.唯一可译性（续
9、2）例1：1)奇异码11译码奇异码一定不是唯一可译码一、信源编码的相关概念一、信源编码的相关概念本讲稿第十四页，共八十六页第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码6.唯一可译性（续3）2)非奇异码01 00 00 100 10 00 01 0译码译码一、信源编码的相关概念一、信源编码的相关概念本讲稿第十五页，共八十六页第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码6.唯一可译性（续4）3)等长码非奇异码0 0 0 1 1 0 1 1唯一可译码译码一、信源编码的相关概念一、信源编码的相关概念本讲稿第十六页，
10、共八十六页第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码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即时为即时码任何一个码字不是其它码字的前缀任何一个码字不是其它码字的前缀一、信源编码的相关概念一、信源编码的相关概念本讲稿第十八页，共八十六页第五章：无失真信源编码第五章
11、：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码7.即时码l 若某个唯一可译码在接收到一个完整的码字时无需参考后续的码符号就能立即译码，则称此码为即时码即时码。l 问题：1)判断下面的码是否即时码？010110111 2)等长码是否即时码？一、信源编码的相关概念一、信源编码的相关概念本讲稿第十九页，共八十六页第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码7.即时码（续1）l 唯一可译码成为即时码的充要条件唯一可译码成为即时码的充要条件：定理定理5.1 一个唯一可译码成为即时码的充要条件是其中一个唯一可译码成为即时码的充要条件是其中任何一个码
12、字都不是其他码字的前缀。任何一个码字都不是其他码字的前缀。一、信源编码的相关概念一、信源编码的相关概念本讲稿第二十页，共八十六页信源概率pi 编 码编码编 码编 码编码s11/2000000s21/401011001s31/810100110011s41/811101111101117.即时码（续2）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码一、信源编码的相关概念一、信源编码的相关概念本讲稿第二十一页，共八十六页消息0000100100000100111000010101100011100110101001000111111011111010110
13、11011100010011101101111001101010111111117.即时码（续3）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码一、信源编码的相关概念一、信源编码的相关概念本讲稿第二十二页，共八十六页第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码8.即时码的构造方法l用树图法可以方便地构造即时码。树中每个中间节点都伸出1至r个树枝，将所有的码字都安排在终端节点上将所有的码字都安排在终端节点上就可以得到即时码。一、信源编码的相关概念一、信源编码的相关概念本讲稿第二十三页，共八十六页8.即时码的构造
14、方法（续1）0101010100010011一阶节点二阶节点三阶节点0101100110101111第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码一、信源编码的相关概念一、信源编码的相关概念本讲稿第二十四页，共八十六页第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码8.即时码的构造方法（续2）一、信源编码的相关概念一、信源编码的相关概念本讲稿第二十五页，共八十六页用树图法可以方便地构造即时码。树中每个中间节点都伸出1至r个树枝，将所有的码字都安排在终端节点上就可以得到即时码。每个中间节点都正好有r个分枝的树称为整
15、树（满树）。整树（满树）。所有终端节点的阶数都相等的树为完全树完全树第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码8.即时码的构造方法（续3）一、信源编码的相关概念一、信源编码的相关概念本讲稿第二十六页，共八十六页第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码图2 各类码之间的关系8.即时码的构造方法（续4）一、信源编码的相关概念一、信源编码的相关概念本讲稿第二十七页，共八十六页1.唯一可译定长码存在的条件l对于定长码，非奇异码一定是唯一可译码。l所谓非奇异码，即信源符号集中的每一个信源符号与码中的某一个码字
16、一一对应。l设信源符号集中共有 个符号，码符号集中共有 种码元，定长码码长为 ,则要满足非奇异性必然有该条件是必要条件，而不是充分条件。该条件是必要条件，而不是充分条件。第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码二、定长码及定长信源编码定理二、定长码及定长信源编码定理本讲稿第二十八页，共八十六页1.唯一可译定长码存在的条件（续1）l如果对N次扩展信源 进行定长编码，要满足非奇异性，须满足条件 其中当r=2 时，第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码二、定长码及定长信源编码定理二、定长码及定长信源编码
17、定理当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=
18、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次扩
19、展信源 进行定长编码，则对于任意 0，只要满足 则当N足够大时，可实现几乎无失真编码，即译码错误概率 PE 为任意小；反之，则不可能实现无失真编码，如果 当N足够大时，译码错误概率 PE 为1。2.定长信源编码定理（续1）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码l 定长编码定理同样也适用于离散平稳有记忆信源，差别是要将信源熵 改为极限熵 。二、定长码及定长信源编码定理二、定长码及定长信源编码定理本讲稿第三十二页，共八十六页l可以验证，对定长信源编码来说，要想实现无失真信源编码，N常常要取非常大的值。这在实际应用中很难实现。2.定长信源编码定理（续
20、2）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码当r=2时二、定长码及定长信源编码定理二、定长码及定长信源编码定理本讲稿第三十三页，共八十六页第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码2.定长信源编码定理（续3）定义：为编码信息率编码信息率 定义：为编码效率编码效率。比特/信源符号比特/信源符号比特比特/信源符号信源符号二、定长码及定长信源编码定理二、定长码及定长信源编码定理本讲稿第三十四页，共八十六页第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码2.定长信源编码
21、定理（续4）根据编码效率的定义，最佳编码效率为：在已知方差和信源熵的条件下，信源符号序列长度N与最佳编码效率和允许编码错误概率 之间的关系为：二、定长码及定长信源编码定理二、定长码及定长信源编码定理本讲稿第三十五页，共八十六页例 5.2如果对信源符号采用定长二元编码，要求编码效率=90%，允许错误概率 ，求所需信源序列长度N。例5.3 设离散无记忆信源 ,要求 求N。第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码2.定长信源编码定理（续5）二、定长码及定长信源编码定理二、定长码及定长信源编码定理本讲稿第三十六页，共八十六页1.Kraft不等式和McMi
22、llan不等式第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码Kraft定理：即时码存在的充要条件是McMillan定理：唯一可译码存在的充要条件是三、变长码及变长信源编码定理三、变长码及变长信源编码定理本讲稿第三十七页，共八十六页1.Kraft不等式和McMillan不等式（续1）l 任何一个唯一可译码均可用一个相同码长的即时码来代替。l 上述定理是存在性定理：当满足Kraft（或McMillan）不等式时，必然可以构造出即时码（或唯一可译码），否则不能构造出即时码（或唯一可译码）。该定理不能作为判断一种码是否是即时码（或唯一可译码）的判断依据。第五章
23、：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码三、变长码及变长信源编码定理三、变长码及变长信源编码定理本讲稿第三十八页，共八十六页信源符号si符号出现的概率码1码2码3码4s10011s211101001s30000100001s41101100000011.Kraft不等式和McMillan不等式（续2）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码1/21/41/81/8三、变长码及变长信源编码定理三、变长码及变长信源编码定理本讲稿第三十九页，共八十六页2.变长唯一可译码判别方法步骤：1.构构造造F1：考察 C中
24、所有码字，如果一个码字是另一个码字的前缀，则将后缀作为F1 中的元素。2.构构造造 ：将C 与 比较。如果 C 中有码字是 中元素的前缀，则将相应的后缀放入 中；同样 中若有元素是 C 中码字的前缀，也将相应的后缀放入 中。3.检验检验 ：1)如果 是空集，则断定码 C 是唯一可译码，退出循环；2)反之，如果 中的某个元素与 C中的某个元素相同，则断定码 不是唯一可译码，退出循环。3)如果上述两个条件都不满足，则返回步骤2。第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码三、变长码及变长信源编码定理三、变长码及变长信源编码定理本讲稿第四十页，共八十六页2
25、.变长唯一可译码判别方法（续）C F1 F2 F3 F4 F5a d eb de b adc bb cde bcdeadabbbaddebbbcde例5.4：结论：F5中包含了C中的元素，因此该变长码不是唯一可译码。第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码问题：判断 C=1,10,100,1000是否是唯一可译码？三、变长码及变长信源编码定理三、变长码及变长信源编码定理本讲稿第四十一页，共八十六页3.紧致码平均码长界限定理码符号/信源符号l 平均码长l 对于给定的信源和码符号集，若有一个唯一可译码，其平均长度 小于所有其他唯一可译码，则称这种码为
26、紧致码紧致码或最最佳码佳码。第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码三、变长码及变长信源编码定理三、变长码及变长信源编码定理本讲稿第四十二页，共八十六页3.紧致码平均码长界限定理（续1）l 紧致码平均码长界限定理紧致码平均码长界限定理：设离散无记忆信源的熵为设离散无记忆信源的熵为H(S)，用，用r 个码符号进行编个码符号进行编码，则总可找到一种无失真信源编码，构成唯一可译码，码，则总可找到一种无失真信源编码，构成唯一可译码，使其平均码长满足：使其平均码长满足：第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码
27、三、变长码及变长信源编码定理三、变长码及变长信源编码定理本讲稿第四十三页，共八十六页定理定理5.6 紧致码平均码长界限定理紧致码平均码长界限定理3.紧致码平均码长界限定理（续2）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码三、变长码及变长信源编码定理三、变长码及变长信源编码定理本讲稿第四十四页，共八十六页3.紧致码平均码长界限定理（续3）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码平均码长=下限值时三、变长码及变长信源编码定理三、变长码及变长信源编码定理本讲稿第四十五页，共八十六页3.紧致码平均码长界限定理
28、（续4）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码三、变长码及变长信源编码定理三、变长码及变长信源编码定理本讲稿第四十六页，共八十六页4.无失真变长信源编码定理l 香农第一定理（变长无失真信源编码定理）：设离散无记忆信源的熵为 H(S)，它的N次扩展信源为 ，对扩展信源 进行编码。总可以找到一种编码方法，构成唯一可译码，使平均码长满足：l 当 时，有第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码三、变长码及变长信源编码定理三、变长码及变长信源编码定理本讲稿第四十七页，共八十六页证明：4.无失真变长信源编码定
29、理（续1）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码三、变长码及变长信源编码定理三、变长码及变长信源编码定理本讲稿第四十八页，共八十六页l 把香农第一定理推广到一般离散信源，有并且4.无失真变长信源编码定理（续2）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码三、变长码及变长信源编码定理三、变长码及变长信源编码定理本讲稿第四十九页，共八十六页bit/信源符号码符号/信源符号=bit/码符号信息传输率(码率)r进制单位/信源符号码符号/信源符号4.无失真变长信源编码定理（续3）第五章：无失真信源编码第五章：无
30、失真信源编码第五章：无失真信源编码第五章：无失真信源编码编码效率三、变长码及变长信源编码定理三、变长码及变长信源编码定理本讲稿第五十页，共八十六页 例5.5 设离散无记忆信源 ,求 R、及扩展信源的R、。4.无失真变长信源编码定理（续4）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码三、变长码及变长信源编码定理三、变长码及变长信源编码定理本讲稿第五十一页，共八十六页第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码1.香农码编码步骤如下：编码步骤如下：1.将信源符号按概率从大到小顺序排列，为方便起见，令将信源符号按
31、概率从大到小顺序排列，为方便起见，令 2.按下式计算第按下式计算第i个符号对应的码字的码长（要取整）个符号对应的码字的码长（要取整）3.计算第计算第i个符号的累加概率个符号的累加概率4.将累加概率变换成二进制小数，取小数点后将累加概率变换成二进制小数，取小数点后li位数作为第位数作为第i个符号个符号的码字。的码字。四、变长码的编码方法四、变长码的编码方法本讲稿第五十二页，共八十六页1.香农码（续1）例5.6 对如下信源编码:第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法本讲稿第五十三页，共八十六页信源符号符号概率
32、累加概率码长码字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)香农码是即时码，但冗余度稍大，不是最佳码。香农码是即时码，但冗余度稍大，不是最佳码。编码效
33、率编码效率第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法本讲稿第五十五页，共八十六页2.香农-费诺-埃利斯编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法1、不用对信源符号按概率大小排序。2、直接计算修正的累加概率3、计算码长 本讲稿第五十六页，共八十六页2.香农-费诺-埃利斯编码（续1）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法本讲稿第五十七页
34、，共八十六页3.Huffman码1.将信源符号按概率从大到小的顺序排列，令将信源符号按概率从大到小的顺序排列，令2.给两个概率最小的信源符号给两个概率最小的信源符号sn-1和和sn各分配一个码元各分配一个码元“0”和和“1”，并将这两个，并将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含结果得到一个只包含(n1)个信源符号的新信源。称为个信源符号的新信源。称为信源的第一次缩减信源信源的第一次缩减信源，用，用S1表示。表示。3.将缩减信源将缩减信源S1的符号仍按概率从大到小顺序排列，
35、的符号仍按概率从大到小顺序排列，重复步骤重复步骤2，得到只含，得到只含(n2)个符个符号的缩减信源号的缩减信源S2。4.重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。源符号所对应的码字。编码步骤如下：编码步骤如下：第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法本讲稿第五十八
36、页，共八十六页3.Huffman码（续1）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法本讲稿第五十九页，共八十六页010101013.Huffman码（续2）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法本讲稿第六十页，共八十六页01010101码符号/信源符号3.Huffman码（续3）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法本讲稿第六十一页
37、，共八十六页01010101码符号/信源符号3.Huffman码（续4）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法本讲稿第六十二页，共八十六页讨论：1)两种方法平均码长相等。2)计算两种码的码长方差：第二种方法编出的码码字长度变化较小，便于实现。3.Huffman码（续5）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法本讲稿第六十三页，共八十六页3.Huffman码（续6）离散信源如下:解：编码过程略，Huffman编码结果如下
38、：第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法本讲稿第六十四页，共八十六页3.Huffman码（续7）l平均码长为平均码长为l信源熵为信源熵为l编码效率为编码效率为第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法本讲稿第六十五页，共八十六页3.Huffman码（续8）注意注意：霍夫曼编码后的码字不是惟一的。：霍夫曼编码后的码字不是惟一的。1 1）每次对缩减信源两个概率最小的符号）每次对缩减信源两个概率最小的符号分配分配“0”“0”或
39、或“1”“1”码元是任意码元是任意的的，所以可得到不同的码字。不同的码元分配，得到的具体码字不，所以可得到不同的码字。不同的码元分配，得到的具体码字不同，但码长同，但码长li不变，平均码长也不变，所以没有本质区别；不变，平均码长也不变，所以没有本质区别；2 2）缩减信源时，）缩减信源时，若合并后的概率与其他概率相等，这几个概率的次序可任若合并后的概率与其他概率相等，这几个概率的次序可任意排列意排列，但得到的码字不相同，但得到的码字不相同,对应的码长也不相同对应的码长也不相同,但平均码长也但平均码长也不变。不变。第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源
40、编码四、变长码的编码方法四、变长码的编码方法本讲稿第六十六页，共八十六页定理5.8 霍夫曼码是紧致码01010101101000001100013.Huffman码（续9）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法假定缩减后信源为 共有m个元素。缩减后信源为 共有m+1个元素。其中第k个元素码长 ,概率为最短则缩减前本讲稿第六十七页，共八十六页4.r 元霍夫曼码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法本讲稿第六十八页，共八
41、十六页0120120124.r 元霍夫曼码（续1）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法本讲稿第六十九页，共八十六页4.r 元霍夫曼码（续2）第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法本讲稿第七十页，共八十六页5.Fano码编码步骤如下：1.将概率按从大到小的顺序排列，令2.将依次排列的信源符号按概率分成两组，使每组概率和尽可能接近或相等。3.给每一组分配一位码元“0”或“1”。4.将每一分组再按同样方法划分，重复步骤2
42、和3，直至概率不再可分为止。第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法本讲稿第七十一页，共八十六页5.Fano码（续1）例第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法本讲稿第七十二页，共八十六页5.Fano码（续2）解：信源符号符号概率第一次分组第一次分组第一次分组第一次分组码字码长0.20000020.191001030.18101130.17101020.151011030.1010111040.01111114第五章：无
43、失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法本讲稿第七十三页，共八十六页5.Fano码（续3）l平均码长为平均码长为l信源熵为信源熵为l编码效率为编码效率为第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法本讲稿第七十四页，共八十六页5.Fano码（续4）四、变长码的编码方法四、变长码的编码方法本讲稿第七十五页，共八十六页香农码、Huffman码、Fano码总结l香农码、费诺码、霍霍夫曼码都考虑了信源的统计特性，使经常出现的信源符号对应较短的码
44、字，使信源的平均码长缩短，从而实现了对信源的压缩。l香农码编码结果唯一，但在很多情况下编码效率不是很高。l费诺码和霍霍夫曼码的编码方法都不唯一。l费诺码比较适合于对分组概率相等或接近的信源编码。l霍霍夫曼码对信源的统计特性没有特殊要求，编码效率比较高，对编码设备的要求也比较简单，因此综合性能优于香农码和费诺码。第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码四、变长码的编码方法四、变长码的编码方法本讲稿第七十六页，共八十六页首先是速率匹配问题其次是差错扩散问题第三是霍霍夫曼码需要查表来进行编译码。信源统计特性未知时，怎么办？可采用所谓通用编码的方法。Hu
45、ffman码编码应用中的一些问题第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码01 00 00 100 10 00 01 0译码译码四、变长码的编码方法四、变长码的编码方法本讲稿第七十七页，共八十六页第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码五、实用的无失真信源编码方法五、实用的无失真信源编码方法游程编码本讲稿第七十八页，共八十六页第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码五、实用的无失真信源编码方法五、实用的无失真信源编码方法游程编码（续1）BBBBBBBBB
46、BXXXXXXXXXAAAAAAUUUUUUUUUUUUU 符号码标识码游程长度编码：B#10X#9A#6U#13 本讲稿第七十九页，共八十六页对于黑、白二值文件:1、黑白游程总是交替出现，可以规定第一游程为白游程。2、不同游程长度出现的概率不同，对游程长度进行编码采用霍夫曼编码，概率大的编长码，概率小的编短码。第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码五、实用的无失真信源编码方法五、实用的无失真信源编码方法游程编码（续2）本讲稿第八十页，共八十六页第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码五、实用的无
47、失真信源编码方法五、实用的无失真信源编码方法l73白游程=64+9：1101110100l001101010100101101010110111101100001100110011000000000001 0白1黑15白4黑77白5黑 压缩比=1728/47=36.7:1 结尾码组合基干码本讲稿第八十一页，共八十六页第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码五、实用的无失真信源编码方法五、实用的无失真信源编码方法算术编码 本讲稿第八十二页，共八十六页10001001 第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信源编码第五章：无失真信
48、源编码五、实用的无失真信源编码方法五、实用的无失真信源编码方法算术编码（续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）本讲稿第八十六页，共八十六页