信息论与编码-第六章

第六章无失真信源编码

信源信源编码信道编码信道译码信源译码信宿信道第一节单义可译码

信源编码：就是在输入信道之前，用信道能传输的符号集，即信道的输入符号集作为码符号集，用码符号集中的码符号，对信源的每一种不同的符号进行编码，构成由码符号组成的序列，即码字。一个码字代表信源的一种符号。因为每一个码字都是由信道能够传递符号组成的符号序列，都能通过信道，所以，每一个码字所代表的信源的符号必能通过信道，使信源适合与信道的传输。

信源编码编出的每一种码字要与信源发出的每一种不同的符号一一对应，而且同时还要求信源的N个符号组成的序列所代表的消息，与相对应的码字组成的码字序列也必须一一对应。只有这样，才能保证任何一个码字或码字序列唯一地翻译成相对应的信源的符号或符号序列，达到无失真传递信源发出的消息的目的。无失真信源编码必须具有这种单义可译性。单义可译的码称为单义可译码。

第二节非延长码及其构成

没有任何一个码字是另一个码字的延长。这就是即时码W(5)在结构上的特点，所以，从结构的角度，即时码又称为非延长码。非延长码是单义可译码的一类子码。非延长码一定单义可译。反之，单义可译码不一定都是非延长码。有些延长码亦单义可译。

由于非延长码单义可译，而且又能即时译码，所以无失真信源编码中经常采用这种码，我们经常采用“树突法”构造非延长码。非延长码的信源符号、码符号集码符号数以及个码字的码长这三种结构参数之间，存在着内在的约束关系。这就是说，能否编出非延长码，取决于对编码的结构要求。

第三节单义可译定理

设信源的符号集；码符号集；个码字长度分别为。则存在单义可译码的充分必要条件是满足克拉夫不等式，即

通过对定理的必要性和充分性的证明，得到：由定理的必要性，任何一个结构为的单义可译码，一定满足Kraft不等式；由定理的充分性，满足Kraft不等式的，至少可构成一种结构为的非延长码。所以，我们可得到一个重要结论：任一单义可译码均可由一个结构相同（与单义可译码相同）的非延长码来代替。因此，对单义可译码的讨论，就可侧重于对非延长码的讨论了。

第四节平均码长与有效性

要讨论通信的有效性问题，首先要解决如何估量无噪信道中每一码符号携带信息量的多少问题，也就是要解决衡量有效性高低的标准问题。为此，必须引入有关“平均码长”的概念。设信源的信源空间为且有若对此信源用无噪信道输入符号集，即码符号集进行单义可译码编码，其单义可译码的码字的长度为，且与信源符号一一对应。

一个信源符号所需的平均码符号数，就应该等于个码字长度在信源的概率空间中的统计平均值，即这个平均值（码符号/信源符号）称为非延长码的平均码长。另一方面，待信源是给定的，信源每一个信源符号所含有的平均信息量，就等于信源的信息熵其值是固定不变的。

由以上两式可得，非延长码每一个码符号所携带的平均信息量，即码的信息传输率（又称码率）为码率体现非延长码在无噪信道中传输信息的有效性的高低。越大，表示每一个码符号携带的平均信息量越多，即有效性越高；越小，表示每一个码符号携带的平均信息量越少，即有效性越低。

在无失真前提下，还要求有较高的有效性的话，则在编码时，不仅要使结构参数满足Kraft不等式，而且还要考虑个码长（即相应的码字）与信源的概率空间中个概率分量（即相应的信源符号）之间的合理搭配，充分利用和挖掘信源的统计特性的潜力，使其平均码长尽量小。

要使非延长码的平均码长尽量小，使无失真信源编码尽量有效，必须遵循码字长度与信源概率空间的概率分量之间的正确搭配原则：概率大（经常出现）的信源符号尽量赋于码长小的码字（短码）；概率小（不经常出现）的信源符号尽量附于码长大的码字（长码）。采取这样的搭配原则，才能充分利用和挖掘信源统计特性的潜力，提高无失真信源编码的有效性。

第五节平均码长的界限定理引言:

码字的信息传输率(码率)为

.比特/码符号码率R越大，表示每一个码符号携带的平均信息量越多，即有效性越高；R越小，表示每一个码符号携带的平均信息量越少，即有效性越多低。

而平均码长为码符号/信源符号,

所以,平均码长越小则每一个码符号携带的平均信息量越多，即有效性越高.在进行无失真信源编码时，若要使有效性最高，不仅要使结构参数满足Kraft不等式,还要考虑q个码长与信源S的信源概率空间P中的q个概率分量之间的合理搭配，充分利用和挖掘信源的统计特性的潜力，使平均码长尽量小。

若离散无记忆信源的信息熵为，码符号集，如要求的q个码字长度为，且满足Kraft不等式。则总找到一种单义可译码，使其平均码长满足这就是平均码长的界限定理。以下分别对其下界和上界给予证明。下界的证明：设离散无记忆信源S的信源空间为且有要证只需证

根据平均码长定义以及信源信息熵的定义得：利用上凸函数的性质得到由于非延长码满足Kraft不等式，即所以证得即由于当且仅当等式才成立，即有

当且仅当信源符号和概率分布满足时，平均码长才能达到下界值。当平均码长达到最小值时，这种码应该是最有效的无失真信源编码，称它为最佳码。新问题：若平均码长小于下界值，会出现什么结果呢？

我们运用反证法进行证明，假设有根据平均码长和信息熵定义得整理并移项得

即因为有不等式，现令由不等式可得可得所以

这时，结构参数不满足Kraft不等式时，不能构成单义可译码。结论：单义可译码的平均码长一定不小于下界值；凡是平均码长小于下界值的码，一定不能构成单义可译码。

我们运用换底公式可得：

所以，单义可译码的平均码长的下界值在数量上取决于给定信源的信息熵。信源给定，其熵值随之确定，该信源的无失真信源编码的平均码长的也就随之确定了，无失真信源编码的有效性的最高限度也就确定了。如不改变码字所代表的对象，只靠改变编码方法来继续提高有效性，已无潜力可挖。如要进一步提高编码有效性，势必对编码对象，即信源本身作文章，进一步挖掘信源本身的潜力。上界的证明：在区间取码长，则有进而有即所以进行对数变换得：取各项倒数有取和可得

既然，在上述区间选择时，结构参数满足Kraft不等式，可构成非延长码。所以，可用乘不等式两边得：所以，

上界定理得证。

结论：平均码长在不超过其上界值的情况下，就可以构成非延长码。但这并不意味着平均码长超过上界值时就不能构成非延长码，只是因为我们总是希望平均码长能够尽量小。在一般情况下，在构成非延长码时，没有必要使平均码长大于其上界值。而决定能否构成非延长码的关键是结构参数必须满足Kraft不等式。所以，平均码长的下界值定理才是关键。问题：如要进一步降低非延长码的平均码长，提高无失真信源编码的有效性，单靠改善编码方法，已无潜力可挖。要进一步提高有效性，必须把我们的注意力转向信源本身，通过改变信源的熵值的途径，进一步挖掘信源本身的潜力。第六节信源扩展与数据压缩旧的编码方式：将单个信源符号作为编码对象。新的编码方法：我们可以在构成非延长码时，直接把消息作为编码对象，使一个完整的码字不对应单个信源符号，而直接对应一个消息，使码字与一一对应。以下，就对信源的无记忆和有记忆两种情况，在运用这种编码方式时平均码长的变化进行讨论。（一）无记忆信源设离散无记忆信源S的信源空间为且则信源S的熵H(S)是确定的，它是

由信源S的信源空间可得信源S的N次扩展信源的信源空间为其中所以，有所以N次扩展信源的熵也是确定的，它是现在直接对N次扩展信源的每一个“大符号”，即消息进行一一对应的无失真编码，构成非延长码。

令表示N次扩展信源的平均码长，则的含义应该是N个信源符号所需的平均码符号，由平均码长的界限定理可得不等式两边同乘一1/N得其中为信源每一个信源符号所需要的平均码符号数，即平均码长。当扩展次数，可得所以

