信息论第5章 无失真信源编码_第1页
信息论第5章 无失真信源编码_第2页
信息论第5章 无失真信源编码_第3页
信息论第5章 无失真信源编码_第4页
信息论第5章 无失真信源编码_第5页
已阅读5页,还剩88页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、1第第5 5章章 无失真信源编码无失真信源编码2编码的意义编码的意义通信的基本问题通信的基本问题:如何高速、高质地传送信息。如何高速、高质地传送信息。高速和高质鱼和熊掌。高速和高质鱼和熊掌。编码讨论的问题编码讨论的问题:(1 1)质量一定,如何提高信息传输速度(提高编码效率或压缩比)质量一定,如何提高信息传输速度(提高编码效率或压缩比)- 信源编码(本章讨论问题)信源编码(本章讨论问题)(2 2)信道传输速度一定,如何提高信息传输质量(抗干扰能力)信道传输速度一定,如何提高信息传输质量(抗干扰能力) -信道编码(下一章讨论)信道编码(下一章讨论)3信源输出的符号序列,需要变换成适合信道传输的符

2、号序列,一般称为码序列.对信源输出的原始符号按照一定的数学规则进行的这种变换称为编码.完成编码功能的器件称为编码器.接收短有一个译码器完成相反的功能.5.1 编码器4编码编码:信息的组织方式:信息的组织方式编码的实质编码的实质:对信源的原始符号按一定:对信源的原始符号按一定的数学规则进行的数学规则进行变换变换。编码的目的编码的目的:提高信息传输的有效性(信源编码);提高信息传输的有效性(信源编码);提高信息传输的可靠性。(信源或信道提高信息传输的可靠性。(信源或信道编码)编码) 5几个术语:几个术语:信源符号信源符号:信源输入:信源输入S=s1,s2,sq码符号码符号 (码元码元):X=x1,

3、x2,xr码字码字Wi: 由由xj (j=1,2,r)组成的长度为组成的长度为 li 的序列,的序列,Wi与与si一一对应。一一对应。码字长度码字长度 (码长码长): Wi的长度的长度li码码 (码书码书):码字:码字Wi的集合的集合C=W1,W2,Wq 编码器编码器:将信源符号:将信源符号si变换成变换成Wi的设备的设备6信源编码信源编码信源编码信源编码:把信源符号:把信源符号si映射为码字映射为码字Wi的的过程。过程。 无失真编码无失真编码:映射是一一对应、可逆的。:映射是一一对应、可逆的。无失真信源编码无失真信源编码:尽可能精确的再现信:尽可能精确的再现信源的输出源的输出 信源编码基本思

4、想信源编码基本思想:尽可能缩短出现概:尽可能缩短出现概率大的信源符号的码率大的信源符号的码 7通信的根本问题是将信源的输出,经信道传输在接收端精确的或近似地重现出来,因此要首先解决两个问题: 第三章中已经回答了第一个问题,这一章要讨 论的是第二个问题.信源编码器如下图所示:89101112定长码和变长码13奇异码和非奇异码14N次扩展码151617说明:本章我们讨论的都是同价码同价码,即每个码元符号所占的传输时间是相同的.显然,对同价码而言,定长码中每个码字的传输时间是相同的,而变长码中每个码字的传输时间不一定相等.185.2 分组码定义:19奇异性2021唯一可译性22即时性2324一个码,

5、若其中所有码字均处于终端节点,即端点上,则该码为非续长码。2526不超过终端节点也叫端点。272829该树的该树的5 5个个终端节点终端节点W1,W2,W3W1,W2,W3,W4,W5,W4,W5分分别表示别表示5 5个个二进制码二进制码字字0 0,100100,111111,10101010,10111011按树图法构成的码一定满足即时码的充要条件,因为从根到叶所走的按树图法构成的码一定满足即时码的充要条件,因为从根到叶所走的路径各不相同,而且中间节点不安排为码字,所以一定满足对前缀的路径各不相同,而且中间节点不安排为码字,所以一定满足对前缀的限制。限制。30各节点(包括树根)长出的树枝树等

6、于r31325.35.3定长码定长码(51)33若令N1,则有qlrlog即lrq (52)(53)与51式一致。式53表示平均每个原始信源符号所需要的码符号个数,对于定长码,平均每个原始信源符号至少需要用 个码符号变换。qrlog343536定理5.3.137其中前一部分被视为正定理,后一部分被视为逆定理。其中前一部分被视为正定理,后一部分被视为逆定理。383940编码效率4142435.45.4变长码变长码变长码是在码符号序列长度N不大时就能编出效率很高而且无失真的信源码。要实现无失真的信源编码,变长码必须是唯一可译码唯一可译码。变长码要满足唯一可译码的条件,它必须是非奇异码非奇异码,而且

