《第五章 信源编码》由会员分享，可在线阅读，更多相关《第五章 信源编码（128页珍藏版）》请在金锄头文库上搜索。
1、第1章：概述,第2章：信源熵,第3章：信道容量,第4章：信息率失真函数,第5章：信源编码,第6章：信道编码,第7章：密码体制的安全性测度,信源编码,信源编码是以提高通信的有效性为目的编码。 通常通过压缩信源的冗余度来实现。 采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。同样多的信息用较少的码率来传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。,信源编码的基本途径有两个： 使序列中的各个符号尽可能地互相独立，即解除相关性； 使编码中各个符号出现的概率尽可能地相等，即概率均匀化。,信源编码的基础是信息论中的两个编码定理：无失真编码定理限失真编码定理 无失真编码只适用于离散
2、信源 对于连续信源，只能在失真受限制的情况下进行限失真编码,下面介绍几种典型的离散信源编码方法。,a1, a2, , aK为信源符号集，序列中每一个符号uml都取自信源符号集。 b1 ，b2 ，bD是适合信道传输的D个符号，用作信源编码器的编码符号。编码输出码字cm = cm1 cm2 cmn， c mkb1 ，b2 ，bD k = 1, 2 , , n ，n表示码字长度，简称码长,信源编码可看成是从信源符号集到码符号集的一种映射，即将信源符号集中的每个元素（可以是单符号，也可以是符号序列）映射成一个长度为n的码字。对于同一个信源，编码方法是多种的。,【例】 用u1 ，u2 ，u3，u4表示信
3、源的四个消息，码符号集为0,1，表5-1列出了该信源的几种不同编码。 表5-1 同一信源的几种不同编码,码的分类,3.变长码 若码字集合C中的所有码字cm (m = 1,2, ,M)，其码长不都相同，称码C为变长码，表5-1中列出的码3、码4 就是变长码。,2.等长码 在一组码字集合C中的所有码字cm (m = 1,2, ,M)，其码长都相同，则称这组码C为等长码，表3-1中列出的码1、码2 就码长n = 2等长码。,一般，可以将码简单的分成如下几类：1.二元码 若码符号集为0，1，则码字就是二元序列，称为二元码,二元码通过二进制信道传输，这是数字通信和计算机通信中最常见的一种码，表5-1列出
4、的4种码都是二元码。,5.非奇异码 从信源消息到码字的影射是一一对应的，每一个不同的信源消息都用不同的码字对其编码，例表5-1中的码2、码3和码4都是非奇异码。,4.奇异码 对奇异码来说，从信源消息到码字的影射不是一一对应的。例表5-1中的码1，信源消息u2和u4都用码字11对其编码，因此这种码就是奇异码，奇异码不具备惟一可译性。,原码的N次扩展码是将信源作N次扩展得到的新信源符号序列u（N）=u1 uN = (u11 u12 u1L) (uN1 uN2 uNL)，对应码符号序列c（N）=c1 cN = (c11 c12 c1n) (cN1 cN2 cNn) ，记集合C (N) = c1(N)
5、, c2(N), ，C (N) 即原码C的N次扩展码。,6.原码C的N次扩展码 原码C的N次扩展码中的每个元素是N次扩展信源中的序列所对应的N个码字组成的序列。,对于定长码，若原码是惟一可译码，则它的N次扩展码也是惟一可译 的，而对于变长码则不尽然，见表5-2。,7.惟一可译码,定义5.1 如果码的任意N次扩展码都是非奇异码，则称该码为惟一可译码。,8. 即时码 对于变长码，又有如下定义,定义5.2 对于码字c = c1 c2 cn,称c、 = c1 c2 ci (i n)为码字c的字头（前缀）。,定义5.3 若码中任一码字都不是另一码字的字头，称该码为异字头码（无前缀码）。,表5-3中码3，
6、收到“1”后就知道一个码字已经完结，无须等待下一个符号抵达，所以无前缀码能够即时译码, 称之为即时可译码，简称即时码。而对于码2，收到“1”后，并不能立即做出判决，就是收到“10”也不能立即做出判决，则还要收到下面的码元才能做出判决。所以非异字头码不能即时译码，称为非即时码，由于非异字头码的其中一些码字是另一些码字的延长，故也称延长码。,显然，即时码是惟一可译码，而惟一可译码不一定是即时码。,即时码可用树图法来构造。,图5-3 用树图法编码,【例】 用树图法表示表5-2中的码3，如图5-3所示（D =2）。,图5-5 码的分类结构图,图5-5是码的分类结构图,由上面的结构图可看出，将码分为奇异
7、码和非奇异码两大类，我们只讨论非奇异码。非奇异码又分为惟一可译码和非惟一可译码两大类，我们只讨论惟一可译码。,平均码长的计算,对于变长码，码集C的平均码长，用符号 表示，定义为码C中每个码字cm( m = 1, 2, ，M)其码长的概率加权平均值为(3-1)式中nm是码字cm所对应的码字的长度，p ( cm )是码字cm出现的概率。,对于等长码，由于码集C中的每个码字的码长都相同，平均码长就等于每个码字的码长,K,p,k,p,k,K,m,m,m,m,m,=,=,=,=,=,1,1,),(,),(,c,c,【例】 给定信源 ，为提高传输效率，使平均码长尽可能短，遵照概率大取码长短，概率小取码长长
8、的原则对上述信源进行二进制不等长编码，得到，求编码后的信息传输率R 。,（比特/符号）（码元/符号）,等长码及等长编码定理,考虑对一简单信源S进行等长编码，信源符号集有n个符号，码符号集含m个符号，码字长度记为K。要得到惟一可译码，必须满足下式 n mK,对单符号信源S的L次扩展信源S（L）进行等长编码，要得到长为K的惟一可译码，必须满足 n L mK （5-5） 对式（5-5）两边取对数，得（5-6）,对于那些出现概率极小的字符序列不予编码，这样可以减小平均码长，当然这样会带来一定的失真。下面的定理 将证明，当满足一定的条件时，在L 时，失真pe 0,译码,定长编码定理：,1,1,反之,2,
9、编码效率：,变长码及变长编码定理,变长码,对变长码的讨论是在L足够大的条件下得到的结论，当L为有限值时，则总会带来一定程度的失真。对于变长码，往往在L不是很大的情况下就可编出高效且无失真的码。变长码也要求原码的任意L次扩展码也是惟一可译的。变长码分为即时码和延长码，为保证即时译码，要求变长惟一可译码采用即时码。对于变长码，要求整个码集的平均码长力求最小，此时编码效率最高。对于给定信源，使平均码长达到最小的编码方法，称为最佳编码，得到的码集称为最佳码。,克拉夫特不等式,定理5.2只是说是存在惟一可译码的充要条件，这里强调的是“存在”，但它并不是唯一可译码的充要条件，换言之，惟一可译码一定满足克拉
10、夫特不等式，反之，满足克拉夫特不等式的码不一定是惟一可译码。,变长编码定理,定理5.3 给定熵为H（X）的离散无记忆信源，及有m个元素的码符号集，则总可找到一种无失真编码方法，构成惟一可译码，其平均码长 满足：（5-19）,定理5.4 变长编码定理 (Shannon第一定理) 给定熵为H（X）的离散无记忆信源 ，其L次扩展信源 的熵记为H（X），给定有m个元素的码符号集，对扩展信源进行编码，总可以找到一种惟一可译码，使码长 满足(5-23),记 为信源每个符号所对应的平均码字数，则式(5-23)为（5-24）,Shannon第一定理的物理意义在于：对信源进行编码，使编码后的码集中各码字尽可能等
11、概分布，如果将这码集看成为一个新的信源，这时新信源所含信息量最大。,编码效率(5-26) 是一个无量纲的数，一般情况下1，在极限情况下=1。,5.1 离散信源编码,5.2 连续信源编码,5.3 相关信源编码,5.4 变换编码,5.1.4 赫夫曼编码,5.1.3 费诺编码,5.1.5 游程编码,5.1.6 冗余位编码,5.1.1 码字唯一可译的条件,5.1.2 香农编码,如何分离码字？,如果0，01都是码字，译码时如何分离？,？,判断以下码字是否可分离？,例2.4.1,对离散无记忆信源，消息长度为L，符号熵为H(X),对信源进行m元变长编码，一定存在无失真的信源编码方法，,5.1.4 赫夫曼编码
12、,5.1.3 费诺编码,5.1.5 游程编码,5.1.6 冗余位编码,5.1.1 码字唯一可译的条件,5.1.2 香农编码,5.1.2 香农编码,设有离散无记忆信源,1,2,3,4,香农编码方法的步骤,例,编码过程,（1）,5.1.4 赫夫曼编码,5.1.3 费诺编码,5.1.5 游程编码,5.1.6 冗余位编码,5.1.1 码字唯一可译的条件,5.1.2 香农编码,5.1.3 费诺编码,对概率按m进行分组，使每组概 率尽可能相等,给每个分组分配一个码元,对每个分组重复2、3步，直到不可分为止,1,2,3,4,例,编码过程,可以看出本例中费诺码有较高的编码效率。 费诺码比较适合于每次分组概率都
13、很接近的信源。,5.1.4 赫夫曼编码,5.1.3 费诺编码,5.1.5 游程编码,5.1.6 冗余位编码,5.1.1 码字唯一可译的条件,5.1.2 香农编码,将信源符号按概率由大到小顺序排队,给两个概率最小的符号各分配一个码位，将其概率相加后合并作为一个新的符号，与剩下的符号一起，再重新排队,给缩减信源中概率最小的符号各分配一个码元,重复步骤2、3直至概率和为1,2,1,4,3,5.1.4 赫夫曼编码,例,编码过程,说明： Huffman码的编码方法不是唯一的。首先，每 次对缩减信源两个最小的符号分配“0”和“1”码 元试任意的，所以可得到不同的码字。只要在 各次缩减信源中保持码元分配的一
14、致性，即能 得到可分离码字。不同的码元分配，得到的具体 码字不同，但码长，平均码长都不变，所以没有 本质区别。其次，若合并后的新符号的概率与其 他符号的概率相等，从编码的方法上来说，这几 个符号的次序可任意排列，编出的码都是正确的，但得到的码字不同。不同的编法得到的码字长度也不尽相同。,对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将合并的概率放在上面，这样可获得较小的码方差。 如下面的例子,例 设有离散无记忆信源,用两种不同的方法对其编二进制huffma
15、n码,方法一,方法二,两种不同的编码方法得到的码字和码长的对比,平均码长和编码效率,两种编码方法编出的码字的码长方差比较,可以看出第二种编码方法的码长方差要小 许多。这意味着第二种编码方法的码长变 化较小，比较接近平均码长。由此可以得 到一个结论(怎样得到码方差较小的huffman 编码)。,结论： 进行赫夫曼编码时，为得到码方差最小的码，应使合并的信源符号位于缩减信源序列尽可能高的位置上，以减少再次合并的次数，充分利用短码。,5.1.4 赫夫曼编码,5.1.3 费诺编码,5.1.5 游程编码,5.1.6 冗余位编码,5.1.1 码字唯一可译的条件,5.1.2 香农编码,5.1.5 游程编码,前面的几种编码方法主要时针对无记忆信源，对有记忆信源，这些编码方法的效率并不高，特别是对二元相关信源，需要一些其它的方法。游程编码就是这样的方法，对相关信源的编码更有效。游程：指数字序列中连续出现相同符号的一段。在二元信源中，连续的一段0称为一个0游程，0的个数称为此游程的长度，同样，也有1游程。游程序列：用交替出现的0游程、1游程的长度，来表示任意二元序列而产生的一个新序列。它和二元序列是一个一一对应的变换。,000101110010001,
