信息论基础与应用-第五章-无失真信源编码资料课件.ppt

《信息论基础与应用-第五章-无失真信源编码资料课件.ppt》由会员分享，可在线阅读，更多相关《信息论基础与应用-第五章-无失真信源编码资料课件.ppt（86页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、一、信源编码的相关概念一、信源编码的相关概念二、定长码及定长信源编码定理二、定长码及定长信源编码定理三、变长码及变长信源编码定理三、变长码及变长信源编码定理四、变长码的编码方法四、变长码的编码方法五、实用的无失真信源编码方法五、实用的无失真信源编码方法l 信源编码的作用：信源编码的作用： 使信源适合于信道的传输，用信道能传输的符号来代使信源适合于信道的传输，用信道能传输的符号来代表信源发出的消息；表信源发出的消息； 在不失真或允许一定失真的条件下，用尽可能少的符在不失真或允许一定失真的条件下，用尽可能少的符号来传递信源消息，提高信息传输率。号来传递信源消息，提高信息传输率。 l 以提高通信有效

2、性为目的以提高通信有效性为目的。通常通过。通常通过压缩信源的冗余压缩信源的冗余度度来实现。采用的一般方法是压缩每个信源符号的平来实现。采用的一般方法是压缩每个信源符号的平均码长均码长。一、信源编码的相关概念一、信源编码的相关概念l 信源编码理论是信息论的一个重要分支，其理论基础信源编码理论是信息论的一个重要分支，其理论基础是信源编码的两个定理：是信源编码的两个定理：无失真信源编码定理无失真信源编码定理限失真信源编码定理限失真信源编码定理l 本章主要介绍本章主要介绍无失真信源编码无失真信源编码，它实质上是一种统，它实质上是一种统计匹配编码，根据信源的不同概率分布而选用与之相计匹配编码，根据信源的

3、不同概率分布而选用与之相匹配的码。匹配的码。 一、信源编码的相关概念一、信源编码的相关概念l 信源的统计剩余度主要决定于以下两个因素信源的统计剩余度主要决定于以下两个因素 ：1）无记忆信源中，符号概率分布的非均匀性；）无记忆信源中，符号概率分布的非均匀性；2）有记忆信源中，符号间的相关性及）有记忆信源中，符号间的相关性及符号概率分布符号概率分布的非均匀性的非均匀性。 l怎样压缩信源的冗余度？怎样压缩信源的冗余度？1) 去除码符号间的相关性。去除码符号间的相关性。2) 使码符号等概分布。使码符号等概分布。一、信源编码的相关概念一、信源编码的相关概念信宿信道信源编码器译码器YXSSl 信源编码：将

4、信源符号序列按一定的数学规律映射成码符号序列的过程。qsssS,2112 ,rXx xx 图1 信源编码器模型一、信源编码的相关概念一、信源编码的相关概念l 将信源符号集中的符号 （或者长为N的信源符号序列）映射成由码符号 组成的长度为 的一一对应的码符号序列 。编码器,.,:21rxxxX码字qsssS,2112liiiiiwx xxixisil12,qCw wwiw一、信源编码的相关概念一、信源编码的相关概念信源符号sip(si)码1码2s1p(s1)=1/2000s2p(s2)=1/40101s3p(s3)=1/810001s4p(s4)=1/811111例例: 5.112341234(

5、 )()()()ssssSp sp sp sp sP 一、信源编码的相关概念一、信源编码的相关概念qsssS,2112,qCw wwisiw12,NNqS s ss,21NqNCwww12Njjjjs sssNqj, 2 , 112Njjjjw wwwqjjjN, 2 , 1,21一、信源编码的相关概念一、信源编码的相关概念二次扩展信源符号 二次扩展码码字(1,2,.,16)jj s(1,2,.,16)jj w221sss331sss4164sss111sss11100www221010www3310010www4164111111www一、信源编码的相关概念一、信源编码的相关概念l编码器输出

