信息论与编码第三版-第3章

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

§3.1概述

一．信源编码的模型为了实现高质量、高效率的通信，引入了信源编码和信道编码。信源编码和信道编码主要需要解决以下两个问题。

（1）提高传输效率：用尽可能少的信道传输符号来传递信源消息，目的是提高传输效率，这是信源编码主要应考虑的问题。这里又分两种情况讨论，即允许接收信号有一定的失真或不允许失真。（2）增强通信的可靠性：如何增加信号的抗干扰能力，提高传输的可靠性，这是信道编码主要考虑的问题。解决这一问题，一般是采用冗余编码法，赋予信码自身一定的纠错和检错能力，只要采取适当的信道编码和译码措施，就可使信道传输的差错概率降到允许的范围之内。综上所述，提高抗干扰能力往往是以降低信息传输效率为代价的，而为了提高传输效率又往往削弱了其抗干扰能力。这样，设计者在取舍之间就要作均衡考虑。信源编码的概念：对信源的原始符号按一定的数学规则进行变换的一种代码。信源编码包括两个功能：（1）将信源符号变换成适合信道传输的符号；（2）压缩信源冗余度，提高传输效率。信源编码模型：{a1,a2,…,ak}为信源符号集，序列中每一个符号uml都取自信源符号集。{b1,b2,…,bD}是适合信道传输的D个符号，用作信源编码器的编码符号。

编码输出码字cm

=cm1

cm2…cmn，cmk∈{b1,b2,…,bD}，k=1,2,

…,n

，n表示码字长度，简称码长。【例】中文电报编码：

信源编码器I

：1－10000个汉字分别对应0000－9999

信源编码器II：每位数字对应五位二进制等重码。对应关系如下：

（1→01011，2→11001，...，9→10011，0→01101）

如：二．码的分类信源编码可看成是从信源符号集到码符号集的一种映射，即将信源符号集中的每个元素（可以是单符号，也可以是符号序列）映射成一个长度为n的码字。对于同一个信源，编码方法是多种的。【例】

用{u1

，u2

，u3，u4}表示信源的四个消息，码符号集为{0,1}，下表列出了该信源的几种不同编码。信源消息各消息概率码1码2码3码4u1p(u1)000001u2p(u2)1101110u3p(u3)101000100u4p(u4)1111111000一般，可以将码简单的分成如下几类:1．二元码若码符号集为{0，1}，则码字就是二元序列，称为二元码，二元码通过二进制信道传输，这是数字通信和计算机通信中最常见的一种码，例子列出的4种码都是二元码。2．等长码在一组码字集合C中的所有码字cm(m=1,2,…,M)，其码长都相同，则称这组码C为等长码，例中的码1、码2就码长n=2等长码。3．变长码若码字集合C中的所有码字cm(m=1,2,…,M)，其码长不都相同，称码C为变长码，例中列出的码3、码4就是变长码。信源消息各消息概率码1码2码3码4u1p(u1)000001u2p(u2)1101110u3p(u3)101000100u4p(u4)11111110004．奇异码对奇异码来说，从信源消息到码字的映射不是一一对应的。例中的码1，信源消息u2和u4都用码字11对其编码，因此这种码就是奇异码，奇异码不具备惟一可译性。5．非奇异码从信源消息到码字的映射是一一对应的，每一个不同的信源消息都用不同的码字对其编码，例中的码2、码3和码4都是非奇异码。信源消息各消息概率码1码2码3码4u1p(u1)000001u2p(u2)1101110u3p(u3)101000100u4p(u4)11111110006．原码C的N次扩展码原码C的N次扩展码中的每个元素是N次扩展信源中的序列所对应的N个码字组成的序列。原码的N次扩展码是将信源作N次扩展得到的新信源符号序列u（N）=u1…uN=(u11

u12…u1L)…(uN1

uN2…uNL)，对应码符号序列c（N）=c1…cN=(c11c12…c1n)…(cN1cN2…cNn)，记集合C(N)={c1(N),c2(N),…}，C(N)

