信息论与编码无失真信源编码优秀课件.ppt

《信息论与编码无失真信源编码优秀课件.ppt》由会员分享，可在线阅读，更多相关《信息论与编码无失真信源编码优秀课件.ppt（47页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、信息论与编码无失真信源编码第1页，本讲稿共47页信息论与编码-无失真信源编码第三章第三章 无失真信源编码无失真信源编码通信的实质是信息的传输。而高速度、高质量地传送信息是信息传输的基本问题。将信源信息通过信道传送给信宿，怎样才能做到尽可能不失真而又快速呢？这就需要解决两个问题：第一，在不失真或允许一定失真的条件下，如何用尽可能少的符号来传送信源信息；第二，在信道受干扰的情况下，如何增加信号的抗干扰能力，同时又使得信息传输率最大。为了解决这两个问题，就要引入信源编码和信道编码。第2页，本讲稿共47页信息论与编码-无失真信源编码一般来说，提高抗干扰能力（降低失真或错误概率）往往是以降低信息传输率为

2、代价的；反之，要提高信息传输率常常又会使抗干扰能力减弱。二者是有矛盾的。然而在信息论的编码定理中，已从理论上证明，至少存在某种最佳的编码或信息处理方法，能够解决上述矛盾，做到既可靠又有效地传输信息。这些结论对各种通信系统的设计和估价具有重大的理论指导意义。第3页，本讲稿共47页信息论与编码-无失真信源编码3.1 编码的定义编码的定义编码实质上是对信源的原始符号按一定的数学规则进行的一种变换。讨论无失真信源编码，可以不考虑干扰问题，所以它的数学描述比较简单。图3.1是一个信源编码器，它的输入是信源符号 ，同时存在另一符号 ，一般来说，元素 是适合信道传输的，称为码符号（或者码元）。编码器的功能就

3、是将信源符号集中的符第4页，本讲稿共47页信息论与编码-无失真信源编码号 （或者长为N的信源符号序列）变换成由 组成的长度为 的一一对应的序列。编 码 器输出图3.1 无失真信源编码器第5页，本讲稿共47页信息论与编码-无失真信源编码输出的码符号序列称为码字，长度 称为码字长度或简称码长。可见，编码就是从信源符号到码符号的一种映射。若要实现无失真编码，则这种映射必须是一一对应的，并且是可逆的。码符号的分类码符号的分类：下图是一个码分类图第6页，本讲稿共47页信息论与编码-无失真信源编码第7页，本讲稿共47页信息论与编码-无失真信源编码下面，我们给出这些码的定义。1.二元码若码符号集为 ，所有码

4、字都是一些二元序列，则称为二元码。二元码是数字通信和计算机系统中最常用的一种码。2.等长码：若一组码中所有码字的码长都相同，即 ，则称为等长码。3.变长码：若一组码组中所有码字的码长各不相同，则称为变长码。第8页，本讲稿共47页信息论与编码-无失真信源编码4.非奇异码：若一组码中所有码字都不相同，则称为非奇异码。5.奇异码：若一组码中有相同的码字，则称为奇异码。6.唯一可译码：若码的任意一串有限长的码符号序列只能唯一地被译成所对应的信源符号序列，则此码称为唯一可译码，否则就称为非唯一可译码。第9页，本讲稿共47页信息论与编码-无失真信源编码7.非即时码和即时码：如果接收端收到一个完整的码字后，

5、不能立即译码，还要等下一个码字开始接收后才能判断是否可以译码，这样的码叫做非即时码。如果收到一个完整的码字以后，就可以立即译码，则叫做即时码。即时码要求任何一个码字都不是其他码字的前缀部分，也叫做异前缀码。第10页，本讲稿共47页信息论与编码-无失真信源编码n码树码树：即时码的一种简单构造方法是树图法。对给定码字的全体集合来说，可以用码树来描述它。所谓树，就是既有根、枝，又有节点，如图3.2所示，图中，最上端A为根节点，A、B、ABCD000E11111010010001图3.2第11页，本讲稿共47页信息论与编码-无失真信源编码C、D、E皆为节点，E为终端节点。A、B、C、D为中间节点，中间

6、节点不安排码字，而只在终端节点安排码字，每个终端节点所对应的码字就是从根节点出发到终端节点走过的路径上所对应的符号组成，如图3.2中的终端节点E，走过的路径为ABCDE，所对应的码符号分别为0、0、0、1，则E对应的码字为0001。可以看出，按树图法构成的码一定满足即时码的定义（一一对应，非前缀码）。第12页，本讲稿共47页信息论与编码-无失真信源编码从码树上可以得知，当第 阶的节点作为终端节点，且分配码字，则码字的码长为 。任一即时码都可以用树图法来表示。当码字长度给定后，用树图法安排的即时码不是唯一的。如图3.2中，如果把左树枝安排为1，右树枝安排为0，则得到不同的结果。对一个给定的码，画

