第四章 数据可靠传输和信道编码

1、 4.1 4.1 4.2 4.2 4.3 4.3 4.4 4.4 4.5 4.5 4.6 4.6 数据可靠传输和信道编码数据可靠传输和信道编码l 信道信道：信息传输的通道。：信息传输的通道。 信息论中的信道划分是人为的信息论中的信道划分是人为的 空间传输空间传输：电缆、光纤、电波传输的空间、载波线路。：电缆、光纤、电波传输的空间、载波线路。 时间传输时间传输：磁带、光盘。：磁带、光盘。信道分类信道分类2. 2. 按输入按输入/ /输出之间的输出之间的记忆性记忆性可分为：可分为： 无记忆信道无记忆信道：信道在某时刻的输出只与信道该时：信道在某时刻的输出只与信道该时刻的输入有关而与信道其它时刻的输

2、入、输出无刻的输入有关而与信道其它时刻的输入、输出无关。噪声独立随机地影响着每个传输码元，因此关。噪声独立随机地影响着每个传输码元，因此接收的码元序列中的错误是独立随机出现的。接收的码元序列中的错误是独立随机出现的。 （太空信道、卫星信道、光缆信道）（太空信道、卫星信道、光缆信道） 有记忆信道有记忆信道：信道在某时刻的输出与其他时刻的：信道在某时刻的输出与其他时刻的输入、输出有关。有记忆信道又称输入、输出有关。有记忆信道又称突发差错信道突发差错信道. .噪声、干扰的影响往往是前后相关的噪声、干扰的影响往往是前后相关的, ,错误是成错误是成串出现的。（短波信道、移动通信信道）串出现的。（短波信道

3、、移动通信信道） 信道分类信道分类 3. 3. 根据信道的根据信道的统计特性是否随时间改变统计特性是否随时间改变可分为可分为: : 平稳信道平稳信道（恒参信道（恒参信道, ,时不变信道时不变信道, ,如卫星通信）如卫星通信） 非平稳信道非平稳信道（变参信道（变参信道, ,时变信道时变信道, ,如移动通信）如移动通信） 4. 4. 根据输入根据输入/ /输出的输出的个数个数可分为：可分为： 单用户信道单用户信道：一个输入一个输出单向通信。：一个输入一个输出单向通信。 多用户信道多用户信道：双向通信或三个或更多个用户之间：双向通信或三个或更多个用户之间 相互通信的情况，例如多元接入信道、广播信道、

4、相互通信的情况，例如多元接入信道、广播信道、网络通信信道等。网络通信信道等。信道分类信道分类 5. 5. 根据信道的输入根据信道的输入/ /输出是否是输出是否是确定关系确定关系可分为可分为: : 有噪声信道有噪声信道, , 无噪声信道无噪声信道 6. 6. 根据信道上根据信道上有无干扰有无干扰可分为：可分为： 有干扰信道有干扰信道, , 无干扰信道无干扰信道 信道分类信道分类噪声噪声(noise)(noise)：电路：电路内部内部产生的无用信号产生的无用信号干扰干扰(interference)(interference)：来自电路：来自电路外部外部的无用信号的无用信号 无干扰信道无干扰信道21

5、0011112无干扰信道无干扰信道是一种最理想的信道，也称是一种最理想的信道，也称无噪信道无噪信道，信道的输，信道的输入和输出符号间入和输出符号间有确定有确定的一一对应关系，的一一对应关系， p (y x ) = 如图三元无干扰信道中，如图三元无干扰信道中，x , y 0 , 1 , 2 ，对应信道矩阵是单对应信道矩阵是单位矩阵位矩阵 01yxyx100010001P Pl 信道的主要研究内容：信道的主要研究内容：信道建模（信道的统计特性描述）信道建模（信道的统计特性描述） 信道传输信息的能力（信道容量）信道传输信息的能力（信道容量） 在有噪信道中能否实现可靠传输？怎样实现可在有噪信道中能否实