即原码C的N次扩展码。7．唯一可译码定义：如果码的任意N次扩展码都是非奇异码，则称该码为惟一可译码。

例中的码1不是唯一可译码。对于定长码，若原码是惟一可译码，则它的N次扩展码也是惟一可译的，而对于变长码则不尽然。信源消息各消息概率码1码2码3码4u1p(u1)000001u2p(u2)1101110u3p(u3)101000100u4p(u4)1111111000信源消息各消息概率码1码2码3u1p(u1)011u2p(u2)11001u3p(u3)00100001u4p(u4)1110000001码1不是唯一可译码，码2、码3是唯一可译码。8．即时码对于变长码，有两个定义：（1）前缀：对于码字C=c1

c2…cn，称c’=c1

c2…ci

(i<n)为码字c的字头（前缀）。（2）异字头码：若码中任一码字都不是另一码字的字头，称该码为异字头码（无前缀码）。码3是无前缀码；其他都不是无前缀码。即时码：例中码3，收到“1”后就知道一个码字已经完结，无须等待下一个符号抵达，所以无前缀码能够即时译码，称之为即时可译码，简称即时码。

信源消息各消息概率码1码2码3u1p(u1)011u2p(u2)11001u3p(u3)00100001u4p(u4)1110000001而对于码2，收到“1”后，并不能立即做出判决，就是收到“10”也不能立即做出判决，则还要收到下面的码元才能做出判决。所以非异字头码不能即时译码，称为非即时码，由于非异字头码的其中一些码字是另一些码字的延长，故也称延长码。

即时码是惟一可译码，而惟一可译码不一定是即时码。即时码的树图构造方法：对于D进制码，从树根出发，可引出D根树枝，每根树枝分别赋予一个不同的码符号，树枝的端点为节点，每一个节点又可引出D根分枝，又分别赋予这D根分枝每根一个不同的码符号，如某一节点被定为码字后，就不再引出树枝，该节点称为终节点。码字就是从树根出发，到达终节点所对应的码符号序列。

【例】用树图法表示码（1，01，001，0001）。码的分类结构图由上面的结构图可看出，将码分为奇异码和非奇异码两大类，我们只讨论非奇异码。非奇异码又分为惟一可译码和非惟一可译码两大类，我们只讨论惟一可译码三．平均码长的计算对于变长码，码集C的平均码长定义为码C中每个码字cm(m=1,2,…，M)其码长的概率加权平均值，用符号表示

式中nm是码字cm所对应的码字的长度，p(cm

)是码字cm出现的概率。对于等长码，由于码集C中的每个码字的码长都相同，平均码长就等于每个码字的码长【例】计算下表各码的平均码长：

信源消息各消息概率码1码2码3码4u10.4000001u20.21101110u30.2101000100u40.21111111000码长221.42.2【推广】N次扩展码的平均码长等于扩展码中码字长度的概率加权平均值。

对于2次扩展码，有：设nm，ns分别是原信源消息um，us所对应的码长，cm，cs是um，us所对应的码字，则式中的nm

+ns是扩展后新的信源序列umus所对应的码字cmcs的长度，p(um)p(us)是cmcs出现的概率。

四．信息传输速率定义：信道的信息传输速率为信道单位时间内所传输的实际信息量。

（1）若信息量以比特为单位，时间以秒为单位，则信息传输速率定义为：

（比特/秒）

式中：H(X)为信源熵；为编码后的平均码长；t为传输一个码符号的时间。

（2）若信息量以比特为单位，时间以码元时间（传输一个码符号的时间）为单位，则信息传输率记为：

(比特/码元时间)

【例】给定信源为提高传输效率，使平均码长尽可能短，遵照概率大取码长短，概率小取码长长的原则对上述信源进行二进制不等长编码，得到如右编码方案，求编码后的信息传输率RD。（比特/符号）

（码元/符号）

