离散信道容量PPT课件

1、4.1 互信息和平均互信息互信息和平均互信息4.1.1单符号离散信道的数学模型单符号离散信道的数学模型信宿Y的数学模型为 mjjjbpbp11)(, 1)(0 )b(,),(,),(),(b , ,b , ,b ,)( 2121mjmjpbpbpbpbYPY1第1页/共81页4.1 互信息和平均互信息互信息和平均互信息4.1.1单符号离散信道的数学模型单符号离散信道的数学模型信道模型的表示方法信道模型的表示方法公式法公式法图示法图示法矩阵法矩阵法2第2页/共81页4.1 互信息和平均互信息互信息和平均互信息4.1.2 互信息量及其性质互信息量及其性质根据前面的信道的数学模型：根据前面的信道的数

2、学模型： 如果信道是理想的，发出如果信道是理想的，发出ai收到收到ai则所获得的信息则所获得的信息量量 ai的不确定度的不确定度I(ai)； 如果信道不理想，发出如果信道不理想，发出ai收到收到bj,由由bj推测推测ai的概率，的概率，()ijp a b后验概率一一、定义、定义1：我们将从bj中获取有关ai的信息量称为互信息量互信息量()(;)log () ijijip a bI a bp a3第3页/共81页4.1.2 互信息量及其性质一、互信息量的一、互信息量的定义定义 继续讨论第二章的例题，即某地二月份天气构成的信源为 81 ,81 ,41 ,21)( ),( ),( ),()(4321

3、雪雨阴晴aaaaXPX“今天不是晴天”作为收到的信息b1，计算b1与各天气之间的互信息量。4第4页/共81页4.1.2 互信息量及其性质一、互信息量的一、互信息量的定义定义2将互信息表达式展开得：将互信息表达式展开得： ()() iijI aI a b )(log)(log);( jiijibapapbaI同样道理，我们可以定义同样道理，我们可以定义a ai i对对b bj j 的互信息量为的互信息量为 (2.1.9) ),2, 1;,2, 1( )( )()()(log);( mjniabIbIbpabpabIijjjijij5第5页/共81页通信前ijab“输入端出现 和输出端出现 ”的概

4、率 )()()(jijibpapbap先验不定度（联合自信息量） )()(1log)(jijibpapbaI发送发送接收接收4.1.2 互信息量及其性质一、互信息量的定义36第6页/共81页输入输出端的联合概率)()()()()(jijijijibapbpabpapbap后验不定度 )(1log)(jijibapbaI 一、互信息量的定义3发送发送接收接收4.1.2 互信息量及其性质通信后7第7页/共81页 这样，通信后流经信道的信息量，等于通信前后不定度的差 ), 2 , 1;, 2 , 1( )()()(logmjnibpapbapjiji )(1log)()(1logjijibapbpa

5、p( ;)()() ijijijI a bI abIab4.1.2 互信息量及其性质一、互信息量的定义38第8页/共81页4.1.2 互信息量及其性质二、互信息量的性质二、互信息量的性质( ;)(;) ijjiI a bI b a对称性 当X和Y相互独立时，互信息为0 12()() () ijijp abp a p b();log =log1=0() ()ijijijp abI a bp a p b（）9第9页/共81页4.1.2 互信息量及其性质二、互信息量的性质二、互信息量的性质)()/(ijiapbap)()/(ijiapbap互信息量可为正值或负值 3互信息量为正，互信息量为正， b

6、bj j使使a ai i的不确定度减小，的不确定度减小，上例中，上例中，“今天不是晴天今天不是晴天”为为0，二者相互独立，二者相互独立，“今天我很高兴今天我很高兴”为负，为负， b bj j没有使没有使a ai i的不确定度减小，的不确定度减小，“今天有风今天有风”。)()/(ijiapbap10第10页/共81页4.1.3 平均互信息量及其性质一、信道疑义度一、信道疑义度( ;)ijI a b研究信源中各个消息之间的关系研究信源中各个消息之间的关系11第11页/共81页4.1.2 互信息量及其性质一、信道疑义度一、信道疑义度信道疑义度信道疑义度：11(| ) (|)() (|)nmijiji

7、jijH X YE I a bp ab I a b含义含义：收到：收到Y后关于后关于X尚存的平均不确定性。尚存的平均不确定性。性质性质： 0(| )H X YH Xequivocation12第12页/共81页4.1.2 互信息量及其性质二、平均互信息量的定义二、平均互信息量的定义平均互信息平均互信息11()()log ( )nmijijijip a bp abp a平均交互信息量；交互熵);();(jibaIEYXInimjjijibaIbap11);()(13第13页/共81页4.1.2 互信息量及其性质二、平均互信息量的定义二、平均互信息量的定义计算时可用公式：计算时可用公式： (; )

8、I X Y)()(YXHXH( )()H YH Y X()( )()H XH YH XY14第14页/共81页4.1.2 互信息量及其性质二、平均互信息量的定义二、平均互信息量的定义平均交互信息量与几个测度函数辨析 和 和 (; )I X Y( ;)ijI a b (; )I X Y()H X相同点：统计平均相同点：统计平均不同点：提供与获得不同点：提供与获得15第15页/共81页4.1.2 互信息量及其性质三、条件互信息和平均条件互信息三、条件互信息和平均条件互信息给定X、Y、Z三个离散概论空间，其连接关系为： 系统1系统2系统1XXYYZZ(a)(b)16第16页/共81页4.1.2 互信

9、息量及其性质练习： 有两个硬币，一个正常硬币（一面是国徽，一面是面值），另一个是不正常的硬币（两面都是面值）。现随机抽取一次硬币，抛掷两次。问出现面值的次数对于硬币的 识别能提供多少信息量？ 17第17页/共81页4.1.2 互信息量及其性质四、平均互信息量的性质四、平均互信息量的性质非负性(; )0I X Y 说明：信道每传递一条消息，总能提供一定的信息量。 注： 可正可负1)()/(ijiapbap)()/(ijiapbap)()/(ijiapbap( ;)ijI a b( ;)ijI a b( ;)ijI a b0,正常通信=0,通信中断( ;)ijI a b=0,=0,如何证明？ 2、

10、C=logn n为输入的符号数为输入的符号数 3、C=logm m为输出的符号数为输出的符号数 43第43页/共81页4.2.3几种特殊离散信道的容量几种特殊离散信道的容量一、离散无噪信道1、一一对应的无噪信道an bna1 b1a2 b21.000.0.0100.100naaaX,21nbbbY,2144第44页/共81页a1 b1a2 b2an-1 bn-1an bn00.10000.010.10.00001.000X、Y一一对应,此时H(X/Y)=0，H(Y/X)=0， CmaxI(X;Y)log n (p(ai)=1/n即等概)p(ai)一一对应的无噪信道45第45页/共81页a1 b

11、1 b2 b32、具有扩展功能的无噪信道具有扩展功能的无噪信道a2 b4 b5 b6a3 b7 b8 38372625241312110000000000000000ababababababababpppppppp46第46页/共81页此时，此时，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、具有扩展功能的无噪信道具有扩展功能的无噪信道47第47页/共81页3、具有归并性的无噪信道、具有归并性的无噪信道a1 b1a2 a3 b2a4100010010001

12、001a5 b3C = max H(Y) = log m p(ai) =？p(ai)H(X/Y) 0，H(Y/X) = 0多个输入变成一个输出48第48页/共81页结论l无噪信道的信道容量只取决于信道的输入符号数n或输出符号数m，与信源无关。49第49页/共81页4.2.3 几种特殊离散信道的信道容量几种特殊离散信道的信道容量二、对称信道容量计算1、对称信道的定义：如果信道转移矩阵满足下列性质：如果信道转移矩阵满足下列性质： (1) 每行都是第一行的某种置换每行都是第一行的某种置换;(2) 每列都是第一列的某种置换。每列都是第一列的某种置换。 则称该信道为对称信道。则称该信道为对称信道。 显然

13、，对称信道是输入显然，对称信道是输入对称的，也是关于输出对称的。对称的，也是关于输出对称的。 50第50页/共81页练习：判断下列矩阵表示的信道是否是对称信道练习：判断下列矩阵表示的信道是否是对称信道 61316131616131313p 40.7 0.20.10.1 0.2 0.7p 31316161616131311p3121612161316131212p51第51页/共81页二、对称信道容量的计算二、对称信道容量的计算 强对称信道（均匀）：pnpnpnpnppnpnpnpp1111.1.111.11n X np：总体错误概率naaaX,21mbbbY,2152第52页/共81页二、对称

14、信道容量的计算二、对称信道容量的计算2、对称信道的性质：对称信道满足下列性质：对称信道满足下列性质： （1）即噪声熵即噪声熵=矩阵第一行元素组成的熵函数矩阵第一行元素组成的熵函数 （2）当）当P(X)（输入）等概分布，输出也是等（输入）等概分布，输出也是等概分布概分布注：这两个性质对后面求信道容量非常重要！注：这两个性质对后面求信道容量非常重要！12(/)(,)mH YXH q qq53第53页/共81页二、对称信道容量的计算二、对称信道容量的计算3、对称信道的信道容量：()()()max (, )max( )(|)max( )(|)iiip ap ap aCI X YH YH Y XH YH

15、 Y X由于对称信道满足：12(/)( ,)mH YXH q qq()max( )logip aH Ym综合起来可以得出对称信道的信道容量为综合起来可以得出对称信道的信道容量为12()max (, )log(,.,)imp aCI X YmH q qq对称信道关于输出也是对称的，当信道输入是等概率分布对称信道关于输出也是对称的，当信道输入是等概率分布时，信道输出也是等概率分布，时，信道输出也是等概率分布，H(Y)取得最大值取得最大值54第54页/共81页典型例子典型例子均匀信道信道容量计算均匀信道信道容量计算解解 显然该信道是对称的，信道容量为显然该信道是对称的，信道容量为log(1,.,)1

16、1ppCnHpnnlog(1)log(1)(1)log(1)(1)ppnppnnnlog( )log(1)nH ppn上述信道称为强对称信道或者均匀信道，是对称信道上述信道称为强对称信道或者均匀信道，是对称信道的一个特例的一个特例。 一般信道转移矩阵中，列元素之和并不等于一般信道转移矩阵中，列元素之和并不等于1，而该信道转移矩阵的各列元素之和都等于而该信道转移矩阵的各列元素之和都等于1。 其中，其中，p为总为总的错误传输概率。的错误传输概率。特别地，当特别地，当r=2时，信道容量为时，信道容量为C=1H(p) 55第55页/共81页几种对称信道之间的关系几种对称信道之间的关系输入对称对称信道均

17、匀信道二元均匀56第56页/共81页二、对称信道容量的计算二、对称信道容量的计算4、准对称信道的信道容量：二元对称纯删除信道该信道转移矩阵该信道转移矩阵为为 ，该信道即二元纯对称删该信道即二元纯对称删除信道，如图所示，除信道，如图所示， 其信道容量为其信道容量为1001qqPqq2(1)log(1)(1)log11Cqqqqq 比特/符号57第57页/共81页二、对称信道容量的计算二、对称信道容量的计算如果信道转移矩阵按列可以划分为几个互不相交的对如果信道转移矩阵按列可以划分为几个互不相交的对称信道的子集，则称该信道为准对称信道。称信道的子集，则称该信道为准对称信道。 显然，准对称显然，准对称

18、信道是输入对称的。信道是输入对称的。4、准对称信道的信道容量：准对称信道可以分解为若干个对称信道之和，所准对称信道可以分解为若干个对称信道之和，所以对于准对称信道，信道输入的最佳分布是等概率分以对于准对称信道，信道输入的最佳分布是等概率分布，而信道容量为布，而信道容量为121log(,.,)logsmkkkCnH qqqNM其中，其中，q1，q2，qm为准对称信道转移矩阵中的一行元素，为准对称信道转移矩阵中的一行元素，s为划分的子集数量，为划分的子集数量，Nk为第为第k个子矩阵的行元素之和，个子矩阵的行元素之和，Mk为为第第k个子矩阵的列元素之和。个子矩阵的列元素之和。58第58页/共81页例

19、题例题信道转移矩阵为信道转移矩阵为1111336611116363P求信道容量求信道容量C。 解解 通过观测可知，该信道是准对称信道，可以分解为通过观测可知，该信道是准对称信道，可以分解为三个互不相交的子集，分别为三个互不相交的子集，分别为11136,1163P213,13P 31616P 59第59页/共81页例题例题对应的参数分别为对应的参数分别为1111,362N 21,3N 316N 1111,362M 2112,333M 31 116 63M 所以信道容量为所以信道容量为121log(,.,)lognskkkCrH p ppNM1 1 1 1111211log2( , , )lblb

20、lb3 3 6 62233630.041H比特/符号 60第60页/共81页练习题：有噪声的打字机信道练习题：有噪声的打字机信道考虑有考虑有26个键的打字机个键的打字机1）如果每敲击一个键，它就准确输出成相应的字符，）如果每敲击一个键，它就准确输出成相应的字符，那么该容量那么该容量C为多少？为多少？2）如果假设敲击一个键都会导致输出该键对应的字母）如果假设敲击一个键都会导致输出该键对应的字母或者下一个字母等概论出现，即敲或者下一个字母等概论出现，即敲A可能输出可能输出A或者或者B，敲敲Z Z可能输出可能输出Z Z或者或者A A，那么此时的容量如何？，那么此时的容量如何？61第61页/共81页复

21、习数学知识复习数学知识62第62页/共81页4.2.3离散信道容量的一般计算法信道容量的求解为一个信道容量的求解为一个多元函数求约束极值多元函数求约束极值的问题。的问题。信道转移矩阵为信道转移矩阵为0.90.10.20.8P例：求信道输入最佳分布和信道容量例：求信道输入最佳分布和信道容量C。 解解 观察信道转移矩阵可知，该信道不是对称的，信道观察信道转移矩阵可知，该信道不是对称的，信道的输入、的输入、 输出符号数量都为输出符号数量都为2，假设信道输入符号的概率分，假设信道输入符号的概率分别为别为p，1p，可以得到平均互信息量。，可以得到平均互信息量。 根据假设的信道输入的概率分布，求出信道输出

22、概率分根据假设的信道输入的概率分布，求出信道输出概率分布布p(bj)：p(b1)=0.9p+0.2(1p)=0.2 + 0.7p p(b2)=0.1p+0.8(1p)=0.80.7p63第63页/共81页4.2.3离散信道容量的一般计算法输入、输入、 输出之间的平均互信息量为：输出之间的平均互信息量为：2211(|)(; )( )(|)log()jiijiijjp baI X Yp ap bap b将相关参数代入上述计算公式，得到：将相关参数代入上述计算公式，得到：0.90.1(; )(0.9log0.1log)0.20.70.20.7I X Yppp0.20.8(1)(0.2log0.8lo

23、g)0.80.70.80.7ppp(0.1)(1)(0.2)log(0.20.7 ) (1)log(0.80.7 )pHp Hpppp 64第64页/共81页4.2.3离散信道容量的一般计算法对对I(X;Y)求导，得到最佳分布求导，得到最佳分布d ( ; )0.7(0.1)(0.2) log(0.2 0.7 )logd0.2 0.70.7(1)log(0.8 0.7 )log00.8 0.7I X YpHHpeppppep得到，得到，p=0.532，所以信道容量为，所以信道容量为C=maxI(X;Y)=0.415 比特比特/符号符号从该例可以看出，即使是简单的非对称二元信道，其最佳分从该例可以

24、看出，即使是简单的非对称二元信道，其最佳分布的求解也十分复杂，所以一般离散信道的信道容量的求解布的求解也十分复杂，所以一般离散信道的信道容量的求解通过计算机进行。通过计算机进行。 下面讨论一般离散信道的解法。下面讨论一般离散信道的解法。 65第65页/共81页4.2.3离散信道容量的一般计算法 平均互信息量平均互信息量I(X;Y)是输入概率分布是输入概率分布p(ai)的凸函数，所的凸函数，所以极大值是一定存在的。以极大值是一定存在的。 假设信道输入的符号数量为假设信道输入的符号数量为n，那，那么么I(X;Y)应当是应当是r个随机变量个随机变量(p1，p2，pn) 的函数，而且的函数，而且满足约

25、束条件，该多元函数的条件极值可以利用拉满足约束条件，该多元函数的条件极值可以利用拉格朗日乘法求出。格朗日乘法求出。 (1) 首先引入函数首先引入函数11niipn1(; )() 1iiI X Yp a其中，其中，为拉格朗日乘子。为拉格朗日乘子。 66第66页/共81页4.2.3离散信道容量的一般计算法(2) 对信道输入概率对信道输入概率p(ai)求导数，并令其为求导数，并令其为0。1 (;)()10()()nkkiiI X Yp ap ap a解方程组可以求出最佳概率分布解方程组可以求出最佳概率分布12 , ,.,rppp和和。(3) 将最佳分布代入将最佳分布代入I(X;Y)，即可求出信道容量

26、，即可求出信道容量C。11(|)(; )( ) (|)log()nmjiijiijjp baI X Yp a p bap b而而p(bj)可以表示为可以表示为1()()(|)njkjkkp bp ap ba67第67页/共81页4.2.3离散信道容量的一般计算法11 (;)()1()()()(;)(;) =-=-()()()nkkiinkkiiiI X Yp ap ap ap aI X YI X Yp ap ap a故关键是求第一项故关键是求第一项我们将这项展开看看哪部分和求偏导有关我们将这项展开看看哪部分和求偏导有关68第68页/共81页4.2.3离散信道容量的一般计算法i 11(|)()(

27、|) log()nmjiijijjp bap ap bap b i 1()()(|)njijip bp ap ba 1111( ) (|)log (|)( ) (|)logp( )p( )nmnmijijiijijijijiip a p bap bap a p bap baa69第69页/共81页4.2.3离散信道容量的一般计算法j 1(|) log(|)mjijip bap ba？第二块分步求第二块分步求（1）将）将 看作常数，对前面的求偏导看作常数，对前面的求偏导（2）将）将 看作常数，对看作常数，对 求偏导求偏导 ()(|)ijip ap ba1j 11i 11()(|)(|) log(

28、|)logp()log()()()nijimmijijijjinmjijjip ap bap bap bap bap bp a bp a 70第70页/共81页4.2.3离散信道容量的一般计算法j 1j 1(|)(|) log(|) log()mmjijijijp bap bap baep b带入合并得：带入合并得：给定给定 后验概率为后验概率为1iaj 1(|)(|) log0()()mjijiijp bap baep ap b故故71第71页/共81页4.2.3离散信道容量的一般计算法11(|)(|) loglog()()1mjijijjmijp bap baep bp a结论结论72第7

29、2页/共81页4.2.3离散信道容量的一般计算法假设信道输入的最佳分布为假设信道输入的最佳分布为(p1，p2，pn)，将，将方程组的两边同时乘以各自的概率方程组的两边同时乘以各自的概率p(ai)，并且两边，并且两边同时对同时对i求和，从而得到信道容量为求和，从而得到信道容量为C=+loge仍然为待定的系数，但我们找到一些仍然为待定的系数，但我们找到一些规律规律(|)11log=loglog()()(|)()(|)=;jijjjijjijip bap bp bp baI bI baI b a（）将将 来分析来分析j 1(|)(|) log()mjijijp bap bap b其中其中73第73页

30、/共81页4.2.3离散信道容量的一般计算法加上前面一个加权加上前面一个加权1=(|);logmjijiijp ba I b aae（）=I(Y; )=规律：规律：信源处于最佳分布时，由输出端观察，每一信源处于最佳分布时，由输出端观察，每一个符号的信息量都是一样的。个符号的信息量都是一样的。74第74页/共81页4.2.3离散信道容量的一般计算法定理定理 设有一般离散信道，它有设有一般离散信道，它有n个输入符号，个输入符号，m个输出符号，其平均互信息个输出符号，其平均互信息I(X;Y)达到极大值达到极大值(即等即等于信道容量于信道容量)的充要条件是输入概率分布的充要条件是输入概率分布p(ai)满足满足(其其中中i=1，2，n)( ; )( ; )iiI a YCI a YC对所有p(ai)0的ai 对所有p(ai)=0的ai常数常数C就是所求的信道容量。就是所求的信道容量。 75第75页/共81页4.2.3离散信道容量的一般计算法1121311222321323330.90.10(|)(|)(|)111(|)(|)(|)333(|)(|)(|)00.10.9p bap bap baPp bap bap bap bap bap ba求该信道的容量求该信道的容量C和信道输入的最佳概率分布。和信道输入的最佳概率分布。 解解 该信道不是对称信道，所以不能直