信息论第五讲3

复习1）离散信源的熵2）条件熵

3）联合熵

1）H(XY)=H(X

)＋H(Y|X)

2）H(XY)=H(Y)＋H(X|Y)3）当X和Y相互独立时，有H(XY)=H(X

)＋H(Y)条件熵与联合熵的关系复习2.6离散信源熵和互信息2.6.4互信息定义简单的通信模型若信源发出符号xi，由于干扰，收到的不是xi而是yj

，从yj中获取有关xi的信息量称为互信息量，用I(xi

;yj)表示。信源Xi有干扰离散信道信宿Yj干扰源I(xi;yj)=I(xi)-I(xi

|yj

)2.6离散信源熵和互信息1º

信源发送符号xi，同时信宿接收符号yj的联合概率：

其中：p(xi)为信源符号xi的先验概率。

p(yj|xi)为信源符号xi已发送，信宿接收到yj的条件概率；称为信道的传递概率或转移概率或前向概率。

2º信宿接收符号yj的概率2.6离散信源熵和互信息3º信宿接收yj

后，推测信源发送的符号是xi的概率（后验概率）：p(xi|yi)2.6离散信源熵和互信息4º互信息量计算公式也可定义：后验概率与先验概率比值的对数称为互信息量，记为I(xi；yj)

互信息量单位bit2.6离散信源熵和互信息

5º互信息量计算

已知:信源符号xi的概率p(xi)---先验概率,

信源xi

发送的条件下，信宿接收到yj的概率p(yj

|xi)

互信息量计算即如何求p(xi|yj)/p(xi)1.联合概率

2.全概率

3.后验概率与先验概率之比2.6离散信源熵和互信息

【例2.6.1】某二元通信系统x0=0，x1=1，信源发送x0和x1的概率分别为p(0)=1/2，p(1)=1/2;信宿y0=0,y1=1

由于信道中有干扰，当信源发送0时，信宿接收为0的概率p(y0|x0)=p(0|0)=3/4

信宿接收为1的概率p(y1|x0)=p(1|0)=1/4

当信源发送1时，信宿接收为0的概率p(y0|x1)=p(0|1)=1/5

信宿接收为1的概率p(y1|x1)=p(1|1)=4/5

求互信息量

I(x0;y0),I(x0;y1),I(x1;y0),I(x1;y1)2.6离散信源熵和互信息x0=0

p(0|0)=3/4y0=0

p(0|1)=1/5p(1|0)=1/4

x1=1p(1|1)=4/5y1=11.联合概率

p(x0y0)=p(x0)p(y0|x0)=1/2×3/4=3/8

p(x0y1)=p(x0)p(y1|x0)=1/2×1/4=1/8

p(x1y0)=p(x1)p(y0|x1)=1/2×1/5=1/10p(x1y1)=p(x1)p(y1|x1)=1/2×4/5=4/102.6离散信源熵和互信息2.全概率

p(y0)=p(x0y0)+p(x1y0)=3/8+1/10=19/40

p(y1)=p(x0y1)+p(x1y1)=1/8+4/10=21/403.后验概率与先验概率之比

p(x0|y0)/p(x0)=p(y0|x0)/p(y0)=3/4÷19/40=30/19p(x0|y1)/p(x0)=p(y1|

x0)/p(y1)=1/4÷21/40=10/21p(x1|y0)/p(x1)=p(y0|

x1)/p(y0)=1/5÷19/40=8/19p(x1|y1)/p(x1)=p(y1|

x1)/p(y1)=4/5÷21/40=32/21

4.互信息量

I(x0;y0)=log(30/19)bitI(x0;y1)

=log(10/21)bitI(x1;y0)=log(8/19)bitI(x1;y1)=log(32/21)bit2.6离散信源熵和互信息3)平均互信息量定义互信息量I(xi

;yj)在联合概率空间P(XY)上的统计平均值称平均互信息量,用I(X;Y)表示平均互信息量单位

bit/消息2.6离散信源熵和互信息当信宿收到某一具体符号yj后，从yj中获取关于输入符号的平均信息量，显然应该是在条件概率空间中的统计平均，可用I(X；yj)表示，有再对其在集合Y中取统计平均，得2.6离散信源熵和互信息平均互信息的三种不同的形式表达式2.6离散信源熵和互信息4)平均互信息量的性质

1º对称性

