信源编码(编码定义及定长编码).ppt

《信源编码(编码定义及定长编码).ppt》由会员分享，可在线阅读，更多相关《信源编码(编码定义及定长编码).ppt（53页珍藏版）》请在三一办公上搜索。

1、第五章 信源编码,5.1编码的定义5.2无失真信源编码定长编码定理,31456002张安然,回顾：为什么进行信源编码？,理论上，信源传送信息所需要的信息率：极限熵H（X）或信息率失真函数R（D）.极限熵H（X）：多符号离散平稳信源实际上就是原始信源在不断地发出符号，随着信源之间的依赖关系（即信源的相关性）变多，信源的实际熵越小（第二章P32-33证明），越趋于H（X）。所以H（X）是离散平稳有记忆信源平均每发一个符号提供的信息量的最小值。,信息率失真函数R（D）：从允许一定失真的条件下，我们去寻找可以用较小的信息率来传送信息，即去掉某些不必要的成分，这时得到的信息率的最小值是R（D）。由此可见

2、，极限熵H（X）或信息率失真函数R（D）是理论上传送信息的最小值。而实际上，信源发出消息时包含了多余信息，即存在冗余度，冗余度体现了信源输出信号的信息携带效率。,冗余度,定义：衡量信源发出消息时包含了多余信息的物理量来源：1.信源符号的相关性。相关程度越大，信源的实际上越小，越趋向于H（X）。2.信源符号分布的不均匀性。等概率分布时信源熵最大，不均匀分布时，信源熵减小。当各符号之间不存在依赖关系且为等概率分布时，信源实际熵趋于最大熵H0（X）,下面，以英文为例，计算文字信源的冗余度：首先给出英文字母（含空档）出现概率如下：,下面，首先求得独立等概率情况，即其次，计算独立不等概率情况，再次，若仅

3、考虑字母有一维相关性，求H2最后，利用统计推断方法求出，由于采用的逼近的方法和所取的样本的不同，推算值也有不同，这里采用Shannon的推断值。,采用等概率下传送方式，计算得这样，可以计算出R=0.71。这一结论说明，英文信源，从理论上看71是多余成分。直观地说100页英文书，理论上看仅有29页是有效的，其余71页是多余的。正是由于这一多余量的存在，才有可能对英文信源进行压缩编码。消息的冗余，特别是大量的冗余，为我们提高通信效率，压缩信号容量提供了基础。为了提高传输效率，对大量冗余进行压缩，即信源编码。,信源编码,信源编码是以提高通信的有效性为目的编码。采用的一般方法是压缩每个信源符号的平均比

4、特数。同样多的信息用较少的信息率来传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。信源编码的目的就是要减少冗余，提高编码效率。,信源编码的基本途径（即消除冗余度来源的途径）有两个：使序列中的各个符号尽可能地互相独立，即解除相关性；使编码中各个符号出现的概率尽可能地相等，即概率均匀化。,根据能否在解码后完全准确的恢复出原始消息（可逆）分为：无失真信源编码 限失真信源编码 无失真编码只适用于离散信源；对于连续信源，只能在失真受限制的情况下进行限失真编码。前者主要用于文字、数据信源的压缩;后者主要用于图像、语音信源的压缩。,一般地：由于这些定理都要求符号数很大（参考极限熵H（X）序列长

5、趋向于）才能使它的值接近所规定的值，因而这些定理被称为极限定理。1.无失真信源编码定理称为第一极限定理；2.信道编码定理(包括离散和连续信道)称为第二极限定理；3.限失真信源编码定理称为第三极限定理。这些定理的完善化，是香农信息论的主要内容。,编码定理不但证明了必然存在一种编码方法，使代码的平均长度可任意接近但不能低于符号熵，而且还阐明了达到这目标的途径，就是使概率与码长匹配。例如之后学习的变长编码，使出现概率小的信源符号用短码编，出现概率大的用长的码编，这样就可以使平均每个信源符号的输出符号降低。以哈夫曼编码为例：,哈夫曼编码的编码结果可以看出，信源出现符号小的a7编码长度是4位，信源出现符