6、现可靠传输？怎样实现可靠传输？靠传输？信宿信宿信道信道信源信源 通信系统的简化模型通信系统的简化模型噪声噪声信信 源源 每发一个符号平均提供的信息量每发一个符号平均提供的信息量H(X)；无噪信道无噪信道信宿可确切无误的接收信息。信宿可确切无误的接收信息。离散单符号信道的数学模型离散单符号信道的数学模型 对于离散单符号信道来说，信道的输入输出均为对于离散单符号信道来说，信道的输入输出均为单个符号的消息单个符号的消息, ,设信道的设信道的输入随机变量输入随机变量X的取值集合为的取值集合为X=x1,x2,xr， 相应的概率分布为相应的概率分布为p(xi ) ， i=1,2,r ；输出随机变量输出随机

7、变量Y的取值集合为的取值集合为Y=y1,y2,ys，相应的概率分布为相应的概率分布为p (yj )， j=1,2,s 信道特性可以用信道特性可以用转移概率矩阵转移概率矩阵来表示：来表示： P=p(yj|xi)rs 信道的数学模型信道的数学模型为为X, P(Y|X),Y离散单符号信道的数学模型离散单符号信道的数学模型XYx1x2xry1y2ysP (Y|X)|(ijxyp1,2,.,;1,2,.,irjs满足满足：（1）0 p(yj|xi) 1 (i=1,2,r；j=1,2,s) （2）(i=1,2,r)sjijxyp11)|(离散单符号信道的数学模型离散单符号信道的数学模型信道转移概率矩阵信道

8、转移概率矩阵:描述输入描述输入/ /输出的统计依赖关系输出的统计依赖关系, ,反映反映信道统计关系信道统计关系)|()|()|()|()|()|()|()|()|(21222211121121rsrrssrxypxypxypxypxypxypxypxypxypxxxP1y2ysysr1信 道Xp(Y|X)Y输入符号集输入符号集A=0,1, 输出符号集输出符号集B=0,1，rs2传递概率传递概率 二元二元对称信道对称信道 (0|0)1(0|1)pepe (1|0)(1|1)1pepe 11eeeePP0101ee1 e1 e(其中其中e称作信道错误概率称作信道错误概率)二元对称信道二元对称信道

9、对于接收符号不能作出肯定或否定判对于接收符号不能作出肯定或否定判决时，引入删除符号，表示对该符号决时，引入删除符号，表示对该符号存有疑问，作为有误或等待得到更多存有疑问，作为有误或等待得到更多信息时再作判决。信息时再作判决。二元删除信道如图所示，输入符号二元删除信道如图所示，输入符号x 0 , 1，输出符号，输出符号y 0 , e , 1，转，转移概率矩阵为移概率矩阵为1001eeeeP Pe0 1-e101e 1-e e 二元删除信道二元删除信道二元删除信道二元删除信道 二元二元Z信道如图所示，信道输入符号信道如图所示，信道输入符号x 0 , 1，输出符号，输出符号y 0 , 1转移转移概率

10、矩阵为概率矩阵为 101eeP P101011-e e二元二元Z Z信道信道 二元二元Z信道信道 例例 已知已知先验概率先验概率 p(xi) ， i=1,2,r ,信道传递概率信道传递概率 p(yj| xi)，i=1,2,r，j=1,2,s ,则则 1. 联合概率联合概率 p(xi ,yj)= p(xi)p(yj| xi)= p(yj)p(xi | yj) i=1,2,r；j=1,2,s 2. 输出符号概率输出符号概率 j=1,2,s p(yj) = p(xiyj)= p(xi)p(yj| xi)ri 1 P)()()()()()(2121rsxpxpxpypypyp)()()()()()(2

11、121rTsxpxpxpypypypPri 13. 后验概率后验概率: : 贝叶斯公式贝叶斯公式riijiijijjijixypxpxypxpypyxpyxp1)|()()|()()()()|(（i =1，2，r; ;j j =1 =1，2 2，s） 1(|)1,rijip xyj j =1 =1，2 2，s 一个好的信息传递系统应：一个好的信息传递系统应：速度快、错误少速度快、错误少。所以。所以衡量一个信息传递系统的好坏，有两个主要指标：衡量一个信息传递系统的好坏，有两个主要指标： 速度指标速度指标：信息（传输）率：信息（传输）率 R, ,即信道中平均每个即信道中平均每个符号传递的信息量；符

12、号传递的信息量； 质量指标质量指标：平均差错率，即对信道输出符号进行译：平均差错率，即对信道输出符号进行译码的平均错误概率码的平均错误概率. .l 信道疑义度信道疑义度H(X|Y) 表示表示接收端接收端收到信道输出的一个符收到信道输出的一个符号之后对信道输入的符号仍然存在的平均不确定性。号之后对信道输入的符号仍然存在的平均不确定性。 理想信道，理想信道，H(X|Y)=0。 一般情况下一般情况下， 。 当当 时时, ,表示接收到输出变量表示接收到输出变量Y后关后关于输入变量于输入变量X的的平均不确定性一点也没有减少平均不确定性一点也没有减少。)()|(XHYXH)()|(XHYXH1.1.信道疑

13、义度信道疑义度l信源熵信源熵是信源输出的信息量，而是信源输出的信息量，而真正被接收者收到的真正被接收者收到的信息量则是信息量则是互信息互信息。平均互信息的三种表达式：平均互信息的三种表达式： l 平均互信息的性质：平均互信息的性质：非负性、极值性、非负性、极值性、凸函数性凸函数性( ; )( ;)( )(| )( )( |)( )( )( , )I X YI Y XH XH X YH YH Y XH XH YH X Y)|()()|(log)|()()()|(log)|()();(ijiiijijijijijijijixypxpxypxypxpypxypxypxpYXI定理定理 对于对于固定信

14、道固定信道，平均互信息，平均互信息I(X;Y)是是信源信源概率概率分布的分布的上凸上凸函数。函数。物理意义：对某一个确定信道，存在一种物理意义：对某一个确定信道，存在一种信源分布，使平均互信息最大。最大值由信源分布，使平均互信息最大。最大值由信道本身的特性决定。信道本身的特性决定。 定理定理 对于对于给定信源给定信源，平均互信息，平均互信息I(X;Y)是是信道信道转移转移概率的概率的下凸下凸函数。函数。物理意义：每一个信源都存在一种对应的最物理意义：每一个信源都存在一种对应的最差信道，此信道的干扰最大，输出端获得的差信道，此信道的干扰最大，输出端获得的信息量最小。信息量最小。 例例 求二元删除

15、信道的求二元删除信道的 4341XP3231002121P()( )(|)(; ).H XH YH X YI X Y、和解解 由先验概率和信道转移矩阵可得输出符号由先验概率和信道转移矩阵可得输出符号Y 的概率分布的概率分布 11013131221244882033YXPP P即即 1(0),8P Y 3(?),8P Y 1(1).2P Y X、Y的的联合概率分布联合概率分布为为 p(xi ，yj)= p(xi)p(yj| xi) |1 11(0,0)(0)(0|0)4 28XYXY Xppp81?), 0(XYp0) 1 , 0(XYp0)0 , 1 (XYp1(1,?)4XYp1(1,1)2

16、XYp由联合概率分布和由联合概率分布和Y Y的概率分布可得后验概率为的概率分布可得后验概率为 ( ,)(|)()ijijjp x yp xyp y1)0|0(|YXp0)0| 1 (|YXp31?)|0(|YXp32?)| 1 (|YXp0) 1 |0(|YXp1) 1 | 1 (|YXp1344XP1102212033 P131882YP11134()(0)log(1)loglog4log(0)(1)4430.811XXXXH Xpppp111( )(0)log(1)log(?)log(0)(1)(?)1.406YYYYYYH Ypppppp|11(| )(0,0)log(1,0)log(0

17、|0)(1|0)11(0,?)log(0,?)log(0|?)(1|?)11(0,1)log(1|1)log0.344(0|1)(1|1)XYXYX YX YXYX YX YX YXYXYX YX YH X Ypppppppppppp11(|)( ,)log (|)nmijjiijH Y Xp x yp yx 另外，另外， 还可以先求得后验熵还可以先求得后验熵 ， ， ，再通过下式计算：，再通过下式计算： )|(YXH0)0|(YXH918. 0?)|(YXH0) 1|(YXH(| )(|0)(0)(|?)(?)(|1)(1)YYYH X YH X YpH X YpH X Yp(; )()(|

18、 )0.467I X YH XH X Y 信道对于信息率的容纳并不是无限制的，它不信道对于信息率的容纳并不是无限制的，它不仅与物理信道本身的特性有关，还与信道输入信号仅与物理信道本身的特性有关，还与信道输入信号的统计特性有关，它有一个极限值，即的统计特性有关，它有一个极限值，即信道容量信道容量。信道容量是有关信道的一个很重要的物理量。信道容量是有关信道的一个很重要的物理量。 信道容量性质：信道容量性质：与信源的概率分布无关；与信源的概率分布无关；是完全描述信道特性的参量是完全描述信道特性的参量；是信道能够传输的最大信息量。是信道能够传输的最大信息量。2. 2. 信道容量信道容量l 信息传输率信

19、息传输率R：信道中平均每个符号所传送的信息量。信道中平均每个符号所传送的信息量。l平均互信息平均互信息 是接收到符号是接收到符号Y后平均获得的关于后平均获得的关于X的信息量，所以的信息量，所以l 设平均传输一个符号需要设平均传输一个符号需要t秒，则信道每秒钟平均传输秒，则信道每秒钟平均传输的信息量为的信息量为信息传输速率信息传输速率 ：(; )I X Y(; )/RI X Y(比特 符号)1(; )/tRI X Yt（比特 秒）tR信道容量信道容量l在信道确定的情况下，在信道确定的情况下， 是信源概率分布是信源概率分布 的的上凸函数上凸函数。(; )RI X Y()max(; )/P XCI

20、X Y比特 符号()P X(; )RI X Y因此，必然存在一种信源概率分布使信息传输率因此，必然存在一种信源概率分布使信息传输率最大。最大。l定义这个最大的信息传输率为定义这个最大的信息传输率为信道容量信道容量：信道容量信道容量l 相应的输入概率分布被称为相应的输入概率分布被称为最佳输入分布最佳输入分布。)|()()|(log)|()()()|(log)|()();(ijiiijijijijijijijixypxpxypxypxpypxypxypxpYXIl 信道单位时间内平均传输的信道单位时间内平均传输的最大信息量最大信息量：()1max(; )/tP XCI X Yt比特 秒信道容量信道

21、容量例例 二元对称信道二元对称信道: : 信源的概率空间为信源的概率空间为0 1()1XP Xpp11eeeeP P信道矩阵为信道矩阵为2) 固定信道，当固定信道，当 时，时， 互信息取得最大值。互信息取得最大值。1)(; )( )(|)( (1)(1) )( )I X YH YH Y XH pep eH e112pp 1( (1)(1) )( )12H pep eH1-H(e)w w010.5 固定二元对称信道的平均互信息固定二元对称信道的平均互信息I(X,Y) 研究信道，其核心问题就是求研究信道，其核心问题就是求信道容量信道容量和和最佳最佳输入分布输入分布。根据定义，求信道容量问题就是求平