I(X;Y)=I(Y;X)2.6离散信源熵和互信息2º非负性（条件熵不大于无条件熵H(X)

≥

H(X|Y)）

I(X;Y)=H(X)

-H(X|Y)≥0证明：2.6离散信源熵和互信息I(X;Y)≥0从整体和平均的意义上来说，信道每通过一条消息，总能传递一定的信息量，或者说接收端每收到一条消息，总能提取到关于信源X的信息量，等效于总能使信源的不确定度有所下降。也可以说从一个事件提取关于另一个事件的信息，最坏的情况是0，不会由于知道了一个事件，反而使另一个事件的不确定度增加。2.6离散信源熵和互信息

3º极值性I(X;Y)H(X)I(Y;X)H(Y)

因此I(X;Y)=H(X)－H(X|Y)

当X与Y无关时，H(X|Y)=H(X)，则I(X;Y)=0；表示无法从Y中获取X的信息。2.6离散信源熵和互信息

I(X;Y)=H(X)+H(Y)–H(XY)根据各种熵的定义，从该式可以清楚看出平均互信息量是一个表征信息流通的量，其物理意义就是信源端的信息通过信道后传输到信宿端的平均信息量。2.6离散信源熵和互信息无条件熵、条件熵、联合熵和平均互信息量(交互熵)之间的关系：H(X/Y)H(Y/X)I(X;Y)H(X)H(Y)H(XY)联合熵和条件熵的一些性质2.6离散信源熵和互信息2.6离散信源熵和互信息

【例2.6.2】已知信源空间

信道特性如图所示，求在该信道上传输的平均互信息量I(X;Y)、H(X|Y)，噪声熵H(Y|X)和共熵H(XY)。2.6离散信源熵和互信息解（1）根据P(xiyj)=P(xi)P(yj

|xi)，求各联合概率，得 P(x1y1)=P(x1)P(y1|x1)=0.5×0.98=0.49 P(x1y2)=P(x1)P(y2|x1)=0.5×0.02=0.01 P(x2y1)=P(x2)P(y1|x2)=0.5×0.20=0.10 P(x2y2)=P(x2)P(y2|x2)=0.5×0.80=0.40（2）根据，求Y集合中各符号的概率，得 P(y1)=P(x1)P(y1|x1)+P(x2)P(y1|x2)=0.5×0.98＋0.5×0.2=0.59 P(y2)=1–0.59=0.412.6离散信源熵和互信息（3）根据P(xi|yj)=P(xi

yj)/P(yj)，求各后验概率，得 P(x1|y1)=P(x1y1)/P(y1)=0.49/0.59=0.831 P(x2|y1)=P(x2y1)/P(y1)=0.10/0.59=0.169 P(x1|y2)=P(x1y2)/P(y2)=0.01/0.41=0.024 P(x2|y2)=P(x2y2)/P(y2)=0.40/0.41=0.9762.6离散信源熵和互信息

（4）求各种熵，有I(X;Y)=H(X)+H(Y)–H(XY)=1+0.98-1.43=0.55比特/信符H(X|Y)=H(X)–I(X;Y)=1–0.55=0.45比特/信符H(Y|X)=H(Y)–I(X;Y)=0.98–0.55=0.43比特/信符2.7冗余度

冗余度（多余度、剩余度）表示给定信源在实际发出消息时所包含的多余信息。

2.7冗余度

1

信息效率（相对熵）表示不肯定的程度2

冗余度表示肯定性的程度，因为肯定性不含有信息量，因此是冗余的。2.7冗余度例2.14：英文26个字母加空格共27个符号，统计结果如表2.5所示，计算英文字母的剩余度2.7冗余度解：假如完全等概，则得英文的最大熵为

Hmax=log227

4.76比特/字母而根据表2.5，可计算这27个符号的实际熵为H1=–0.1817lb0.1817–0.1073lb0.1073–…–0.00063lb0.00063

4.065比特/字母为了进一步逼近实际情况，考虑到符号间的相互影响。2.7冗余度

H2=3.32(比特/符号)、H3=3.1(比特/符号)山农曾作过分析和统计，有依赖关系的字母越多，输出的序列越接近于实际情况。当依赖关系延伸到无穷时，信源输出就是真正的英语。此时：H100