6、号小的a1编码长度是2位，平均码长计算得2.72码元/符号，输出符号码长减小。,信源编码（主要内容）,信源编码定理信源编码基本概念定长信源编码变长信源编码信源编码方法离散信源编码连续信源编码相关信源编码变换编码,5.1编码的定义,分组码定义：将信源消息分成若干组，即符号序列Xi=xi1,xi2,.,xiL,序列中的每一个符号取自于符号集A，xil属于a1，a2，ai，an，而每个符号序列Xi依照固定的码表映射成一个码字Yi，这样的码称为分组码，有时也叫块码。分组码百科定义：它把信源待发的信息序列按固定的位一组划分成消息组,再将每一消息组独立变换成长为n(n)的二进制数字组,称为码字。如果消息组

7、的数目为M(显然M2),由此所获得的M个码字的全体便称为码长为n、信息数目为M的分组码,记为【n，M】。,只有分组码才有对应的码表，而非分组码中不存在码表。编码定义：二元信道（基本符号0,1）中，若将信源X通过这样的二元信道传输，就必须把信源符号ai 变换成有1.0符号组成的码符号序列，这个过程就是信源编码。编码的广泛定义：编码是信息从一种形式或格式转换为另一种形式的过程也称为计算机编程语言的代码简称编码。用预先规定的方法将文字、数字或其它对象编成数码，或将信息、数据转换成规定的电脉冲信号。我们之后介绍的是二元信道中的编码。,信源编码器示意图,信源符号集Xa1,a2,an：代表信源发出的消息，

8、共有n个信源符号。码表（码符号集）码符号集中的元素称为码元或者码符号，适合信道传输。码字集合Y=W1,W2,Wn：与信源符号一一对应，码字由码符号序列组成。,一个简单的编码实例,【例】对学生的成绩等级进行编码，分为优、良、中、差4个 等级。信源符号集Xa1,a2,an=优、良、中、差用二元码，码符号集合为0,1码字集合为 Y=W1,W2,Wn=00,01,10,11编码过程：00代表优，01代表良，10代表中，11代表差。每一个码字都是2个码符号组成的序列。,(1)奇异码与非奇异码,书中定义：若信源符号和码字是一一对应的，则该码是非奇异码；反之，是奇异码。这个定义可以理解为数学意义上的映射，每

9、一个符号均可以在码字集合中找到唯一对应的码。华中科技大学书中定义：若一种码中的所有码字都互不相同，则称此分组码为非奇异码，否则称为奇异码。可以看出，表中码1是奇异码，有两个11码。其他是非奇异码,（2）唯一可译码,书中定义：任意有限长序列，只能被分割成一个个的码字，便可以称为唯一可译码。例如给定一个信源,编码后的码字有0,，10，11，就是说信源只能变出这三种码字。任意给定一个序列100111000，按照分割成信源定义的三种码字可以分成10,0,11,10,0,0唯一一种方式。任何其他分割法都会产生信源不能发出的码字。这种码字就是唯一可译码码1是奇异码，必定不能唯一可译，因为如果分到11码，就

10、不确定是信源发的a2还是a4码2也不是唯一可译码，看码2的码字特点，若是序列中有一段码是00，我们即可以分成00对应a3，也可以分成0,0对应发两次a1.码3是唯一可译码。因为分解时只要遇到1就看后面有几个0，确定唯一译码,（3）非即时码和即时码,书中定义：如果接受端收到一个完整的码字后，不能立即译码，还需要等下一个码字开始接受后才能判断是否可以译码，这样的码叫做非即时码。一个唯一可译码成为即时码的充要条件是其中任何一个码字都不是其它码字的前缀（前缀问题）这里是建立在唯一可译码基础上的，表中码3码4是唯一可译码。码3，接到0后不能确定到某个码，码4只要接到1就确认是哪个码了。,(1)哪些是唯一

