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

第3章

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

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

增强通信的可靠性

（1）提高传输效率，用尽可能少的信道传输符号来传递信源消息，目的是提高传输效率，这是信源编码主要应考虑的问题。这里又分两种情况讨论，即允许接收信号有一定的失真或不允许失真。综上所述，提高抗干扰能力往往是以降低信息传输效率为代价的，而为了提高传输效率又往往削弱了其抗干扰能力。这样，设计者在取舍之间就要作均衡考虑。

（2）

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

将信源符号变换成适合信道传输的符号；（2）

压缩信源冗余度，提高传输效率。{a1,a2,…,aK}为信源符号集，序列中每一个符号uml都取自信源符号集。{b1

，b2

，…，bD}是适合信道传输的D个符号，用作信源编码器的编码符号。编码输出码字cm=cm1cm2…cmn，cmk∈{b1

，b2

，…，bD}k=1,2,

…,n，n表示码字长度，简称码长

信源符号{a1,a2,…,aK}

信道符号（码符号）{b1,b2,…,bD}

图3-1信源编码器模型

信源

信源编码器

一般来说，信源编码可归纳为如图3-1所示的模型。

消息

ui=ui1ui2…uiL

码字ci=ci1ci2…cin

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

，u2

，u3，u4}表示信源的四个消息，码符号集为{0,1}，表3-1列出了该信源的几种不同编码。表3-1同一信源的几种不同编码信源消息各消息概率码1码2码3码4u1q(u1)000001u2q(u2)1101110u3q(u3)101000100u4q(u4)11111110003.1.1码的分类3.变长码若码字集合C中的所有码字cm(m=1,2,…,M)，其码长不都相同，称码C为变长码。2.等长码在一组码字集合C中的所有码字cm(m=1,2,…,M)，其码长都相同，则称这组码C为等长码。一般，可以将码简单的分成如下几类：1.二元码若码符号集为{0，1}，则码字就是二元序列，称为二元码,二元码通过二进制信道传输，这是数字通信和计算机通信中最常见的一种码。4.奇异码对奇异码来说，从信源消息到码字的影射不是一一对应的。奇异码不具备惟一可译性。

信源消息各消息概率码1码2码3码4u1q(u1)000001u2q(u2)1101110u3q(u3)101000100u4q(u4)1111111000表3-1同一信源的几种不同编码5.非奇异码从信源消息到码字的影射是一一对应的，每一个不同的信源消息都用不同的码字对其编码。信源消息各消息概率码1码2码3码4u1q(u1)000001u2q(u2)1101110u3q(u3)101000100u4q(u4)1111111000表3-1同一信源的几种不同编码扩展信源

信源编码器

信源符号{a1,a2,…,aK}

信道符号（码符号）{b1,b2,…,bD}

消息

u1

…uN=(u11u12…u1L)…(uN1uN2…uNL)N次扩展码字

c1

…cN=(c11c12…c1n)…(cN1cN2…cNn)图3-2N次扩展信源编码器模型

原码的N次扩展码是将信源作N次扩展得到的新信源符号序列u（N）=u1

…uN=(u11u12…u1L)…(uN1uN2…uNL)，对应码符号序列c（N）=c1

…cN=(c11c12…c1n)…(cN1cN2…cNn)，记集合C(N)={c1(N),c2(N),…}，C

(N)即原码C的N次扩展码。6.原码C的N次扩展码原码C的N次扩展码中的每个元素是N次扩展信源中的序列所对应的N个码字组成的序列。对于定长码，若原码是惟一可译码，则它的N次扩展码也是惟一可译的，而对于变长码则不尽然，见表3-2。7.惟一可译码定义3.1如果码的任意N次扩展码都是非奇异码，则称该码为惟一可译码。信源消息各消息概率码1码2码3码4u1q(u1)000001u2q(u2)1101110u3q(u3)101000100u4q(u4)1111111000表3-1同一信源的几种不同编码对于定长码，若原码是惟一可译码，则它的N次扩展码也是惟一可译的，而对于变长码则不尽然，见表3-2。信源消息各消息概率码1码2码3u1q(u1)011u2q(u2)11001u3q(u3)00100001u4q(u4)1110000001表3-2同一信源的几种不同变长编码7.惟一可译码8.即时码对于变长码，又有如下定义定义3.2