6、的码符号序列 称为码字码字；长度 称为码字长度，简称码长码长；全体码字的集合C称为码码。l若码符号集合为X=0,1，则所得的码字都是二元序列，称为二元码二元码。iwisiwil一、信源编码的相关概念一、信源编码的相关概念l将信源符号集中的每个信源符号 固定的映射成某一个码字 ，这样的码称为分组码分组码。 l若一个码中所有码字的码长都相等，则称为定长码定长码； 否则为变长码变长码。若一个码中所有码字互不相同，则称为非奇异码非奇异码；否则为奇异码奇异码。信源符号si码1码2s1s2s3s401100110100001一、信源编码的相关概念一、信源编码的相关概念l 若任意一串有限长的码符号序列只能被

7、唯一地译为对应的信源符号序列，则称此码为唯一可译码唯一可译码。信源符号si码1码2码3s1s2s3s401100110100001010110111一、信源编码的相关概念一、信源编码的相关概念l 唯一可译码应当满足的条件(1,2,., )(1,2,., )iiw iqs iq码字与信源符号一一对应2) 不同的信源符号序列对应不同的码字序列1) 一、信源编码的相关概念一、信源编码的相关概念例1：1)11001104321ssss2s4s奇异码11译码奇异码一定不是唯一可译码一、信源编码的相关概念一、信源编码的相关概念2)01001004321ssss非奇异码14321sssss2334ssss0

8、 1 00 00 1 00 10 00 0 1 0译码译码一、信源编码的相关概念一、信源编码的相关概念3)111001004321ssss等长码非奇异码0 0 0 1 1 0 1 14321ssss唯一可译码译码一、信源编码的相关概念一、信源编码的相关概念4)10001001014321ssss唯一可译码1 023/?ss01为非即时码1 1 0 1 0 0 1 0 0 0一、信源编码的相关概念一、信源编码的相关概念5)00010010114321ssss1 0 1 0 0 1 0 0 0 1唯一可译码0 12s即时为即时码任何一个码字不是其它码字的前缀任何一个码字不是其它码字的前缀一、信源编

9、码的相关概念一、信源编码的相关概念l 若某个唯一可译码在接收到一个完整的码字时无需参考后续的码符号就能立即译码，则称此码为即时码即时码。l 问题： 1) 判断下面的码是否即时码？010110111 2) 等长码是否即时码？一、信源编码的相关概念一、信源编码的相关概念l 唯一可译码成为即时码的充要条件唯一可译码成为即时码的充要条件： 定理定理5.1 一个唯一可译码成为即时码的充要条件是其一个唯一可译码成为即时码的充要条件是其中任何一个码字都不是其他码字的前缀。中任何一个码字都不是其他码字的前缀。一、信源编码的相关概念一、信源编码的相关概念信源概率pi 编 码编码编码编码编码s11/2000000

10、s21/401011001s31/810100110011s41/81110111110111一、信源编码的相关概念一、信源编码的相关概念ABCDEF1s2s3s4s5s6s消息00001001000001001110000101011000111001101010010001111110111110101101101110001001110110111100110101011111111一、信源编码的相关概念一、信源编码的相关概念l用树图法可以方便地构造即时码。树中每个中间节点都伸出1至r个树枝，将所有的码字都安排在终端将所有的码字都安排在终端节点上节点上就可以得到即时码。一、信源编码的相关

11、概念一、信源编码的相关概念2r 0101010100010 011一阶节点二阶节点三阶节点0101100110101111一、信源编码的相关概念一、信源编码的相关概念一、信源编码的相关概念一、信源编码的相关概念 用树图法可以方便地构造即时码。树中每个中间节点都伸出1至r个树枝，将所有的码字都安排在终端节点上就可以得到即时码。 每个中间节点都正好有r个分枝的树称为整树（满整树（满树）。树）。 所有终端节点的阶数都相等的树为完全树完全树一、信源编码的相关概念一、信源编码的相关概念非分组码奇异码非唯一可译码码分组码非奇异码即时码唯一可译码非即时码图2 各类码之间的关系一、信源编码的相关概念一、信源编