(比特/码元时间)

§3.2等长码及等长编码定理一．等长编码定理考虑对一简单信源S进行等长编码，信源符号集有K个符号，码符号集含D个符号，码字长度记为n。对信源作等长无差错编码，要得到惟一可译码，必须满足下式：K≤Dn对单符号信源S的L次扩展信源S（L）进行等长编码，要得到长为n的惟一可译码，必须满足:KL

≤Dn对上式两边取对数，得：，对信源输出的L长序列si

，i=1,2,…,KL

进行等长编码，码字是长度为n的D进制符号串，当满足条件，则L→∞时，可使译码差错pe

<δ(ε、δ为无穷小量)；反之，当时，则不可能实现无差错编码。对于那些出现概率极小的字符序列不予编码，这样可以减小平均码长，当然这样会带来一定的失真。下面的定理将证明，当满足一定的条件时，在L→∞时，失真pe→0。【定理】等长编码定理

设离散无记忆信源S={x1,x2,…,xk}的熵为H(X)，S的L维扩展信源为二．编码效率根据等长码的编码定理，我们可以得到一个衡量编码质量的重要指标，编码效率。等长编码定理要求，即，可看出比值是一个小于1的无量纲纯数，定义它为等长编码的编码效率，记为：编码效率η是衡量编码质量的一个重要指标，对信源编码时应尽量提高编码效率。【例】

（1）给定离散无记忆信源，对该信源进行二进制等长编码，并求编码效率。

【解】先确定码长：信源消息数目K＝3，信源序列长度L＝1，码符号数D＝2①根据

②根据等长编码定理：

（比特/符号）

根据前面计算，由等长编码定理计算出的下界更小，但由于码长都取整，故取n1=n2=2。并做如下编码：，得到唯一可译码。

编码效率为：

（2）对原信源进行L=2维扩展，得到新信源：

对扩展信源进行二进制等长编码。

【解】对扩展码K＝3，信源序列长度L＝2，码符号数D＝2

①由确定码长：

取n3=4，对扩展信源编码的编码如下：

信源序列x0x0x0x1x0x2x1x0x1x1x1x2x2x0x2x1x2x2码字000000010010001101000101011001111000编码效率：

②按等长编码定理：

取n4=3，对扩展信源编码的编码如下：

信源序列x0x0x0x1x0x2x1x0x1x1x1x2x2x0x2x1x2x2码字000001000010011100101110111对于二进制码，取码长为3，共可构成8个不同的码字，而扩展信源含9个序列，故编码时对序列中概率小的两个序列赋予同一个码字000，这样势必存在译码差错概率pe：

§3.3变长码及变长编码定理一．变长码对等长码的讨论是在L足够大的条件下得到的结论，当L为有限值时，则总会带来一定程度的失真。对于变长码，往往在L不是很大的情况下就可编出高效且无失真的码。变长码也要求原码的任意L次扩展码也是惟一可译的。变长码分为即时码和延长码，为保证即时译码，要求变长惟一可译码采用即时码。对于变长码，要求整个码集的平均码长力求最小，此时编码效率最高。对于给定信源，使平均码长达到最小的编码方法，称为最佳编码，得到的码集称为最佳码。二．克拉夫特不等式定理：D进制码字集合C={c1，c2，…，cM}，码集中每一cm（m=1,2,…,M）都是一个D进制符号串，设c1，c2，…，cM

对应的码长分别是n1，n2，…，nM，则存在唯一可译码的充要条件是（克拉夫特不等式）

定理只是说是存在惟一可译码的充要条件，这里强调的是“存在”，但它并不是唯一可译码的充要条件，换言之，惟一可译码一定满足克拉夫特不等式，反之，满足克拉夫特不等式的码不一定是惟一可译码。三．变长编码定理

平均码长极限定理（离散无记忆信源变长编码定理）：

给定熵为H（X）的离散无记忆信源，及有D个元素的码符号集，则总可找到一种无失真编码方法，构成惟一可译码，其平均码长满足：

