信息论与编码全套教学课件

信息论与编码

第1章绪论第2章信源与信息熵第3章信道与信道容量第4章失真与信息率失真函数第5章信源编码第6章信道编码第7章网络信息论初步全套可编辑PPT课件2第1章绪论信息论是什么？编码是用来干什么的？全套可编辑PPT课件3第1章绪论信息论与编码课程的内容体系信息与编码的若干基本概念信息论的发展历史全套可编辑PPT课件4第1章之“信息论与编码”课程的内容体系通信系统基本模型信息论与编码课程内容体系5第1章之“信息论与编码”课程的内容体系本课程所说“信息论”，主要是指“香农信息论”；香农信息论的主要内容，来自于其1948年发表在贝尔技术杂志上的文章：“通信中的数学理论”；所以，香农信息论，严格来说应该是“通信论”。6通信系统基本模型既然是通信理论，首先看看通信的定义、基本框图和基本问题：定义：通信是把信息从一个地方（发送端，信源）通过信息的通道（信道）送到另一个地方（接收端，信宿）。7通信系统基本模型基本框图：信源信宿噪声源信息信息干扰信道8通信系统基本模型基本问题：如何使通信“又快又好又安全”？快：用尽可能少的符号携带尽可能多的信息—有效性；好：信息传输要尽可能准确无误—可靠性；安全：信息的安全性。本书只考虑有效性和可靠性。9“信息论与编码”课程的内容体系对有效性和可靠性这两个通信中的基本问题，又各有两个方面的内容：希望“又快”（有效性）、“又好”（可靠性），这个“快”和“好”有没有极限？如果有，极限是多少？这是“信息论”要解决的问题；用什么方法和手段达到或接近该极限？这是“编码”所要解决的问题。

所以这门课叫做《信息论与编码》10“信息论与编码”课程的内容体系所以，《信息论与编码课程》的内容体系，可以表示成一个2×2的矩阵：信息论编码可靠性有效性有效性的极限是否存在及其大小问题可靠性的极限是否存在及其大小问题达到或接近有效性极限的手段和方法达到或接近可靠性极限的手段和方法11“信息论与编码”课程的内容体系有效性是要用尽可能少的符号携带尽可能多的信息，这个取决于信源的特性。所以在接下来的第2章，要研究信源与信源熵；可靠性取决于信息传输通道（信道）的特性，因此第3章研究信道与信道容量；12“信息论与编码”课程的内容体系相应地：提高有效性的方法，是对信源进行编码，称为信源编码，是第5章的内容；提高可靠性的方法，是对信道上传输的信息进行编码，称为信道编码，是第6章的内容；13“信息论与编码”课程的内容体系此外：第4章也是关于信源的，与第2章的不同在于：第2章的内容用于无失真信源编码，而第4章的内容用于限失真信源编码。由于其处理手段，类似于第3章信道的处理方法，故放于第3章之后；第7章对信息论的前沿技术—网络信息论，进行了简要介绍。14“信息论与编码”课程的内容体系所以，可以把上面的2×2矩阵重新表示为：信息论编码可靠性有效性第2章、第4章第3章第5章第6章15“信息论与编码”课程的内容体系从横的方向看：第2章（包括第4章）和第3章是平行的第2章研究信源，主要关心信源熵，是有关有效性的；

第3章研究信道，主要关心信道容量，是有关可靠性的；

第2章和第3章的章节结构是几乎一样的。16“信息论与编码”课程的内容体系第5章和第6章是平行的第5章研究信源编码，是实现有效性的方法；

第6章研究信道编码，是实现可靠性的方法；

第5章和第6章的章节结构是几乎一样的。17“信息论与编码”课程的内容体系从纵的方向看：第2章（包括第4章）和第5章是前后衔接的第2章研究信源特性，第5章在第2章的基础上，研究提高有效性的手段和方法（信源编码），这是一条有关有效性的主线；18“信息论与编码”课程的内容体系第3章和第6章是前后衔接的第3章研究信道特性，第6章在第3章的基础上，研究提高可靠性的手段和方法（信道编码），这是一条有关可靠性的主线；有效性的主线（第2、5章）和可靠性的主线（第3、6章）是平行的。19第1章绪论信息论与编码课程的内容体系信息与编码的若干基本概念信息论的发展历史20第1章之信息与编码的若干基本概念信息的概念信息的度量21信息的概念信息论是研究信息的，所以首先要明白什么是信息？信息的本质是什么？22信息的概念全部意义上的信息（全信息）包括：语法信息、语义信息和语用信息语法信息只考虑信息的外在形式；语义信息要考虑信息的内容；语用信息要考虑信息的作用对象。23信息的概念考虑全信息，则无法进行深入研究。克劳德•香农等只考虑语法信息，对信息进行了深入研究，得到了有关信息的系统理论，是为“香农信息论”，也称“狭义信息论”。24信息的概念香农：“信息是使随机不确定性减少的程度”。要进行通信，一定是接收方关于某事件是未知的或不确定的；接收方接收到信息以后，可以消除或者减少这种不确定性。25信息的度量毕达哥拉斯：“万物皆数”。要对信息进行深入研究，必须定量；信息量的多少，等于对随机不确定性减少的程度；随机不确定性可以用概率来描述。26信息的度量要实现度量，首先需定义一个单位：信息的基本单位：比特（bit）可以用一个“是（或否）”的回答来消除的不确定性，定义为1比特（2选1的不确定性）。27信息的度量一个事件包含的信息量必须满足：与该事件出现的概率是反比例关系（备选答案越多（某一备选答案选中的概率越小），不确定程度越大，信息量越大）；确定性的事件信息量为0；信息量具有可加性。28信息的度量根据以上条件，可以用公式：来计算信息的多少。当取以2为底的对数时，信息量的单位为比特。29第1章之信息论的形成和发展历史略30第2章信源与信源熵信源的分类与数学模型离散单符号信源熵离散序列信源熵马尔科夫信源极限熵连续信源熵波形信源熵连续信源最大熵定理信源的冗余度31信号分类

离散信号

时间和幅度均离散

连续信号

时间和幅度均连续

时间离散幅度连续信号

抽样信号

