第四章 离散信道容量.ppt

1、第四章 离散信道容量,1,4.1 互信息和平均互信息,4.1.1单符号离散信道的数学模型,离散信源X的数学模型为,2,4.1 互信息和平均互信息,4.1.1单符号离散信道的数学模型,信宿Y的数学模型为,3,4.1 互信息和平均互信息,4.1.1单符号离散信道的数学模型,信道模型的表示方法,公式法,图示法,矩阵法,4,4.1 互信息和平均互信息,4.1.2 互信息量及其性质,根据前面的信道的数学模型： 如果信道是理想的，发出ai收到ai则所获得的信息量 ai的不确定度I(ai)； 如果信道不理想，发出ai收到bj,由bj推测ai的概率，,一、定义1：我们将从bj中获取有关ai的信息量称为互信息量

2、,5,4.1.2 互信息量及其性质,一、互信息量的定义,继续讨论第二章的例题，即某地二月份天气构成的信源为,“今天不是晴天”作为收到的信息b1，计算b1 与各天气之间的互信息量。,6,4.1.2 互信息量及其性质,一、互信息量的定义2 将互信息表达式展开得：,同样道理，我们可以定义ai对bj 的互信息量为,7,通信前,先验不定度（联合自信息量）,4.1.2 互信息量及其性质,一、互信息量的定义3,8,后验不定度,一、互信息量的定义3,4.1.2 互信息量及其性质,通信后,9,这样，通信后流经信道的信息量，等于通信前后不定度的差,4.1.2 互信息量及其性质,一、互信息量的定义3,10,4.1.

3、2 互信息量及其性质,二、互信息量的性质,对称性,当X和Y相互独立时，互信息为0,1,2,11,4.1.2 互信息量及其性质,二、互信息量的性质,互信息量可为正值或负值,3,互信息量为正， bj使ai的不确定度减小， 上例中，“今天不是晴天”,为0，二者相互独立，“今天我很高兴”,为负， bj没有使ai的不确定度减小， “今天有风”。,12,4.1.3 平均互信息量及其性质,一、信道疑义度,研究信源中各个消息之间的关系,13,4.1.2 互信息量及其性质,一、信道疑义度,损失熵,信道疑义度：,含义：收到Y后关于X尚存的平均不确定性。,性质：,equivocation,14,4.1.2 互信息量

4、及其性质,二、平均互信息量的定义,平均互信息,平均交互信息量；交互熵,15,4.1.2 互信息量及其性质,二、平均互信息量的定义 计算时可用公式：,16,4.1.2 互信息量及其性质,二、平均互信息量的定义,平均交互信息量与几个测度函数辨析 和 和,相同点：统计平均,不同点：提供与获得,17,4.1.2 互信息量及其性质,三、条件互信息和平均条件互信息,给定X、Y、Z三个离散概论空间，其连接关系为：,系统1,系统2,系统1,X,X,Y,Y,Z,Z,(a),(b),18,4.1.2 互信息量及其性质,练习：,有两个硬币，一个正常硬币（一面是国徽，一面是面值），另一个是不正常的硬币（两面都是面值）

5、。现随机抽取一次硬币，抛掷两次。问出现面值的次数对于硬币的 识别能提供多少信息量？,19,4.1.2 互信息量及其性质,四、平均互信息量的性质,非负性,说明：信道每传递一条消息，总能提供一定的信息量。 注： 可正可负,1,0,正常通信,=0,通信中断,0,通信受干扰,20,极值性,1,2,四、平均互信息量的性质,4.1.2 互信息量及其性质,21,2,极值性,2,四、平均互信息量的性质,4.1.2 互信息量及其性质,22,4.1.2 互信息量及其性质,四、平均互信息量的性质,对称性,3,说明：从X中提取关于Y的信息量与由Y中提取到X的信息量是相同的，是信息流通的总体测度。,23,4.1.2 互

