离散信道容量.ppt

离散信道容量1现在学习的是第1页，共82页4.1 互信息和平均互信息互信息和平均互信息4.1.1单符号离散信道的数学模型单符号离散信道的数学模型信源信源X信宿信宿Y有扰信道有扰信道C C干扰源干扰源N N离散信源X的数学模型为2现在学习的是第2页，共82页4.1 互信息和平均互信息互信息和平均互信息4.1.1单符号离散信道的数学模型单符号离散信道的数学模型信宿Y的数学模型为 3现在学习的是第3页，共82页4.1 互信息和平均互信息互信息和平均互信息4.1.1单符号离散信道的数学模型单符号离散信道的数学模型信道模型的表示方法信道模型的表示方法公式法公式法图示法图示法矩阵法矩阵法4现在学习的是第4页，共82页4.1 互信息和平均互信息互信息和平均互信息4.1.2 互信息量及其性质互信息量及其性质根据前面的信道的数学模型：根据前面的信道的数学模型：l如果信道是理想的，发出如果信道是理想的，发出ai收到收到ai则所获得的信息量则所获得的信息量 ai的不确定度的不确定度I(ai)；l如果信道不理想，发出如果信道不理想，发出ai收到收到bj,由由bj推测推测ai的概率，的概率，一一、定义、定义1：我们将从bj中获取有关ai的信息量称为互信互信息量息量5现在学习的是第5页，共82页4.1.2 互信息量及其性质互信息量及其性质一、互信息量的一、互信息量的定义定义 继续讨论第二章的例题，即某地二月份天气构成的信源为“今天不是晴天”作为收到的信息b1，计算b1与各天气之间的互信息量。6现在学习的是第6页，共82页4.1.2 互信息量及其性质互信息量及其性质一、互信息量的一、互信息量的定义定义2将互信息表达式展开得：将互信息表达式展开得：同样道理，我们可以定义同样道理，我们可以定义a ai i对对b bj j 的互信息量为的互信息量为7现在学习的是第7页，共82页通信前先验不定度（联合自信息量）发送发送接收接收4.1.2 互信息量及其性质互信息量及其性质一、互信息量的一、互信息量的定义定义38现在学习的是第8页，共82页后验不定度 一、互信息量的定义一、互信息量的定义3发送发送接收接收4.1.2 互信息量及其性质互信息量及其性质通信后9现在学习的是第9页，共82页 这样，通信后流经信道的信息量，等于通信前后不定度的差4.1.2 互信息量及其性质互信息量及其性质一、互信息量的定义一、互信息量的定义310现在学习的是第10页，共82页4.1.2 互信息量及其性质互信息量及其性质二、互信息量的性质二、互信息量的性质对称性 当X和Y相互独立时，互信息为0 1211现在学习的是第11页，共82页4.1.2 互信息量及其性质互信息量及其性质二、互信息量的性质二、互信息量的性质互信息量可为正值或负值互信息量可为正值或负值 3互信息量为正，互信息量为正，b bj j使使a ai i的不确定度减小，的不确定度减小，上例中，上例中，“今天不是晴天今天不是晴天”为为0，二者相互独立，二者相互独立，“今天我很高兴今天我很高兴”为负，为负，b bj j没有使没有使a ai i的不确定度减小，的不确定度减小，“今天有风今天有风”。12现在学习的是第12页，共82页4.1.3 平均互信息量及其性质平均互信息量及其性质一、信道疑义度一、信道疑义度研究信源中各个消息之间的关系研究信源中各个消息之间的关系13现在学习的是第13页，共82页4.1.2 互信息量及其性质互信息量及其性质一、信道疑义度一、信道疑义度损失熵损失熵信道疑义度信道疑义度：含义含义：收到：收到Y后关于后关于X尚存的平均不确定性。尚存的平均不确定性。性质性质：equivocation14现在学习的是第14页，共82页4.1.2 互信息量及其性质互信息量及其性质二、平均互信息量的定义二、平均互信息量的定义平均互信息平均互信息互信息量在联合概率空间P(XY)统计平均。平均交互信息量；交互熵15现在学习的是第15页，共82页4.1.2 互信息量及其性质互信息量及其性质二、平均互信息量的定义二、平均互信息量的定义计算时可用公式：计算时可用公式：16现在学习的是第16页，共82页4.1.2 互信息量及其性质互信息量及其性质二、平均互信息量的定义二、平均互信息量的定义平均交互信息量与几个测度函数辨析l和l和相同点：统计平均相同点：统计平均不同点：提供与获得不同点：提供与获得17现在学习的是第17页，共82页4.1.2 互信息量及其性质互信息量及其性质三、条件互信息和平均条件互信息三、条件互信息和平均条件互信息给定X、Y、Z三个离散概论空间，其连接关系为：系统1系统2系统1XXYYZZ(a)(b)18现在学习的是第18页，共82页4.1.2 互信息量及其性质互信息量及其性质练习：练习：有两个硬币，一个正常硬币（一面是国徽，一面是面值），另一个是不正常的硬币（两面都是面值）。现随机抽取一次硬币，抛掷两次。问出现面值的次数对于硬币的识别能提供多少信息量？19现在学习的是第19页，共82页4.1.2 互信息量及其性质互信息量及其性质四、平均互信息量的性质四、平均互信息量的性质非负性非负性说明：信道每传递一条消息，总能提供一定的信息量。l注：可正可负10,正常通信=0,通信中断=0,=0,如何证明？如何证明？2、C=logn n为输入的符号数为输入的符号数 3、C=logm m为输出的符号数为输出的符号数 45现在学习的是第45页，共82页4.2.3几种特殊离散信道的容量几种特殊离散信道的容量一、离散无噪信道一、离散无噪信道1、一一对应的无噪信道、一一对应的无噪信道anbna1b1a2b246现在学习的是第46页，共82页a1b1a2b2an-1bn-1anbnX、Y一一对应一一对应,此时此时H(X/Y)=0，H(Y/X)=0，lCmaxI(X;Y)log n (p(ai)=1/n即等概即等概)p(ai)一一对应的无噪信道一一对应的无噪信道47现在学习的是第47页，共82页a1 b1b2b32、具有扩展功能的无噪信道具有扩展功能的无噪信道a2b4b5b6a3b7b848现在学习的是第48页，共82页此时，此时，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现在学习的是第49页，共82页3、具有归并性的无噪信道、具有归并性的无噪信道a1b1a2a3b2a4a5b3C=max H(Y)=log m p(ai)=？p(ai)H(X/Y)0，H(Y/X)=0多个输入变成一个输出多个输入变成一个输出50现在学习的是第50页，共82页结论l无噪信道的信道容量只取决于信道的输入符号无噪信道的信道容量只取决于信道的输入符号数数n或输出符号数或输出符号数m，与信源无关。，与信源无关。51现在学习的是第51页，共82页4.2.3 几种特殊离散信道的信道容量几种特殊离散信道的信道容量二、对称信道容量计算二、对称信道容量计算1、对称信道的定义、对称信道的定义：如果信道转移矩阵满足下列性质：如果信道转移矩阵满足下列性质：(1)每行都是第一行的某种置换每行都是第一行的某种置换;(2)每列都是第一列的某种置换。每列都是第一列的某种置换。则称该信道为对称信道。则称该信道为对称信道。显然，对称信道是输入对称的，显然，对称信道是输入对称的，也是关于输出对称的。也是关于输出对称的。52现在学习的是第52页，共82页练习：判断下列矩阵表示的信道是否是对称信道练习：判断下列矩阵表示的信道是否是对称信道53现在学习的是第53页，共82页二、对称信道容量的计算二、对称信道容量的计算l强对称信道（均匀）强对称信道（均匀）：nXnp：总体错误概率54现在学习的是第54页，共82页二、对称信道容量的计算二、对称信道容量的计算2、对称信道的性质、对称信道的性质：对称信道满足下列性质：对称信道满足下列性质：（1）即噪声熵即噪声熵=矩阵第一行元素组成的熵函数矩阵第一行元素组成的熵函数 （2）当）当P(X)（输入）等概分布，输出也是等概分布（输入）等概分布，输出也是等概分布注：这两个性质对后面求信道容量非常重要！注：这两个性质对后面求信道容量非常重要！55现在学习的是第55页，共82页二、对称信道容量的计算二、对称信道容量的计算3、对称信道的信道容量：、对称信道的信道容量：由于对称信道满足：由于对称信道满足：综合起来可以得出对称信道的信道容量为综合起来可以得出对称信道的信道容量为对称信道关于输出也是对称的，当信道输入是等概率分布时，信对称信道关于输出也是对称的，当信道输入是等概率分布时，信道输出也是等概率分布，道输出也是等概率分布，H(Y)取得最大值取得最大值56现在学习的是第56页，共82页典型例子典型例子均匀信道信道容量计算均匀信道信道容量计算解解 显然该信道是对称的，信显然该信道是对称的，信道容量为道容量为上述信道称为强对称信道或者均匀信道，是对称信道的一个上述信道称为强对称信道或者均匀信道，是对称信道的一个特例特例。一般信道转移矩阵中，列元素之和并不等于一般信道转移矩阵中，列元素之和并不等于1，而该信，而该信道转移矩阵的各列元素之和都等于道转移矩阵的各列元素之和都等于1。其中，其中，p为总的错误传输概为总的错误传输概率。率。特别地，当特别地，当r=2时，信道容量为时，信道容量为C=1H(p)57现在学习的是第57页，共82页几种对称信道之间的关系几种对称信道之间的关系输入对称输入对称对称信道对称信道均匀信道均匀信道二元二元均匀均匀58现在学习的是第58页，共82页二、对称信道容量的计算二、对称信道容量的计算4、准对称信道的信道容量：、准对称信道的信道容量：二元对称纯删除信道二元对称纯删除信道该信道转移矩阵为该信道转移矩阵为 ，该信道即二元纯对称，该信道即二元纯对称删除信道，如图所示，删除信道，如图所示，其信道容量为其信道容量为比特比特/符号符号59现在学习的是第59页，共82页二、对称信道容量的计算二、对称信道容量的计算如果信道转移矩阵按列可以划分为几个互不相交的对称信道的如果信道转移矩阵按列可以划分为几个互不相交的对称信道的子集，则称该信道为准对称信道。子集，则称该信道为准对称信道。显然，准对称信道是输入对称的。显然，准对称信道是输入对称的。4、准对称信道的信道容量：、准对称信道的信道容量：准对称信道可以分解为若干个对称信道之和，所以对于准准对称信道可以分解为若干个对称信道之和，所以对于准对称信道，信道输入的最佳分布是等概率分布，而信道容量为对称信道，信道输入的最佳分布是等概率分布，而信道容量为其中，其中，q1，q2，qm为准对称信道转移矩阵中的一行元素，为准对称信道转移矩阵中的一行元素，s为为划分的子集数量，划分的子集数量，Nk为第为第k个子矩阵的行元素之和，个子矩阵的行元素之和，Mk为第为第k个子个子矩阵的列元素之和。矩阵的列元素之和。60现在学习的是第60页，共82页例题例题信道转移矩阵为信道转移矩阵为求信道容量求信道容量C。解解 通过观测可知，该信道是准对称信道，可以分解为三个互不通过观测可知，该信道是准对称信道，可以分解为三个互不相交的子集，分别为相交的子集，分别为61现在学习的是第61页，共82页例题例题对应的参数分别为对应的参数分别为所以信道容量为所以信道容量为比特/符号 62现在学习的是第62页，共82页练习题：有噪声的打字机信道练习题：有噪声的打字机信道考虑有考虑有26个键的打字机个键的打字机1）如果每敲击一个键，它就准确输出成相应的字符，那么该容量）如果每敲击一个键，它就准确输出成相应的字符，那么该容量C为多少？为多少？2）如果假设敲击一个键都会导致输出该键对应的字母或者）如果假设敲击一个键都会导致输出该键对应的字母或者下一个字母等概论出现，即敲下一个字母等概论出现，即敲A可能输出可能输出A或者或者B，敲敲Z Z可能可能输出输出Z Z或者或者A A，那么此时的容量如何？，那么此时的容量如何？63现在学习的是第63页，共82页复习数学知识复习数学知识64现在学习的是第64页，共82页4.2.3离散信道容量的一般计算法信道容量的求解为一个信道容量的求解为一个多元函数求约束极值多元函数求约束极值的问题。的问题。信道转移矩阵为信道转移矩阵为例：求信道输入最佳分布和信道容量例：求信道输入最佳分布和信道容量C。解解 观察信道转移矩阵可知，该信道不是对称的，信道的输观察信道转移矩阵可知，该信道不是对称的，信道的输入、入、输出符号数量都为输出符号数量都为2，假设信道输入符号的概率分别为，假设信道输入符号的概率分别为p，1p，可以得到平均互信息量。，可以得到平均互信息量。根据假设的信道输入的概率分布，求出信道输出概率分布根据假设的信道输入的概率分布，求出信道输出概率分布p(bj)：p(b1)=0.9p+0.2(1p)=0.2+0.7p p(b2)=0.1p+0.8(1p)=0.80.7p65现在学习的是第65页，共82页4.2.3离散信道容量的一般计算法输入、输入、输出之间的平均互信息量为：输出之间的平均互信息量为：将相关参数代入上述计算公式，得到：将相关参数代入上述计算公式，得到：66现在学习的是第66页，共82页4.2.3离散信道容量的一般计算法对对I(X;Y)求导，得到最佳分布求导，得到最佳分布得到，得到，p=0.532，所以信道容量为，所以信道容量为C=maxI(X;Y)=0.415 比特比特/符号符号从该例可以看出，即使是简单的非对称二元信道，其最佳分布的求从该例可以看出，即使是简单的非对称二元信道，其最佳分布的求解也十分复杂，所以一般离散信道的信道容量的求解通过计算机进解也十分复杂，所以一般离散信道的信道容量的求解通过计算机进行。行。下面讨论一般离散信道的解法。下面讨论一般离散信道的解法。67现在学习的是第67页，共82页4.2.3离散信道容量的一般计算法平均互信息量平均互信息量I(X;Y)是输入概率分布是输入概率分布p(ai)的凸函数，所以极的凸函数，所以极大值是一定存在的。大值是一定存在的。假设信道输入的符号数量为假设信道输入的符号数量为n，那么，那么I(X;Y)应应当是当是r个随机变量个随机变量(p1，p2，pn)的函数，而且满足约束条件的函数，而且满足约束条件，该多元函数的条件极值可以利用拉格朗日乘法求出。，该多元函数的条件极值可以利用拉格朗日乘法求出。(1)首先引入函数首先引入函数其中，其中，为拉格朗日乘子。为拉格朗日乘子。68现在学习的是第68页，共82页4.2.3离散信道容量的一般计算法(2)对信道输入概率对信道输入概率p(ai)求导数，并令其为求导数，并令其为0。解方程组可以求出最佳概率分布解方程组可以求出最佳概率分布和和。(3)将最佳分布代入将最佳分布代入I(X;Y)，即可求出信道容量，即可求出信道容量C。而而p(bj)可以表示为可以表示为69现在学习的是第69页，共82页4.2.3离散信道容量的一般计算法故关键是求第一项故关键是求第一项我们将这项展开看看哪部分和求偏导有关我们将这项展开看看哪部分和求偏导有关70现在学习的是第70页，共82页4.2.3离散信道容量的一般计算法71现在学习的是第71页，共82页4.2.3离散信道容量的一般计算法第二块分步求第二块分步求（1）将）将 看作常数，对前面的求偏导看作常数，对前面的求偏导（2）将）将 看作常数，对看作常数，对 求偏导求偏导 72现在学习的是第72页，共82页4.2.3离散信道容量的一般计算法带入合并得：带入合并得：给定给定 后验概率为后验概率为1故故73现在学习的是第73页，共82页4.2.3离散信道容量的一般计算法结论结论74现在学习的是第74页，共82页4.2.3离散信道容量的一般计算法假设信道输入的最佳分布为假设信道输入的最佳分布为(p1，p2，pn)，将方程，将方程组的两边同时乘以各自的概率组的两边同时乘以各自的概率p(ai)，并且两边同时对，并且两边同时对i求和，从而得到信道容量为求和，从而得到信道容量为C=+loge仍然为待定的系数，但我们找到一些仍然为待定的系数，但我们找到一些规律规律将将 来分析来分析其中其中75现在学习的是第75页，共82页4.2.3离散信道容量的一般计算法加上前面一个加权加上前面一个加权规律：规律：信源处于最佳分布时，由输出端观察，每一个信源处于最佳分布时，由输出端观察，每一个符号的信息量都是一样的。符号的信息量都是一样的。76现在学习的是第76页，共82页4.2.3离散信道容量的一般计算法定理定理 设有一般离散信道，它有设有一般离散信道，它有n个输入符号，个输入符号，m个个输出符号，其平均互信息输出符号，其平均互信息I(X;Y)达到极大值达到极大值(即等于信道容即等于信道容量量)的充要条件是输入概率分布的充要条件是输入概率分布p(ai)满足满足(其中其中i=1，2，n)对所有p(ai)0的ai 对所有p(ai)=0的ai常数常数C就是所求的信道容量。就是所求的信道容量。77现在学习的是第77页，共82页4.2.3离散信道容量的一般计算法求该信道的容量求该信道的容量C和信道输入的最佳概率分布。和信道输入的最佳概率分布。解解 该信道不是对称信道，所以不能直接使用对称信道计算其信道容该信道不是对称信道，所以不能直接使用对称信道计算其信道容量。量。但是通过观察发现，如果信道输入符号的概率但是通过观察发现，如果信道输入符号的概率p(a2)=0，该信道就，该信道就是一个二元纯对称删除信道。是一个二元纯对称删除信道。这样就这样就可以假设可以假设p(a2)=0，p(a1)=p(a3)=1/2，然后检查是否满足上述定理，然后检查是否满足上述定理条件，如果满足就可以计算出信道容量。条件，如果满足就可以计算出信道容量。例例78现在学习的是第78页，共82页4.2.3离散信道容量的一般计算法首先根据假设求出相应的首先根据假设求出相应的p(bj)然后计算互信息量然后计算互信息量I(ai;Y)比特/符号比特/符号比特/符号79现在学习的是第79页，共82页4.2.3离散信道容量的一般计算法显然该输入概率分布满足定理的条件，所以信道容量为显然该输入概率分布满足定理的条件，所以信道容量为C=0.9，对应的信道输入最佳概率分布为对应的信道输入最佳概率分布为(0.5，0，0.5)。定理给出了达到信道容量定理给出了达到信道容量C时，输入符号概率分布所要满足时，输入符号概率分布所要满足的充要条件，并未给出具体值。一般情况下，最佳分布不是唯一的，的充要条件，并未给出具体值。一般情况下，最佳分布不是唯一的，只需满足定理，并试交互熵最大即可。只需满足定理，并试交互熵最大即可。80现在学习的是第80页，共82页4.3多符号离散信道的信道容量4.3.1多符号离散信道容量的数学模型 多符号信源通过离散信道传输形成多符号离散信道。81现在学习的是第81页，共82页1YNY4.3.2 离散无记忆信道的N次扩展信道82现在学习的是第82页，共82页