11、可译码（2）哪些是即时码（3）计算平均码长和编码效率,树图法,对于m进制树图，有树根、树枝和节点。树图最顶部的节点称为树根；每一个分支称为树枝；树枝的尽头称为节点，每个节点生出的树枝数目等于码符号数m；从树根到终端节点各树枝代表的码符号顺次连接，就得到了编码码字。,m2的二进制树图,整树与非整树,考虑一个树有r阶节点整树：码树的各个分支都延伸到最后一级端点，此时，将共有mr个码字；非整树：码树中存在分支，没有延伸到最后一级端点，此时，将少于mr个码字。,整树图例,非整树图例,即时码的构造树图法,编码：用树图法构造即时码，只要将信源符号全部对应于终端节点，而不是中间节点即可。这样就可以保证任何一

12、个码字都不是其它码字的前缀解码：按照码符号的顺序，从根节点依次查询到终端节点，就得到对应的信源符号。再从根节点对剩下的码符号序列做相同的处理，直到处理完码符号序列中所有的码符号对应表中的码4分析,唯一可译码存在的充要条件,克劳夫特不等式：m是进制数，n是信源符号数1.唯一可译码必定满足不等式2.满足不等式的码存在唯一可译码，但不一定是唯一可译码此定理只证明存在性,例题p88,无失真信源编码概念,无失真信源编码：要求精确地复现信源的输出保证信源的全部信息无损的送给信宿研究方法：只考虑有效性，不考虑可靠性将信道编解码看成一个无噪无损信道,输入序列X长度L，每一位n种可能。编码后Y的长度是KL，每一

13、位m种可能。北京邮电大学周炯槃的书中解释无失真条件：无失真：nL mK(每个消息序列有对应的编码码组)信源输出有效：nL 大于等于mK（编码输出的码组数小于信源消息序列总数）,信源编码,输入,输出,XX1,X2,XL,YY1,Y2,YKL,由无失真条件可得：,编码的目的：希望传送Y时所需的信息率（信息率是通过接收到的信息可获得的发送信息的信息量,即互信息。单位:bit/符号）最小。序列Y的最大信息量是Klogm(序列长乘以每个符号的最大信息熵)所以送一个信源符号x需要的平均信息率为：信息率最小就是找到一种编码方式使 最小。,定长编码定理,定义：各个码字码长都相等的码 定长码中每个码字长度相等，

14、所以只要定长码是非奇异码，则必为唯一可译码,唯一可译定长码的存在条件,对一个简单信源X进行定长编码，信源X存在唯一可译定长码的条件是：nmK其中，n是信源X的符号个数，m是信道基本码符号数，K 是定长码的码长。此为华中科技大学书中给出的定理。,英文电报有32个符号，即n32，26个英文字母加上6个标点符号采用二元码时，则m2。对信源X的逐个符号xi,i1,2,32进行二元编码，则 322K这就是说，每个英文电报符号至少要用5位二元符号进行编码才能得到唯一可译码,定长信源编码定理（香农第一等长编码公式）,定理内容：由L个符号组成的，每个符号的熵为HL（X）的无记忆平稳信源符号XX1,X2,XL，

15、编码K个符号YY1,Y2,YKL（每个符号m种可能）对任意0,0，只要满足则当L足够大时，必可使译码差错小于。反之，若则当L足够大时，可以实现几乎无失真编码，译码错误概率趋于1，几乎必定出错。,定长信源编码定理的意义：信源经过定长编码后，所能携带的信息量，一定要大于信源所携带的平均信息量(熵)。若是小于，肯定不能无失真若是等于，是临界状态。可能失真，也可能不失真。,例如某信源有8种符号，L=1，信源序列熵=log8=3bit/符号。说明可以用3bit的信息屡进行无失真编码。采用二进制，0,1，等概时lb8=3 bit/符号（这是等概信源的）若信源非等概，p(ai)=0.4,0.18,0.1,0