=1(比特/符号)冗余度：=79%2.7冗余度正是因为信源符号中存在的这些统计不均匀性和相关性，才使得信源存在冗余度。当英文字母的结构信息已预先充分获得时，可用合理符号来表达英语，例如传送或存储这些符号，可大量压缩，100页的英语，大约只要21页就可以了。（消息中大量的剩余度：提高系统传输效率提供理论基础，但目前还没有指出可行的解决方法）在实际通信系统中，为了提高传输效率，往往需要把信源的大量冗余进行压缩，即所谓信源编码。但是考虑通信中的抗干扰问题，则需要信源具有一定的冗余度。因此在传输之前通常加人某些特殊的冗余度，即所谓信道编码，以达到通信系统理想的传输有效性和可靠性。2.8信源与信道匹配的编码

编码的目的是为了优化通信系统。一般说来，通信系统的性能指标主要是有效性、可靠性、安全性和经济性。所谓优化，就是使这些指标达到最佳。除了经济性外，这些指标正是信息论研究的对象。按照不同的编码目的，编码问题可分为两类：信源编码、信道编码。一、基本概念信源编码是以提高通信有效性为目的的编码。通常通过压缩信源的冗余度来实现。采用压缩每个信源符号的平均比特数或信源的码率。信道编码是以提高信息传输的可靠性为目的的编码。通常通过增加信源的冗余度来实现。采用增大码率或带宽。与信源编码正好相反。

2.8信源与信道匹配的编码二、信源编码的一般模型

信源编码器信道基本符号(0、1)N个消息集合X={x1、x2、…xN}N个代码组集合C={c1、c2、…cN}2.8信源与信道匹配的编码⑴单义可译码定义如果一个码组的任一有限长的码字序列（一串码字），只能唯一地被译成一个一个码字，则称为单义可译码，也称为异前置码。三、基本定义2.8信源与信道匹配的编码例如：信源符号:S:{s1,s2,s3};码元符号:A:{0,1};码字集合:W:{w1=0,w2=10,w3=11},为单义可译码。在无差错条件下，当接收码字序列为：010011001111…，可以唯一地译为：w1,w2,w1,w3,w1,w1,w3,w3……;如果码字集合为：W:{0,01,11}则为非单义可译码。当接收码字序列为：010011001111…

时，可以译为：w2,w1,w1,w3,w1,w1,w3,w3,(w2,w3..),…即可以有不同的译码方法。2.8信源与信道匹配的编码⑵非续长码（瞬时可译码）定义如果一个码组中的任一个码字都不是另一个码字的续长，或者说，任何一个码字后加上若干码元后都不是码组中另一个码字。则称为瞬时可译码，也称为非续长码。例如：W：{0，10，100，111}不是瞬时可译码，100为10的续长。非续长码一定是单义的，单义可译码却不一定是瞬时可译码。例如：W：{0，01}是单义的，但不是瞬时可译码。2.8信源与信道匹配的编码⑶单义可译码定理设原始信源符号集为S:{s1,s2,…sn}，码元符号集为A:{a1,a2,…,aq}，码字集合为W:{W1,W2,…Wn}，其码长分别为L1,L2,…,Ln；则单义可译码存在的充要条件为码长组合满足Kraft不等式，即其中：D为符号集元素的个数，n为码字个数，L为码长2.8信源与信道匹配的编码①Kraft不等式不仅是单义可译码的充要条件，也是非续长码的充要条件；②这里所说的充要条件是对于码长组合而言，而不是对于码字本身而言，就是说：满足Kraft不等式的码长组合一定能构成单义码，单义码的码长组合一定满足Kraft不等式。③有些码字的码长组合满足Kraft不等式，但不是单义码。2.8信源与信道匹配的编码信源[W1][W2][W3][W4][W5][W6]s10000000s2011011101001s30111101001101110s40111111011011111011W1:满足Kraft不等式，但只是单义的，不是非续长码；码长组合为1,2,3,4；W2:满足Kraft不等式，是单义的，也是非续长码；码长组合为1,2,3,4；W3:满足Kraft不等式，不是单义的，也不是瞬时可译码；码长组合为1,2,3,3；W4:满足Kraft不等式，是单义的，也是非续长码；码长组合为1,2,3,3；W5:不满足Kraft不等式，不可能为单义的；码长组合为1,2,2,3；W6:满足Kraft不等式，是单义的，也是非续长码；为等长码；

2.8信源与信道匹配的编码⑷用码树图构成非续长码