定理的证明过程给了我们一种最佳编码的构造方法，即如果信源的概率分布均有

的形式，那么直接取ni作为对应消息符号的码字长度，就可以得到紧致码（最佳码）。

等号成立时编码效率最高，此时的码称为最佳码【例3.3.1】对其进行二元编码，码长分别取{1，2，3，3}此时的平均码长为（码元/符号）信源熵为（bit/符号）编码效率信息传输率（bit/码元）其L次扩展信源的熵记为

定理：变长编码定理(Shannon第一定理)

给定熵为H（X）的离散无记忆信源

给定有D个元素的码符号集，对扩展信源进行编码，总可以找到一种惟一可译码，使码长满足：

记为信源每个符号所对应的平均码字数，则上式为：

编码效率：

η是一个无量纲的数，一般情况下η<1，在极限情况下η=1。

Shannon第一定理的物理意义在于：对信源进行编码，使编码后的码集中各码元符号尽可能等概分布，如果将这码集看成为一个新的信源，这时新信源的每个码符号平均所含信息量达到最大。【例】已知离散无记忆信源对X进行二进制等长编码取n=1,x1→0,x2→1,

（bit/符号）对X2进行二进制变长编码x1x1x1x2x2x1x2x2Pi9/163/163/161/16C010110111(严格的无失真编码)

若进行等长编码效率η=0.96,差错率

Pe≤10-5,L≥4.13×107（有失真编码）③对X3进行二进制变长编码

η=98.5%，R=0.985bit/码元④对X4进行二进制变长编码

η=99.1%，R=0.991bit/码元§3.4变长码的编码方法常用的变长编码法：①香农（Shannon）编码法②费诺(Fano)编码法③霍夫曼(Huffman)编码法

对于同一种信源，三种编码法中以香农编码法的编码效率最低，费诺编码法也不是一种最佳编码法，但用这种方法有时候也能找到紧致码（在所有的唯一可译码中，平均码长最小的码称紧致码，也就是最佳码）。一般情况下，霍夫曼编码法得到的平均码长最短，即编码效率最高。

一.香农编码法记离散信源

给定有D个元素的码符号集，对信源进行变长编码，将各消息概率p(xm)(m=1,2,…,M)写成如下的形式：取码长nm(m=1,2,…,M)满足：由此得香农编码法码长取值范围:对于二进制香农编码法，有

编码步骤：（1）将信源发出的M个消息，按其概率递减顺序进行排列；

（2）计算出各消息的－logp(xm)值，m=1,2,…,M；

（3）根据式：计算出每个消息的二进制代码的长度nm。

（－logp(xm)为整数时取等号）（4）计算出第m个消息的累加概率，再将pi变换成二进制小数，取小数点后面nm位作为第m个消息的代码组。

【例】对给定信源进行D=2进制香农编码并求编码效率。【解】（1）编码消息符号xi消息概率p(xm)－logp(xm)码长ni累加概率pi码字Cix10.22.3430000x20.192.4130.2001x30.182.4830.39011x40.172.5630.57100x50.152.7430.74101x60.103.3440.891110x70.016.6670.991111110（2）求编码效率信源熵：

比特/符号

平均码长：

码元/符号

编码效率：

消息符号xi消息概率p(xm)－logp(xm)码长ni累加概率pi码字Cix10.22.3430000x20.192.4130.2001x30.182.4830.39011x40.172.5630.57100x50.152.7430.74101x60.103.3440.891110x70.016.6670.991111110二．费诺编码法费诺编码法的具体步骤如下：

（1）信源发出的M个消息，按其概率递减顺序进行排列，把消息集{x1,x2,x3,…,xM}按其概率大小分解成两个子集，使两个子集的概率之和尽可能接近相等，把第一个子集编码为“0”，第二个子集编码为“1”，作为代码组的第一个码元；（2）对子集做第二次分解，同样分解成两个子集，并使两个