无失真信源编码ppt课件教学教程.ppt

第三章第三章 无失真信源编码无失真信源编码第一节第一节 编码的定义编码的定义第二节第二节 定长编码定理定长编码定理第三节第三节 变长编码定理变长编码定理第四节第四节 最佳编码最佳编码引言引言引言 编码分为编码分为信源编码信源编码和和信道编码信道编码，其中信源，其中信源编码又分为编码又分为无失真信源编码无失真信源编码和和限失真信源限失真信源编码编码。无失真信源编码无失真信源编码：适用于离散信源或数字：适用于离散信源或数字 信号。信号。限失真信源编码限失真信源编码：主要用于连续信源或模：主要用于连续信源或模拟信号，如语音、图像等信号的数字处理。拟信号，如语音、图像等信号的数字处理。香农信息论三大定理香农信息论三大定理:1.第一极限定理第一极限定理:无失真信源编码定理无失真信源编码定理.2.第二极限定理第二极限定理:信道编码定理（包括离信道编码定理（包括离 散和连续信道）散和连续信道）.3.第三极限定理第三极限定理:限失真信源编码定理限失真信源编码定理.信源编码的主要任务是什么信源编码的主要任务是什么?由于信源符号之间存在分布由于信源符号之间存在分布不均匀不均匀和和相相关性关性，使得信源存在冗余度，信源编码，使得信源存在冗余度，信源编码的的主要任务主要任务就是减少冗余，提高编码效就是减少冗余，提高编码效率。具体说，就是针对信源输出符号序率。具体说，就是针对信源输出符号序列的统计特性，寻找一定的方法把信源列的统计特性，寻找一定的方法把信源输出符号序列变换为最短的码字序列。输出符号序列变换为最短的码字序列。信源编码的基本途径信源编码的基本途径 是什么是什么?信源编码的信源编码的基本途径基本途径有两个，有两个，一是一是使序使序列中的各个符号尽可能地互相独立，即列中的各个符号尽可能地互相独立，即解除相关性；解除相关性；二是二是使编码中各个符号出使编码中各个符号出现的概率尽可能地相等，即概率均匀化。现的概率尽可能地相等，即概率均匀化。信源编码的基础是什么信源编码的基础是什么?信源编码的信源编码的基础基础是：两个编码定理，即是：两个编码定理，即无失真编码定理和限失真编码定理。无失真编码定理和限失真编码定理。编码定理证明编码定理证明：（1）必存在一种编码方法，使代码的平均长度必存在一种编码方法，使代码的平均长度可任意接近但不能低于符号熵可任意接近但不能低于符号熵 （2）达到这目标的途径，就是使概率与码长匹达到这目标的途径，就是使概率与码长匹配。配。说明说明：（1）无失真编码或可逆编码只适用于离散信源。无失真编码或可逆编码只适用于离散信源。（2 2）对于连续信源，编成代码后就无法无失真）对于连续信源，编成代码后就无法无失真地恢复原来的连续值，因为后者的取值可有无地恢复原来的连续值，因为后者的取值可有无限多个。此时只能根据限失真编码定理进行限限多个。此时只能根据限失真编码定理进行限失真编码失真编码 。什么分组码？什么分组码？设设:信源消息为符号序列信源消息为符号序列Xi，序列中的每个符号取自于符号集序列中的每个符号取自于符号集A，。而每个符号序列。而每个符号序列Xi依照固依照固 定的码表映射成一个码字定的码表映射成一个码字Yi，这样的码称为分组，这样的码称为分组 码，有时也叫块码。只有分组码才有对应的码表，码，有时也叫块码。只有分组码才有对应的码表，而非分组码中则不存在码表。而非分组码中则不存在码表。第一节 编码的定义信源编码器L长序列长序列K长码字长码字图图3-1-1 信源编码器信源编码器设设:信源输出的序列长度为信源输出的序列长度为1，即信源符号集，即信源符号集 信源概率空间为：信源概率空间为：二元信道的信道基本符号集为二元信道的信道基本符号集为0，1。若将信源。若将信源X通过一个二元信道传输，就必须把信源符号通过一个二元信道传输，就必须把信源符号xi变换成由变换成由0，1符号组成的码符号序列，即编码。符号组成的码符号序列，即编码。可用不同的码符号序列，如表可用不同的码符号序列，如表3 31111所示。所示。见书见书 (P35)P35)分组码的一些直观属性分组码的一些直观属性 码码非分组码非分组码分组码分组码奇异码奇异码非奇异码非奇异码非唯一可译码非唯一可译码唯一可译码唯一可译码非即时码非即时码即时码（非延长码）即时码（非延长码）码树图 A0100000000000001111111011111二进制码树二进制码树2000001111122222三进制码树三进制码树唯一可译码存在的充分和必要条件唯一可译码存在的充分和必要条件 用用树树的的概概念念可可导导出出唯唯一一可可译译码码存存在在的的充充分分和和必必要要条条件件，即即各各码码字字的的长长度度Ki应应符符合合克克劳劳夫夫特特不不等等式：式：(3-1-1)式中，式中，m是进制数，是进制数，n是信源符号数。是信源符号数。看书看书P36(例例3-1-1）无失真信源编码定理要研究的内容无失真信源编码定理要研究的内容 若信源输出符号序列的长度若信源输出符号序列的长度 ，即，即 变换成由变换成由K KL L个符号组成的码序列（码字个符号组成的码序列（码字)变换的要求变换的要求:(1)(1)能够无失真或无差错地从能够无失真或无差错地从Y恢复恢复X，也就是能正确地进行反变，也就是能正确地进行反变换或译码换或译码(2)传送传送Y时所需要的信息率最小时所需要的信息率最小 由由于于Y Yk k可可取取m m种种可可能能值值，即即平平均均每每个个符符号号输输出出的的最最大大信信息息量量为为logmlogm，K KL L长长码码字字的的最最大大信信息息量量为为K KL Llogmlogm。用用该该码码字字表表示示L L长长的的信信源源序序列列,则则送送出出一一个个信信源源符符号号所所需需要要的的信信息率平均为息率平均为:其中其中 是是Y Y所能编成的码字的个数。所能编成的码字的个数。信息率最小信息率最小，就是找到一种编码方式使，就是找到一种编码方式使 最小。最小。无失真信源编码定理要研究的内容无失真信源编码定理要研究的内容:(1)(1)最小信息率为多少时，才能得到无失真的译码？最小信息率为多少时，才能得到无失真的译码？(2)(2)若小于这个信息率是否还能无失真地译码？若小于这个信息率是否还能无失真地译码？定长编码定理定长编码定理 由由L个符号组成的、每个符号的熵为个符号组成的、每个符号的熵为HL（X）的无记忆）的无记忆平稳信源符号序列平稳信源符号序列 ，可用，可用KL个符号个符号 （每个符号有（每个符号有m种可能值）进行定长种可能值）进行定长编码。对任意编码。对任意 ，只要，只要 则当则当L足够大时，必可使译码差错小于足够大时，必可使译码差错小于 ；反之，当；反之，当 时，译码差错一定是有限值，而当时，译码差错一定是有限值，而当L足够大时，译码几足够大时，译码几乎必定出错。乎必定出错。第二节 定长编码定理 说明说明（1）当编码器容许的输出信息率，也就是当每）当编码器容许的输出信息率，也就是当每个信源符号所必须输出的码长是个信源符号所必须输出的码长是时，只要时，只要 ，这种编码器一定可以做到几，这种编码器一定可以做到几乎无失真，也就是收端的译码差错概率接近于零，乎无失真，也就是收端的译码差错概率接近于零，条件是所取的符号数条件是所取的符号数L足够大。足够大。（2）将定理的条件改写成）将定理的条件改写成其中：其中：左边：左边：KL长码字所能携带的最大信息量，长码字所能携带的最大信息量，右边：右边：L长信源序列携带的信息量。长信源序列携带的信息量。上述定理表明上述定理表明，只要码字所能携带的信息量大于，只要码字所能携带的信息量大于信源序列输出的信息量，则可以使传输几乎无信源序列输出的信息量，则可以使传输几乎无失真，当然条件是失真，当然条件是L足够大。足够大。反之，当反之，当 时，不可能构成无失真时，不可能构成无失真的编码，也就是不可能做一种编码器，能使收的编码，也就是不可能做一种编码器，能使收端译码时差错概率趋于零。端译码时差错概率趋于零。时，则为临界状态，可能无失真，时，则为临界状态，可能无失真，也可能有失真。也可能有失真。看看p38例子例子