12、码的相关概念l对于定长码，非奇异码一定是唯一可译码。l所谓非奇异码，即信源符号集中的每一个信源符号与码中的某一个码字 一一对应。l设信源符号集中共有 个符号， ， 码符号集中共有 种码元， ， 定长码码长为 , 则要满足非奇异性必然有lrq 12,qSs ss,.,:21rxxxXiwislrq该条件是必要条件，而不是充分条件。该条件是必要条件，而不是充分条件。二、定长码及定长信源编码定理二、定长码及定长信源编码定理l如果对N次扩展信源 进行定长编码，要满足非奇异性，须满足条件 NlqrNs其中1212,: ,.,NNrqSXx xx s ssqNllogqllog当r=2 时，二、定长码及定

13、长信源编码定理二、定长码及定长信源编码定理当N=1时，例2：英文字母表中，每一字母用定长编码转换成二进制表示，码字的最短长度是多少？26q 解：2r 信源符号数码符号数lrqloglog264.7loglog2qlrmin5l二、定长码及定长信源编码定理二、定长码及定长信源编码定理 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

14、)/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 二、定长码及定长信源编码定理二、定长码及定长信源编码定理l定理5.3.1 设离散平稳无记忆信源的熵为H(S), 若对N次扩展信源 进行定长编码，则对于任意 0，只要满足 则当N足够大时，可实现几乎无失真编码，即译码错误概率 PE 为任意小；反之，则不可能实现无失真编码， 如果 当N

15、足够大时，译码错误概率 PE 为1。rSHNllog)(rSHNllog2)(Nsl 定长编码定理同样也适用于离散平稳有记忆信源，差别是要将信源熵 改为极限熵 。( )H SH二、定长码及定长信源编码定理二、定长码及定长信源编码定理l可以验证，对定长信源编码来说，要想实现无失真信源编码，N常常要取非常大的值。这在实际应用中很难实现。当r=2时)(SHNl二、定长码及定长信源编码定理二、定长码及定长信源编码定理 定义： 为编码信息率编码信息率 定义： 为编码效率编码效率。rNlSHRSHlog)()(rNlRdeflog 比特/信源符号比特/信源符号比特比特/信源符号信源符号二、定长码及定长信源

16、编码定理二、定长码及定长信源编码定理 根据编码效率的定义，最佳编码效率为： 在已知方差和信源熵的条件下，信源符号序列长度N与最佳编码效率和允许编码错误概率 之间的关系为：)()(SHSH2222( )( )( ) (1)iiD I sD I sNHS )()(SHSH二、定长码及定长信源编码定理二、定长码及定长信源编码定理例 5.204. 005. 006. 007. 010. 010. 018. 04 . 087654321ssssssssPS如果对信源符号采用定长二元编码，要求编码效率=90%，允许错误概率 ，求所需信源序列长度N。 610例5.3 设离散无记忆信源 , 要求 求N。 41

17、4321ssPS51096. 0，( )( )H SH S79.8 10N 74.13 10N 二、定长码及定长信源编码定理二、定长码及定长信源编码定理 Kraft定理：即时码存在的充要条件是 McMillan定理：唯一可译码存在的充要条件是qilir11qilir11三、变长码及变长信源编码定理三、变长码及变长信源编码定理l 任何一个唯一可译码均可用一个相同码长的即时码来代替。l 上述定理是存在性定理： 当满足Kraft（或McMillan）不等式时，必然可以构造出即时码（或唯一可译码），否则不能构造出即时码（或唯一可译码）。 该定理不能作为判断一种码是否是即时码（或唯一可译码）的判断依据。

18、三、变长码及变长信源编码定理三、变长码及变长信源编码定理信 源 符号si符 号 出 现的概率码1码2码3码4s10011s211101001s30000100001s41101100000011/21/41/81/8三、变长码及变长信源编码定理三、变长码及变长信源编码定理步骤：1.构造构造F1 ：考察 C中所有码字，如果一个码字是另一个码字的前缀，则将后缀作为F1 中的元素。2.构造构造 ：将C 与 比较。如果 C 中有码字是 中元素的前缀，则将相应的后缀放入 中；同样 中若有元素是 C 中码字的前缀，也将相应的后缀放入 中。3.检验检验 ： 1)如果 是空集，则断定码 C 是唯一可译码，退出