且接近程度随着扩展次数N的增加而增加。所以，可以采用扩展信源的手段达到数据压缩的目的，提高通信的有效性，但编码的难度将增加。（二）有记忆信源信源S的各维条件概率为

所以可得信源S的N次扩展信源的概率分布为且有信源S的N次扩展信源的熵为对于平稳遍历有记忆信源S，当每发一个信源符号所含有的平均信息量，即极限熵为

与无记忆信源同样，有记忆信源也遵循平均码长界限定理，可得由“大符号”消息的平均码长界限定理可以推得信源符号的平均码长界限定理，并且当时所以即得所以，直接把信源S的N次扩展信源的“大符号”（消息）作为编码对象，进行一一对应的编码，编出的非延长码的平均码长，将随着扩展次数N的增加，可无限接近于已知可得即可得所以

由于考虑了N次扩展信源中N个随机变量之间的统计依赖关系，挖掘并利用了有记忆信源S各时刻随机变量之间的依赖关系对减少码符号数，提高通信有效性的潜力，所以其平均码长下界值，比不考虑各时刻随机变量之间的统计依赖关系的无记忆信源S的N次扩展信源的平均码长的下界值，又有了进一步的减少。特别当平稳遍历有记忆信源S是m阶Markov信源时，m阶Markov信源的极限熵就是m阶条件熵，即其平均码长的极限值又因为所以，每一信源符号所需要的平均符号数（平均码长）可无限接近其下界，而下界值又随记忆长度m的增大而减小，记忆长度m越长，每一信源符号所需的平均符号数（平均码长）的下界值就越小，数据压缩的程度就越大，无失真信源编码的有效性就越高。第七节无失真信源编码定理

无失真信源编码定理，以无失真信源编码在无噪信道中每单位时间通过的信源符号数（码字数），即码速度为有效性的衡量测度，论述无失真信源编码有效性的限度。设离散无记忆信源S的熵为，离散无噪信道的信道容量为。则信源S的无失真信源编码在无噪信道上的码速度的限度为每秒个信源符号（其中是任意小的正数）。要使码速度大于是不可能的。注意：1、区分信道传输率（码率）与信道的平均信息传输速率（码速率）；2、信道容量与信道的最大平均信息传输率（最大码速率）；3、特别是各个变量的单位。证明：无噪信道每一码符号传输的平均信息量，即信道的信息传输率（码率）由于离散无记忆信源S的无失真信源编码的平均码长可无限接近于下界值所以，当时，有有r个输入符号的离散无噪信道的信道容量综合上面两式得这表明，无失真信源编码编出的非延长码，每一码符号所携带的平均信息量（码率），即无噪离散信道的平均信息传输率可以无限接近，但不能超过无噪信道的容量。

若离散无噪信道每传递一个码符号需要t秒时间，则离散无噪信道在每秒时间内能传输的平均信息量，即信道的平均信息传输速率（码速率）同样由信道容量的定义，可得离散无噪信道在每秒时间内，能传输的最大平均信息量，即信道的最大平均信息传输率（最大码速率）当，得

由离散无噪信道在单位时间（每秒）内传递的信源符号数，也就是码速度当时，得若令为任意小的正数，则所以定理得证。

这表明，在无失真信源编码中，采用扩展信源的手段，虽然可以减少每一信源符号所需要的平均码符号数，使编码的有效性有所提高。但无论怎样扩展，无失真信源编码编出的非延长码，在无噪离散信道中传输的有效性是有一定的限度的。也可以将上述定理推广到平稳遍历有记忆信源的情况。设平稳遍历有记忆信源S的极限熵为，离散无噪信道的信道容量为。则信源S的无失真信源编码在离散无噪信道上的平均信息传输速率的限度为每秒个信源符号（其中是任意小的正数）。要使平均信息传输速率大于是不可能的。证明：无失真信源编码的平均码长的极限值为而无失真信源编码在离散无噪信道中的信息传输率，也就是码率R的极限值由离散无噪信道的容量，有