6、信息量及其性质,四、平均互信息量的性质,24,4.1.2 互信息量及其性质,四、平均互信息量的性质,凸函数性,4,1,2,25,4.1.2 互信息量及其性质,凸函数性,4,定理1 对于固定的信道，平均互信息I(X;Y)是信源概率分布p(x)的上凸函数,这就是说，对于一定的信道转移概率分布p(y|x)，总可以找到某一个先验概率分布的信源X，使平均交互信息量I(X;Y)达到相应的最大值Imax，这时称这个信源为该信道的匹配信源。可以说，不同的信道转移概率对应不同的Imax。,26,4.1.2 互信息量及其性质,凸函数性,4,定理2 对于固定的信源，平均互信息I(X;Y)信道传递概率分布p(y|x)

7、的下凸函数,这就是说，对于一个已知先验概率为p的离散信源，总可以找到某一个转移概率分布的信道q，使平均互信息量达到相应的最小值Imin。,27,4.1.2 互信息量及其性质,凸函数性例题,4,例：对于二元对称信道,如果信源分布X=p,1-p，则,28,4.1.2 互信息量及其性质,凸函数性,4,而：,所以：,当信道固定时，q为一个固定常数，平均互信息是信源分布的上凸函数，最大只为1-H(q)。图示曲线表明，对于固定信道，输入符号X的概率分布不同时，在接收端平均每个符号所获得的信息量就不同。当输入符号为等概率分布时，平均互信息量为最大值，接收每个符号所获得的信息量最大。信道容量的理论基础,29,

8、4.1.2 互信息量及其性质,凸函数性,4,当信源固定后，p为一个固定常数，改变信道特性q可获得不同的平均互信息I(X;Y)。当q=1/2时，I(X;Y)=0,即在信道输出端获得的信息最小，这意味着信源的信息全部损失在信道中，这是一种最差的信道，其噪声最大。信息率失真理论的基础。,30,多次处理信息量将减少。,数据处理定理,5,4.1.2 互信息量及其性质,四、平均互信息量的性质,31,总结：各种熵之间的关系,H(X) ,H(Y) 信源熵，无条件熵 H(X/Y) 疑义度，损失熵 H(Y/X) 噪声熵 H(XY)联合熵 I(X;Y)平均互信息量，交互熵,32,总结,33,4.2 信道容量,信道的

9、主要任务：以信号的形式传输和存储信息。 问题：在什么条件下，通过信道的信息量最大，即信道容量的问题。,34,4.2 信道容量,4.2.1 信道容量的模型和分类,1、信道的数学模型：,X P(Y/X) Y,输入与输出之间一般不是确定的函数关系， 而是统计依赖的。,35,4.2.1 信道容量的模型和分类,2.信道的分类,根据统计特性可以将信道分为恒参信道和随参信道。 (1) 恒参信道： 信道的统计特性不随时间而变化。 如卫星信道一般被视为恒参信道。 (2) 随参信道： 信道的统计特性随时间而变化。 大多数的信道都是随参信道，统计特性随着环境、 温度、 湿度等参数而变化。 如短波信道、 微波信道等。

10、,36,4.2.1 信道容量的模型和分类,2.信道的分类,根据信道用户量多少可以将其分为单用户信道和多用户信道。 (1) 单用户信道： 也称两端信道，该信道只有一个输入端和一个输出端，而且只能进行单方向的通信。 (2) 多用户信道： 也称多端信道，输入端或者输出端至少有一端具有两个或者两个以上用户，并且可以实现双向通信。 目前大多数信道都是多端信道。,37,4.2.1 信道容量的模型和分类,2.信道的分类,根据输入、 输出的取值特性可以将信道划分为离散信道、 连续信道、 半离散半连续信道和波形信道。 (1) 离散信道： 也称为数字信道，该类信道中输入空间、 输出空间均为离散事件集合，集合中事件

11、的数量是有限的，或者有限可数的，随机变量取值都是离散的。,(2) 连续信道： 也称为模拟信道，输入空间、 输出空间均为连续事件集合，集合中事件的数量是无限的、 不可数的，即随机变量的取值数量是无限的，或者不可数的。,38,4.2.1 信道容量的模型和分类,2.信道的分类,(3) 半离散半连续信道： 输入空间、 输出空间一个为离散事件集合，而另一个则为连续事件集合，即输入、 输出随机变量一个是离散的，另一个是连续的。,(4) 波形信道： 也称为时间连续信道，信道输入、 输出都是时间的函数，而且随机变量的取值都取自连续集合，且在时间上的取值是连续的。,39,4.2.2 信道容量的定义,1.复习平均