7、任意有限长N次扩展码也是非奇异的。为能即时进行译码,变长码还必须是即时码即时码。445.4.1 码的分类和主要编码方法45464748495.4.2 Kraft不等式50注意:仅仅是存在!5.4.2 克拉夫特不等式 与麦克米伦不等式 克拉夫特(kraft)不等式515253定理定理5.4.3 若存在一个码长为若存在一个码长为l1,l2,lq的惟一可译码,则一定存在具有相同码的惟一可译码,则一定存在具有相同码长的即时码。长的即时码。若存在一个码长为若存在一个码长为l1,l2,lq的惟一可译码的惟一可译码 满足满足Kraft不等式(定理不等式(定理5.4.2) 存在具有相同码长的即时码(定理存在具

8、有相同码长的即时码(定理5. 4.1)任何一个惟一可译码均可用一个即时码来代替,任何一个惟一可译码均可用一个即时码来代替,而不改变任一码字的长度。而不改变任一码字的长度。即时码可用树图法来构造。因此要构造惟一可即时码可用树图法来构造。因此要构造惟一可译码,只需讨论构造即时码。译码,只需讨论构造即时码。545.4.3 唯一可译码的判别准则若码长若码长l1, l2, , lq l1, l2, , lq 不满足不满足KraftKraft不等式不等式 不是惟一可译码;反之,不是惟一可译码;反之, l1, l2, , lq l1, l2, , lq 满满足足KraftKraft不等式的码,不一定是惟一可

9、译码。不等式的码,不一定是惟一可译码。结论:不能用克拉夫特不等式,只能根据定义结论:不能用克拉夫特不等式,只能根据定义判断码判断码C C是否是惟一可译码。是否是惟一可译码。判别依据:非惟一可译变长码判别依据:非惟一可译变长码 有限长的码有限长的码符号序列能译成两种不同的码字序列。符号序列能译成两种不同的码字序列。55例:如下图中情况发生,其中例:如下图中情况发生,其中Ai,Bi都是都是码字码字(Ai,Bi C)。 B1一定是一定是A1的前缀,而的前缀,而A1的尾随后缀一的尾随后缀一定是另一码字定是另一码字B2的前缀,的前缀,B2的尾随后缀的尾随后缀又是其他码字的前缀。最后,码符号序又是其他码字

10、的前缀。最后,码符号序列的尾部一定是一个码字。列的尾部一定是一个码字。56判别准则:判别准则:5758唯一可译码的判别方法唯一可译码的判断方法:方法一 : (可确切判断)计算出分组码中所有可能的尾随后缀集合F,观察F中有没有包含任一码字,若无则为唯一可译码,否则一定不是唯一可译码。方法二: 步骤如下 1。观察是否是非奇异码。若是奇异码则一定不是唯一可译码。2。计算是否满足Kraft不等式。若不满足则一定不是唯一可译码。3。画出码树,观察是否满足即时码的树图的构造,若满足则是唯一可译码。595.4.45.4.4变长编码定理变长编码定理对于已知信源对于已知信源S S可用码符号可用码符号X X进行变

11、长编码,进行变长编码,而且对同一信源可有多种即时码或惟一可译而且对同一信源可有多种即时码或惟一可译码。码。选择哪一种呢?从高速度传输信息的角度,选择哪一种呢?从高速度传输信息的角度,希望用短的码符号组成码字,即用码长作为希望用短的码符号组成码字,即用码长作为选择准则选择准则-引进码的平均长度。引进码的平均长度。60平均码长平均码长6162对于某一信源和某一码符号集来说,若有一个对于某一信源和某一码符号集来说,若有一个惟一可译码,其平均长度小于所有其他惟一可惟一可译码,其平均长度小于所有其他惟一可译码的平均长度,则该码称为紧致码,或称最译码的平均长度,则该码称为紧致码,或称最佳码佳码 无失真信源

12、编码的基本问题无失真信源编码的基本问题找出紧致码。找出紧致码。63646566定理定理4.84.8(香农信息论的主要定理之一)的结论:(香农信息论的主要定理之一)的结论:要做到无失真的信源编码,编码每个信源符号平均所要做到无失真的信源编码,编码每个信源符号平均所需最少的需最少的r r元码元数为信源的熵元码元数为信源的熵Hr(S) Hr(S) 。即。即Hr(S) Hr(S) 是无是无失真信源压缩的极限值。失真信源压缩的极限值。若编码的平均码长小于信源的熵值若编码的平均码长小于信源的熵值Hr(S) Hr(S) ,则惟一可,则惟一可译码不存在,在译码或反变换时必然要带来失真或差译码不存在,在译码或反

13、变换时必然要带来失真或差错。错。通过对扩展信源进行变长编码,当通过对扩展信源进行变长编码,当N N 时,平均码长时,平均码长 Hr(S) Hr(S) 。67香农第一定理的物理意义香农第一定理的物理意义无失真信源编码的实质无失真信源编码的实质:对离散信源进行变换:对离散信源进行变换 变换后信源符号变换后信源符号(信道的输入信源信道的输入信源)尽可能为等概尽可能为等概率分布率分布 新信源符号平均所含的信息量达到最大新信源符号平均所含的信息量达到最大 使信道的信息传输率使信道的信息传输率R达到信道容量达到信道容量C,实,实现信源与信道理想的统计匹配。现信源与信道理想的统计匹配。无失真信源编码定理通常又称为无失真信源编码定理通常又称为无噪信道编码定无噪信道编码定理理。表述为:若信道的信息传输率。表述为:若信道的信息传输率R不大于信道不大于信道容量容量C,总能对信源的输出进行适当的编码,使,总能对信源的输出进行适当的编码,使得在无噪无损信道上能无差错地以最大信息传输得在无噪无损信道上能无差错地以最大信息传输率率C传输信息,但要使

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论