则无失真信源编码在离散无噪信道上的平均信息传输速率，也就是码速率的极限值所以，离散无噪信道在单位时间内传递的信源符号数，用码速度表示，则有若令为任意小的正数，则

将平稳遍历有记忆信源的极限熵与离散无记忆信源的信息熵比较得：所以，比较两者的码速度可得到

这表明，在采用扩展信源的办法，来提高通信有效性的过程中，考虑信源发出符号之间的统计依赖关系，比不考虑信源发出符号之间的统计依赖关系时的有效性要高。无失真信源编码定理，就是香农第一定理。又因为要进行无失真传输，在无失真信源编码后，必须接入无噪信道.所以,无失真信源编码定理,也称为无噪离散信道编码定理。

比特/符号数信道的信息传输率（码率）比特/符号数信道容量（即信道的最大信息传输率）比特/秒信道的平均信息传输速率（码速率）比特/秒信道的最大平均信息传输速率（最大码速率）信源符号/秒信道在单位时间内传递的信源符号数（码速度）

无失真信源编码定理（香农第一定理）是一个极限定理，它指出了单义可译的非延长码的平均码长可无限接近极限值，无噪信道在传输无失真信源编码的码符号时，信息传输率可无限接近信道容量的美好前景但定理本身并没有给出如何构造这种有效码的方法。第八节霍夫曼（Huffman）有效码1952年，霍夫曼（Huffman）提出了一种无失真信源编码的方法。这种编码方法，根据给定信源的信源空间和规定的码符号集，合理利用信源的统计特性，构造出单义可译的非延长码，并具有尽可能小的平均码长，使无失真信源编码具有较高的有效性。为此，用霍夫曼编码编出的码通常称之为有效码。霍夫曼编码方法：若以为码符号集，用霍夫曼编码方法，对信源空间为（其中：）的离散无记忆信源，进行无失真信源编码的具体步骤是：（1）把个信源符号按其概率分布的大小，以递减次序，由大到小，自上至下排成一列；

（2）对处于最下面的概率最小的个信源符号，一一对应地分别赋于码符号。把这个概率最小的信源符号相应的概率相加，所得和值用一个虚拟符号代表，与余下的个信源符号组成含有个符号的第一次缩减信源；（3）缩减信源中的符号，仍按其概率大小，以递减次序，由小到大，自上至下排列。对处于最下面的个概率最小的符号，按步骤（2）中的同样顺序，一一对应地分别赋于码符号。把这个概率最小的符号相应的概率相加，所得和值用一个虚拟符号代表，与余下的个符号组成含有个符号的第二次缩减信源；

（4）按照以上方法，依次继续下去。每次缩减所减少的符号数是，缩减到第次时，总共减少的符号数是，第次缩减信源含有的符号数是。当缩减信源含有符号数大于码符号集码符号数时，缩减过程继续进行下去；（5）当第次缩减信源中所含符号数正好等于码符号集码符号数，即有时，表明缩减过程已到最后一次，对这最后余下的个符号，按以前的同样顺序，一一对应地分别赋于码符号。最后余下的这个符号的概率之和，必定等于1。

（6）从最后赋于的码符号开始，沿着每一信源符号在各次缩减过程中得到码符号的行进路线向前返回，达至每一信源符号。按前后次序，把返回路途中所遇到的码符号排成码符号序列。这个码符号序列，就是返回路线终点信源符号相应的码字。到此，完成编码过程。（7）若第次缩减信源含有符号数小于码符号集码符号数，即则必须中止缩减过程。在原来按概率大小，以递减次序，由大到小，自上而下排列的信源符号列队下面，增添个概率为零（实际上不用的）虚假信源符号。正整数等于码符号集码符号数，与第次缩减信源含有的符号数的差值，即。

的新信源。按照前面所讲的步骤对新信源进行缩减。对最后余下的个符号，一一对应地分别赋于码符号。然后，按步骤（6）得到新信源各符号相应的码字：。其中，前个码字是我们所需要的，后个码字概率为零的虚假码字，我们可以丢掉不用。最终，我们所编的码，就是由所组成的码。这样，就完成了编码全过程。此时，信源原有的个符号与增添的个虚假符号组成符号数为信源空间为霍夫曼编码方式信源符号sis1s2s3s4s5得霍夫曼码其平均码长