对于码字c

=c1c2…cn,称c、

=c1c2…ci(i<n)为码字c的字头（前缀）。定义3.3若码中任一码字都不是另一码字的字头，称该码为异字头码（无前缀码）。表3-2中码3，收到“1”后就知道一个码字已经完结，无须等待下一个符号抵达，所以无前缀码能够即时译码,称之为即时可译码，简称即时码。而对于码2，收到“1”后，并不能立即做出判决，就是收到“10”也不能立即做出判决，则还要收到下面的码元才能做出判决。所以非异字头码不能即时译码，称为非即时码，由于非异字头码的其中一些码字是另一些码字的延长，故也称延长码。显然，即时码是惟一可译码，而惟一可译码不一定是即时码。

即时码可用树图法来构造。图3-3用树图法编码树根编码深度u1：1u2：01u3：001u4：00011

0u1u2u3u41

1

1

00【例3.4】用树图法表示表3-2中的码3，如图3-3所示（D=2）。

码奇异码非奇异码非惟一可译码惟一可译码变长码等长码即时码延长码

图3-5码的分类结构图

图3-5是码的分类结构图

由上面的结构图可看出，将码分为奇异码和非奇异码两大类，我们只讨论非奇异码。非奇异码又分为惟一可译码和非惟一可译码两大类，我们只讨论惟一可译码。

3.1.2平均码长的计算对于变长码，码集C的平均码长，用符号表示，定义为码C中每个码字cm(m=1,2,…，M)其码长的概率加权平均值为 (3-1)式中nm是码字cm所对应的码字的长度，p(cm

)是码字cm出现的概率。对于等长码，由于码集C中的每个码字的码长都相同，平均码长就等于每个码字的码长N次扩展码的平均码长等于扩展码中码字长度的概率加权平均值。对于2次扩展码，有：

(3-2)设nm,

ns分别是原信源消息um,

us所对应的码长,

cm,

cs是um,

us所对应的码字，则式(3-2)中的nm+ns是扩展后新的信源序列nmns所对应的码字cmcs的长度；q(um)q(us)是cmcs出现的概率。3.1.3信息传输速率信道的信息传输速率为信道单位时间内所传输的实际信息量。若信息量以比特为单位，时间以秒为单位，则信息传输率定义为： (比特/秒)(3-3)若信息量以比特为单位，时间以码元时间（传输一个码符号的时间）为单位，则信息传输率记为

(比特/码元时间) (3-4)

为编码后的平均码长；H(X)为信源熵；式中：t为传输一个码符号的时间。【例3.8】给定信源，为提高传输效率，使平均码长尽可能短，遵照概率大取码长短，概率小取码长长的原则对上述信源进行二进制不等长编码，得到，求编码后的信息传输率RD。

（比特/符号）

（码元/符号）

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

≤Dn（3-5）对式（3-5）两边取对数，得（3-6）

对于那些出现概率极小的字符序列不予编码，这样可以减小平均码长，当然这样会带来一定的失真。定理3.1

等长编码定理

设离散无记忆信源S={x1

，x2

，…，xk}的熵为H（X），S的L维扩展信源为，对信源输出的L长序列si，i=1,2,…,KL进行等长编码，码字是长度为n的D进制符号串，当满足条件，则L→∞时，可使译码差错率pe<δ(ε、δ为无穷小量)，反之，当时，则不可能实现无差错编码。编码效率定理3.1要求，即，可看出比值是一个小于1的无量纲纯数，定义它为等长编码的编码效率，记为（3-7）

3.3变长码及变长编码定理