7、出其对应的树，如果有中间节点安排了码字，则该码一定不是即时码。每个节点上都有 个分支的树称为满树，否则为第13页，本讲稿共47页信息论与编码-无失真信源编码非满树。即时码的码树图还可以用来译码。当收到一串码符号序列后，首先从根节点出发，根据接收到的第一个码符号来选择应走的第一条路径，再根据收到的第二个符号来选择应走的第二条路径，直到走到终端节点为止，就可以根据终端节点，立即判断出所接收的码字。然后从树根继续下一个码字的判断。这样，就可以将接收到的一串码符号序列译成对应的信源符号序列。第14页，本讲稿共47页信息论与编码-无失真信源编码n克拉夫特（Kraft）不等式定理3.1 对于码符号为 的任

8、意唯一可译码，其码字为 ，所对应的码长为 ，则必定满足克拉夫特不等式反之，若码长满足上面的不等式，则一定存在具有这样码长的即时码。注意：克拉夫特不等式只是说明唯一可译码是否第15页，本讲稿共47页信息论与编码-无失真信源编码存在，并不能作为唯一可译码的判据（可以排除，不能肯定）。如0，10，010，111满足克拉夫特不等式，但却不是唯一可译码。例题：设二进制码树中 ，对应的 ，由上述定理，可得因此不存在满足这种码长的唯一可译码。可以用树码进行检查。第16页，本讲稿共47页信息论与编码-无失真信源编码n唯一可译码的判断法（变长）：将码C中所有可能的尾随后缀组成一个集合F，当且仅当集合F中没有包含

9、任一码字，则可判断此码C为唯一可译码。集合F的构成方法：首先，观察码C中最短的码字是否是其它码字的前缀，若是，将其所有可能的尾随后缀排列出。而这些尾随后缀又有可能是某些码字的前缀，再将这些尾随后缀产生的新的尾随后缀列出，第17页，本讲稿共47页信息论与编码-无失真信源编码然后再观察这些新的尾随后缀是否是某些码字的前缀，再将产生的尾随后缀列出，依此下去，直到没有一个尾随后缀是码字的前缀为止。这样，首先获得了由最短的码字能引起的所有尾随后缀，接着，按照上述步骤将次短码字、等等所有码字可能产生的尾随后缀全部列出。由此得到由码C的所有可能的尾随后缀的集合F。例题：设码C=0,10,1100,1110,

10、1011,1101，根据上述测试方法，判断是否是唯一可译码。第18页，本讲稿共47页信息论与编码-无失真信源编码解：1.先看最短的码字：“0”，它不是其他码字 前缀，所以没有尾随后缀。2.再观察码字“10”，它是码字“1011”的前缀，因此有尾随后缀：101100100111010100110011101011第19页，本讲稿共47页信息论与编码-无失真信源编码所以，集合F=11，00，10，01，其中“10”为码字，故码C不是唯一可译码。第20页，本讲稿共47页信息论与编码-无失真信源编码3.2 定长编码定理定长编码定理前面已经说过，所谓信源编码，就是将信源符号序列变换成另一个序列（码字）。

11、设信源输出符号序列长度为L，码字的长度为 ，编码的目的，就是要是信源的信息率最小，也就是说，要用最少的符号来代表信源。在定长编码中，对每一个信源序列，都是定值，设等于K，我们的目的是寻找最小K值。要实现无失真的信源编码，要求信源符号第21页，本讲稿共47页信息论与编码-无失真信源编码与码字是一一对应的，并求由码字组成的符号序列的逆变换也是唯一的（唯一可译码）。定长编码定理定长编码定理：由L个符号组成的、每个符号熵为 的无记忆平稳信源符号序列 ，可用 个符号 （每个符号有m中可能值）进行定长变码。对任意 ，只要第22页，本讲稿共47页信息论与编码-无失真信源编码则当L足够大时，必可使译码差错小于

12、 ；反之，当时，译码差错一定是有限值，当L足够大时，译码几乎必定出错。式中，左边是输出码字每符号所能载荷的最大信息量第23页，本讲稿共47页信息论与编码-无失真信源编码所以等长编码定理告诉我们，只要码字传输的信息量大于信源序列携带的信息量，总可以实现几乎无失真的编码。条件时所取得符号数L足够大。设差错概率为 ，信源序列的自方差为则有：第24页，本讲稿共47页信息论与编码-无失真信源编码当 和 均为定值时，只要L足够大，可一小于任一整数 ，即此时要求：第25页，本讲稿共47页信息论与编码-无失真信源编码只要 足够小，就可以几乎无差错地译码，当然代价是L变得更大。令为码字最大平均符号信息量。定义编

13、码效率为：第26页，本讲稿共47页信息论与编码-无失真信源编码最佳编码效率为无失真信源编码定理从理论上阐明了编码效率接近于1的理想编码器的存在性，它使输出符号的信息率与信源熵之比接近于1，但要在实际中实现，则要求信源符号序列的L非常大进行统一编码才行，这往往是不现实的。例如：第27页，本讲稿共47页信息论与编码-无失真信源编码例题：设离散无记忆信源概率空间为信源熵为自信息方差为第28页，本讲稿共47页信息论与编码-无失真信源编码第29页，本讲稿共47页信息论与编码-无失真信源编码对信源符号采用定长二元编码，要求编码效率 ，无记忆信源有 ，因此可以得到如果要求译码错误概率 ，则第30页，本讲稿共