19、循环； 2)反之，如果 中的某个元素与 C中的某个元素相同，则断定码 不是唯一可译码，退出循环。 3)如果上述两个条件都不满足，则返回步骤2。 C(1)nF n 1nFnF1nF1nF三、变长码及变长信源编码定理三、变长码及变长信源编码定理nFnFnFnFC F1 F2 F3 F4 F5a d eb de b adc bb cde bcdeadabbbaddebbbcde例5.4 ：结论：F5中包含了C中的元素，因此该变长码不是唯一可译码。问题： 判断 C=1,10,100,1000是否是唯一可译码？三、变长码及变长信源编码定理三、变长码及变长信源编码定理qiiilspL1)(码符号/信源符号

20、l 平均码长l 对于给定的信源和码符号集，若有一个唯一可译码，其平均长度 小于所有其他唯一可译码，则称这种码为紧致码紧致码或最佳码最佳码。 L三、变长码及变长信源编码定理三、变长码及变长信源编码定理l 紧致码平均码长界限定理紧致码平均码长界限定理： 设离散无记忆信源的熵为设离散无记忆信源的熵为H(S)，用，用r 个码符号进行个码符号进行编码，则总可找到一种无失真信源编码，构成唯一可编码，则总可找到一种无失真信源编码，构成唯一可译码，使其平均码长满足：译码，使其平均码长满足： ( )( )1loglogH SH SLrr三、变长码及变长信源编码定理三、变长码及变长信源编码定理1log)(log)

21、(rSHLrSH定理定理5.6 紧致码平均码长界限定理紧致码平均码长界限定理0log)(rLSHqiqiiiiirlspspsp11log)()(log)(qiqiliiiirspspsp11log)()(log)(三、变长码及变长信源编码定理三、变长码及变长信源编码定理qiqiliiiirspspsp11log)()(log)(qiilisprspi1)(log)(qiilisprspi1)()(logqilir1log01log rSHLlog)( )(1,2,., )log( )iliirip sriqlp s 平均码长=下限值时三、变长码及变长信源编码定理三、变长码及变长信源编码定理1

22、log)(log)(rSHLrSH1111log( )log( ) 1( )log( )( )( )log( )( )( )log( )( )( )log( )( )( )( )1loglogriiriiriiiiriiqqqqiriiiiriiiiiip slp sp sp sp s lp sp sp sp sp sp s lp sp sp sH SH SLrr 三、变长码及变长信源编码定理三、变长码及变长信源编码定理l 香农第一定理（变长无失真信源编码定理）： 设离散无记忆信源的熵为 H(S) ，它的N次扩展信源为 ，对扩展信源 进行编码。总可以找到一种编码方法，构成唯一可译码，使平均码长

23、满足： ( )( )1loglogNH SLH SrNrNNSNSl 当 时，有N lim( )NrNLHSN三、变长码及变长信源编码定理三、变长码及变长信源编码定理证明：12( )( )1loglog()()1loglog()()1loglog( )( )1loglogNNNNNNNNNH SH SLrrSS SSH SH SLrrH SLH SNrNNrNH SLH SrNrNrSHLNlog)(lim三、变长码及变长信源编码定理三、变长码及变长信源编码定理l 把香农第一定理推广到一般离散信源，有limlogNNLHNrNSSS21S1loglogNHHLrNrN)(SHH并且三、变长码及

24、变长信源编码定理三、变长码及变长信源编码定理LSHXHR)()(bit/信源符号码符号/信源符号= bit/码符号信息传输率(码率)L有效性LSHr)(r进制单位/信源符号码符号/信源符号编码效率( )( )log( )logH SH SRrH SLr三、变长码及变长信源编码定理三、变长码及变长信源编码定理 例5.5 设离散无记忆信源 , 求 R、及扩展信源的R、 。 414321ssPS三、变长码及变长信源编码定理三、变长码及变长信源编码定理编码步骤如下：编码步骤如下：1. 将信源符号按概率从大到小顺序排列，为方便起见，令将信源符号按概率从大到小顺序排列，为方便起见，令 2. 按下式计算第按

25、下式计算第i个符号对应的码字的码长（要取整）个符号对应的码字的码长（要取整）3. 计算第计算第i个符号的累加概率个符号的累加概率4. 将累加概率变换成二进制小数，取小数点后将累加概率变换成二进制小数，取小数点后li位数作为第位数作为第i个符号的码字。个符号的码字。12( )()()qp sp sp s11()iikkPp slog ( )log ( )1iiip slp s 四、变长码的编码方法四、变长码的编码方法例5.6 对如下信源编码:1234567( )0.20 0.19 0.18 0.17 0.15 0.10 0.01SsssssssP S四、变长码的编码方法四、变长码的编码方法信源符

26、号符号概率累加概率码长码字s10.2002.343000s20.190.22.413001s30.180.392.483011s40.170.572.563100s50.150.742.743101s60.100.593.3441110s70.010.996.6671111110iPis()ip sillog()ip s四、变长码的编码方法四、变长码的编码方法 平均码长平均码长1( )3.14/qiiiLp s l码元符号 信源符号信源熵信源熵1( )( )log ( )2.61/qiiiH Sp sp s 比特 信源符号结论：结论： 1) 2) 香农码是即时码，但冗余度稍大，不是最佳码。香农