16、.1,0.07,0.06,0.05,0.04,则 H(X)=2.55 bit/符号的信息率在二进制中可以表示22.55=5.856种码字，还有部分符号没有编码，当出现没编码的符号只能用其他符号代替，这就是失真。当L足够大时，有些符号的发生概率变得很小，差错率就变得很小。,典型序列及非典型序列的说明,引入信源的不等概统计特性后，无需将信源所有符号序列编码，仅对大概率典型序列编码，小的不编码（会失真），下面介绍北京邮电大学周炯槃书中的对典型序列及非典型序列的说明：当L足够大时，根据大数定理，其中一些序列的集合会以趋向概率1出现，如果每一个序列等概率出现，这个概率为2-LH（X）（这个计算是先确定等

17、概率的信息上是 log 2-LH（X）这个计算=LH(X),就是是平均每个序列的信息量，L长序列，序列中每个符号信息量是H(X)。）所以证明这个集合就是典型序列集合，共有2 LH（X）个典型序列，只需要对这些序列编码即可。这一概念对应本书中的互补集合。,L增大时，典型序列数目增多，小概率事件概率更小。根据切比雪夫不等式式中，为信源序列的自信息方差，为一正数。当 和 均为定值时，P可以小于任一正数。信源序列长度L必满足可以看出，L无穷大时，误码概率趋向于0.,信源编码效率,对于等长编码，编码效率一定是小于或等于1的数。对同一信源来说，若码的平均码长越短，信息传输率就越高，这时也越接近1。所以编码

18、效率可以用来衡量各种编码方法在有效性方面的优劣。,上面介绍到了，L无限长时，实际编码长变小，越接近最小可能码长。看下面的例子：设离散无记忆信源概率空间为信源熵为对信源符号采用定长二元编码，要求编码效率为若取L=1，则可以算出：即每个符号用2.83bit进行定长二元编码，共有7.11种可能性，按7种算，有一个符号没有对应的码字，取概率最小的a8，差错仍0.04，太大。,试想信源发送的L很大时，可以用编码效率的公式计算：信源序列的自信息方差为若要求译码错误概率则可见，一定错误概率下，要对L=108个信源符号一起编码，对存储和处理要求太高，无法实现。,如果不限制编码效率，用3bit信息率（即H(X)

19、+=3）来对8个符号编码，L=1，有8种可能性，正好实现无差错译码，。这种情况，L足够大关于差错概率的公式不适用了。但此时编码效率 为2.55/3=85%。因此一般来说，当L有限时，高传输效率的定长码往往引入一定的失真和错误，它不像变长码那样可以实现无失真编码。定长编码在理论上可以达到很高的编码效率，但是从上例中可以看到，在编码效率、错误概率要求较严格的情况下，扩展次数L需要非常大，这在实际工程中是无法实现的。在实际过程中，普遍使用变长编码。,定长编码与变长编码比较,定长编码要实现无失真,需要的编码长度大,效率不高。变长编码的编码长度不需要很大就可以达到相当高的编码效率,而且可以实现无失真编码.香农编码、费诺编码和哈夫曼编码是常见的离散无记忆信源编码方法.采用变长编码L不需要很大就可以达到相当高的编码效率，而且可以实现元失真编码。且随着L的增大编码效率越来越接近于1。（张晓梅 常见离散信源编码方法的比较【J】.福建电脑，2009,5,48-52）,参考文献,1曹雪虹。信息论与编码（第二版）。北京。清华大学出版社2周炯槃。通信原理（第3版）。北京;人民邮电出版社3陈运。信息论与编码（第二版）。北京：电子工业出版社4张晓梅 常见离散信源编码方法的比较【J】.福建电脑，2009,5,48-52,谢谢！,