信息论第三章离散信源无失真编码

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

2、解决以下两个问题。提高传输效率提高传输效率 增强通信的可靠性增强通信的可靠性 （1）提高传输效率提高传输效率，用尽可能少的信道传用尽可能少的信道传输符号来传递信源消输符号来传递信源消息，目的是提高传输息，目的是提高传输效率，这是信源编码效率，这是信源编码主要应考虑的问题。主要应考虑的问题。这里又分两种情况讨这里又分两种情况讨论，即允许接收信号论，即允许接收信号有一定的失真或不允有一定的失真或不允许失真。许失真。 综上所述，提高抗干扰能力往往是以降低信息传输效率为综上所述，提高抗干扰能力往往是以降低信息传输效率为代价的，而为了提高传输效率又往往削弱了其抗干扰能力。代价的，而为了提高传输效率又往往

3、削弱了其抗干扰能力。这样，设计者在取舍之间就要作均衡考虑。这样，设计者在取舍之间就要作均衡考虑。 （2 2） 增强通信的可靠性增强通信的可靠性如何增加信号的抗干扰能力，如何增加信号的抗干扰能力，提高传输的可靠性，这是信道提高传输的可靠性，这是信道编码主要考虑的问题。解决这编码主要考虑的问题。解决这一问题，一般是采用冗余编码一问题，一般是采用冗余编码法，赋予信码自身一定的纠错法，赋予信码自身一定的纠错和检错能力，只要采取适当的和检错能力，只要采取适当的信道编码和译码措施，就可使信道编码和译码措施，就可使信道传输的差错概率降到允许信道传输的差错概率降到允许的范围之内。的范围之内。信源编码包括两个功

4、能：信源编码包括两个功能： （1 1） 将信源符号变换成适合信道传输的符号；将信源符号变换成适合信道传输的符号； （2 2） 压缩信源冗余度，提高传输效率。压缩信源冗余度，提高传输效率。 a1, a2, , aK 为信源符号集，序列中每一个符号为信源符号集，序列中每一个符号uml都都取自信源符号集。取自信源符号集。 b1 ，b2 ，bD 是适合信道传输的是适合信道传输的D个符号，用作信个符号，用作信源编码器的编码符号。编码输出码字源编码器的编码符号。编码输出码字cm = cm1 cm2 cmn， c mk b1 ，b2 ，bD k = 1, 2 , , n ，n表示码字长表示码字长度，简称度，

5、简称码长码长 信源符号信源符号 a1,a2, , aK 信道符号（码符号）信道符号（码符号） b1, b2, , bD 图图3-1 3-1 信源编码器模型信源编码器模型 信源信源 信源编码器信源编码器 一般来说，信源编码可归纳为如图一般来说，信源编码可归纳为如图3-1所示的模型。所示的模型。 消息消息 ui = ui1 ui2 uiL 码字码字ci = ci1 ci2 cin 信源编码可看成是从信源符号集到码符号集的一种映射，即将信源编码可看成是从信源符号集到码符号集的一种映射，即将信源符号集中的每个元素（可以是单符号，也可以是符号序列）映信源符号集中的每个元素（可以是单符号，也可以是符号序列

6、）映射成一个长度为射成一个长度为n的码字。对于同一个信源，编码方法是多种的。的码字。对于同一个信源，编码方法是多种的。【例【例3.3】 用用 u1 ，u2 ，u3，u4 表示信源的四个消息，码符号集为表示信源的四个消息，码符号集为0,1，表，表3-1列出了该信源的几种不同编码。列出了该信源的几种不同编码。表表3-1 同一信源的几种不同编码同一信源的几种不同编码信源信源消息消息各消息各消息概率概率码码1 1码码2 2码码3 3码码4 4u1q( (u1) )000001u2q( (u2) )1101110u3q( (u3) )101000100u4q( (u4) )11111110003.1.1

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

8、通过二进制信道传输，这是数字通信和计算机通信中最常见的一种码。信中最常见的一种码。 4.奇异码奇异码对奇异码来说，从信源消息到码对奇异码来说，从信源消息到码字的影射不是一一对应的。奇异码字的影射不是一一对应的。奇异码不具备惟一可译性。不具备惟一可译性。信源信源消息消息各消息各消息概率概率码码1 1码码2 2码码3 3码码4 4u1q( (u1) )000001u2q( (u2) )1101110u3q( (u3) )101000100u4q( (u4) )1111111000表表3-1 同一信源的几种不同编码同一信源的几种不同编码 5.非奇异码非奇异码从信源消息到码字的影射是一一对应的从信源消