3.3.1变长码对于变长码，往往在L不是很大的情况下就可编出高效且无失真的码。变长码也要求原码的任意L次扩展码也是惟一可译的。变长码分为即时码和延长码，为保证即时译码，要求变长惟一可译码采用即时码。对于变长码，要求整个码集的平均码长力求最小，此时编码效率最高。对于给定信源，使平均码长达到最小的编码方法，称为最佳编码，得到的码集称为最佳码。3.3.2克拉夫特不等式定理3.2

D进制码字集合C={c1,c2,…,cM}，码集中每一cm（m=1,2,…,M）都是一个D进制符号串，设c1,c2,…,cM对应的码长分别是n1,n2,…,nM

，则存在唯一可译码的充要条件是

(3-10)

式（3-10）也称克拉夫特不等式

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

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

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

给定熵为H（X）的离散无记忆信源，其L次扩展信源的熵记为H（X），给定有D个元素的码符号集，对扩展信源进行编码，总可以找到一种惟一可译码，使码长满足(3-23)

记为信源每个符号所对应的平均码字数，则式(3-23)为

（3-24）

Shannon第一定理的物理意义在于：对信源进行编码，使编码后的码集中各码字尽可能等概分布，如果将这码集看成为一个新的信源，这时新信源所含信息量最大。定义编码效率(3-26)η是一个无量纲的数，一般情况下η<1，在极限情况下η=1。对于同一种信源，三种编码法中以香农编码法的编码效率最低，费诺编码法也不是一种最佳编码法，但用这种方法有时候也能找到紧致码。一般情况下，霍夫曼编码法得到的平均码长最短，即编码效率最高。

编码效率定义为：3.4变长码的编码方法香农（Shannon）编码法费诺(Fano)编码法霍夫曼(Huffman)编码法变长编码法：3.4.1香农编码法

二进制香农编码法其码长的取值范围:-logq(xm)

nm<-logq(xm)+1

（3-30）记离散信源，给定有D个元素的码符号集，对信源进行变长编码，将各消息概率q(xm)(m=1,2,…,M)写成如下的形式：

取码长nm(m=1,2,…,M)

满足：tm

nm<

tm

+1（3-28）

香农编码法具体步骤如下，（4）计算出第m个消息的累加概率，再将pi变换成二进制小数，取小数点后面nm位作为第m个消息的代码组（3）根据式（3-30）：-logq(xm)

nm<-logq(xm)+1（-logq(xm)为整数时取等号），计算出每个消息的二进制代码的长度nm。（2）计算出各消息的-logq(xm)值，m=1,2,…,M；

（1）将信源发出的M个消息，按其概率递减顺序进行排列【例3.14】对给定信源

进行D=2进制香农编码。消息符号ai消息概率qi-log2qi码长ni累加概率码字cia10.22.3430000a20.192.4130.2001a30.182.4830.39011a40.172.5630.57100a50.152.7430.74101a60.103.3440.891110a70.016.6670.991111110

表3-8香农编码

以消息x5为例，对其进行编码：计算出-logq(x5)=-log0.15=2.74，取整数n5=3作为x5的码字的码长，计算出消息x1,x2,x3,x4累加概率将0.74变换成二进制小数(0.74)10=(0.1011110)2，取小数点后面三位101作为x5的代码。

计算该编码的编码效率

先算出信源熵=2.61(比特/符号)平均码长=3.14(比特/符号)则编码效率

3.4.2费诺编码法费诺编码法的具体步骤如下：

（1）信源发出的M个消息，按其概率递减顺序进行排列，把消息集{

x1,x2,x3,…,xM

}按其概率大小分解成两个子集，使两个子集的概率之和尽可能接近相等，把第一个子集编码为“0”，第二个子集编码为“1”，作为代码组的第一个码元；（2）对子集做第二次分解，同样分解成两个子集，并使两个子集的概率尽可能接近相等，再把第一个子集编码为“0”，第二个子集编码为“1”，作为代码组的第二个码元；

（3）如此一直进行下去，直到各子集仅含一个消息为止

（4）将逐次分解过程当中得到的码元排列起来就是各消息的代码。

【例3.15】对[例3.14]给出的信源进行费诺编码