22、均。根据定义，求信道容量问题就是求平均互信息量互信息量I(X,Y)关于输入概率分布关于输入概率分布P(X)的最大值问的最大值问题。题。 一般来说，这是一个很困难的问题，只有对一一般来说，这是一个很困难的问题，只有对一些特殊信道，如无噪信道等，才能得到解析解，对些特殊信道，如无噪信道等，才能得到解析解，对于一般信道，必须借助于数值算法。于一般信道，必须借助于数值算法。信道容量信道容量 对于一般信道对于一般信道, ,信道容量计算相当复杂信道容量计算相当复杂, ,我们只我们只讨论某些特殊类型的信道：讨论某些特殊类型的信道： 离散信道离散信道可分成：可分成： 无干扰无干扰( (无噪无噪) )信道信道

23、无嗓无损信道无嗓无损信道 有噪无损信道有噪无损信道 无噪有损信道无噪有损信道 有干扰无记忆有干扰无记忆信道信道 有干扰有记忆有干扰有记忆信道信道信道容量的计算信道容量的计算 1. 无损信道无损信道 有噪无损信道有噪无损信道，一个输入对应多个输出。，一个输入对应多个输出。( (具有扩展性能）具有扩展性能）( )( )max (; )max()logp xp xCI X YH Xr(; )()(|)()I X YH XH X YH X(|)0H X Y 3. 3. 几种特殊信道的信道容量几种特殊信道的信道容量 信 道Xrp(Y|X)Ys2. 无噪信道无噪信道 无噪有损信道无噪有损信道，它是一个输出

24、对应多，它是一个输出对应多 个输入。（具有个输入。（具有归并性能归并性能）( )( )max (; )max( )logp xp xCI X YH Ys(; )( )(|)( )I X YH YH YXH Y(|)0H YX 几种特殊信道的信道容量几种特殊信道的信道容量 3. 无噪无损信道无噪无损信道 输入、输出之间有确定的一一输入、输出之间有确定的一一 对应关系。对应关系。 ( )( )max (; )max()logp xp xCI X YH Xr(; )()( )I X YH XH Y(|)0,(|)0,H Y XH X Yrs几种特殊信道的信道容量几种特殊信道的信道容量 离散对称信道的

25、信道容量离散对称信道的信道容量 定义定义 若信道矩阵若信道矩阵P中每行都是第一行的排列，则称中每行都是第一行的排列，则称 此信道是此信道是行对称信道行对称信道。3161316161613131P( |)( )( |)( )(|)log(|)(|)log(|)( |)iiiijijiijjijiijH Y Xp x H Y xp xp yxp yxp yxp yxH Y x 几种特殊信道的信道容量几种特殊信道的信道容量 定义定义 若信道矩阵中每行都是第一行的排列，并若信道矩阵中每行都是第一行的排列，并 且每列都是第一列的排列，则称之为且每列都是第一列的排列，则称之为对称对称 信道信道。 3131

26、616161613131P216131312161613121P离散对称信道的信道容量离散对称信道的信道容量 定义定义 虽然不是对称信道，但是信道矩阵可以按虽然不是对称信道，但是信道矩阵可以按 列分为一些对称的子阵，则称之为列分为一些对称的子阵，则称之为准对称准对称 信道信道。8 . 01 . 01 . 01 . 01 . 08 . 0P8 . 01 . 01 . 08 . 01P1 . 01 . 02P离散对称信道的信道容量离散对称信道的信道容量 定义定义 若若r=s，且对于每一个输入符号，正确传输概率且对于每一个输入符号，正确传输概率 都相等，且错误传输概率都相等，且错误传输概率 p 均匀

27、地分配到均匀地分配到 r-1 个个 符号符号,则称此信道为则称此信道为强对称信道强对称信道或或均匀信道均匀信道。prprprprprpprprprprpp111111111Ppppp1010P离散对称信道的信道容量离散对称信道的信道容量 强对称信道具备四个特征：强对称信道具备四个特征： 1. 矩阵中的每一行都是第一行的排列；矩阵中的每一行都是第一行的排列；( (行对称行对称) ) 矩阵中的每一列都是第一列的排列。矩阵中的每一列都是第一列的排列。( (列对称列对称) ) 2. 信道输入与输出消息（符号）数相等，即信道输入与输出消息（符号）数相等，即 r=s。 3. 错误分布是均匀的：信道矩阵中正

28、确传输概率都错误分布是均匀的：信道矩阵中正确传输概率都 相等，且错误传输概率均匀地分配到相等，且错误传输概率均匀地分配到r-1个符号上。个符号上。 4. 不仅每一行元素之和为不仅每一行元素之和为1,每一列元素之和也为每一列元素之和也为1。显然显然,对称性的基本条件是对称性的基本条件是1，而，而2、3、4是加强条件。是加强条件。离散对称信道的信道容量离散对称信道的信道容量 放松对信道的约束，仅满足条件放松对信道的约束，仅满足条件1 1，就构成，就构成一般的一般的对称信道对称信道。 例例1 1 例例2 23131616161613131P216131312161613121P离散对称信道的信道容量

29、离散对称信道的信道容量再进一步放松条件，信道矩阵按列分成若干子阵，再进一步放松条件，信道矩阵按列分成若干子阵，如果子阵是对称的，则称为如果子阵是对称的，则称为准对称信道准对称信道。 122121211221121211 1 1 1 2PPPqppqqpqp11P离散对称信道的信道容量离散对称信道的信道容量定理定理 对于对称信道，当信道输入概率分布为等对于对称信道，当信道输入概率分布为等 概分布时，输出概率分布必为概分布时，输出概率分布必为等概分布等概分布。证明：证明：当输入为等概分布时当输入为等概分布时 ， 则输出则输出 ，其中其中rxpi1)(ri, 2 , 1jijiijiijHrxypr

30、xypxpyp1)|(1)|()()(1(|)rjjiiHp yx 为信道矩阵第为信道矩阵第j列元素之和。列元素之和。而对称信道每一列是第一列的不同排列。因此而对称信道每一列是第一列的不同排列。因此12sHHH即当信道输入为等概分布时，输出即当信道输入为等概分布时，输出 亦为等概分布。亦为等概分布。 1(),jp ysj=1,2,s定理定理 对称信道对称信道当当信道输出概率分布为等概信道输出概率分布为等概的情况的情况 下达到信道容量下达到信道容量 其中其中 是信道矩阵中的任意一行中的元素。是信道矩阵中的任意一行中的元素。,12log(,),sCsH p pp,2,1,sppp证明：证明：12(

31、|)(|)(,)isH Y XH Y xH p pp,12(; )( )(|)( )(,)sI X YH YH Y XH YH p pp,12( )( ),1212( )max (; )max( )(,)max( )(,)log(,)sp xp xssp xCI X YH YH p ppH YH p ppsH p pp准对称信道准对称信道当信道输入概率分布为等概的情况下达到信道容量当信道输入概率分布为等概的情况下达到信道容量 设信道矩阵可划分为设信道矩阵可划分为n个子矩阵，其中个子矩阵，其中Nk是第是第k个子矩阵个子矩阵中行元素之和，中行元素之和，Mk是第是第k k个子矩阵中列元素之和。个子矩

32、阵中列元素之和。,121log(,)lognskkkCrH p ppNM),(log,2,1spppHsC,12( )max( )(,)sp xCH YH p pp推论推论 对于对于强对称信道强对称信道有有 C=logr-plog(r-1)-H(p) )() 1log(logloglog) 1log(log1logloglog1log11log1loglog)1,1,(log),(log,2,1pHrprpppprprrpppprrprprprppprrprppHrpppHsCss = r 例例 求对称信道的信道容量求对称信道的信道容量解解216131312161613121P,12log(,

33、)1 1 1log3( , )2 3 60.126/sCsH p ppH比特 符号,12log(,),sCsH p pp例例 求准对称信道的信道容量。求准对称信道的信道容量。 二元对称删除信道二元对称删除信道qppqqpqp11P,121log(,)lognskkkCrH p ppNM解解 N1=1-q, M1=1-q, N2=q, M2=2q = log2-H(1-p-q, q, p)-(1-q)log(1-q)-qlog(2q),121log(,)lognskkkCrH p ppNM信道容量信道容量约束条件约束条件求求信道容量信道容量转化为求转化为求 对信源概率分布对信源概率分布 的的条件

34、极值条件极值。（拉格朗日乘子法）（拉格朗日乘子法） ()max(; )P XCI X Y(; )I X Y()P X( )1iip x( )0,1, 2,ip xir5. 5. 一般离散信道的信道容量一般离散信道的信道容量解：解： 引入辅助函数引入辅助函数 1(; )()1riiFI X Yp x（ 为待定系数）1(; )( ) 1(1,., )( )( )(; )( )riiiiiFI X Yp xirp xp xI X Yp x拉格朗日乘子法求信道容量拉格朗日乘子法求信道容量11(|)(; )( ) (|)log()rsjiijiijjp yxI X Yp x p yxp y1()( )

35、(|)rjijiip yp x p yx()(|)( )jjiip yp yxp x(; )( )iI X Yp x111( )(|)log(|)()log()rssijijijjijjp xp yxp yxp yp y111(|)log(|)(|)log()(|)logsssjijijijjijjjp yxp yxp yxp yp yxe1(|)(|)loglog()sjijijjp yxp yxep ylog()(|)log()()jjiijp yp yxep xp y拉格朗日乘子法求信道容量拉格朗日乘子法求信道容量令令 0()iFp x1(|)(|)loglog0( )()sjijiji

36、jp yxFp yxep xp y则则 1(|)(|)loglog1,2,()sjijijjp yxp yxeirp y111(|)()(|)log()(log)()rsrjiijiiijijp yxp xp yxp xep ylogCe拉格朗日乘子法求信道容量拉格朗日乘子法求信道容量在某些条件下利用这个方法可以计算在某些条件下利用这个方法可以计算C：(|)(|)loglog()jijijjp yxp yxeCp y(|)log(|)(|)log()(|)log()jijijijjjjijjp yxp yxp yxp yCp yxp yClog()jjp yC令令(|)(|)log (|)ji

37、jjijijjp yxp yxp yx1110244010000101110442P拉格朗日乘子法求信道容量拉格朗日乘子法求信道容量这是一个含有这是一个含有s个未知数、由个未知数、由r个方程组成的方程组。个方程组成的方程组。当当r= =s,且且信道矩阵是可逆矩阵时信道矩阵是可逆矩阵时, ,该方程组有唯一解该方程组有唯一解。 log()jjp yC()2jCjp y()1jjp yjjC2log()( ) (|)jijiip yp x p yx21jCj( )(1,2, )ip xirj()2jCjp y(|)(|)log (|)jijjijijjp yxp yxp yx拉格朗日乘子法求信道容量

38、拉格朗日乘子法求信道容量例例 求以下信道的信道容量。求以下信道的信道容量。 信道矩阵信道矩阵 1110244010000101110442P21log2141log4141log412141410041log4141log4121log2141412143132421解解2, 0413215log)2222log(2log2002jjC比特比特/符号符号(|)(|)log (|)jijjijijjp yxp yxp yx1042)()(1012)()(15log03215log241ypypypyp3011)()(,304)()(3241xpxpxpxp()2jCjp y()( ) (|)ji

39、jiip yp x p yx 当计算结果为负值时当计算结果为负值时, ,此解无效此解无效。它表明最大值在边界上。它表明最大值在边界上, ,即某些输入符号的概率为即某些输入符号的概率为0 0。设某些输入符号的概率为。设某些输入符号的概率为0 0，然后重新进行计算。然后重新进行计算。2 2）如果如果 r = 2，则可以直接对，则可以直接对I(X;Y)求导，得到信道容量和求导，得到信道容量和最佳输入分布。最佳输入分布。1）采用上述方法求出信道容量以后）采用上述方法求出信道容量以后,还必须解出还必须解出 ，因为在，因为在采用拉格朗日数乘法时并没有加上采用拉格朗日数乘法时并没有加上 的约束条件，因此的约

40、束条件，因此算出的算出的 可能是负值。可能是负值。 ( )ip x( )0ip x( )ip x例例 已知信道的转移矩阵为已知信道的转移矩阵为 ， 求信道容量。求信道容量。 2 . 05 . 03 . 02 . 03 . 05 . 0P解解 设输入概率分布设输入概率分布 1)()(21xpxp，|0.20.2YXY XPP P(; )( )(|)()log()(|)(0.30.2 )log(0.30.2 )(0.50.2 )log(0.50.2 )0.2log0.20.5log0.50.3log0.30.2log0.2jjijI X YH

41、 YH Y Xp yp yH Y x 0);(YXI0.2log(0.3+0.2 )-0.2+0.2log(0.5-0.2 )+0.2=0 1/2036. 0);(maxYXIC例例 信道输入符号集信道输入符号集X = x1, x2，输出符号集，输出符号集Y = y1, y2, y3, y4，给定信道转移概率矩阵给定信道转移概率矩阵 ，求该信道的，求该信道的信道容量信道容量C。 8141218181812141P P这是一个这是一个准对称信道准对称信道，根据定理，当，根据定理，当X等概分布，等概分布，时，信道容量时，信道容量平均互信息量平均互信息量 I（X; Y）= H（Y）- -H（YX）

42、(1) 21)()(21xqxq21)()(21);(xqxqYXIC412141)(log)()()(log)(jijijijijjxypxypxqyyww由由 ，先算出，先算出 (2) 2121)(21)()()(iijiijijxypxypxqyw214421332122211181)8181(21)(21)(163)4181(21)(21)(21)2121(21)(21)(163)8141(21)(21)(iiiiiiiixypyxypyxypyxypywwww将式将式(2)和和 代入式代入式(1)，可算得信道容量，可算得信道容量 = 0.0325 (比特比特/符号符号)21)()(2

43、1xqxq21)()(21);(xqxqYXIC412141)(log)(21)(log)(jijijijjjxypxypyyww定理定理 I(X;Y) 达到信道容量的达到信道容量的充要条件充要条件是输入分布是输入分布 p(xi) 满足：满足：p(xi) 0 时，时， I(xi;Y) C ；p(xi) = 0 时，时， I(xi;Y) C ，(|);(|)log()jiijijjp yxI x Yp yxp y 某些特殊矩阵可以利用这个方法推导得到某些特殊矩阵可以利用这个方法推导得到C C。6. 6. 信道容量定理信道容量定理定义定义 若在任意时刻信道的输出只与此时刻信道的输入若在任意时刻信道

44、的输出只与此时刻信道的输入有关，而与其他时刻的输入和输出无关，则称之为有关，而与其他时刻的输入和输出无关，则称之为离离散无记忆信道散无记忆信道，简称为，简称为DMC (discrete memoryless channel)。 输入、输出随机序列的长度为输入、输出随机序列的长度为N的离散无记忆平稳的离散无记忆平稳信道通常称为信道通常称为离散无记忆信道的离散无记忆信道的N次扩展信道次扩展信道。 离散多符号信道离散多符号信道( )3)(; )( )(|),(|)0(; )( )max( )log.p yI X YH YH Y XH Y XI X YH YH Y因为，所以( ( | ),)10;2)