9、息到码字的影射是一一对应的，每一个不同的信源消息都用不同的码，每一个不同的信源消息都用不同的码字对其编码。字对其编码。信源信源消息消息各消息各消息概率概率码码1 1码码2 2码码3 3码码4 4u1q( (u1) )000001u2q( (u2) )1101110u3q( (u3) )101000100u4q( (u4) )1111111000表表3-1 同一信源的几种不同编码同一信源的几种不同编码扩展信源扩展信源 信源编码器信源编码器 信源符号信源符号 a1,a2, , aK 信道符号（码符号）信道符号（码符号） b1, b2, , bD 消息消息 u1 uN = (u11 u12 u1L)

10、 (uN1 uN2 uNL) N次扩展码字次扩展码字 c1 cN = (c11 c12 c1n) (cN1 cN2 cNn)图图3-2 3-2 N次扩展信源编码器模型次扩展信源编码器模型 原码的原码的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), c2(N), ，C (N) 即原码即原码C的的N次扩展码。次扩展码。

11、 6.原码原码C的的N次扩展码次扩展码原码原码C的的N次扩展码中的每个元素是次扩展码中的每个元素是N次扩展信源中的序列所对次扩展信源中的序列所对应的应的N个码字组成的序列。个码字组成的序列。对于定长码，对于定长码，若原码是惟一可译码，则它的若原码是惟一可译码，则它的N次扩展码也是惟一次扩展码也是惟一可译的可译的，而对于变长码则不尽然，见表，而对于变长码则不尽然，见表3-2。 7.惟一可译码惟一可译码定义定义3.1 如果码的任意如果码的任意N次扩展码都是非奇异码，则称该码为次扩展码都是非奇异码，则称该码为惟一可译码。惟一可译码。信源信源消息消息各消息各消息概率概率码码1 1码码2 2码码3 3码

12、码4 4u1q( (u1) )000001u2q( (u2) )1101110u3q( (u3) )101000100u4q( (u4) )1111111000表表3-1 同一信源的几种不同编码同一信源的几种不同编码对于定长码，若原码是惟一可译码，则它的对于定长码，若原码是惟一可译码，则它的N次扩展码也是惟次扩展码也是惟一可译的，一可译的，而对于变长码则不尽然而对于变长码则不尽然，见表，见表3-2。信源消息信源消息各消息概各消息概率率码码1 1码码2 2码码3 3u1q( (u1) )011u2q( (u2) )11001u3q( (u3) )00100001u4q( (u4) )111000

13、0001表表3-2 同一信源的几种不同变长编码同一信源的几种不同变长编码 7.惟一可译码惟一可译码 8. 即时码即时码对于变长码，又有如下定义对于变长码，又有如下定义定义定义3.2 对于码字对于码字c = c1 c2 cn, ,称称c、 = c1 c2 ci ( (i n) )为为码字码字c的字头（前缀）。的字头（前缀）。定义定义3.3 若码中任一码字若码中任一码字都不是另一码字的字头，都不是另一码字的字头，称该码为异字头码（无前称该码为异字头码（无前缀码）。缀码）。 表表3-3-2 2中码中码3，收到，收到“1”后就知道一个码字已经完结，后就知道一个码字已经完结，无须等待下一个符号抵达，所以

14、无前缀码能够即时译码无须等待下一个符号抵达，所以无前缀码能够即时译码, , 称称之为即时可译码，简称之为即时可译码，简称即时码即时码。 而对于码而对于码2，收到，收到“1”后，并不能立即做出判决，就是后，并不能立即做出判决，就是收到收到“10”也不能立即做出判决，则还要收到下面的码元才也不能立即做出判决，则还要收到下面的码元才能做出判决。所以非异字头码不能即时译码，称为能做出判决。所以非异字头码不能即时译码，称为非即时非即时码码，由于非异字头码的其中一些码字是另一些码字的延长，由于非异字头码的其中一些码字是另一些码字的延长，故也称延长码。故也称延长码。显然，即时码是惟一可译码，而惟一可译码不一

15、定是即显然，即时码是惟一可译码，而惟一可译码不一定是即时码。时码。 即时码可用树图法来构造。即时码可用树图法来构造。图图3-3 3-3 用树图法编码用树图法编码树根树根编编码码深度深度u1：1u2：01u3：001u4：00011 0 u1u2u3u41 1 1 0 0 【例【例3.4】 用树图法表示用树图法表示表表3-2中的码中的码3，如图，如图3-3所示所示（D =2）。）。码码奇异码奇异码非奇异码非奇异码非惟一可译码非惟一可译码 惟一可译码惟一可译码变长码变长码等长码等长码即时码即时码延长码延长码 图图3-5 3-5 码的分类结构图码的分类结构图 图图3-5是码的分类结构图是码的分类结构