从根开始，画出q条分支，任选一个分支作为W1；在另一个分支上再分出q条分支，任选一个分支作为W2；继续进行，直至结束；从根到各端点，所经过状态即为码字；2.8信源与信道匹配的编码（5）平均码字长度如果一个码组的参数满足Kraft不等式，就一定可以构成无噪声信道下的无失真传输，然而，在一个通信系统中，信源编码的主要目的是提高编码效率，即每个码元符号要携带更多的信息量。因此要定义平均码长的概念。2.8信源与信道匹配的编码设原始信源的信源空间为[S,P]=s1s2…snp(s1)p(s2)…p(sn)对此信源用码元符号集A;{a1,a2,…aq}进行编码，得单义可译码W：{W1，W2，…Wn}。相应得码字长度分别为：Li,(i=1,2,…,n)。则这个信源编码的平均码长为：2.8信源与信道匹配的编码这时看一下信息传输效率：每个信道码元所携带的平均信息量。当信源S给定，信源的熵为H(S)，则每个信道码元所携带的平均信息量可以表示为:2.8信源与信道匹配的编码

可见，当原始信源一定时，编码后的平均码长越小，信道传信率越高，编码效率越高。①编码效率可以用平均码长来描述；②每个码字的长度应当与对应的信源符号的先验概率有关。2.8信源与信道匹配的编码四、最佳编码通常称具有最短的代码组平均长度或编码效率接近于1的信源编码为最佳信源编码，亦简称为最佳编码。2.8信源与信道匹配的编码编码效率：实际传输能力/最大传输能力，为：为了提高编码效率，总希望平均码长越小越好，但平均码长能否无限小呢？最佳编码的原则：①把信源符号集合中出现概率大的符号编成长度较短的代码组，而把出现概率小的符号编成长度较长的代码组；②信源编码器输出的代码组为单义可译码组，即序列中不必使用间隔就能把序列逐个分成代码组（因为间隔不携带信息量，使用了间隔自然降低了编码效率）2.8信源与信道匹配的编码

一）香农编码设有离散无记忆信源{XP(X)}，其编码步骤如下：1.将信源符号按其出现概率从大到小排序；2.

令p(x0)=0计算累加概率i，即2.8信源与信道匹配的编码3.按照下式计算出各概率对应的码字长度ki；

4.把各个累加概率由十进制转化为二进制，取该二进制数的前ki位作为对应信源符号的码字。2.8信源与信道匹配的编码[例2.8.1]某信源具有7个消息符号，其概率分别为：0.20,0.19,0.18,0.17,0.15,0.10,0.01。欲对其进行香农方法的二进制编码，求其二进制代码组及其编码效率。解先计算每一个码字的码长，分别为：3,3,3,3,3,4,7；再计算累加概率。2.8信源与信道匹配的编码例如：P4=p1+p2+p3=0.20+0.19+0.18=0.57，变换成二进制数为：0.1001···，因为b4=3，故对于概率为0.17的消息符号x4，其编码为100。依此类推，与本题有关的数据和编码结果列于下表。2.8信源与信道匹配的编码2.8信源与信道匹配的编码可以求出其平均码长和信源熵分别为3.14码元/符号和2.16比特/符号，故其信息传输速率为本题是二进制信道，信道容量C=1比特/码元时间，故其编码效率在数值上等于信息传输速率，即

=83.1%。2.8信源与信道匹配的编码二）费诺编码费诺编码也是一种常见的信源编码方法。其步骤：1.将信源消息符号按其出现的概率大小依次排列，即p(x1)

p(x2)

…p(xn

)

2.将依次排列的信源符号按概率值分为两大组，使两个组的概率之和接近于相同，并对各组赋予一个二进制码元“0”和“1”；2.8信源与信道匹配的编码3.将每一大组的信源符号进一步再分成两个组，使分解后的两个组的概率之和接近于相同，并又赋予两个组一个二进制符号“0”和“1”；4.如此重复，直至每个组只剩下一个信源符号为止信源符号所对应的码字即为费诺编码。2.8信源与信道匹配的编码费诺编码特点：概率大，则分解的次数小；概率小,则分解的次数多。这符合最佳编码原则。码字集合是唯一的。分解完了，码字出来了，码长也有了。因此，费诺编码方法又称为子集分解法。2.8信源与信道匹配的编码例试对例2.8.1的信源用费诺编码方法，求其二进制代码组及其编码效率。