12、信息量,信源熵为H(X)，由于干扰的存在，一般只接收到I(X;Y)。 定义:平均每个符号能传送的消息总量为信道的信息传输速率（信息率），R R=I(X;Y) 若平均传送一个符号为t秒，则信道每秒钟平均传送的信息量,40,2.信道容量的定义,I(X;Y)是p(ai)的上凸函数，总能找到一个p(ai)使得信息率最大。 信道容量：信道中最大的传输速率，C， 单位：比特/信道符号 单位时间的信道容量，比特/秒,4.2.2 信道容量的定义,41,信道容量,42,4.2.2 信道容量的定义,例1：求二元对称信道的信道容量,当信道固定时，q为一个固定常数，平均互信息是信源分布的上凸函数，最大只为1-H(q)

13、。当输入符号为等概率分布时，平均互信息量为最大值，接收每个符号所获得的信息量最大。信道容量的理论基础,43,4.2.2 信道容量的定义,例2：计算下列信道容量及最佳输入分布,b1,b2,a1,a2,a3,a4,a5,1,1,1,1,1,a1,a2,a3,b1,b2,b3,b4,b5,b6,无噪有损信道,无损有噪信道,（A）,（B）,44,4.2.2 信道容量的定义,信道容量的性质： 1、C=0,如何证明？ 2、C=logn n为输入的符号数 3、C=logm m为输出的符号数,45,4.2.3几种特殊离散信道的容量,一、离散无噪信道 1、一一对应的无噪信道,46,X、Y一一对应,此时H(X/Y

14、)=0，H(Y/X)=0， CmaxI(X;Y)log n (p(ai)=1/n即等概),p(ai),一一对应的无噪信道,47,2、具有扩展功能的无噪信道,48,此时，H(X/Y)=0，H(Y/X) 0， 且 H(X) H(Y)。 所以，C = max H(X) = log n (p(ai)=1/n即等概),p(ai),一个输入对应多个输出,2、具有扩展功能的无噪信道,49,3、具有归并性的无噪信道,H(X/Y) 0，H(Y/X) = 0,多个输入变成一个输出,50,结论,无噪信道的信道容量只取决于信道的输入符号数n或输出符号数m，与信源无关。,51,4.2.3 几种特殊离散信道的信道容量,二

15、、对称信道容量计算 1、对称信道的定义：,如果信道转移矩阵满足下列性质： (1) 每行都是第一行的某种置换;(2) 每列都是第一列的某种置换。 则称该信道为对称信道。 显然，对称信道是输入对称的，也是关于输出对称的。,52,练习：判断下列矩阵表示的信道是否是对称信道,53,二、对称信道容量的计算,强对称信道（均匀）：,n X n,p：总体错误概率,54,二、对称信道容量的计算,2、对称信道的性质：,对称信道满足下列性质： （1）即噪声熵=矩阵第一行元素组成的熵函数 （2）当P(X)（输入）等概分布，输出也是等概分布注：这两个性质对后面求信道容量非常重要！,55,二、对称信道容量的计算,3、对称

16、信道的信道容量：,由于对称信道满足：,综合起来可以得出对称信道的信道容量为,对称信道关于输出也是对称的，当信道输入是等概率分布时，信道输出也是等概率分布，H(Y)取得最大值,56,典型例子均匀信道信道容量计算,解 显然该信道是对称的，信道容量为,上述信道称为强对称信道或者均匀信道，是对称信道的一个特例。 一般信道转移矩阵中，列元素之和并不等于1，而该信道转移矩阵的各列元素之和都等于1。 其中，p为总的错误传输概率。 特别地，当r=2时，信道容量为 C=1H(p),57,几种对称信道之间的关系,58,二、对称信道容量的计算,4、准对称信道的信道容量：,二元对称纯删除信道,该信道转移矩阵为 ，该信