16、图 由上面的结构图可看出，将码分为奇异码和非奇异码两大类，由上面的结构图可看出，将码分为奇异码和非奇异码两大类，我们只讨论我们只讨论非奇异码非奇异码。非奇异码又分为惟一可译码和非惟一。非奇异码又分为惟一可译码和非惟一可译码两大类，我们只讨论可译码两大类，我们只讨论惟一可译码惟一可译码。 3.1.2 平均码长的计算平均码长的计算 对于对于变长码变长码，码集，码集C的平均码长，用符号的平均码长，用符号 表示，定义为表示，定义为码码C中每个码字中每个码字cm( ( m = = 1, 2, ，M) )其码长的概率加权平均值为其码长的概率加权平均值为 (3-1) (3-1) 式中式中nm是码字是码字cm

17、所对应的码字的长度，所对应的码字的长度，p ( cm )是码字是码字cm出现的出现的概率。概率。 Mmmmpnn1)(c cn 对于对于等长码等长码，由于码集，由于码集C中的每个码字的码长都相同，平中的每个码字的码长都相同，平均码长就等于每个码字的码长均码长就等于每个码字的码长npnpnnmmmmm11)()(c cc c N次次扩展码扩展码的平均码长的平均码长 等于扩展码中码字长度的概率等于扩展码中码字长度的概率加权平均值。加权平均值。 对对于于2次次扩展码，有：扩展码，有： (3-2)(3-2) 设设nm, , ns分别是原信源消息分别是原信源消息um, , us所对应的码长所对应的码长,

18、 , cm, , cs是是um, , us所对应的码字，所对应的码字， 则式则式(3-2)中中的的nm + + ns是扩展后新的信源序列是扩展后新的信源序列nmns所对所对应的码字应的码字cmcs的长度；的长度； q q( (um) q (us)是是cmcs出现的概率。出现的概率。n smmssmuquqnnn3.1.3 信息传输速率信息传输速率 信道的信道的信息传输速率信息传输速率为信道单位时间内所传输的实际信为信道单位时间内所传输的实际信息量。若信息量以比特为单位，时间以秒为单位，则信息传输息量。若信息量以比特为单位，时间以秒为单位，则信息传输率定义为：率定义为： ( (比特比特/ /秒秒

19、) ) (3-3)(3-3)nXtHtR若信息量以比特为单位，时间以码元时间（传输一个码符号若信息量以比特为单位，时间以码元时间（传输一个码符号的时间）为单位，则信息传输率记为的时间）为单位，则信息传输率记为 ( (比特比特/ /码元时间码元时间) ) (3- (3-4)4) nXHRDn为编码后的平均码长；为编码后的平均码长；H(X)为信源熵；为信源熵；式中式中：t为传输一个码符号的时间。为传输一个码符号的时间。【例【例3.8】 给定信源给定信源 ，为，为提高传输效率，使平均码长尽可能短，遵照概率大取码长短，概率提高传输效率，使平均码长尽可能短，遵照概率大取码长短，概率小取码长长的原则对上述

20、信源进行二进制不等长编码，得到小取码长长的原则对上述信源进行二进制不等长编码，得到 ，求编码后的信息传输率，求编码后的信息传输率RD 。16116116116181814141)(76543210 xxxxxxxxXqX1111:101:1110:110:1001:01:1000:00:73625140 xxxxxxxx （比特（比特/ /符号）符号） （码元（码元/ /符号）符号） ( (比特比特/ /码元时间码元时间) ) 75. 22log75. 2161log161481log81241log412XH75. 21614481324122n 175. 275. 2nXHRD3.2 等长

21、码及等长编码定理等长码及等长编码定理对一简单信源对一简单信源S进行等长编码，信源符号集有进行等长编码，信源符号集有K个符号，码符个符号，码符号集含号集含D个符号，码字长度记为个符号，码字长度记为n。要得到惟一可译码，必须要得到惟一可译码，必须满足满足K D n信源信源消息消息各消息各消息概率概率码码1 1码码2 2码码3 3码码4 4u1q( (u1) )000001u2q( (u2) )1101110u3q( (u3) )101000100u4q( (u4) )1111111000表表3-1 同一信源的几种不同编码同一信源的几种不同编码3.2 等长码及等长编码定理等长码及等长编码定理对单符号

22、信源对单符号信源S的的L次扩展信源次扩展信源S（L）进行等长编码，要得到长进行等长编码，要得到长为为n的惟一可译码，必须满足的惟一可译码，必须满足K L D n （3-53-5）对式对式（3-5）两边取对数，得两边取对数，得 （3-63-6） DKLnloglog 对于那些出现概率极小的字符序列不予编码，这样可以对于那些出现概率极小的字符序列不予编码，这样可以减小平均码长，当然这样会带来一定的失真。减小平均码长，当然这样会带来一定的失真。定理定理3.1 等长编码定理等长编码定理 设离散无记忆信源设离散无记忆信源S = x1 ，x2 ，xk 的熵为的熵为H（X），S的的L维扩展维扩展信源为信源为

23、 ，对信源输出的，对信源输出的L长序列长序列si ，i = 1, 2, , KL 进行等长编码，码字是长度为进行等长编码，码字是长度为n的的D进制符号串，当满足条件进制符号串，当满足条件 ，则，则L 时，可使时，可使译码译码差错率差错率pe (、为无穷小量为无穷小量) )，反之，当，反之，当时，则不可能实现无差错编码。时，则不可能实现无差错编码。,21)(LkLSs ss ss s DXHLnlog DXHLnlog编码效率编码效率 定理定理3.1要求要求 ，即，即 ，可看出比值可看出比值 是一个小于是一个小于1的无量纲纯数，定义它为等长编码的编码的无量纲纯数，定义它为等长编码的编码效率，记为

24、效率，记为 （3-73-7） DXHLnlogDnXHLlog)(1DnXLHlog)(DnXLHlog)(3.3 3.3 变长码及变长编码定理变长码及变长编码定理 3.3.1 变长码变长码 对于变长码，往往在对于变长码，往往在L不是很大的情况下就可编出高效不是很大的情况下就可编出高效且无失真的码。且无失真的码。 变长码也要求原码的任意变长码也要求原码的任意L L次扩展码也是惟一可译的。次扩展码也是惟一可译的。变长码分为即时码和延长码，为保证即时译码，要求变长变长码分为即时码和延长码，为保证即时译码，要求变长惟一可译码采用即时码。惟一可译码采用即时码。 对于变长码，要求整个码集的平均码长力求最

25、小，此对于变长码，要求整个码集的平均码长力求最小，此时编码效率最高。时编码效率最高。 对于给定信源，使平均码长达到最小的编码方法，称对于给定信源，使平均码长达到最小的编码方法，称为为最佳编码最佳编码，得到的码集称为，得到的码集称为最佳码最佳码。3.3.2 克拉夫特不等式克拉夫特不等式 定理定理3.2 D进制码字集合进制码字集合C =c1, , c2, cM ，码集中码集中每一每一cm（m = 1, 2, , M）都是一个都是一个D进制符号串，设进制符号串，设c1, , c2, cM 对应的码长分别是对应的码长分别是n1, n2, , nM ，则存在唯一则存在唯一可译码的充要条件是可译码的充要条

26、件是 (3-10)(3-10) MmnmD11式（式（3-10）也称）也称克拉夫特不等式克拉夫特不等式 定理定理3.2只是说是只是说是存在存在惟一可译码的充要条件，这里强惟一可译码的充要条件，这里强调的是调的是“存在存在”，但它并不是唯一可译码的充要条件，换，但它并不是唯一可译码的充要条件，换言之，惟一可译码一定满足克拉夫特不等式，反之，满足言之，惟一可译码一定满足克拉夫特不等式，反之，满足克拉夫特不等式的码不一定是惟一可译码克拉夫特不等式的码不一定是惟一可译码。 3.3.3 变长编码定理变长编码定理 定理定理3.3 给定熵为给定熵为H（X）的离散无记忆信源，及有的离散无记忆信源，及有D个元素

27、的码符号集，则总可找到一种无失真编码方法，个元素的码符号集，则总可找到一种无失真编码方法，构成惟一可译码，其平均码长构成惟一可译码，其平均码长 满足：满足： （3-193-19）n DXHnDXHlog1log3.3.3 变长编码定理变长编码定理 定理定理3.4 变长编码定理变长编码定理 ( (Shannon第一定理第一定理) ) 给定熵为给定熵为H（X）的离散无记忆信源的离散无记忆信源 ，其其L次扩展信源次扩展信源 的熵记为的熵记为H（X），给定有给定有D个元素的码符号集，对扩展信源进行编码，总可以找到个元素的码符号集，对扩展信源进行编码，总可以找到一种惟一可译码，使码长一种惟一可译码，使码

28、长 满足满足 (3-23) (3-23) )()()()(2121MMxqxqxqxxxXqX)()()()(2121LMMqqqqx xx xx xx xx xx xX XX XLnLDXHLnDXHL1loglog记记 为信源每个符号所对应的平均码字数，则为信源每个符号所对应的平均码字数，则式式(3-23)为为 （3-243-24） nLnL LDXHnDXH1loglogShannonShannon第一定理的第一定理的物理意义物理意义在于：对信源进行编码，使在于：对信源进行编码，使编码后的码集中各码字尽可能等概分布，如果将这码集编码后的码集中各码字尽可能等概分布，如果将这码集看成为一个新

29、的信源，这时新信源所含信息量最大。看成为一个新的信源，这时新信源所含信息量最大。定义定义编码效率编码效率 (3-26) (3-26)是一个无量纲的数，一般情况下是一个无量纲的数，一般情况下1，在极限情况在极限情况下下=1。 DnXHnDXHloglog 对于同一种信源，三种编码法中以香农编码法的编码效对于同一种信源，三种编码法中以香农编码法的编码效率最低，费诺编码法也不是一种最佳编码法，但用这种方法率最低，费诺编码法也不是一种最佳编码法，但用这种方法有时候也能找到紧致码。有时候也能找到紧致码。 一般情况下，霍夫曼编码法得到的平均码长一般情况下，霍夫曼编码法得到的平均码长 最短，即最短，即编码效

30、率最高。编码效率最高。 编码效率编码效率定义为：定义为：DnXHlogn3.4 3.4 变长码的编码方法变长码的编码方法香农（香农（Shannon）编码法编码法费诺费诺( (Fano) )编码法编码法霍夫曼霍夫曼( (Huffman) )编码法编码法变长编码法：变长编码法：3.4.1 香农编码法香农编码法 二进制香农编码法其码长的取值范围二进制香农编码法其码长的取值范围: : - -log q (xm) nm - -log q (xm) +1 （3-303-30）记离散信源记离散信源 ，给定有，给定有D个个元素的码符号集，对信源进行变长编码，元素的码符号集，对信源进行变长编码，将各消息概率将各

31、消息概率q q( (x xm m) ) ( (m m = 1, 2, = 1, 2, , , M M) ) 写成如下的形式：写成如下的形式： )()()()(2121MMxqxqxqxxxXqXmtmDxq1)(取码长取码长nm (m = 1, 2, , M) 满足：满足： tm nm tm +1 （3-283-28） 香农编码法具体步骤如下，香农编码法具体步骤如下， （4 4）计算出第）计算出第m个消息的累加概率个消息的累加概率 ，再将，再将pi变换成二进制小数，取小数点后面变换成二进制小数，取小数点后面nm位作为第位作为第m个消息的代码个消息的代码组组11)(immixqp （3）根据式（

32、）根据式（3-30）：）：-log q (xm) nm1时，量化分层很密，有 利用均匀量化 则，可得压压 缩缩 x 均均 匀匀 量量 化化 编编 码码 解解 码码 解解 压压 缩缩 y x 2220( )( )6Vqxf xP x dx( )( )zkdzf xxdx221( )( )12Vqkxvx P x dx最佳非均匀量化最佳非均匀量化A律对数压缩特性z信号归一化z压缩特性z国际标准：A=87.6z输入正弦信号的信噪比 ixxV110()1 ln( )1 ln1 ()1 lnAAAxxAf xAxxA 线形均匀量化对数非均匀律对数压缩特性z压缩特性z国际标准：u=255ln(1)( )l

33、n(1)uxf xu折线近似zA律：13折线zu律：15折线5.5.2 2 连续信源编码连续信源编码z常用编码方法NBCFBCRBC自然二进制码组常见：折叠二进制码组格雷二进制码组在在PCM中，把量化后的信号电平值转换成二进中，把量化后的信号电平值转换成二进制码组的过程叫做编码，其逆过程称为解码或制码组的过程叫做编码，其逆过程称为解码或者译码者译码PCM编码规则 M 0 M 1 M 2 M 3 M 4 M 5 M 6 M 7 极极性性码码 段段落落 线线性性量量化化 段落序号段落序号段落码段落码c2 c3 c4段落范围段落范围（量化单位）（量化单位）81 1 11024204871 1 0512102461 0 125651251 0 012825640 1 16412830 1 0326420 0 1163210 0 0016PCM编码规则段落码编码规则表