第3章无失真信源编码--廖-2013-本科生

《第3章无失真信源编码--廖-2013-本科生》由会员分享，可在线阅读，更多相关《第3章无失真信源编码--廖-2013-本科生（173页珍藏版）》请在文档大全上搜索。

1、 第第3章章离散信源无失真编码第第3章章 离散信源无失真编码离散信源无失真编码内容提要用尽可能少的符号来传输信源消息，目的是提高传输效率，这是信源编码应考虑的问题，这章讨论在不允许失真情况下的信源编码。等长编码定理给出了等长编码条件下，其码长的下限值，变长编码定理（香农第一定理）给出了信源无失真变长编码时其码长的上、下限值。本章还介绍了三种通用信源编码方法：香农编码法、Fano编码法和霍夫曼编码法。z离散信源：消息集X为离散集合。即时间和幅度取值都离散的信源。31概述 为了实现高质量、高效率的通信，引入了信源编码和信道编码。信源编码和信道编码主要需要解决以下两个问题。提高传输效率增强通信的可靠

2、性信息论的研究对象信息论的研究对象-通信系统模型，信源，通信系统模型，信源，编码器，编码器，信道，信道，译码器，信宿。译码器，信宿。（1）提高传输效率，用尽可能少的信道传输符号来传递信源消息，目的是提高传输效率，这是信源编码主要应考虑的问题。这里又分两种情况讨论，即允许接收信号有一定的失真或不允许失真。 综上所述，提高抗干扰能力往往是以降低信息传输效率为代价的，而为了提高传输效率又往往削弱了其抗干扰能力。这样，设计者在取舍之间就要作均衡考虑。（2）增强通信的可靠性如何增加信号的抗干扰能力，提高传输的可靠性，这是信道编码主要考虑的问题。解决这一问题，一般是采用冗余编码法，赋予信码自身一定的纠错和

3、检错能力，只要采取适当的信道编码和译码措施，就可使信道传输的差错概率降到允许的范围之内。信源编码包括两个功能： （1）将信源符号变换成适合信道传输的符号； （2）压缩信源冗余度，提高传输效率。7由于信源符号之间存在分布由于信源符号之间存在分布不均匀和相关性不均匀和相关性，使得信源存在使得信源存在冗余度冗余度，信源编码的主要任务，信源编码的主要任务就是减少冗余，提高编码效率。就是减少冗余，提高编码效率。 8信源编码的基本途径有两个：信源编码的基本途径有两个：z使序列中的各个符号尽可能地互相独立，使序列中的各个符号尽可能地互相独立，即解除相关性；即解除相关性；z使编码中各个符号出现的概率尽可能地相

4、使编码中各个符号出现的概率尽可能地相等，即概率均匀化。等，即概率均匀化。 9信源编码的基础是信息论中的两个编码定理：信源编码的基础是信息论中的两个编码定理：z无失真编码定理无失真编码定理-香农第一定律，给出了香农第一定律，给出了信源无失真变长编码时其码长的上、下限值。信源无失真变长编码时其码长的上、下限值。z限失真编码定理限失真编码定理 无失真编码无失真编码只适用于离散信源只适用于离散信源 对于连续信源，只能在失真受限制的情况下进行对于连续信源，只能在失真受限制的情况下进行限失真编码限失真编码 无失真信源编码：无失真信源编码：能够精确地复现信源的输出，保证信源产生的全部信息无损地送给信宿，这时

5、的信源编码就是无失真信源编码。3.1.1信源编码的相关概念编码器3.1图3.1信源编码器3.1书上例子：3.1,3.2z 信源编码有以下3种主要方法：z (1)匹配编码匹配编码根据信源符号的概率不同，编码的码长不同：概率大的信源符号，所编的代码短；概率小的信源符号所编的代码长，这样使平均码长最短。将要讲述的香农编码、哈夫曼编码、费诺码都是概率匹配编码，都是无失真信源编码。z (2)变换编码变换编码 先对信号进行变换，从一种信号空间变换为另一种信号空间，然后针对变换后的信号进行编码。z (3)识别编码识别编码识别编码主要用于印刷或打字机等有标准形状的文字符号和数据的编码，比如中文文字和语音的识别