17、道即二元纯对称删除信道，如图所示， 其信道容量为,比特/符号,59,二、对称信道容量的计算,如果信道转移矩阵按列可以划分为几个互不相交的对称信道的子集，则称该信道为准对称信道。 显然，准对称信道是输入对称的。,4、准对称信道的信道容量：,准对称信道可以分解为若干个对称信道之和，所以对于准对称信道，信道输入的最佳分布是等概率分布，而信道容量为,其中，q1，q2，qm为准对称信道转移矩阵中的一行元素，s为划分的子集数量，Nk为第k个子矩阵的行元素之和，Mk为第k个子矩阵的列元素之和。,60,例题,信道转移矩阵为,求信道容量C。 解 通过观测可知，该信道是准对称信道，可以分解为三个互不相交的子集，分

18、别为,61,例题,对应的参数分别为,所以信道容量为,比特/符号,62,练习题：有噪声的打字机信道,考虑有26个键的打字机 1）如果每敲击一个键，它就准确输出成相应的字符，那么该容量C为多少？ 2）如果假设敲击一个键都会导致输出该键对应的字母或者下一个字母等概论出现，即敲A可能输出A或者B，敲Z可能输出Z或者A，那么此时的容量如何？,63,复习数学知识,64,4.2.3离散信道容量的一般计算法,信道容量的求解为一个多元函数求约束极值的问题。,信道转移矩阵为,例：求信道输入最佳分布和信道容量C。 解 观察信道转移矩阵可知，该信道不是对称的，信道的输入、 输出符号数量都为2，假设信道输入符号的概率分

19、别为p，1p，可以得到平均互信息量。 根据假设的信道输入的概率分布，求出信道输出概率分布p(bj)： p(b1)=0.9p+0.2(1p)=0.2 + 0.7p p(b2)=0.1p+0.8(1p)=0.80.7p,65,4.2.3离散信道容量的一般计算法,输入、 输出之间的平均互信息量为：,将相关参数代入上述计算公式，得到：,66,4.2.3离散信道容量的一般计算法,对I(X;Y)求导，得到最佳分布,得到，p=0.532，所以信道容量为 C=maxI(X;Y)=0.415 比特/符号 从该例可以看出，即使是简单的非对称二元信道，其最佳分布的求解也十分复杂，所以一般离散信道的信道容量的求解通过

20、计算机进行。 下面讨论一般离散信道的解法。,67,4.2.3离散信道容量的一般计算法,平均互信息量I(X;Y)是输入概率分布p(ai)的凸函数，所以极大值是一定存在的。 假设信道输入的符号数量为n，那么I(X;Y)应当是r个随机变量(p1，p2，pn) 的函数，而且满足约束条件，该多元函数的条件极值可以利用拉格朗日乘法求出。 (1) 首先引入函数,其中，为拉格朗日乘子。,68,4.2.3离散信道容量的一般计算法,(2) 对信道输入概率p(ai)求导数，并令其为0。,解方程组可以求出最佳概率分布,和。,(3) 将最佳分布代入I(X;Y)，即可求出信道容量C。,而p(bj)可以表示为,69,4.2

21、.3离散信道容量的一般计算法,故关键是求第一项,我们将这项展开看看哪部分和求偏导有关,70,4.2.3离散信道容量的一般计算法,71,4.2.3离散信道容量的一般计算法,第二块分步求 （1）将 看作常数，对前面的求偏导 （2）将 看作常数，对 求偏导,72,4.2.3离散信道容量的一般计算法,带入合并得：,给定 后验概率为1,故,73,4.2.3离散信道容量的一般计算法,结论,74,4.2.3离散信道容量的一般计算法,假设信道输入的最佳分布为(p1，p2，pn)，将方程组的两边同时乘以各自的概率p(ai)，并且两边同时对i求和，从而得到信道容量为C=+loge 仍然为待定的系数，但我们找到一些规律,将 来分析,其中,75,4.2.3离散信道容量的一般计算法,加上前面一个加权,规律：信源处于最佳分布时，由输出端观察，每一个符号的信息量都是一样的。,76,4.2.3离散信道容量的一般计算法,定理 设有一般离散信道，它有n个输入符号，m个输出符号，其平均互信息I(X;Y)达到极大值(即等于信道容量)的充要条件是输入概率分布p(ai)满足(其中i=1，2，n),对所有p(ai)0的ai 对所有p(ai)=0的ai,常数C就是所求的信道容量。,77,4.2