幅度离散时间连续信号2.1信源的分类及数学模型2.1.1信源分类321、离散信源离散单符号信源离散序列信源2、时间离散幅度连续信源连续单符号信源连续序列信源无记忆有记忆马尔科夫信源无记忆有记忆3、时间连续幅度连读信源（波形信源）2.1.1信源分类信源分类：（由简单到复杂）（1）离散单符号信源；（2）离散序列信源；（3）马尔科夫信源；（4）连续单符号信源；（5）连续序列信源；（6）波形信源。33342.1.2信源的数学模型描述：通过概率空间描述（1）离散单符号信源离散信源：，pi

0。2.1.2信源的数学模型（2）离散序列信源（L次扩展信源）联合概率：无记忆：

352.1.2信源的数学模型（3）马尔科夫信源联合概率：

3637（4）连续单符号信源显然应满足pX(x)

0，

2.1.2信源的数学模型38（5）连续序列信源若为无记忆的，则

2.1.2信源的数学模型2.1.2信源的数学模型（6）波形信源某时刻的取值是随机的，用随机过程{x(t)}来描述对于限频波形信源，设其最高频率为fm，根据奈奎斯特抽样定理，只要抽样频率fs≥2fm，则可用其抽样信号无失真恢复原信号。设该波形信源持续时间为tB，如果我们取最低抽样频率fs＝2fm，则只需要个2fmtB采样点即可。因此，一个代表波形信源的平稳随机过程{x(t)}，可以用序列长度L＝2fmtB的随机矢量来表示即可，其概率空间可

用序列长度L＝2fmtB的连续序列信源的概率空间

来描述。3940从理论上说任何时间受限的函数，其频谱是无限的；反之，任何频带受限的函数，其时间上是无限的。实际中，可认为函数在频带fm、时间tB以外的取值很小，不至于引起函数的严重失真。2.1.2信源的数学模型41（1）马尔可夫信源简化形式当信源的记忆长度为m+1时，该时刻发出的符号与前m个符号有关联性，而与更前面的符号无关。2.1.3马尔科夫信源的稳态分布42离散有记忆序列信源与马尔可夫信源区别(a)离散有记忆序列信源(b)马尔可夫信源43（2）齐次马尔可夫信源齐次马尔可夫信源：条件概率与时间起点无关。平稳包含齐次，齐次不一定平稳。2.1.3马尔科夫信源的稳态分布平稳与齐次区别若Q和T为任意两个时刻，平稳满足44运用概率的一般运算法则45（3）马尔可夫信源状态转移概率矩阵信源在某一时刻出现符号概率xj与信源此时所处状态si有关，用符号条件概率表示p(xj/si)，状态转移概率表示为p(sj/si)状态集为：2.1.3马尔科夫信源的稳态分布46马尔可夫信源一步转移概率特别关心n-m=1情况，pij(m,m+1)2.1.3马尔科夫信源的稳态分布47马尔可夫信源一步转移概率矩阵系统在任一时刻可处于状态空间的任意一状态，状态转移时，转移概率是一个矩阵。由于共有Q=nm种不同状态，可用Q×Q的矩阵来描述一步转移概率矩阵：2.1.3马尔科夫信源的稳态分布48齐次马尔可夫信源性质对于齐次马尔可夫链，一步转移概率完全决定了k步转移概率。定义：若齐次马尔可夫链对一切i,j存在不依赖于i的极限，则称其具有遍历性，pj称为平稳分布2.1.3马尔科夫信源的稳态分布49马尔可夫信源定理：设有一齐次马尔可夫链，其状态转移矩阵为P，其稳态分布为wj=p(sj)2.1.3马尔科夫信源的稳态分布2.1.3马尔科夫信源的稳态分布该方程是否存在解？解是否唯一结论1：该方程一定存在非零解。

502.1.3马尔科夫信源的稳态分布解的唯一性

说明：以上条件只是马尔科夫信源存在稳态分布的必要条件，并不是充要条件。51由于52不可约性:就是任意一对i和j，都存在至少一个k，使pij(k)>0。非周期性:所有pii(n)>0的n中没有比1大的公因子。2.1.3马尔科夫信源的稳态分布53如图2-1所示的二进制相对码编码器（其中T为时延模块），初始状态Y1=X1；其余时刻，如输入X=0，则当前时刻输出等于上时刻输出，Yi+1=Yi；如输入X=1，则当前时刻输出异于上时刻输出，

；若已知P(X=0)=p，P(X=1)=1-p=q，试写出其转移概率矩阵，并画出状态转移图。2.1.3马尔科夫信源的稳态分布解：由于当前时刻的输出，取决于当前时刻的输入，以及前一个时刻的输出，所以输出序列是一个一阶马尔可夫链。对于二进制信源，前一个时刻的输出共有两种（0或者1），所以状态共有两种：“0”状态和“1”状态。

即转移概率矩阵为：其状态转移图为：

54pqp10q2.1.3马尔科夫信源的稳态分布二阶马尔科夫信源，X{0,1},求稳态概率分布55起始状态符号01s1(00)1/21/2s2(01)1/32/3s3(10)1/43/4s4(11)1/54/5表2-1符号条件概率p(aj|si)解：对二阶马尔可夫链，其状态共有四种，分别为：S=(00，01，10，11)，根据符号条件概率表2-1，可以写出符号条件概率矩阵为：可得状态转移概率矩阵为5657状态转移概率起始状态(si)s1(00)s2(01)s3(10)s4(11)1/201/401/203/4001/301/502/304/5s1(00)s2(01)s3(10)s4(11)2.1.3马尔科夫信源的稳态分布表2-2状态条件概率p(sj|si)终止状态(sj)状态转移图：5800100111(0)1/2(0)1/5(1)2/3(0)1/4(1)1/2(1)4/5(1)3/4(0)1/359

设四种状态的稳态概率为W1，W2，W3，W4可得方程组解得稳态分布的概率为：达到稳态后的符号概率为：2.1.3马尔科夫信源的稳态分布例：设有一马尔科夫链，其状态转移矩阵为判断该马尔科夫链是否存在稳态分布？

60612.2离散单符号信源熵自信息量离散单符号信源熵离散单符号信源条件熵离散单符号信源联合熵互信息信源熵性质622.2.1自信息量自信息量