27、码是即时码，但冗余度稍大，不是最佳码。( )( )1H SLH S2.6183.1%3.14编码效率编码效率四、变长码的编码方法四、变长码的编码方法四、变长码的编码方法四、变长码的编码方法1、不用对信源符号按概率大小排序。2、直接计算修正的累加概率3、计算码长 111( )()( )2iikikF sp sp slog( )1iilp s 四、变长码的编码方法四、变长码的编码方法112log1log1log( )( )( )iiiilp sp sp s 1( )1( )()22iiiilp sF sF s1( )( )2iiilF sF s210.1101 0.110.0121( )( )(

28、)()iiiiF sF sF sF s1.将信源符号按概率从大到小的顺序排列，令将信源符号按概率从大到小的顺序排列，令2.给两个概率最小的信源符号给两个概率最小的信源符号sn-1和和sn各分配一个码元各分配一个码元“0”和和“1”，并将这两，并将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含概率，结果得到一个只包含(n1)个信源符号的新信源。称为个信源符号的新信源。称为信源的第一信源的第一次缩减信源次缩减信源，用，用S1表示。表示。3.将缩减信源将缩减信源S1的符号仍按概率从大到小顺序

29、排列，的符号仍按概率从大到小顺序排列，重复步骤重复步骤2，得到只含，得到只含(n2)个符号的缩减信源个符号的缩减信源S2。4.重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。得到各信源符号所对应的码字。12( )()()qp sp sp s编码步骤如下：编码步骤如下：四、变长码的编码方法四、变长码的编码方法12345:0.40.20.20.10.1sssssS P

30、1 , 0:X四、变长码的编码方法四、变长码的编码方法1 . 0:1 . 0:2 . 0:2 . 0:4 . 0:54321sssss014 . 02 . 02 . 02 . 0014 . 04 . 02 . 0016 . 04 . 001qS :) 1(:1 rqS) 1(2:2rqS(1)qrrrS:末四、变长码的编码方法四、变长码的编码方法1 . 0:1 . 0:2 . 0:2 . 0:4 . 0:54321sssss014 . 02 . 02 . 02 . 0014 . 04 . 02 . 0016 . 04 . 00111w012w0003w00104w00115w2 . 2)(1q

31、iiilspL码符号/信源符号四、变长码的编码方法四、变长码的编码方法1 . 0:1 . 0:2 . 0:2 . 0:4 . 0:54321sssss014 . 02 . 02 . 02 . 0014 . 04 . 02 . 0016 . 04 . 001100w 210w 311w 4010w 5011w 2 . 2)(1qiiilspL码符号/信源符号四、变长码的编码方法四、变长码的编码方法讨论：1) 两种方法平均码长相等。2) 计算两种码的码长方差：52211( )()1.36iiip slL52221( )()0.16iiip slL第二种方法编出的码码字长度变化较小，便于实现。四、变