45、log;3)log.QQ y x xyCCCC离散无记忆信道的信道容量 有性质：）定理1(; )0;I X Y 证）因为( )2)(; )()(|),(|)0(; )()max()log;p xI X YH XH X YH X YI X YH XH X因为，所以例例 二元对称信道的二次扩展信道。二元对称信道的二次扩展信道。解解 二次扩展信道的输入、二次扩展信道的输入、输出序列的每一个随机变量输出序列的每一个随机变量均取值于均取值于0,10,1，输入共有，输入共有 个个取值，输出共取值，输出共有有 个取值。根据个取值。根据 422Nr422Ns1(|)|)NkkkPP YXY X（=0000=1y=01=10=111x2x3x4x01=2y10=3y11=4yXY2112131241(|)(00|00)(0|0) (0|0)(|)(01|00)(0|0) (1|0)(|)(10|00)(1|0) (0|0)(|)(11|00)(1|0) (1|0)ppppppppppppppppppppppyxyxyxyx可求出可求出同理可求出其他的转移概率同理可求出其他的转移概率 得到信道矩阵得到信道矩阵 ,2,3,4,1,2,3,4ijpij22222222ppppppppppppppppppppppppP 定理定理 若信道的输入和输出分别是若信道的输入和输出分别是N长序列长序列X