信息论与编码课件(第四章).ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《信息论与编码课件(第四章).ppt》由会员分享,可在线阅读,更多相关《信息论与编码课件(第四章).ppt(96页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第四章 无失真信源编码电气信息工程学院4.1 编码器及码的分类4.2 等长码4.4 等长信源编码定理4.5变长码4.6变长信源编码定理4.7霍夫曼码和其它编码方法4.8几种实用的无失真信源编码小结第四章 无失真信源编码本章的重、难点内容1、理解等长码和等长信源编码定理2、理解和掌握变长码及变长码编码定理3、理解Huffman编码、费诺码、香农码4、了解几种实用的无失真信源编码方法,包括(MH编码、算术编码、LZ码)电气信息工程学院第四章 无失真信源编码编码的意义:通信的基本问题:如何高速、高质地传送信息。高速和高质鱼和熊掌。编码讨论的问题:(1)质量一定,如何提高信息传输速度(提高编码效率或压
2、缩比)-信源编码(本章讨论问题)(2)信道传输速度一定,如何提高信息传输质量(抗干扰能力)-信道编码(下一章讨论)电气信息工程学院引言信源编码信源编码:以提高通信有效性为目的的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送,使单位时间内传送的平均信息量增加,从而提高通信的有效性。电气信息工程学院引言信道编码信道编码:是以提高信息传输的可靠性为目的的编码。通常通过增加信源的冗余度来实现。采用的一般方法是增大码率/带宽。与信源编码正好相反。密码密码:是以提高通信系统的安全性为目的的编码。通常通过加密和解密来实现。从信息
3、论的观点出发,“加密”可视为增熵的过程,“解密”可视为减熵的过程。电气信息工程学院引言信源编码理论是信息论的一个重要分支,其理论基础是信源编码的两个定理。无失真信源编码定理:是离散信源/数字信号编码的基础;限失真信源编码定理:是连续信源/模拟信号编码的基础。电气信息工程学院引言信源编码的分类:离散信源编码、连续信源编码和相关信源编码三类。离散信源编码:独立信源编码,可做到无失真编码;连续信源编码:独立信源编码,只能做到限失真信源编码;相关信源编码:非独立信源编码。电气信息工程学院4.1 编码器及码的分类编码:信息的组织方式编码的实质:对信源的原始符号按一定的数学规则进行变换。编码的目的:信源编
4、码:提高信息传输的有效性信道编码:提高信息传输的可靠性 本章不考虑干扰问题电气信息工程学院4.1 编码器及码的分类无失真编码器结构框图几个术语:信源符号:信源输入码符号(码元):电气信息工程学院编码器编码器信源码字符号集4.1 编码器及码的分类码字Wi:由xj(j=1,2,r)组成的长度为 li 的序列,Wi与si一一对应。码字长度(码长):Wi的长度li编码器:将信源符号si变换成Wi的设备信源编码信源编码:把信源符号si映射为码字Wi的过程。无失真编码:映射是一一对应、可逆的。信源编码基本思想:尽可能缩短出现概率大的信源符号的码字电气信息工程学院4.1 编码器及码的分类码的分类二元码:若码
5、符号集X0,1,所得码字为一些二元序列,则称二元码。在二元信道中传输等长码(固定长度码):若一组码中所有码字的长度都相同(即li=l,i=1,q),则称为等长码。变长码:不满足等长码条件的码组称为变长码。电气信息工程学院4.1 编码器及码的分类非奇异码:若一组码中所有码字都不相同(即所有信源符号映射到不同的码符号序列,不同信源符号可分辨),则称为非奇异码。奇异码:反之,若码组中含有相同的码字则为奇异码。同价码:若码符号集X:x1,x2,xr中每个码符号所占的传输时间都相同,则所得的码为同价码。电气信息工程学院4.1 编码器及码的分类码的N次扩展码:电气信息工程学院信源符号出现概率码1码2s1P
6、(s1)000s2P(s2)0101s3P(s3)10001s4P(s4)11111信源码 字信源码 字信源码 字a100W1W1=B1a5.010W2W1=B1.a16.111111=W4W4=B16a2001W1W2=B2a30001W1W3=B3a40111W1W4=B44.1 编码器及码的分类惟一可译码:若码的任意一串有限长的码符号序列只能被惟一地译成所对应的信源符号序列,则此码称为惟一可译码(单义可译码)。否则就称为非惟一可译码或非单义可译码。表1中码1是惟一可译码,而码2是非惟一可译码。因为对于码2,其有限长的码符号序列能译成不同的信源符号序列。如码符号序列0010,可译成s1s2
7、s1或s3s1,就不惟一了。问题:怎样才能做到无失真编码即惟一可译码?电气信息工程学院4.2 等长码若要实现无失真编码,不但要求信源符号si与码字Wi是一一对应的,而且要求码符号序列的反变换也是惟一的。即所编的码必须是惟一可译码。对于等长码来说,若等长码是非奇异码,则它的任意有限长N次扩展码一定也是非奇异码。等长非奇异码一定是惟一可译码。电气信息工程学院信源符号码1码2s10000s20111s31010s41111非奇异码唯一可译码奇异码非惟一可译码4.2 等长码等长编码惟一可译的必要条件:其中:q为信源符号数,r为符号集中的码元数,l为码长。例如:若信源符号数 q4,进行二元等长编码,则码
8、符号个数为 r 2。信源S存在惟一可译等长码的条件是码长 l2。若q8,r 2,l3。电气信息工程学院4.2 等长码对 两边取对数得平均每个信源符号所需的码符号个数上式表明:对于等长惟一可译码而言,平均每个信源符号至少需要用 logqlogr个码符号来表示。即:每个信源符号所需最短码长为 logqlogr个。电气信息工程学院4.2 等长码当r=2(二元码)时logr=1,上式变成上式表明:对于二元等长惟一可译码,平均每个信源符号至少需要用logq个码符号来变换。或:对信源进行二元等长不失真编码时,每个信源符号所需的极限值为logq个。电气信息工程学院4.2 等长码当考虑到符号之间的依赖关系或关
9、联性时,可以从N次扩展信源中去掉一些符号,使得总符号数小于 ,这样使编码所需码字个数大大减少,因此平均每个信源符号所需的码符号个数就可以大大减少,从而提高传输效率。当N足够长后,这种误差概率可以任意小,做到几乎无失真编码。等长编码定理给出了信源进行等长编码所需码长的理论极限值。电气信息工程学院4.4 等长信源编码定理定理4.3(等长信源编码定理):一个熵为H(S)的离散无记忆信源,若对信源长为N的符号序列进行等长编码,设码字是从r个字母的码符号集中选取l个码元组成。对于任意0,只要满足:则当N足够大时,可实现几乎无失真编码,即译码错误概率能为任意小。反之,若 当N足够大时,译码错误概率近 似为
10、1,不可能实现无失真编码。电气信息工程学院4.4 等长信源编码定理说明:定理4.3是在平稳无记忆离散信源的条件下得出,但它同样适合于平稳有记忆信源。当进行二元编码时,r2,则:一般情况下,信源符号并非等概率分布,且符号之间有很强的关联性,故信源的熵H(S)logq。电气信息工程学院等长编码时平均每个信源符号所需的二元码符号的理论极限信源等概分布时4.4 等长信源编码定理从定理4.3可知,在等长编码中每个信源符号平均所需的二元码符号可大大减少,从而使编码效率提高。定理4.3中的条件式可改写成:电气信息工程学院长为l的码符号序列所能载荷的最大信息量长为N的信源序列平均携带的信息量4.4 等长信源编
11、码定理所以等长编码定理告诉我们:只要码字传输的信息量大于信源序列携带的信息量,总可实现几乎无失真编码。令 它是编码后平均每个信源符号能载荷的最大信息量,称为编码信息率。可见,当编码信息率大于信源的熵时,才能实现几乎无失真编码。为衡量编码效果,引入编码效率。电气信息工程学院4.4 等长信源编码定理称 为编码效率。由定理4.3可得最佳等长编码的效率为:如果自信息的方差 和均为定值时,只要N足够大,编码错误就可以小于任一正数。也即要求误差小于时,电气信息工程学院4.4 等长信源编码定理信源序列长度N必须满足:该式给出了在已知方差和信源熵的条件下,信源序列长度N与最佳编码效率和允许错误概率的关系。允许
12、错误概率越小,编码效率要求越高,则信源序列长度N就必须越长。实际情况下,要实现几乎无失真的等长编码,N需要非常大。电气信息工程学院4.4 等长信源编码定理例 设离散无记忆信源信源熵自信息方差若对信源S采用等长二元编码,要求编码效率=0.96,允许错误概率电气信息工程学院4.4 等长信源编码定理则得即序列长度达4130万以上,这在实际中很难实现。因此,一般来说,当N有限时,高传输效率的等长码往往要引入一定的失真和错误,它不能像变长码那样可以实现无失真编码。下面介绍变长码,及其编码定理。电气信息工程学院4.5 变长码4.5.1 惟一可译变长码与即时码等长码仅当N很大才会有较高的编码效率;变长码往往
13、在N不很大时就可编出效率很高而且无失真的码。等长码:非奇异 惟一可译变长码:任意有限长N次扩展码是非奇异 惟一可译电气信息工程学院4.5 变长码即时码:在译码时无需参考后续的码符号就能立即作出判断,译成对应的信源符号的惟一可译码码4以“1”作为结束符号,起到逗号的作用,又称为逗点码。逗点码是一种即时码。电气信息工程学院信源符号出现概率码1码2码3码4s1s2s3s41/21/41/81/80110011010000111010010001010010001非惟一可译奇异码非惟一可译非奇异码惟一可译非奇异码惟一可译非奇异码4.5 变长码定义定义:如果一个码组中的任一个码字都不是另一个码字的续长,
14、或者说,任何一个码字都不是另一个码字的前缀,则称为即时码也称非延长码或前缀条件码。电气信息工程学院所有码非奇异码惟一可译码即时码4.5 变长码4.5.2 即时码的树图构造法构造即时码的一种简单方法是树图法。电气信息工程学院信源符号码4s1s2s3s41010010001根:树的最上端树枝的个数为r,r=2为二元码树01001111010010001码4的树图ABCD中间节点(空心)节点:树枝的终端,从节点生出树枝,每个节点伸出r个枝终端节点(实心)码字:从根到终端节点对应的码符号,又称树叶4.5 变长码按树图法构成的码一定满足即时码的充要条件,因为从根到叶所走的路径各不相同,而且中间节点不安排
15、为码字,所以一定满足对前缀的限制。该树的5个终端节点W1,W2,W3,W4,W5分别表示5个二进制码字0,100,111,1010,1011电气信息工程学院4.5 变长码码树的性质:任一即时码都可用树图表示。当码字长度给定,即时码不是惟一的。整树:每个节点上都有r个分枝。非整树:至少有一个节点上没有r个分枝的树。电气信息工程学院4.5.4 惟一可译变长码的判断法结论:不能用Kraft不等式,只能根据定义判断码C是否是惟一可译码。依据:非惟一可译变长码 有限长的码符号序列能译成两种不同的码字序列。惟一可译变长码判别惟一可译变长码判别:将码C中所有可能的尾随后缀组成一个集合F,当且仅当集合F中没有
16、包含任一码字时,码C为惟一可译变长码。电气信息工程学院4.5.4 惟一可译变长码的判断法构成集合F的方法:首先,观察码C中最短的码字是否是其他码字的前缀。若是,将其所有可能的尾随后缀排列出。而这些尾随后缀又可能是某些码字的前缀,再将由这些尾随后缀产生的新的尾随后缀列出。依此下去,直至没有一个尾随后缀是码字的前缀或没有新的尾随后缀产生为止。接着,按照上述步骤将次短的码字直至所有码字可能产生的尾随后缀全部列出。电气信息工程学院4.6 变长信源编码定理对于已知信源S可用码符号X进行变长编码,而且对同一信源可有多种即时码或惟一可译码。选择哪一种最好呢?从高速度传输信息的角度,希望用短的码符号组成码字,
17、即用码长作为选择准则引进码的平均长度。电气信息工程学院4.6 变长信源编码定理设信源为编码后的码字为其码长分别为对于惟一可译码,有则这个码的平均长度为:单位是码符号/信源符号,是每个信源符号平均需用的码元数。电气信息工程学院4.6 变长信源编码定理编码后信道的信息传输率(编码后平均每个码元携带的信息量):若传输一个码符号平均需要t秒钟,则编码后信道每秒传输的信息量为可见,码的平均长度越短、越大,信息传输效率就越高。对于编码者来说,感兴趣的是平均码长 短的码。问题:如何找到码长最短的惟一可译码?电气信息工程学院4.6 变长信源编码定理紧致码(最佳码):对于某一信源和某一码符号集来说,若有一个惟一
18、可译码,其平均长度小于所有其他惟一可译码的平均长度,则该码称为紧致码,或称最佳码。无失真信源编码的基本问题转化为找出紧致码。最佳码也就是紧致码的平均长度不是可以无限制缩小的,在理论上是有它的极限值的(在无失真信源编码的条件下),香农第一定理给出了这一极限值,这一定理有很大的实际意义。电气信息工程学院4.6 变长信源编码定理定理4.8 无失真变长信源编码定理(即香农第一定理):离散无记忆信源S的N次扩展信源 ,其熵为 ,并有码符号X=x1,x2,xr。对信源 进行编码,总可以找到一种编码方法,构成惟一可译码,使信源S中每个信源符号所需的平均码长满足:电气信息工程学院4.6 变长信源编码定理当 时
19、,得其中 表示对N个信源符号的序列 进行编码。电气信息工程学院4.6 变长信源编码定理定理4.8是香农信息论的主要定理之一,它说明要做到无失真的信源编码,编码每个信源符号平均所需最少的r元码元数为信源的熵Hr(S)。即熵Hr(S)是无失真信源压缩的极限值。若编码的平均码长小于信源的熵值Hr(S),则惟一可译码不存在,在译码或反变换时必然要带来失真或差错。通过对扩展信源进行变长编码,当 时,平均码长 电气信息工程学院4.6 变长信源编码定理从信道角度看,信道的信息传输率因为 所以极限情况下,编码后信道的信息传输率为:这时信道的信息传输率等于无噪无损信通的信道容量C,信息传输效率最高。电气信息工程
20、学院4.6 变长信源编码定理香农第一定理的物理意义:无失真信源编码的实质:对离散信源进行适当变换 变换后新信源符号(信道的输入信源)尽可能为等概率分布 新信源符号平均所含的信息量达到最大 使信道的信息传输率R达到信道容量C,实现信源与信道理想的统计匹配。电气信息工程学院4.6 变长信源编码定理无失真信源编码定理通常又称为无噪信道编码定理。表述为:若信道的信息传输率R不大于信道容量C,总能对信源的输出进行适当的编码,使得在无噪无损信道上能无差错地以最大信息传输率C传输信息,但要使信道的信息传输率R大于C而无差错地传输信息则是不可能的。电气信息工程学院4.6 变长信源编码定理为了衡量各种编码是否达
21、到极限情况,定义变长码的编码效率为:一般用码的效率来衡量各种编码的优劣。为了衡量各种编码与理论极限的差距,定义码的剩余度为:电气信息工程学院4.6 变长信源编码定理在二元无损无噪信道中r=2,所以在二元无损无噪信道中信息传输率和R数值相同但单位不同在二元信道中若=1,即信息传输率R=1比特码符号,达到了信道的信道容量,编码效率最高,码剩余度为零。电气信息工程学院4.6 变长信源编码定理例:有一离散无记忆信源其熵为:0.811用二元码符号构造一个即时码平均码长编码效率 编码效率较低,为此对信源S的二次扩展信源S2 进行编码。电气信息工程学院4.6 变长信源编码定理平均码长电气信息工程学院即时码s
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 信息论 编码 课件 第四
![提示](https://www.taowenge.com/images/bang_tan.gif)
限制150内