32、长码的编码方法四、变长码的编码方法离散信源如下:1234567( )0.20 0.19 0.18 0.17 0.15 0.10 0.01SsssssssP S解：编码过程略，Huffman编码结果如下：123456710 11 000 001 010 0110 0111sssssss信源符号码字四、变长码的编码方法四、变长码的编码方法l平均码长为平均码长为l信源熵为信源熵为l编码效率为编码效率为71( )( )log ( )2.61/iiiH Sp sp s 比特 信源符号71( )2.72/iiiLp s l码元符号 信源符号2.6196.0%2.7271( )( )log ( )2.61/

33、iiiH Sp sp s 比特 信源符号四、变长码的编码方法四、变长码的编码方法注意注意：霍夫曼编码后的码字不是惟一的。：霍夫曼编码后的码字不是惟一的。1 1）每次对缩减信源两个概率最小的符号）每次对缩减信源两个概率最小的符号分配分配“0”0”或或“1”1”码元码元是任意的是任意的，所以可得到不同的码字。不同的码元分配，得到，所以可得到不同的码字。不同的码元分配，得到的具体码字不同，但码长的具体码字不同，但码长li不变，平均码长也不变，所以没有不变，平均码长也不变，所以没有本质区别；本质区别；2 2）缩减信源时，）缩减信源时，若合并后的概率与其他概率相等，这几个概率若合并后的概率与其他概率相等

34、，这几个概率的次序可任意排列的次序可任意排列，但得到的码字不相同，但得到的码字不相同, ,对应的码长也不相对应的码长也不相同同, ,但平均码长也不变但平均码长也不变。四、变长码的编码方法四、变长码的编码方法定理5.8 霍夫曼码是紧致码12345:0.4:0.2:0.2:0.1:0.1sssss014 . 02 . 02 . 02 . 0014 . 04 . 02 . 0016 . 04 . 001qS :) 1(:1 rqS) 1(2:2rqSrS:末10100000110001四、变长码的编码方法四、变长码的编码方法假定缩减后信源为 共有m个元素。jS 缩减前信源为 共有m+1个元素。1jS

35、1( )mjiiiLp sl其中第k个元素码长 ,概率为最短01()()()kkkp sp sp skl则缩减前01010101111111( )()(1)()(1)( )()()()()( )()()mjiikkkkimiikkkkkimiikkiLp slp slp slp slp sp slp sp sp slp sp s123456:0.240.200.180.160.140.08ssssssS P2 , 1 , 0:Xrriq) 1(1)qrr1i四、变长码的编码方法四、变长码的编码方法00. 0:08. 0:14. 0:16. 0:18. 0:20. 0:24. 0:1654321

36、sssssss01222. 024. 020. 018. 016. 001254. 024. 022. 001211w002w013w024w205w216w227w四、变长码的编码方法四、变长码的编码方法12345678:0.40.20.10.10.05 0.050.05 0.05ssssssssS P:0,1,2X四、变长码的编码方法四、变长码的编码方法编码步骤如下：1. 将概率按从大到小的顺序排列，令2. 将依次排列的信源符号按概率分成两组，使每组概率和尽可能接近或相等。3. 给每一组分配一位码元“0”或“1”。4. 将每一分组再按同样方法划分，重复步骤2和3，直至概率不再可分为止。12

