信息论基础与应用-第五章-无失真信源编码解析课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《信息论基础与应用-第五章-无失真信源编码解析课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 信息论 基础 应用 第五 失真 信源 编码 解析 课件
- 资源描述:
-
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
展开阅读全文