无失真信源编码

上传人: 毕业设计 IP属地:江苏 文档编号: 20191002081805158 上传时间: 2020-10-20 格式:ppt 页数:63 大小:1.52MB
收藏 版权申诉 举报
无失真信源编码_第1页
第1页 / 共63页
无失真信源编码_第2页
第2页 / 共63页
无失真信源编码_第3页
第3页 / 共63页
无失真信源编码_第4页
第4页 / 共63页
无失真信源编码_第5页
第5页 / 共63页
资源描述:
第三章无失真信源编码编码的相关概念定长编码定理变长编码定理最佳编码无失真信源编码为什么要对进行编码?信源发出的消息符号可能不适合信道的传输,将信源发出的消息符号转换为适合信道传输的符号。信源消息确定后,提高通信的有效性信源编码。提高通信的可靠性编码具有发现错误或纠正错误的抗干扰能力信道编码。提高通信的安全性加密编码。编码的相关概念信源编码的定义信源编码的研究方法编码相关概念唯一可译码的存在条件编码的相关概念信源编码的定义信源编码定义:指定能够满足信道特性适合于信道传输的符号序列码序列,来代表信源输出的消息。完成编码功能的器件称为编码器。离散信源输出的码序列离散信源输出的消息是由一个个离散符号组成的随机序列——信源符号序列;=()∈信源编码就是把信源输出的随机符号序列变成码序列。=()∈信源编码的研究方法研究方法研究信源编码时,将信道编码和译码看成是信道的一部分,而突出信源编码;信道信源编码的研究方法研究信道编码时,将信源编码和译码看成是信源和信宿的一部分,而突出信道编码。信源信宿信源编码的研究方法讨论无失真信源编码可以先不考虑抗干扰问题,所以它的数学模型比较简单,如图所示。编码相关概念码元和码字码元(符)集:信道可传输的基本符号的集合记为设有个符号:=,其中称为码元或码符。元信道:可传输个基本符号的信道;二元信道:可传输个基本符号的信道。这是一种最常用的信道基本符号常用表示。码字:由码元组成的序列称为码字,记为。码字的码元个数称为的码长。所有码字的码长均相等称为定长码。码字的码长不全相等称为变长码。编码相关概念编码与译码信源编码:将信源符号或符号序列按一种规则映射成码字的过程。无失真编码:信源符号到码字的映射必须一一对应。译码:从码符号到信源符号的映射。码表:所有映射规则的集合。编码相关概念许用码和禁用码许用码字:信源的符号或符号序列与码字定义了对应关系的码字。禁用码字:信源的符号或符号序列与码字未定义对应关系的码字。许用码字的全体称为码集。编码相关概念分组码(块码)分类按码字的码长分类定长码:码集中所有码字的码长相等。变长码:码集中所有码字的码长不全相等。按信源符号与码字对应关系分类非奇异码:信源符号与码字是一一对应的。奇异码:信源符号与码字不是一一对应的。编码相关概念分类按译码唯一性分类唯一可译码:对于多个码字组成的有限长码流,只能唯一地分割一个个的码字。唯一可译码又称为单义码。唯一可译码在传输过程中不需要同步码。非唯一可译码:对有限长码流,不能唯一地分割一个个的码字。例:码流码:→→→可分割码:→→→则无法唯一分割编码相关概念分类按译码的即时性分类非即时码:接收端收到一个完整的码字后,不能立即译码;还需要等到下一个码字开始接收后才能判断是否可以译码。即时码:接收端收到一个完整的码字后,就能立即译码;即时码又称为非延长码或异前缀码。例:非即时码,码流→→→译码为即时码,码流→→→译码为结论:即时码指的是码集任何一个码不能是其他码的前缀,即时码必定是唯一可译码唯一可译码不一定是即时码。编码相关概念分类举例例:码:显然不是惟一可译码。和对应于同一码字“”,码本身是一个奇异码。码:是非奇异码,不是惟一可译码。当收到一串码符号“”时,可将它译成“”,也可译为“”,“”或“”等,这种码从单个码字来看虽然不是奇异的,单从有限长的码序列来看,它仍然是一个奇异码。码:虽然是惟一可译码,但它要等到下一个“”收到后才能确定码字的结束,译码有延时。码:既是惟一可译码,又没有译码延时。码字中的符号“”起了逗点的作用,故称为逗点码。前缀条件码异前置码异字头码逗点码即时码非延长码:如果一个码的任何一个码字都不是其它码字的前缀。唯一可译码的存在条件码树图码树图:用码树来描述给定码集各码字的方法。码树图有树根、树枝、节点:一般中间节点(一级节点、二级节点)用○表示终端节点用●表示。传输个基本符号信道的码可用。例:二元(进制)码树→→→唯一可译码的存在条件码树图如果节点过多,也可以用如下方法表示码树图。唯一可译码的存在条件码树图用码树图构造码的方法在树的生长过程中,中间节点生出树枝,各树枝标出相应的码元;为了清晰起见相同码元的树枝方向相同,终端节点表示信源符号;从树根到终端节点所经过的树枝旁的码元按经过的顺序组成的序列构成码字。用码树图构造即时码的条件如果表示信源符号的终端节点不再延伸,即信源符号都在终端节点上,这样构造的码满足即时码条件。唯一可译码的存在条件前提条件:非奇异码唯一可译码存在定理:设为信源符号或信源符号序列个数,为码元个数或进制数,为信源各符号或信源符号序列对应的码长则唯一可译码存在的充分和必要条件是满足不等式:注意:不等式是一个存在定理,不是唯一可译码的判定定理。如果、、满足该不等式则存在唯一可译码如果是唯一可译码则、、必定满足该不等式。唯一可译码的存在条件例:设二进制码树中∈,=,=,=,=,应用上述判断定理,可得因此,不存在满足这种的唯一可译码用树码进行检查如图所示。唯一可译码的存在条件信息率若信源输出符号序列长度≥变换成由个符号组成的码序列码字变换要求:能够无失真或无差错地从恢复,同时传送时所需要的信息率最小。唯一可译码的存在条件信息率有种可能值,能编成的码字个数所以平均每个符号输出的最大信息量为,长码字最大信息量为。用该码字表示长度为的信源序列,则送出一个信源符号所需要的信息率平均为所谓信息率最小,就是找到一种编码方式使最小。几个问题:信息率最小为多少时,才能无失真译码?若小于这个信息率是否还能无失真译码?定长编码定理平均码长和编码有效性定长编码定理平均码长和编码有效性平均码长单符号信源空间,其中信源符号对应的码字为(=)码字对应的码长为(=)。所有的相等为定长码,记为不相等时为变长码。单符号对应变长码的平均码长码符信源符号平均码长和编码有效性平均码长符号序列信源空间其中是的次扩展。信源符号序列对应的码字为(=)码字对应的码长为(=)。符号序列对应变长码的平均码长码符信源符号序列码符信源符号平均码长和编码有效性编码效率编码效率(码率)定义:平均一个码符所携带的平均信息量称为编码效率,记作η;平均码长和编码有效性例:信源空间()=()=消息信源符号个数为=,二元码符码符个数为=,为信源各符号对应的码字长且满足不等式。定长码:=====码字:====编码效率η=()==平均码长和编码有效性举例变长码:====满足不等式:=码字:====方案:→,→,→,→==码符信源符号η==方案:→,→,→,→==码符信源符号η==平均码长和编码有效性讨论:为什么定长码的编码效率小于,而变长码的编码效率能达到?原因:因为()=,是个小数,而定长码的码长不可能为小数,所以编码效率小于。除非()为整数。但变长码的平均码长可以为小数,可能等于()。平均码长和编码有效性讨论:编码后码字集合确定,符号对应的码字长度不同,为什么编码效率不同?原因:不同符号的先验概率不同,对应的码字长度不同,计算出的平均码长也不同,编码效率也就不同。总结:一般情况下,变长编码的编码效率可能达到;对于变长编码,若概率大的符号对应短码概率小的符号对应长码,编码效率越高;反之越低。这也是后面最佳编码的思路。定长编码定理定理:由个符号组成的、每个符号的熵为()的无记忆平稳信源符号序列,可用个符号(每个符号有种可能值)进行定长编码。对任意ε>,δ>,只要则当足够大时,必可使译码差错小于δ;反之,当时,译码差错一定是有限值,而当足够大时,译码几乎必定出错。定长编码定理定理中的公式改写成表明:不等式左边表示长为的码字能载荷的最大信息量,右边代表长为的信源序列平均携带的信息量。所以定长编码定理告诉我们:只要码字传输的信息量大于信源携带的信息量,总可实现几乎无失真编码。定长编码定理信源熵()就是一个界限临界值。当编码器输出的信息率超过这个临界值时,就能无失真译码,否则就不行。信源编码定理从理论上说明了编码效率接近于,即的理想编码器的存在性,代价是在实际编码时取无限长的信源符号(→∞)进行统一编码。只要δ足够小,就可实现几乎无失真译码;若ε足够小,编码效率就接近于。说明:定长编码定理是在平稳无记忆离散信源的条件下论证的,但它同样适用于平稳有记忆信源,只是要求有记忆信源的极限熵和极限方差存在即可。对于平稳有记忆信源,定理中的熵应改为极限熵。定长编码定理定长编码计算随机变量();()的数学期望[()],即();()的方差σ();符号序列长度;已知编码效率η和译码错误概率δ。定长编码定理例:设单符号信源模型为信源熵为:()=(比特符号)自信息方差为:σ()=若要求编码效率为%,即译码差错率为δ=,则由此可见:在差错率和效率要求都不苛刻的情况下,就必须有多万个信源符号一起编码,技术实现非常困难。变长编码定理变长编码定理单个符号变长编码定理:若一离散无记忆信源的符号熵为(),每个信源符号用进制码元进行变长编码,一定存在一种无失真编码方法,其码字平均长度满足下列不等式变长编码定理单符号证明:若按如下不等式取所对应码字的码长为若为整数则上述不等式左边取等号。故可得:变长编码定理单符号∴所有码字长度满足不等式。如何降低平均码长:、减少信源熵()、增加信道码元数变长编码定理离散平稳无记忆序列变长编码定理:对于平均符号熵为()的离散平稳无记忆信源,必存在一种无失真编码方法,使平均信息率满足不等式:证明:信源的次扩展信源的信源熵为()个信源符号所对应码字的码长码符个信源符号变长编码定理证明编码效率的下界:码的剩余度:变长编码定理举例例:设单符号信源模型为其信息熵为:()=(比特符号)这里=,=要求η%,则结论:与定长编码相比,对同一信源,要求编码效率都达到%时,变长编码只需=进行编码,而等长码则要求大于。用变长编码时,不需要很大就可以达到相当高的编码效率而且可实现无失真编码。变长编码定理举例例:设离散无记忆信源的概率空间为其信源熵为=定长码:→,→,则=编码效率:η=()==()()=个符号变长编码定理举例定长码=码符个信源符号编码效率:η=()=()=变长码===码符个信源符号编码效率:η=()==当=η==η=采用扩展信源提高编码效率带来的问题:码表迅速扩大;需求内存大;译码延时。变长编码定理信息传输效率平均信息率:平均每个码元所含有的信息量。单位:码元码元传输率码元速率():每秒钟传输码元的数目。单位:波特()码元时间长度():=单位:秒()平均信息传输率():平均每秒钟传输的信息量。单位:=最佳编码香农编码费诺编码哈夫曼编码最佳编码最佳码:能载荷一定信息量且码字的平均码长最短可分离的码字集合。编码思路:对概率大的信息符号编以短码;对概率小的信息符号编以长码。目的:使平均码字长度最短。这种编码方法称为统计编码熵编码概率匹配编码。最佳编码香农编码若单个字符按如下不等式取所对应码字的码长为当=时=,则香农编码编码方法:()将信源符号消息按其出现概率的大小依次排序。()≥()≥()()按如下不等式取所对应码字的码长为。()计算第个消息的累加概率以便获得唯一可译码;()将累加概率变换为二进制数;()取二进制数的小数点后位作为符号消息的二进制码字。香农编码举例例:()编码过程香农编码举例信源熵:()=符号平均码长编码效率费诺编码编码方法:()将信源符号消息按其出现概率的大小依次排列。()≥()≥()()将依次排列的信源符号按其概率分为两大组使两个组的概率之和近似相等并对各组赋予一个码元和。()按()方法将每一大组再分为两组各组再赋予一个码元和。()如此重复直至每个组只剩一个信源符号为止。()信源符号所对应的码字即为码费诺编码举例例:()编码过程费诺编码举例信源熵:()=符号平均码长编码效率哈夫曼编码编码方法:()将信源符号消息按其出现概率的大小依次排序。()≥()≥()()取两个概率最小的符号分别配以和并将这两个概率相加作为新字母的概率,与未分配的字母重新排序。()对重新排序后的两个概率最小的符号重复()的过程。()不断重复上述过程直至最后两个符号配以和为止。()从最后一级开始向前返回到各个信源符号所对应的码元序列即为相应的码字。哈夫曼编码举例例:()编码过程哈夫曼编码举例信源熵:()=符号平均码长编码效率哈夫曼编码哈夫曼编码方法得到的码并非唯一的。原因如下:每次对信源缩减时,赋予信源最后两个概率最小的符号,用和是可以任意的,所以可以得到不同的哈夫曼码,但不会影响码字的长度。对信源进行缩减时,两个概率最小的符号合并后的概率与其它信源符号的概率相同时,这两者在缩减信源中进行概率排序,其放置次序是可以任意的,故会得到不同的哈夫曼码。此时将影响码字的长度,一般将合并的概率放在上面,这样可获得较小的码方差。哈夫曼编码举例例:设有离散无记忆信源方法一:将合并的概率放在下面。哈夫曼编码举例方法二:将合并的概率放在上面。结论:哈夫曼码的平均码长相等,编码效率也相等。但是两种码的质量不完全相同,可用码方差来表示。码方差越小,越接近平均码长,质量越好。哈夫曼编码举例码方差:哈夫曼编码特点:最佳变长码;编码不是唯一的;码方差小的编码质量好。局限性:只能用近似的整数位来表示单个符号,而不是理想的小数位。需要知道输入符号集的概率分布。本章小结、非奇异码、唯一可译码、即时码等相关概念;、定长编码定理和变长编码定理;、最佳编码:香农编码、费诺编码和哈夫曼编码的编码方法。(重点)作业
展开
温馨提示:
1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 本站仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 举报非法信息、侵权联系 QQ:9411152

机械图纸源码,实习报告等文档下载

备案号:浙ICP备20018660号
收起
展开