37、( )()()qp sp sp s四、变长码的编码方法四、变长码的编码方法例1234567( )0.20 0.19 0.18 0.17 0.15 0.10 0.01SsssssssP S四、变长码的编码方法四、变长码的编码方法解：信源符号符号概率第一次分组第一次分组第一次分组第一次分组码字码长0.20000020.191001030.18101130.17101020.151011030.1010111040.011111141s2s4s3s5s6s7s四、变长码的编码方法四、变长码的编码方法l平均码长为平均码长为l信源熵为信源熵为l编码效率为编码效率为2.6195.3%2.7471( )(

38、)log ( )2.61/iiiH Sp sp s 比特 信源符号71( )2.74/iiiLp s l码元符号 信源符号四、变长码的编码方法四、变长码的编码方法123456:0.320.220.180.160.08 0.04ssssssS P四、变长码的编码方法四、变长码的编码方法l香农码、费诺码、霍霍夫曼码都考虑了信源的统计特性，使经常出现的信源符号对应较短的码字，使信源的平均码长缩短，从而实现了对信源的压缩。l香农码编码结果唯一，但在很多情况下编码效率不是很高。l费诺码和霍霍夫曼码的编码方法都不唯一。l费诺码比较适合于对分组概率相等或接近的信源编码。l霍霍夫曼码对信源的统计特性没有特殊要

39、求，编码效率比较高，对编码设备的要求也比较简单，因此综合性能优于香农码和费诺码。四、变长码的编码方法四、变长码的编码方法首先是速率匹配问题其次是差错扩散问题第三是霍霍夫曼码需要查表来进行编译码。信源统计特性未知时，怎么办？可采用所谓通用编码的方法。 14321sssss2334ssss01 00 00 100 10 00 01 0译码译码四、变长码的编码方法四、变长码的编码方法五、实用的无失真信源编码方法五、实用的无失真信源编码方法五、实用的无失真信源编码方法五、实用的无失真信源编码方法BBBBBBBBBBXXXXXXXXXAAAAAAUUUUUUUUUUUUU 符号码标识码游程长度编码： B

40、#10X#9A#6U#13 对于黑、白二值文件:1、黑白游程总是交替出现，可以规定第一游程为白游程。2、不同游程长度出现的概率不同，对游程长度进行编码采用霍夫曼编码，概率大的编长码，概率小的编短码。五、实用的无失真信源编码方法五、实用的无失真信源编码方法五、实用的无失真信源编码方法五、实用的无失真信源编码方法l73白游程=64+9 ：1101110100l001101010100101101010110111101100001100110011000000000001 0白1黑15白4黑77白5黑 压缩比=1728/47=36.7:1 结尾码组合基干码五、实用的无失真信源编码方法五、实用的无失

41、真信源编码方法(0)0.30,(1)0.70,111pp输入符号序列(0)0(1)(0)FFp(10)(1)FF(11)(1)(1)(0)FFpp (110)(11)FF(111)(11)(11)(0)FFpp()( )( ) ( )()( ) ( )FrFpF rp rpp rsssss1234()0.6, ()0.2, ()0.1, ()0.1p ap ap ap a()( )( ) ( )()( ) ( )FrFpF rp rpp rsssss1log( )lps134134()()()()0.6 0.1 0.10.006p a a ap ap ap a13413134113134()(

42、)()()()()()()()00.6 0.80.6 0.1 0.90.534F a a aF a ap a aF aF ap aF ap a aF a1log80.006l134102()(0.534)(0.100010001.)F a a a10001001 五、实用的无失真信源编码方法五、实用的无失真信源编码方法1log7( )lps13(0),(1)44pp11111100s6231( )44p s( )(0)(10)(110)(1110)(11110)(111110)1( )1(11111111)(11111110)(11111101)(11111100)0.110100100111

43、Fppppppppppp y ssy11010100.1101010( )0.81192.7%7/8CCH SL( )CFs1( )2lCFs1( )2lCFs1log( )lps1( )2lps1( )( )( )( )2lFCFFpssss五、实用的无失真信源编码方法五、实用的无失真信源编码方法()( )( ) ( )()( ) ( )FrFpF rp rpp rsssss五、实用的无失真信源编码方法五、实用的无失真信源编码方法 输入符号序列：ABCABDABCAAAABBBABCABCA 前缀 尾字符序号0X0000X0410X0FF0X1000X1010X1020X1030X1040X1050X1060X1070X1080X1090X10A0X10B0XFFFQ(FFF) Q(FFF) AQ(FFF)A(041) BB CC AAB DD AAB CCA AA AAA BB BBB AABC A五、实用的无失真信源编码方法五、实用的无失真信源编码方法