例以2为底，单位为比特，用bit（或b）表示。自信息量与不确定度自信息量：符号出现后，提供给收信者的信息量；不确定度：符号出现前，所含有的不确定性。二者数量上相等，物理含义不同。632.2.1自信息量642.2.1自信息量自信息量的性质p(xi)=1,I(xi)=0；确定性事件不包含任何信息量；p(xi)=0,I(xi)=∞；出现的概率越小，包含的信息量越大；概率等于零时，包含的信息量为无穷大；非负性：p(xi)∈[0,1]，所以，故I(xi)≥0；可加性：如果符号xi中包含I(xi)的信息量，符号yj中包含I(yj)的信息量，则符号xi和yj同时出现包含的信息量，为两者的自信息量之和（假定两者互相独立p(xi,yj)＝p(xi)p(yj)）：

I(xi,yj)=I(xi)+I(yj)

例：假设一次掷两个各自均匀、互相不可区分但又不相关的骰子。如(A)、(B)分别表示：仅有一个骰子是3；至少有一个骰子是4；试计算(A)、(B)发生后提供的信息量。65662.2.2离散单符号信源熵离散单符号信源熵就是其平均不确定度

对于

，平均信息量为

离散单符号信源熵例题例：二元信源的熵67H(X)=-plogp-(1-p)log(1-p)=H(p)当p=0.5时，具有最大熵；当p=1或p=0时，H(X)=0;信源熵是p的上凸函数。682.2.3离散单符号信源条件熵给定条件yj，信源X的概率空间变化为

给定条件yj，可得条件熵：信息量例：某高三毕业生中，25%的女生考取了大学。在考取大学的女生中75%居住在城区，而高三毕业生中50%住在城区。假如我们得知“住在城区的女生考取了大学”的消息，试问获取了多少信息量？69702.2.3离散单符号信源条件熵若Y∈{yj,j=1,2,…,m}，可得{H(Y|y1),H(Y|y2),…,H(Y|ym)}若以Y为条件下，则X的条件熵为条件熵H(Y|X)表示当已知Y时，X仍然具有的不确定度。

例2-4

某二进制数字通信系统如图2-5所示。发送端信源X为二进制信源{0，1}，其概率空间为由于通信信道中有干扰和噪声，导致接收端判决结果除了“0”和“1”以外，还有一种未知的状态（既不是“0”也不是“1”），我们表示为“？”状态。设信道的符号转移概率为：求信源熵H(X)、条件熵H(X/Y)和H(Y/X)，以及信源熵H(Y)。71p(y=0/x=0)=3/4，

p(y=0/x=1)=0；p(y=1/x=0)=0，

p(y=1/x=1)=1/2；p(y=?/x=0)=1/4，

p(y=?/x=1)=1/2；图2-5二进制数字通信系统解：（1）信源熵H(X)可直接由公式求得（2）根据条件熵公式，求条件熵H(Y/X)，，需要知道条件概率p(y=0/x=0)、p(y=1/x=0)、p(y=？/x=0)和p(y=0/x=1)、p(y=1/x=1)、p(y=？/x=1)；以及联合概率p(x=0,

y=0)、p(x=0,

y=1)、p(x=0,y=？)和p(x=1，y=0)、p(x=1,y=1)、p(x=1,y=？)等：p(x

=0,y=0)=p(x=0)p(y=0/x=0)=1/2p(x

=0,

y=1)=p(x=0)p(y=1/x=0)=0p(x=0,y=?)=p(x=0)p(y=?/x=0)=1/6p(x=1,y=0)=p(x=1)p(y=0/x=1)=0p(x=1,y=1)=p(x=1)p(y=1/x=1)=1/6p(x=1,y=?)=p(x=1)p(y=?/x=1)=1/6则由条件熵公式可得：72（3）、根据条件熵公式，求条件熵H(X/Y)，，需要知道条件概率p(x=0/y=0)、p(x=0/y=1)、p(x=0/y=？)和p(x=1/y=0)、p(x=1/y=1)、p(x=1/y=？)；以及联合概率p(x=0,y=0)、p(x=0,y=1)、p(x=0,y=？)和p(x=1,y=0)、p(x=1,y=1)、p(x=1,y=?)等：故

73因此（4）由74得：752.2.4离散单符号信源联合熵当X和Y联合出现，若X∈{x1,x2,…,xn},Y∈{y1,y2,…,ym}，则其概率空间变化为

联合熵：信息量例题例2-5根据例2-4的信源X和信源Y，求联合熵H(X,Y)。

根据例2-4的求解过程，已知：

p(x

=0,y=0)=p(x=0)p(y=0/x=0)=1/2

p(x

=0,

y=1)=p(x=0)p(y=1/x=0)=0p(x=0,y=?)=p(x=0)p(y=?/x=0)=1/6

p(x=1,y=0)=p(x=1)p(y=0/x=1)=0p(x=1,y=1)=p(x=1)p(y=1/x=1)=1/6p(x=1,y=?)=p(x=1)p(y=?/x=1)=1/676772.2.5互信息互信息：例2-4数字通信系统78符号间互信息：在X取值集合上做概率统计平均，即得：进一步，在Y取值集合上做概率统计平均，即得2.2.5互信息79而且：例2-6，求例2-4中，符号X和符号Y之间的互信息2.2.5互信息80信源熵、条件熵、联合熵之间的关系若X和Y相互独立，则信源熵、条件熵、联合熵、互信息之间的关系

2.2.6信源熵、条件熵、联合熵、互信息等之间的关系812.2.6信源熵、条件熵、联合熵、互信息等之间的关系图2-6互信息量与熵之间的关系图2-7收、发两端的熵关系822.2.7信源熵的性质非负性对称性确定性可扩展性递增性83非负性84对称性85确定性可扩展性递增性这条性质表明，若原信源X中有一元素划分成m个元素（符号），而这m个元素的概率之和等于原元素的概率，则新信源的熵增加。熵增加了一项是由于划分而产生的不确定性量。例H(1/3,1/3,1/6,1/6)8687上凸性极值性（最大离散熵定理）熵函数H(P)是概率矢量P={p1，p2，…，pn}的严格∩型凸函数（上凸函数）。可加性

一般式当X、Y相互独立时熵的可加性可这样理解：复合事件集合的平均不确定性为各个分事件集合的平均不确定性的和。88递增性这条性质表明，若原信源X中有一元素划分成m个元素（符号），而这m个元素的概率之和等于原元素的概率，则新信源的熵增加。熵增加了一项是由于划分而产生的不确定性量。例H(1/3,1/3,1/6,1/6)8990