解先将消息符号按概率大小排列，再按步骤进行子集分解，本题经过4次分解完成编码，整个过程列于下表2.8信源与信道匹配的编码2.8信源与信道匹配的编码由上表的数据可得，代码组集合的平均长度为：=2.74码元/符号信息传输速率为由于二进制信道的信道容量C=1比特/码元时间，故编码效率为

=R/C=0.953/1=92.8%

可见，费诺方法的编码效率比香农编码方法要高。2.8信源与信道匹配的编码0000001111110001001110110111011112.8信源与信道匹配的编码例2.8.3有一单符号离散无记忆信源对该信源用费诺编码方法，求其二进制代码组及其编码效率。解该信源熵为H(X)=2.75(比特/符号)平均码长=0.2522+0.12523+0.062544=2.75(比特/符号)2.8信源与信道匹配的编码信源符号概率编码码字码长x10.2500002x20.251012x30.1251001003x40.12511013x50.062510011004x60.0625111014x70.06251011104x80.06251111142.8信源与信道匹配的编码三）哈夫曼编码哈夫曼编码方法的步骤：将信源消息的概率按大小顺序排队；把两个最小的概率相加，作为新的概率，和剩余的概率重新排队；再把最小的两个概率相加，再重新排队，直到最后变成概率1；2.8信源与信道匹配的编码每次相加时都将“0”和“1”按同一规律赋予相加的两个概率，例如概率大的赋予“0”、小的赋予“1”，读出时由该符号开始一直走到最后的概率1，将路径上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的哈夫曼编码。2.8信源与信道匹配的编码例2.8.4一个信源包含6个符号消息，它们的出现概率分别为0.3,0.2,0.15,0.15,0.1,0.1，信道基本符号为二进制码元，试用霍夫曼编码方法对该信源的6个符号进行信源编码，并求出代码组的平均长度和信息传输速率。解根据霍夫曼编码的步骤，可得其编码过程和编码结果，如下图所示。2.8信源与信道匹配的编码0.10.10.150.150.20.3符号概率编码过程11000.2100.3100.60.4101.0二进制代码组0010010011110111ibi2233332.8信源与信道匹配的编码由图的编码结果，求得平均码长为=2.5码元/符号信源熵为信息传输速率为由此可得其编码效率为98.8%，接近于最佳编码。2.8信源与信道匹配的编码例2.8.5已知一信源的概率空间为用霍夫曼编码方法找出各消息的代码组并计算编码效率。解（解法一）根据霍夫曼编码的步骤，可得其编码过程和编码结果，如下图所示。2.8信源与信道匹配的编码求得平均码长为信源熵为2.8信源与信道匹配的编码0.10.10.20.20.4概率编码过程11000.2100.40.6101.0二进制代码组0010010011bi2223311消息x1x2x3x4x52.8信源与信道匹配的编码信息传输速率和编码效率分别为

1=R1/C=0.9645/1=96.45%

由本例可见，编码效率也接近于最佳编码。2.8信源与信道匹配的编码（解法二）但组合的方法和解法一有所不同，所得编码过程和编码结果，如下图

0.10.10.20.20.4概率编码过程1000.200.40.610二进制代码组10100100011bi12344000消息x1111.0x2x3x4x52.8信源与信道匹配的编码由上图的编码结果，求得平均码长为

=0.4

1+0.2

2+0.3

3+0.1

4

2=2.2码元/代码组由于平均码长与解法一相同，故信息传输速率和编码效率均与解法一相同。由此可见，尽管概率相加的组合方法不同而导致编码路径（编码结果）不同，但编码效率都是一样的。2.8信源与信道匹配的编码在实际应用中，选择那种编码方法？我们定义码字长度的方差为ki与平均码长之差的平方的数学期望，记为

2，即

2.8信源与信道匹配的编码计算上例中两种码的方差分别得

21=0.16

22=1.36可见第一种编码方法的码长方差要小许多。这意味着第一种编码方法的码长变化较小，比较接近平均码长。2.8信源与信道匹配的编码在哈夫曼编码过程中，对缩减信源符号按概率由大到小的顺序重新排列时，应使合并后的新符号尽可能排在靠前的位置，这样可使合并后的新符号重复编码次数减少，使短码得到充分利用。

2.8信源与信道匹配的编码把二进制的编码方法推广到m进制哈夫曼码。所不同的只是每次把m个概率最小的符号分别用0,1,…,m-1等码元来表示，然后再合并成一个新的信源符号。其余步骤与二进制编码相同。2.8