信源符号sis1s2s3s4s5另一种霍夫曼编码方式最终，得霍夫曼码信源符号相应的码字为其平均码长

两种霍夫曼编码的不同之处仅仅在于码长相同的两种码字的码符号序列形式不同。由此可见，同一信源的霍夫曼码的形式不是唯一的。

在遵循“缩减信源中的符号按其概率大小，以递减次序，由大到小，自上至下排列”这个原则的前提下，各次缩减所得的虚拟符号可能有多于1个合适的位置。合适位置的不同选择，也会导致构成结构相同、有效性相同，而形式不同的多种霍夫曼码。

验证可知，本题不满足上述的关系，所以需要增加概率为零的虚拟符号，因为，所以，当时，，需增加的符号数为：编码过程如下表码长码字信源符号概率第一次缩减第二次缩减

0.5411s1

0.24

0.240.24200s2

0.20

0.22

0.22201s3

0.18

0.20

202s4

0.16

0.18

220s5

0.14

0.16

221s60.08

222s1

0

由霍夫曼编码得出的码长求得平均码长：

若不设置一个概率为零的虚拟信号，直接对含有6个信源符号的原信源进行霍夫曼编码，如下表:码长码字信源符号概率第一次缩减第二次缩减

2100.24

0.38

0.382100.20

0.24

2120.18

0.20

2200.16

0.18

2210.14

2220.08

根据上述表中求出的码长得出平均码长：0.62

从以上两个表中可以看出：直接对含有6个信源符号的原信源进行霍夫曼编码，在最后一次缩减信源赋于的码符号“0”构成的码长为1的最短码字就不可能代表概率最大的信源符号，码长为1的最短码字没有得到合理而充分的利用。相反，把码长为最长的码字不合理地给了信源符号，所以导致平均码长增大，其有效性下降。霍夫曼码是非延长码

以[例6.1]为例，以霍夫曼编码缩减过程的终点作为“树根”，以码符号集码符号数r=2作为“分枝”数，经过四次分枝可得具有四阶节点的“码树”，可知，赋于各信源符号的码字都是“码树”的“端点”。所以，表6.3所得霍夫曼码在结构上是非延长码。对于表6.4，同样可得相应的“码树”如图6.7所示。表6.4中的霍夫曼码的码字同样也是图6.7所示“码树”的“端点”。所以，霍夫曼码在结构上也是非延长码。

由以上的实例分析可知：霍夫曼编码方法中的逐次缩减过程，实际上是“码树”构码方法中逐级分枝过程的逆过程；霍夫曼编码方法对码字的构成原则，确保霍夫曼码各码字是“码树”的“端点”。因此，霍夫曼码在结构上是非延长码，是单义可译码。霍夫曼码是有效码霍夫曼码的两个特点：保证概率大的信源符号对应短码；概率小的信源符号对应长码。而且，所有短码都得到充分利用；

每次缩减信源中概率最小的r个符号对应的码符号序列中，总是最后一个码符号不同，前面各位码符号均相同。

这两个特点保证了霍夫曼码的平均码长是用其它编码方法编出的结构相同的单义可译码的平均码长中最小的平均码长。即，霍夫曼码是有效码。两种霍夫曼码的比较信源符号sis1s2s3s4s5平均码长：表6.3信源符号sis1s2s3s4s5平均码长：表6.7

两种霍夫曼码的平均码长是相等的，由二者的“码树”图可以看出，两种霍夫曼码的码字在“码树”上的“端点”的位置不同，这体现了两种霍夫曼码的码字长度结构的区别。所以，两种霍夫曼码都是非延长码，且都是有效码。A010=w110=w21100=w51101110w4=1101w3=111表一的“码树”图101101001010w(1)=11w(4)=101w(5)=100w(2)=01w(3)=00A10表二的“码树”图101为了区分两种方法，我们引入码长方差的概念：设码中各码字的长度分别为，其平均码长为。则码中