2.3离散序列信源熵离散无记忆信源及其信息熵离散有记忆信源熵离散平稳信源的极限熵

2.3离散序列信源熵离散序列信源（L次扩展信源）概率空间离散序列信源熵：

91单位：比特/序列独立但非同分布独同分布序列熵

2.3.1离散无记忆信源的序列熵92消息熵平均符号熵单位：比特/符号i.i.d.9394

2.3.2离散有记忆信源熵消息熵：序列熵：95对于有记忆离散序列信源，可得：结论1：离散序列信源的极限熵为：

结论2：

是L的单调非增函数结论3：

结论4：

是L的单调非增函数2.3.3离散平稳信源的极限熵96例

离散有记忆信源p(xj/xi)xjxix1x2x3x19/111/80x22/113/42/9x301/87/997解：

H(X2/X1)＝0.87比特/符号

H(X1)＝1.5比特/符号

H(X1,X2)＝H(X1)＋H(X2/X1)

＝1.5＋0.87＝2.37比特/序列 平均符号熵H2(X)＝0.5H(X2)＝1.185比特/符号比较上述结果可得：H2(X)<H1

(X)，即二重序列的符号熵值较单符号熵变小了，也就是不确定度减小了，这是由于符号之间存在相关性造成的。98马氏链极限熵齐次马尔科夫链2.4马尔科夫信源的极限熵99例2-8求马氏链平均符号熵（三个状态）

1/0.1s1

1/0.50/0.90/0.50/0.8s2

s31/0.2

三状态马尔可夫信源状态转移图解得：W1＝5/59，W2＝9/59，W3＝45/59。马尔可夫信源的熵：比特/符号100求解马尔可夫信源熵的步骤为：(1)根据题意画出状态转移图，或写出状态转移矩阵；(2)计算信源的平稳分布概率（假定信源具有平稳分布）；(3)根据一步转移概率和稳态分布概率，计算信源熵（极限熵）。1011022.5连续单符号信源熵2.5.1幅度连续的单个符号信源熵1032.5.1幅度连续的单个符号信源熵1042.6连续序列信源熵连续序列的熵和离散序列的熵性质完全相同，只要把离散信源熵用连续信源熵替代即可。105

2.7波形信源熵波形信源可用随机过程x(t)表示。对限时tB和限频fm平稳随机过程，可以抽样成序列长度L=2fmtB的连续序列信源，其熵为：2.8连续信源最大熵定理问题的提出:

在连续信源中，不同约束条件(峰值功率、平均功率)下，有不同的最大熵。无约束时，最大熵不存在。106对于定义域为有限的随机变量X，当它是均匀分布时，具有最大熵。变量X的幅度取值限制在[a，b]，当pX

(x)=1/(b-a)，则Hc(X)=log(b-a)峰值功率受限为P，则输出信号的瞬时电压限定在

P1/2，等价于取值幅度受限。

限峰功率最大熵定理107108限平均功率最大熵定理对于相关矩阵一定随机变量X，当它是正态分布时具有最大熵最大熵定理（总结）无约束条件的最大熵不存在限峰功率最大熵限平均功率最大熵1091102.9信源的冗余度冗余度，表示给定信源在实际发出消息时所包含的多余信息。它来自两个方面，一是信源符号间的相关性；二是信源符号分布的不均匀性1112.9信源的冗余度例：计算英文字母冗余度H0(X)=l0g27=4.76比特/符号H1(X)=4.03比特/符号H2(X)=3.32比特/符号H3(X)=3.1比特/符号H∞(X)=1.4比特/符号本章小结112第二章主要内容结构113本章小结本章学习思路信源（信息的出发点）→对信源进行分类→给出数学模型→信源的重要参数：熵、互信息等→按照分类，从简单到复杂，研究信源的熵等重要参数114定义、性质

计算公式、相互关系自信息量信源熵、条件熵、联合熵、互信息序列熵、平均符号熵、极限熵连续信源最大熵定理冗余度115第3章信道与信道容量信道的分类与数学模型离散单符号信道的信道容量离散序列信道的信道容量连续单符号信道的信道容量连续序列信道的信道容量波形信道的信道容量信道冗余度1163.1.1信道的分类（按照信道输入信号分类）

离散单符号信道

离散序列信道

连续单符号信道

连续序列信道