14、47页信息论与编码-无失真信源编码由此可见，在对编码效率和译码错误概率的要求不是十分苛刻的情况下，就需要 个信源符号一起进行编码，这对存储和处理技术的要求太高，目前还无法实现。如果用3比特来对上述信源的8个符号进行定长二元编码，L=1，此时可实现译码无差错，但编码效率只有2.55/3=85%。因此，一般说来，当L有限时，高传输效率的定长码往往要引入一定的失真和译码错误。解决的办法是可以采用变长编码。第31页，本讲稿共47页信息论与编码-无失真信源编码3.3 变长编码定理变长编码定理在变长编码中，码长是变化的。对同一信源，其即时码或唯一可译码可以有许多种。究竟哪一种好呢？从高速传输信息的观点来考

15、虑，当然 希望选择由短的码符号组成的码字，就是用码长来作为选择准则，为此我们引入码的平均长度。设信源为第32页，本讲稿共47页信息论与编码-无失真信源编码编码后的码字为其码长分别为因为对唯一可译码来说，信源符号与码字是一一对应的，所以有则这个码的平均长度为第33页，本讲稿共47页信息论与编码-无失真信源编码它是每个信源符号平均需用的码元数。对某一信源来说，若有一个唯一可译码，其平均长度小于所有其它的唯一可译码的平均长度，则该码称为紧致码，或称最佳码。无失真变长信源编码的基本问题就是要找最佳码。单个符号变长编码定理单个符号变长编码定理：若一离散无记忆信源的符号熵为H(X)，每个信源符号用m进制码

16、元进行变长编码，一定存在一种无失真编码方法，其码字平均长度 满足下面的不等式第34页，本讲稿共47页信息论与编码-无失真信源编码离散平稳无记忆序列变长编码定理（香农第一定离散平稳无记忆序列变长编码定理（香农第一定理）理）：对于平均符号熵为 的离散平稳无记忆信源，必存在一种无失真信源编码方法，使平均信息率 满足下面的不等式其中，为任意小正数。第35页，本讲稿共47页信息论与编码-无失真信源编码上面的两个定理实际上是一样的，可以由第一个推导出第二个。设用m进制码元做变长编码，序列长度为L个信源符号，则该序列所对应的码字的平均长度 满足下面的不等式而平均输出信息率为第36页，本讲稿共47页信息论与编

17、码-无失真信源编码故有当L足够大时，可使因此第37页，本讲稿共47页信息论与编码-无失真信源编码香农第一编码定理给出了码字的平均长度的下界和上界。但并不是说大于这上界不能构成唯一可译码，而是因为我们总是希望 尽可能短。定理说明当平均码长小于上界时，唯一可译码也存在。也就是说，定理给出的是最佳码的最短平均码长，并指出这个最短的平均码长与信源熵是有关的。编码效率为第38页，本讲稿共47页信息论与编码-无失真信源编码剩余度（冗余度）为例题：设离散无记忆信源的概率空间为第39页，本讲稿共47页信息论与编码-无失真信源编码其信源熵为若用二元定长编码（0，1）来构造一个即时码：，这时平均码长为编码效率为第

18、40页，本讲稿共47页信息论与编码-无失真信源编码输出的信息率为再对长度为2的信源序列进行变长编码，其即时码如下表所示：序列序列概率 即时码 序列序列概率 即时码 9/16 0 3/16 110 3/16 10 1/16 111第41页，本讲稿共47页信息论与编码-无失真信源编码这个码的平均长度为每一单个符号的平均码长为其编码效率为第42页，本讲稿共47页信息论与编码-无失真信源编码编码复杂了，但信息传输率和效率有了提高。同样可以求得信源序列长度增加到3和4时，进行变长编码所得的编码效率和信息传输率分别为如果对这一信源采用定长二元码编码，要求编码效率达到96%，允许译码错误概率 ，则第43页，

19、本讲稿共47页信息论与编码-无失真信源编码可以算出自信息方差为 为需要的信源序列长度为第44页，本讲稿共47页信息论与编码-无失真信源编码可以看出，使用定长编码时，为了使编码效率较高（96%），需要对非常长的信源序列进行编码，且总存在译码差错。而使用变长编码，为了使编码效率达到96%，只要L=2就行了，且可以实现无失真编码。当然，变长编码的译码相对来说要复杂一些。第45页，本讲稿共47页信息论与编码-无失真信源编码小结：小结：无失真信源编码无失真信源编码n一些编码的定义：定长码、变长码、奇异码、唯一可译码、即时码等，唯一可译码的判断。n定长编码定理定长编码定理的实质是说编码后的每一个符号所携带的信息量，不能少于信源的熵（每信源符号的平均信息量）。n变长编码定理第46页，本讲稿共47页无失真变长编码定理的实质是说，编码后的每一个符号所携带的平均信息量，不能少于信源的熵（每信源符号的平均信息量）。习题：信息论与编码-无失真信源编码第47页，本讲稿共47页