（1）将信源消息分成两个子集{

x1，x2，x3}和{

x4，x5，x6，x7}，两个子集的和概率分别为0.2+0.19+0.18=0.57与0.17+0.15+0.10+0.01=0.43，赋予第一个子集码元“0”，赋予第二个子集码元“1”；

（2）又将子集分成和概率尽可能接近相等的两个子集，分别赋予第一个子集码元“0”，赋予第二个子集码元“1”；

（3）一直进行下去，直到每个子集仅含一个消息为止。

该编码的编码效率：[例3.14]中已算出信源熵H（X）=2.61（比特/符号）

平均码长=2.74则编码效率：

消息符号xi消息概率q(xm)第一次分解所得码元第二次分解所得码元第三次分解所得码元第四次分解所得码元码字cm码长nix10.2

0

0

002x20.19

10

0103x30.181

0113x40.17

10

102x50.15

10

1103x60.10

1011104x70.01111114表3-9费诺编码

3.4.3霍夫曼编码法设信源消息数M

2，记概率分布为，存在D进制惟一可译码C

={c1,c2,…,cM}，对应的码长分别为{n1,n2,…,nM}，不失一般性，设q(x1)

q(x2)

…q(xM

)，则C

={c1,c2,…,cM}是最佳码必须具备如下两条性质：1.

n1

n2

…

nM；2.最后（最长）的D*个码字，它们具有相同的前缀c，惟一的区别是最后一位码符号不同，可将这D*个最长的码字分别表示为c·0，c·1，…，c·（D*-1）其中D*∈{2，3，…，D}（3-31）且D*=M[mod(D-1)]（3-32）

定理3.5假定C

*

={c1,c2,…,cM-D’，c

}

为最佳码，对应概率Q*={q(x1)

,q(x2)

,…,q(xM-D*)，q*

}

其中q*可记为q*=q(xM-D*+1)+q

(xM-D*+2)+…+q(xM)且概率分布满足q(x1)

q(x2)

…q(xM-D*)q

(xM-D*+1)…q(xM

)则对应概率分布为

Q={q(x1)

,q(x2)

,…,q(xM-D*),

q(xM-D*+1),…,q(xM)

}的最佳码是C={c1,c2,…,cM-D*,c·0,

c·1,

…,c·(D*-1)}（3）将上述概率之和作为一新消息的概率，与余下的消息一起组成一新的信源，再按概率递减顺序重新排列，如果概率之和与原信源的某个概率相等，则把概率之和排在上面，这样可使合并消息重复编码的次数减少，使短码得到充分利用。（4）如此一直进行下去，直到两个合并消息的概率之和为1；

（5）从最后一步骤开始，沿编码逆程取下各步骤得到的码符号，如此构成的码符号序列即为对应消息的码字。

（2）将概率最小的二个消息分别编码为“1”和“0”，（一般，将概率大的编码为“1”，概率小的编码为“0”），再对这两个消息求概率之和

可以按照如下步骤编码（先考虑D=2的情况），参见图3-7

。（1）将信源发出的M个消息，按其概率递减顺序进行排列，得：q(x1)

q(x2)

q(x3)

…

q(xM

)计算该编码的编码效率：[例3.14]中已算出信源熵H（X）=2.61（比特/符号）计算平均码长

=2×0.39+3×0.5+4×0.11=2.72则编码效率

【例3.17】对[例3.14]给出的信源进行D=2进制霍夫曼编码，编码结果如图3-7所示。

a70.01a60.10a50.15a40.17a30.18a20.19a10.200.260.350.390.6110.11010101010101编码010011111010110011000图3-7二元霍夫曼编码例

设有离散无记忆信源用两种不同的方法对其编二进制huffman码信源符号xi概率p(xi)码字Wi1码长Ki1码字Wi2码长K’i2x10.411002x20.2012102x30.20003112x40.1001040103x50.1001140113两种不同的编码方法得到的码字和码长的对比两种不同的编码方法的平均码长相等，所以具有相同的编码效率。但第