波形信道主要目的：研究信道中理论上能够传输或存储的最大信息量，即信道容量。3.1信道的分类1173.1.2信道的数学模型描述：信道把特定输入符号映射为特定输出符号的能力（正确概率）以及映射为其他输出符号的可能性（错误概率）。图3-1信道模型图P(Y|X)1181.离散单符号信道的数学模型转移概率矩阵离散单符号信道模型P(Y|X)119例：二进制对称信道（BSC）转移概率矩阵图3-2二进制对称信道（BSC）p11=1-p，p12=p，p21=p，p22=1-p1202.离散序列信道的数学模型当输入为离散序列时，用随机矢量x来表示，若输出随机矢量为y，则信道可用转移概率P(y/x）表示。当信源和信道无记忆时，离散序列信道可看成一系列离散单符号信道。121例:扩展信道如果对离散单符号信道进行L次扩展，就形成了L次离散无记忆序列信道BSC的二次扩展信道

00101101000111X

{00,01,10,11}，Y

{00,01,10,11}，二次扩展无记忆信道的序列转移概率p(00/00)=p(0/0)p(0/0)=(1-p)2，p(01/00)=p(0/0)p(1/0)=p(1-p)，p(10/00)=p(1/0)p(0/0)=p(1-p)，p(11/00)=p(1/0)p(1/0)=p2101223.连续单符号信道的数学模型对连续单符号输入信源x，对应的输出为随机变量y。若信道为加性高斯白噪声信道:

y=x+n其中，n为0均值、方差为σ2的高斯随机变量。若给定输入x0，则1234.连续序列信道的数学模型当输入为连续序列时，用随机矢量x来表示，若输出随机矢量为y，则信道可用转移概率密度pY(y/x）表示。若输入序列无记忆，无记忆连续序列信道可以看作是一系列连续单符号信道。1245.波形信道的数学模型若输入为波形信源，用随机过程{x(t)}表示，则输出也为随机过程，记为{y(t)}。若满足限时（tB）限频（fm）条件，则可以抽样成L=2fmtB的连续平稳随机序列，则信道用转移概率密度描述，为：若信源信道无记忆，则1251.互信息量表达式3.1.3信道容量的定义126定理3.1

在p(yj|xi)给定时，互信息量I(X;Y)是p(xi)的上凸函数。通信的目的:每次信道使用（每发送一个符号），传送到接收端尽可能多的信息量（互信息量I(X;Y)取最大值）。需要解决的问题是：①该最大值是多少？②p(xi)是什么分布时，取得该最大值？1272.信道容量的定义信道容量（ChannelCapacity）：信道所能传送的最大信息量。比特/符号（bits/symbol或bits/channeluse）

在p(y/x)给定时，I(X;Y)是关于p(x)的上凸函数。信道容量要解决的问题：C=?p(xi)=?128离散无记忆信道（DMC）

对称离散无记忆信道

准对称离散无记忆信道

一般离散无记忆信道3.2离散单符号信道的信道容量129输入对称如果转移概率矩阵P的每一行都是第一行的置换(包含同样元素)，称该矩阵是输入对称。输出对称如果转移概率矩阵P的每一列都是第一列的置换(包含同样元素)，称该矩阵是输出对称。对称信道如果输入、输出都对称。3.2.1对称离散无记忆信道130对称DMC信道例子131输入对称132如果信道输入符号等概分布p(ai)＝1/n当转移概率矩阵列对称时，信道输出符号p(bj)等概分布－－输出对称133例3-2.求信道容量134例3-3.求信道容量信道输入符号和输出符号的个数相同，都为n，且正确的传输概率为1－

，错误概率

被对称地均分给n-1个输出符号，此信道称为强对称信道或均匀信道，是对称离散信道的一个特例。135例3-4.二进制对称信道（BSC）：当

时，错误概率为0，无差错，信道容量达到最大，每符号1bit，输入端的信息全部传输至输出端。当

时，错误概率与正确概率相同，从输出端得不到关于输入的任何信息，互信息为0，即信道容量为0。对于

的情况，可在BSC的输出端颠倒0和1，导致信道容量以

点中心对称。136例3-5.串联信道137例3-5.串联信道图3-6m个BSC串联信道的互信息串接的信道越多，其信道容量可能会越小，当串接信道数无限大时，信道容量就有可能趋于零。

138若信道的转移概率矩阵输入对称而输出不对称，这样的信道称为准对称离散无记忆信道。当输入等概率时不能确保输出等概：一般情况下：

3.2.2准对称离散无记忆信道1391.求极值方法例：求信道容量信道的输入符号有两个，可设p(a1)＝

，p(a2)＝1－

，信道的输出符号有三个，用b1、b2、b3表示

3.2.2准对称离散无记忆信道1401.求极值方法因为

，所以应有：

p(a1)＝p(a2)＝1/21412.矩阵分解法

将转移概率矩阵划分成若干个互不相交的对称的子集，则准对称DMC的信道容量为：其中，Nk为第k个对称子矩阵一行元素之和，Mk为第k个对称子矩阵一列元素之和。

1422.矩阵分解法

1433.观察法

观察该矩阵可知，因为p(xi)无论如何分布，p(b3)为恒定值0.2，故要得到最大的H(Y)，b1和b2应为均匀分布，即p(b1)=p(b2)=0.4，此时：p(a1)=p(a2)=0.5。

144一般地说，为使I(X;Y)最大化以便求取DMC容量，输入符号概率集{p(ai)}必须满足的充分和必要条件是：

当信道平均互信息达到信道容量时，输入符号概率集{p(ai)}中每一个符号ai对输出端Y提供相同的互信息，只是概率为零的符号除外。

3.2.2一般离散无记忆信道145离散序列信道

对离散无记忆序列信道：若信道同时还是平稳的，则3.3离散序列信道的信道容量1461.信道无记忆的情形例：X1=X2=…=XL=Y1=Y2=…=YL3.3.1信道与信源无记忆情形1472.信源无记忆的情形例：Yi=Xi+1,YL=X1;X1,X2,…，XL互相独立1483.信源和信道皆无记忆的情形此时，149对离散单符号信道进行N次扩展，就形成了N次离散无记忆信道。3.3.2N次扩展信道BSC的二次扩展信道0010110100011011X

{00,01,10,11}，Y

{00,01,10,11}，二次扩展无记忆信道的序列转移概率p(00/00)=p(0/0)p(0/0)=(1-p)2，p(01/00)=p(0/0)p(1/0)=p(1-p)，p(10/00)=p(1/0)p(0/0)=p(1-p)，p(11/00)=p(1/0)p(1/0)=p2150扩展信道若p＝0.1，则C2＝2－0.938＝1.062比特/序列

151序列转移概率若信道无记忆，则3.3.3独立并联信道图3-8独立并联信道只有当输入相互独立时取等号。152平均互信息

I(X;Y)＝HC(Y)－HC(Y/X)3.4连续单符号信道的信道容量图3-9连续单符号信道y=x+npn(x)＝N(0,

2)153pn(n)＝N(0,

2)，当

pY(y)＝N(0,Po)时取得maxHC(Y)，

pX(x)＝N(0,Ps)，Po=Ps+2C＝1/2log(1+SNR)

信道输入X是均值为零、方差为PS的高斯分布随机变量时，信息传输率达到最大值。若是加性的，可以求出信道容量的上下界

154

信道输入随机序列X＝X1X2…XL，输出随机序列Y＝Y1Y2…YL，加性信道有y=x+n，其中n=n1n2…nL

是均值为零的高斯噪声

3.5连续序列信道的信道容量图3-10多维无记忆加性信道等价于L个独立并联加性信道155连续单符多维无记忆高斯加性信道就可等价成L个独立的并联高斯加性信道。若

将总功率P如何分配给输入序列中的各个符号，才能得到最大的信道容量？3.5连续序列信道的信道容量156噪声均值为零、方差相同（平均分配，每个符号均值为0，方差为S的高斯变量）

若噪声均值为零、方差不同，总平均功率受限P，功率则应合理分配。最大容量问题即为：3.5连续序列信道的信道容量157用拉格朗日乘子法构造无约束极值问题：各个时刻的信道输出功率相等设为常数

158讨论均值为零、方差不同，总平均功率受限P，功率合理分配。159注水法(water-filling)功率分配该功率分配方法，可以形象地描述为图3-11，如果把噪声功率看成是容器底部的凸起，把v看成是水平面，则每个子信道上分配的功率，就如往底部有不同凸起的容器中注水，故形象地称为“注水算法”。图3-11注水法功率分配160例：有一并联高斯加性信道，各子信道噪声方差为（1）P=5：输出端总功率

各子信道分配的功率分别是：0.95，0.85，0.75，0.65，0.55，0.45，0.35，0.25，0.15，0.05。（2）P=3？平均输出功率（水平面）为10.5/10=1.05161限时限频(fm)高斯白噪声过程可分解L＝2fmtB维统计独立的随机序列

若每个抽样时刻的噪声均为零均值、方差为σ2的加性高斯噪声（W为带宽，W=fm），则：3.6波形信道的信道容量162信道容量单位时间的信道容量香农公式

输入信号{x(t)}满足均值为零、平均功率P的高斯白噪声的特性163带宽W一定时，信噪比SNR与信道容量Ct成对数关系，SNR增大，Ct就增大，但增大到一定程度后就趋于缓慢。增加输入信号功率有助于容量的增大，但该方法是有限的；降低噪声功率也是有用的，当N0→0,Ct→∞即无噪声信道的容量为无穷大。讨论

Ct

＝Wlog(1+SNR)单位时间的信道容量图3-12信道容量与信噪比的关系164Ct一定时，带宽W增大，信噪比SNR可降低，即两者是可以互换的。若有较大的传输带宽，则在保持信号功率不变的情况下，可容许较大的噪声，即系统的抗噪声能力提高。无线通信中的扩频系统就是利用了这个原理，将所需传送的信号扩频，使之远远大于原始信号带宽，以增强抗干扰的能力。Ct＝Wlog(1+SNR)比特/秒165Ct/W＝log(1+SNR)比特/秒/Hz，单位频带的信息传输速率－－频带利用率，该值越大，信道就利用得越充分。当SNR=1（0dB），Ct/W=1bit/s/Hz；当SNR=-1.6dB，Ct/W=0bit/s/Hz。（因为此时需要无穷大的的带宽W）。频带利用率图3-13频带利用率与信噪比的关系166

信源发出的消息（符号）要通过信道来传输，因此要求信源的输出与信道的输入匹配。符号匹配：信源输出的符号必须是信道能够传送的符号；信息匹配：当信源与信道连接时，信息传输率达到信道容量，则称信源与信道达到匹配。3.7信道冗余度167

信道冗余度信道绝对冗余度

γ=C－I(X;Y)；信道相对冗余度γ=168信道冗余度冗余度大：信源与信道匹配程度低，信道的信息传递能力未得到充分利用；冗余度小：信源与信道匹配程度高，信道的信息传递能力得到较充分利用；冗余度为零，说明信源与信道（信息）完全匹配，即信源概率分布符合最佳输入分布。一般来说，实际信源的概率分布未必就是信道的最佳输入分布，所以I(X;Y)≤C，冗余度不为零。本章小结169第三章主要内容结构170本章小结本章学习思路信道（信息传输的通路）→对信道进行分类→给出数学模型→信道的重要参数：信道容量→按照分类，从简单到复杂，研究信道的信道容量。171第4章失真与信息率失真函数失真的概念和性质信息率失真函数172问题信源熵H(X)的物理含义是什么？为什么要研究信源熵？信源无失真传输所需的最小信息率为R

H(X)；允许信源有失真时，输出的最小速率可降低为R<H(X)；失真D越大，R可以越小，因此R是D的函数，且为单调递减函数。R(D)就叫做信息率失真函数。173限失真编码的必要性对于连续信源，因为其熵为无穷大，若要求对其进行无失真编码，需要用无穷多个比特才能完全无失真地来描述。由于人耳能够接收的带宽和分辨率是有限的，因此对数字音频，就允许有一定的失真，并且对音乐欣赏没有影响。可把频谱范围从20Hz~8000Hz的语音信号去掉低频和高频，保留带宽范围300Hz~3400Hz的信号，这种失真是允许的。对于数字电视，由于人的视觉系统对低频比较敏感，对高频不太敏感，且人眼分辨率有限，因此可以在一定限度内损失部分高频分量。174限失真编码从直观感觉可知，若允许失真越大，信息传输率可越小；若允许失真越小，信息传输率需越大。所以信息传输率与信源编码所引起的失真(或误差)是有关的。1754.1失真的概念和性质X={xi}，xi

{a1,…an}

信源编码器

Y={yj}，yj

{b1,…bm}失真函数d(xi，yj)176最常用的失真函数均方失真：

相对失真：误码失真：绝对失真：前三种失真度量适用于连续信源，后一种适用于离散信源。177失真矩阵

单个符号的失真度的全体构成的矩阵，称为失真矩阵178平均单符号失真

已知p(ai)和d(ai，bj)，平均失真只是符号转移概率p(bj/ai)的函数。p(bj/ai

)在此实质上代表编码方式。179例：x1

y1x2

y2x1

y1x2

y1180序列失真函数平均序列失真其中d(Xl，Yl)是编码前序列中的第l个符号和编码后序列中的第l个符号之间的失真。

1814.2信息率失真函数

信源编码器的目的是使编码后所需的信息传输率R尽量小，R

给定失真的限制值D，使

D，找最小R，

R(D)，定义为信息率失真函数。4.2.1信息率失真函数的定义：182p(yj/xi)信源符号编码概率信道转移概率

将信源编码器看作信道，信源编码器输出的信息率R对应到信道，即为接收端Y需要获得的有关X的信息量，也就是互信息I(X;Y)。183D允许试验信道

若p(xi)和d(xi，yj)已定，则可给出满足条件的所有转移概率分布pij，它们构成了一个信道集合PD。称为D允许试验信道。184信息率失真函数R(D)所有的允许试验信道PD（即满足

失真要求的所有假想信道）上，最低的输出信息速率（最有效的信源编码），就叫做信息率失真函数。离散无记忆信源：185例4-1：计算平均失真。已知编码器输入的概率分布为p(x)=[0.5,0.5]，两种信源编码器转移矩阵分别为：定义单符号失真度：186例4-1：计算平均失真。由此可得：由转移概率矩阵，可得：1874.2.2信息率失真函数的性质1.R(D)函数的定义域和值域

⑴Dmin和R(Dmin)

Dmin＝0

对于连续信源：

188讨论何时Dmin=0?只有当失真矩阵中每行至少有一个零元素。何时R(0)=H(X)?只有当失真矩阵中每行至少有一个零，并每一列最多只有一个零。否则R(0)可以小于H(X)，表示这时信源符号集中有些符号可以压缩、合并而不带来任何失真。189定理证明：190证明：1911.R(D)函数的定义域和值域

(2)

Dmax和R(Dmax)

选择所有满足R(D)＝0中D的最小值，定义为R(D)定义域的上限Dmax，即因此可以得到R(D)的定义域为192Dmax=?R(D)＝0就是I(X;Y)＝0，这时试验信道输入与输出是互相独立的，所以条件概率p(yj/xi)与xi无关。即需满足条件193

从上式观察可得：在j=1，…，m中，可找到

值最小的j，当该j对应的pj＝1，而其余pj为零时，上式右边达到最小，这时上式可简化成194例4-2：设输入输出符号表为X＝Y

{0，1}，输入概率分布p(x)={1/3，2/3}，失真矩阵为求Dmin和Dmax。195解：

当Dmin＝0时，R(Dmin)＝H(X)＝H(1/3,2/3)＝0.91比特/符号，这时信源编码器无失真，该编码器的转移概率为196当R(Dmax)＝0时

此时输出符号概率p(b1)＝0，p(b2)＝1，

所以这时的编码器的转移概率为

1972.R(D)函数的下凸性

当给定信源概率分布p(x)时，互信息量I(X;Y)是信道（假想信道）的转移概率p(y/x)的下凸函数，有极小值，该极小值即为信息率失真函数：3.R(D)函数的单调递减性

若D>D’,PD

PD’(选择pij的范围大)198综上所述，可以得出如下结论：R(D)是非负的实数，即R(D)

0。其定义域为0～Dmax，其值为0～H(X)。当D>Dmax时，R(D)

0。R(D)是关于D的下凸函数，因而也是关于D的连续函数。R(D)是关于D的严格递减函数。容许的D越大，所要求的R越小。反之亦然。199由以上三点结论，对一般信息率失真R(D)曲线的形态可以画出来：R(D)H(X)R(D)

0

D

Dmax

DR(D)0Dmax

D

离散信源连续信源2004.信息率失真函数与信道容量的比较

信息率失真函数R(D)信道容量C研究对象信源信道给定条件信源概率分布p(x)信道转移概率p(y|x)选择参数信源编码器编码方法p(y|x)信源分布p(x)限制条件结论H(X/Y)=H(X)-I(X;Y)噪声干扰丢失的信息量编码压缩损失的信息量比较项本章小结201第四章主要内容结构202本章小结本章学习思路失真信源编码必要性→失真测度函数→信源编码器数学模型→D允许试验信道→信息率失真函数→信息率失真函数性质203本章小结本章学习要点1.失真函数

均方失真、绝对失真、相对失真、误码失真2.平均失真度测量

(1)单符号平均失真：

(2)序列平均失真：204本章小结本章学习要点3.D允许试验信道4.信息率失真函数5.失真函数的性质

下凸性，单调递减性

205第5章信源编码目的：提高通信系统的有效性，即通过编码，用尽可能短的编码序列符号来表示原信源序列。基本思想是：1.尽可能去除原消息序列中符号之间的相关性；2.尽可能使编码后各符号出现的概率相等。206第5章信源编码主要解决两个方面的问题：1.“信源编码是用尽可能短的编码序列符号来表示原信源序列”，这个“短”，有没有极限？如果有，该极限是多少？2.用什么方法达到或者接近该极限？207非分组码和分组码将长消息序列按顺序分成若干个符号一组，对每一组独立进行编码，称为分组码；否则称为非分组码。定长码和变长码若编码后的码字长度都相同，则称为定长码；否则称为变长码。5.1信源编码的有关概念5.1.1几个概念208奇异码和非奇异码若编码前的信源组和编码后的码字是一一对应的，则称为非奇异码；否则称为奇异码。非唯一可译码和唯一可译码如果任意有限长的码元序列都只能被唯一地分割成一个个的码字，则称为唯一可译码；否则称为非唯一可译码。5.1信源编码的有关概念209非即时码和即时码在接收端接收码元序列的过程中，如果接收到的码元序列已经组成了一个码字，但接收端并不能立即判断出，还要等下一个码字开始接收的时候才能判断出前者已经是一个完整码字，从而开始译码，则称为非即时码；反之则称为即时码。5.1信源编码的有关概念2105.1信源编码的有关概念5-1编码的分类2115.1信源编码的有关概念信源符号ai符号出现的概率p(ai)码1码2码3码4码5a11/2000011a21/40111101001a31/8100000100001a41/811110110000001例5-1表5-1中的分组码1、码2、码3、码4和码5，从上述的4个方面分别判断属于什么类型的码。表5-1码的不同属性2125.1.2克劳福特不等式唯一可译码存在的充分和必要条件各码字的长度Ki应符合克劳夫特不等式：

其中m是进制，n是信源可能取值的符号数。213例：设对符号集{ai,i=1,2,3,4}进行二进制编码；(1)对应的码长分别为K1＝1,K2＝2,K3＝2,K4＝3，试判断是否存在这样的唯一可译码；(2)

若K1=1,

K2=2,

K3=3,

K4=3又如何？答：(1)由克劳福特定理可得：因此不存在满足这种码长的唯一可译码。

214(2)由克劳福特定理可得：因此满足这种码长的唯一可译码是存在的,例如{0，10，110，111}。

克劳夫特不等式只是用来说明唯一可译码是否存在，并不能作为唯一可译码的判据。例如，{0,10,010,111}215无失真信源编码定理定长信源编码定理变长信源编码定理限失真信源编码定理

5.2信源编码定理2165.2.1无失真信源编码（香农第一定理）X＝(X1X2…Xi…XL)Xi

{a1,a2,…,ai,…,an}

nL种信源编码器Yk

{b1,b2,…,bj,…,bm}

M=mKL种

KL

logm用Y表示L长的信源序列X，则送出一个信源符号所需要的信息率平均为

编码目的：使最小。

217无失真信源编码定理研究的内容:最小信息率为多少时，才能得到无失真的译码？若小于这个信息率是否还能无失真地译码?

无记忆平稳信源平均符号熵为HL(X)，对任意

，只要

则当L足够大时，必可使译码差错概率小于δ；即可实现几乎无失真编码；

反之，当时，译码差错一定是有限值，而L足够大时，译码几乎必定出错。2181.无失真定长信源编码定理：码字所能携带的信息量大于信源序列输出的信息量，则可以使传输几乎无失真，当然条件是L足够大。反之，当时，不可能构成无失真的编码，也就是不可能做一种编码器，能使收端译码时差错概率趋于零。当时，则为临界状态，可能无失真，也可能有失真。219说明：L,,

,δ三者之间有什么关系？对于给定的

和δ，多大的L算足够大？220问题：式中

为信源序列的自信息方差，

为一正数。当

和

2均为定值时，只要L足够大，Pe可以小于任一正数

。即，如果给定差错概率上界δ，则

越小，要求的编码长度L就越大。L越大，编码器越复杂，且时延越大，在有时延要求的场合，往往难以满足实时性要求。增加

，可以减小对编码长度L的要求，但以牺牲编码效率为代价：221讨论：222例题5-3：设离散无记忆信源概率空间为若要求编码效率为90%，译码差错概率δ≤10-6试求所需要的编码序列长度L。223例题5-3：自信息方差为：若要求编码效率η=90%：若要求编码效率δ≤10-6：当L有限时，要做到高编码效率、低错误率，对于定长编码来说是不可能做到的。对例5-3中的信源，有8种不同的信源符号取值（a1~a8），如果用二进制序列来表示的话，每个符号需要3

bit（3位二进制数可以表示8中不同的符号）。但由于不是等概率的，所以其熵H(X)=2.55

bit，按照无失真定长信源编码定理，其极限编码长度是2.55bit，而，也就是说，只能表示5.856种不同的符号，其余的符号怎么办？实际上，由于a1~a8中部分符号的概率较小，如果序列长度L足够大，则总有某种序列出现的概率足够小，对这些概率足够小的序列，如果不设计对应的编码码字，造成的错误概率也非常小。224思考：2252.无失真变长信源编码定理：平均码长：定长编码中，由于所有的码字都使用相同的长度，限制了其灵活性，导致或者效率不高，或者复杂度太高（L太大）。变长编码可以对出现概率大的信源尽量用短码，从而提高编码效率.（统计匹配）2262.无失真变长信源编码定理：(1).单符号变长编码定理若离散单符号信源X：xi∈{a1,a2,…,an}的熵为H(X)，对每个单符号进行无失真变长编码，设yj∈{b1,b2,…,bm}。则227(2).离散平稳无记忆序列变长编码定理

对于平均符号熵为HL(X)的离散平稳无记忆信源，必存在一种无失真编码方法，使平均信息率满足不等式其中

为任意小正数。228例题5-4：设离散无记忆信源概率空间为试讨论其编码效率。若L=1,用二元定长编码(0，1)来构造一个即时码：x1→0，x2→1。平均码长＝1二元码符号/信源符号

编码效率为输出的信息率为229（续）例题5-4：若对长度为L=2的信源序列进行变长编码，其即时码如表5-2所示。230（续）例题5-4：xip(xi)即时码x1x19/160x1x23/1610x2x13/16110x2x21/16111表5-2长度为2的信源序列对应的即时码该码平均长度：单符号平均码长：编码效率为：231（续）例题5-4：232（续）例题5-4：L＝3

η3=0.985

R3＝0.985比特/二元码符号

L＝4

η4=0.991

R4＝0.991比特/二元码符号

233（续）例题5-4：定长二元码编码，要求编码效率达到96％时，允许译码错误概率δ≤10-5

。2345.2.2限失真信源编码（香农第三定理）

信息率失真函数给出了失真小于D时所必须具有的最小信息率R(D)；只要信息率大于R(D)，一定可以找到一种编码，使译码后的失真小于D。

限失真信源编码定理：对于任意的D≥0和

＞0，当信息率R>R(D)时，一定存在一种编码方法，其译码失真小于或等于D+

，条件是编码的信源序列长度L足够长。反之，如果R<R(D)，则无论采用什么编码方法，其译码失真必大于D。2355.2.2限失真信源编码（香农第三定理）香农第三定理是一个存在性定理，它只说明一定存在一种满足要求的编码方法。至于如何寻找这种最佳压缩编码方法，定理中没有给出。在实际应用中，该理论主要存在以下两类问题：（1）符合实际信源的R(D)函数的计算相当困难；（2）即使求得了符合实际的信息率失真函数，还需要研究采用何种编码方法，才能达到或接近极限值R(D)。2365.2.2限失真信源编码（香农第三定理）237香农编码哈弗曼编码算术编码（非分组码）

5.3常用信源编码方法2385.3.1

香农编码将信源消息符号按其出现的概率大小依次排列确定满足下列不等式的整数码长Ki

5.3常用信源编码方法239香农编码为了编成唯一可译码，计算第i个消息的累加概率将累加概率Pi变换成二进制数。取Pi二进数的小数点后Ki位即为该消息符号的二进制码字。

5.3常用信源编码方法240香农编码为了编成唯一可译码，计算第i个消息的累加概率将累加概率Pi变换成二进制数。取Pi二进数的小数点后Ki位即为该消息符号的二进制码字。

241香农编码

香农编码的基本做法：是把长度为1的整个累积概率区间，按照信源符号集中q个信源符号的概率大小，分成q份不同长度的子区间（每份子区间的长度正比于对应符号的概率大小），将每种信源符号xi，映射到其对应子区间上的一个点。这样，每个信源符号xi映射区间都是不重叠的，从而可以保证唯一可译码，而且可以证明，也是即时码；另一方面，码字长度由其概率决定，概率大的用短码。

242香农编码

例5.4设信源共7个符号消息

信源消息符号ai符号概率p(ai)累加概率Pi-logp(ai)码字长度Ki码字a10.200