6、。z 后两种信源编码均为有失真的信源编码。z 无失真信源编码主要针对离散信源，连续信源在量化编码的过程中必然会有量化失真，所以对连续信源只能近似地再现信源的消息。 信源编码可看成是从信源符号集到码符号集的一种映射，即将信源符号集中的每个元素（可以是单符号，也可以是符号序列）映射成一个长度为n的码字。对于同一个信源，编码方法是多种的。【例例3.3】 用u1 ，u2 ，u3，u4表示信源的四个消息，码符号集为0,1，表3-1列出了该信源的几种不同编码。表3-1同一信源的几种不同编码信源消息各消息概率码1码2码3码4u1q(u1)000001u2q(u2)1101110u3q(u3)10100010

7、0u4q(u4)11111110003.1.2码的分类3.变长码变长码若码字集合C中的所有码字cm (m =1,2,M)，其码长不都相同，码码中的码字长短不一中的码字长短不一，称码C为变长码，表3-1中列出的码3、码4就是变长码。2.等长码等长码在一组码字集合C中的所有码字cm (m =1,2,M)，其码长都相同，码中所有码字的长度，都相同，码中所有码字的长度，都相同，则称这组码C为等长码，表3-1中列出的码1、码2就码长n=2等长码。一般，可以将码简单的分成如下几类：1.二元码二元码若码符号集为0，1，则码字就是二元序列，称为二元码,二元码通过二进制信道传输，这是数字通信和计算机通信中最常见

8、的一种码，表3-1列出的4种码都是二元码。5.非奇异码非奇异码从信源消息到码字的影射是一一对应的，每一个不同的信源消息都用不同的码字对其编码，若一组码中所有码字都不相同，则称为非奇异码。例表3-1中的码2、码3和码4都是非奇异码。4.奇异码奇异码对奇异码来说，从信源消息到码字的影射不是一一对应的。若一组码中有相同的码字，则称为奇异码。例表3-1中的码1，信源消息u2和u4都用码字11对其编码，因此这种码就是奇异码，奇异码不具备惟一可译性。扩展信源信源编码器 信源符号 a1,a2,aK 信道符号（码符号）b1, b2,bD消息u1 uN =(u11u12 u1L) (uN1uN2 uNL)N次扩

9、展码字 c1 cN =(c11c12 c1n) (cN1cN2 cNn)图3-2 N次扩展信源编码器模型原码的N次扩展码是将信源作N次扩展得到的新信源符号序列u（N）=u1 uN =(u11u12 u1L) (uN1uN2 uNL)，对应码符号序列c（N）=c1 cN =(c11c12 c1n) (cN1cN2 cNn)，记集合C (N)=c1(N),c2(N),，C (N)即原码C的N次扩展码。6.原码原码C的的N次扩展码次扩展码原码C的N次扩展码中的每个元素是N次扩展信源中的序列所对应的N个码字组成的序列。草稿对于定长码，若原码是惟一可译码，则它的N次扩展码也是惟一可译的，而对于变长码则不

10、尽然，见表3-2。信源消息各消息概率码1码2码3u1q(u1)011u2q(u2)11001u3q(u3)00100001u4q(u4)1110000001表3-2同一信源的几种不同变长编码表3-2同一信源的几种不同变长编码7.惟一可译码惟一可译码定义定义3.1 如果码的任意如果码的任意N次扩展码都是非奇异码，则称该码为次扩展码都是非奇异码，则称该码为惟一可译码。惟一可译码。NYYz对于码1，由于它的每一个信源符号对应不同的码字，所以它本身是唯一可译，但将它进行二次扩展后得到的二次扩展码就不唯一可译，例如，二次扩展码中的u1u3和u3u1对应同一个码字000，u2u4和u4u2对应同一个码字1

11、11，因此码1不是唯一可译码。z对于码2，码3不仅本身是唯一可译码，进行N次扩展后得到的N次扩展码也是唯一可译的，按照定义3.1，码2、码3是唯一可译码。第三章：离散信源无失真编码z编码器码的分类z1.二元码：若码符号集为0，1，则码字就是二元序列，称为二元码；z2.等长码：码中所有码字的长度，都相同；z3.变长码：码中的码字长短不一；z4.奇异码：若一组码中有相同的码字，则称为奇异码；z5.非奇异码：若一组码中所有码字都不相同。z6.原码C的N次扩展码z7.惟一可译码：如果码的任意N次扩展码都是非奇异码，则称该码为惟一可译码。8.即时码即时码对于变长码，又有如下定义定义定义3.2 对于码字对