信息论与编码基础-教学课件-3

1、信息论与编码基础信息论与编码基础离散信道离散信道一、信道疑义度与平均互信息二、信道容量三、有噪信道编码定理一、信道疑义度与平均互信息一、信道疑义度与平均互信息二、信道容量三、有噪信道编码定理信道模型信道疑义度平均互信息及其性质信息论与编码基础信息论与编码基础离散信道离散信道一、信道疑义度与平均互信息一、信道疑义度与平均互信息二、信道容量三、有噪信道编码定理信道模型信道疑义度平均互信息及其性质信息论与编码基础信息论与编码基础离散信道离散信道根据输入、输出信号的时间特性和取值特性离散信道连续信道半离散或半连续信道波形信道信道的分类数字信道根据信道的用户多少单用户信道多用户信道一对多、多对一多对多信

2、息论与编码基础信息论与编码基础离散信道离散信道根据信道转移概率的性质无扰信道有扰信道实际的通信信道几乎都是有扰信道无记忆信道有记忆信道实际信道一般都是有记忆的，信道中的记忆现象来源于物理信道中的惯性，如电缆信道中的电感或电容、无线信道中电波传播的衰落现象等。按信道统计特性恒参信道变参信道卫星信道短波信道根据信道噪声的性质高斯噪声信道非高斯噪声信道信道的分类信息论与编码基础信息论与编码基础离散信道离散信道离散信道的数学模型信道信道X1212(,.,): ( , ,., )NirXX XXXa aaY1212( ,.,): ( ,.,)NisYY YYYb bb( | )P y x , ( | )

3、, X P y x Y 无扰（无噪）信道有扰信道1,( )( | )0,( )yf xP y xyf x 无记忆信道有记忆信道111( | )(.|.)(|)NNNiiiP y xP yyxxP yx 信息论与编码基础信息论与编码基础离散信道离散信道信道信道X12: ( , ,., )rXa aaY12: ( ,.,)sYb bb( | )P y x单符号离散信道例例1 BSC信道信道BSC(p)信道信道是实际中几乎所有重要的二进制脉冲传输系统的模型p为交叉为交叉(crossover)概率概率等于解调器/检测器出现硬判决译码错误的概率信息论与编码基础信息论与编码基础离散信道离散信道条件转移概率

4、ijijijPabPaxbyPxyP)|()|()|(),.,2 , 1;,.,2 , 1(sjri转移矩阵rsrrssPPPPPPPPPP.212222111211转移概率图),.2 , 1( 10riPsjijXY0101pp1-p1-pXYa0arb0bsP(bj|ai)信息论与编码基础信息论与编码基础离散信道离散信道单符号离散信道一定比例的bit被删除，并且接收者知道是那些bit已经被删除。例2 二进制删除信道1001ppPqq信息论与编码基础信息论与编码基础离散信道离散信道单符号离散信道一、信道疑义度与平均互信息一、信道疑义度与平均互信息二、信道容量三、有噪信道编码定理信道模型信道疑

5、义度平均互信息及其性质信息论与编码基础信息论与编码基础离散信道离散信道XriiiaPaPxPxPXH1)(1log)()(log)()(先验熵先验熵rijijijbaPbaPbXH1)|(log)|()|(后验熵后验熵若信道中存在干扰时sjjjjbXHbPbXHEYXH1)|()()|()|(rijijisjjbaPbaPbP11)|(1log)|()(risjjijibaPbaP11)|(1log)(信道疑义度0H(X|Y)H(X)损失熵信息论与编码基础信息论与编码基础离散信道离散信道一、信道疑义度与平均互信息一、信道疑义度与平均互信息二、信道容量三、有噪信道编码定理信道模型信道疑义度平均互

6、信息及其性质信息论与编码基础信息论与编码基础离散信道离散信道互信息互信息)|(1log)(1logjiibaPaP);(jibaI自信息条件自信息1log( )iP a1log(|)ijP a b由于条件引入获得的信息量(|)( ;)log( )ijijiP a bI a bP a1）对称性I(ai;bj) = I(bj;ai)2）事件统计独立时I(ai;bj) = 03）可正、可负4）I(ai;bj) I(ai)信息论与编码基础信息论与编码基础离散信道离散信道信息论与编码基础信息论与编码基础绪论绪论表表11（x，y）的的联联合合概概率率分分布布 x0 x1 y0 0.06 0.04 y1 0

7、.54 0.36 练习练习：令随机变量x表示随机抽取人群中的性别，x0为男性，x1为女性。随机变量y表示随机抽取人是否抽烟，y0表示抽烟，y1表示不抽烟。（1）若（x，y）的联合概率分布如表11所示，求“已知抽取人为男性”，对“该人抽烟”提供的信息量。（2）若（x，y）的联合概率分布如表12所示，求“已知抽取人为男性”，对“该人抽烟”提供的信息量。 表表12（x，y）的的联联合合概概率率分分布布 x0 x1 y0 0.6 0.04 y1 0 0.36 本课小结本课小结2 2、信道疑义度、互信息、信道疑义度、互信息信息论与编码基础信息论与编码基础离散信道离散信道1 1、信道模型、信道模型BSC,

8、 BEC信息论与编码基础信息论与编码基础离散信道离散信道一、信道疑义度与平均互信息二、信道容量三、有噪信道编码定理一、信道疑义度与平均互信息一、信道疑义度与平均互信息二、信道容量三、有噪信道编码定理信道模型信道疑义度平均互信息及其性质信息论与编码基础信息论与编码基础离散信道离散信道互信息互信息(|)11logloglog( )(|)( )ijiijiP a bP aP a bP a( ;)ijI a b由于条件引入获得的信息量1）对称性I(ai;bj) = I(bj;ai)2）事件统计独立时I(ai;bj) = 03）可正、可负4）I(ai;bj) I(ai)信息论与编码基础信息论与编码基础离

9、散信道离散信道平均互信息平均互信息定义 令)|()();(YXHXHYXI为信道输入X与输出Y之间的平均互信息平均互信息接收到每个输出符号后获得的关于X的平均信息量bit/sig11(; )( )log()log( )( | )XXYI X YP xP xyP xP x y11()log()log( )( | )XYXYP xyP xyP xP x y( | )()log( )XYP x yP xyP x互信息互信息信息论与编码基础信息论与编码基础离散信道离散信道信息传输率不确定性消除的多少获得信息量的大小)|()();(YXHXHYXI平均互信息是互信息的统计平均值。XYxPyxPxyP)(

10、)|(log)()()log( ) ( )XYP xyP xyP x P y( | )()log( )XYP y xP xyP y信息论与编码基础信息论与编码基础离散信道离散信道平均互信息平均互信息1、非负性)|()();(YXHXHYXIXYyPxPxyPxyP)()()(log)(利用詹森不等式XYxyPyPxPxyPYXI)()()(log)();( ) ( )log()log10()XYP x P yP xyP xy信源信源加密加密信道信道解密解密信宿信宿密钥源密钥源全损信道全损信道信息论与编码基础信息论与编码基础离散信道离散信道2、极值性)();(XHYXI接收者通过信道获得的信息量

11、不可能超过信源本身固有的信息量。0I(X;Y)H(X)信息论与编码基础信息论与编码基础离散信道离散信道3、对称性);();(XYIYXI( | )(; )()log( )XYP x yI X YP xyP x()()log( ) ( )XYP xyP xyP x P y发出X后获得的关于Y的平均信息量信息论与编码基础信息论与编码基础离散信道离散信道( | )()log( ;)( )XYP y xP xyI Y XP y4、与各类熵的关系( | )(; )()log( )XYP x yI X YP xyP x()()log( ) ( )XYP xyP xyP x P y( | )()log( )

12、XYP y xP xyP y()(|)H XH X Y损失熵损失熵()( )()H XH YH XY( )(|)H YH Y X噪声熵噪声熵散布度：表示信道输入信号由于干扰作用在输出端表现的散布范围。0);(YXI)()();(YHXHYXIH(X|Y)H(Y|X)I(X;Y)H(XY)H(X)H(Y)信息论与编码基础信息论与编码基础离散信道离散信道5、);(YXI的凸函数性XYyPxyPxyPYXI)()|(log)();(xxyPxPyP)|()()(XYxxyPxPxyPxyPxPYXI)|()()|(log)|()();()|(),(xyPxPf信息论与编码基础信息论与编码基础离散信道

13、离散信道例1 设二元对称信道的输入概率空间为110)(xPX其信道特性如图，求平均互信息。定理定理在信道转移概率)|(xyP给定的条件下，平均互信息);(YXI是输入信源概率分布)(xP的型凸函数。XY0101pp1-p1-p00.51I(X;Y)1-H(p)00.51H()1信源熵信源熵信息论与编码基础信息论与编码基础离散信道离散信道定理定理在输入信源概率分布)|(xyP给定的条件下，平均互信息);(YXI是信道转移概率分布的型凸函数。)(xP例例1（续）（续）(; )()( )I X YHppH p当p = 0时(; )( )(0)( )I X YHHH当p = 1时(; )( )(1)(

14、 )I X YHHH当p = 1/2时(; )(1/2)(1/2)0I X YHH00.51pI(X;Y)H()信息论与编码基础信息论与编码基础离散信道离散信道思考题思考题令X,Y1,Y2为二进制随机变量，1）如果I(X; Y1) = 0 且 I(X; Y2) = 0，可否推出I(X; Y1, Y2) = 0? 试举例说明。2）如果 I(X; Y1) = 0 且I(X; Y2) = 0，是否可推出 I(Y1; Y2) = 0? 请说明。 信息论与编码基础信息论与编码基础离散信道离散信道若三个离散随机变量，又如下关系ZYX其中X和Y相互统计独立。试证明：)()() 1ZHXH)()()2ZHYH

15、3)( )()()( )H ZH XYH XH Y)();()4XHYZXI信息论与编码基础信息论与编码基础离散信道离散信道综合例题综合例题信息论与编码基础信息论与编码基础离散信道离散信道一、信道疑义度与平均互信息三、有噪信道编码定理定义简单离散信道的信道容量对称离散信道的信道容量扩展信道的信道容量香农公式二、信道容量二、信道容量信息论与编码基础信息论与编码基础离散信道离散信道一、信道疑义度与平均互信息三、有噪信道编码定理定义简单离散信道的信道容量对称离散信道的信道容量扩展信道的信道容量香农公式二、信道容量二、信道容量信息论与编码基础信息论与编码基础离散信道离散信道平均互信息I(X;Y)代表了

16、接收到每个输出符号后获得的关于X的平均信息量，又叫做信道的信息传输率。( | )(; )( ) ( | )log( ) ( | )XYXP y xI X YP x P y xP x P y x)|(),(xyPxPf定理定理在信道转移概率)|(xyP给定的条件下，平均互信息);(YXI是输入信源概率分布)(xP的型凸函数。定义定义一个平稳离散无记忆信道的容量C为输入与输出平均互信息);(YXI的最大值。);(max)(YXICxP说明：说明：bit/sig1）信道给定后，p(y|x)就固定，C仅与p(y|x)有关，而与P(x)无关2）Ct是信道最大传输速率。Ct = C/t bit/s信息论与

17、编码基础信息论与编码基础离散信道离散信道一、信道疑义度与平均互信息二、信道容量二、信道容量三、有噪信道编码定理定义简单离散信道的信道容量对称离散信道的信道容量扩展信道的信道容量香农公式信息论与编码基础信息论与编码基础离散信道离散信道信道信道X12: ( , ,., )rXa aaY12: ( ,.,)sYb bb( | )P y x1、无噪无损信道无噪无损信道100010001P1a1b2a2b3a3b)3 , 2 , 1,(, 1, 0)|(jijijiabPij)/(log)(max);(max)()(signbitrXHYXICxPxPI(X;Y)=H(X)-H(X|Y)信息论与编码基础

18、信息论与编码基础离散信道离散信道2、有噪无损信道有噪无损信道1000000101103530000002121P1a1b2b2a3b4b5b3a6b)/(log)(max);(max)()(signbitrXHYXICxPxPI(X;Y)=H(X)-H(X|Y)信息论与编码基础信息论与编码基础离散信道离散信道3、有损无噪信道有损无噪信道100100010010010001P1a1b2b2a3b3a4a5a6a)/(log)(max);(max)()(signbitsYHYXICxPxPI(X;Y)=H(Y)-H(Y|X)信息论与编码基础信息论与编码基础离散信道离散信道总结：总结：1）若严格区分

19、，凡）若严格区分，凡损失熵损失熵等于等于0的信道称为无损信道；的信道称为无损信道；凡凡噪声熵噪声熵等于等于0的信道称为无噪信道。的信道称为无噪信道。2）无损信道）无损信道( )max (; )log (/)P xCI X Yr bit sign3）无噪信道）无噪信道( )max (; )log (/)P xCI X Ys bit sign信息论与编码基础信息论与编码基础离散信道离散信道例例求BEC的信道容量0101e1-p1-ppp信息论与编码基础信息论与编码基础离散信道离散信道信息论与编码基础信息论与编码基础离散信道离散信道一、信道疑义度与平均互信息二、信道容量二、信道容量三、有噪信道编码定

20、理定义简单离散信道的信道容量对称离散信道的信道容量扩展信道的信道容量香农公式3131616161613131P1111336611116363P ？12,.,sp pp12 ,.,rq qq信息论与编码基础信息论与编码基础离散信道离散信道(|)( )( | )log( | )XYH Y XP xP y xP y x ),.,(log21spppHsC12(,.,)sH p pp(; )( )(|)I X YH YH Y X12( )(,.,)sH YH p pp？3131616161613131P12,.,sp pp12 ,.,rq qq信息论与编码基础信息论与编码基础离散信道离散信道3131

21、616161613131P12,.,sp pp12 ,.,rq qq例prprprpprprprpp1.11.1.111.11强对称信道信息论与编码基础信息论与编码基础离散信道离散信道有噪声的打字机信道考虑26个键的打字机1）如果每敲击一个键，它就准确地输出相应的字符，那么该容量C是多少？2）如果假设敲击一个键都会导致输出该键对应的字母或者下一个字母等概率出现，即敲A可能输出A或B，敲Z可能输出Z或A。那么此时的容量如何？信息论与编码基础信息论与编码基础离散信道离散信道本课小结本课小结2 2、平均互信息性质、平均互信息性质非负性、极值性、对称性、凸函数特性信息论与编码基础信息论与编码基础离散信

22、道离散信道1 1、平均互信息概念、平均互信息概念3 3、信道容量及其计算、信道容量及其计算信息论与编码基础信息论与编码基础离散信道离散信道一、信道疑义度与平均互信息二、信道容量二、信道容量三、有噪信道编码定理定义简单离散信道的信道容量对称离散信道的信道容量对称离散信道的信道容量扩展信道的信道容量香农公式3131616161613131P1111336611116363P ？12,.,sp pp12 ,.,rq qq信息论与编码基础信息论与编码基础离散信道离散信道(|)( )( | )log( | )XYH Y XP xP y xP y x ),.,(log21spppHsC12(,.,)sH

23、p pp(; )( )(|)I X YH YH Y X12( )(,.,)sH YH p pp？3131616161613131P12,.,sp pp12 ,.,rq qq信息论与编码基础信息论与编码基础离散信道离散信道3131616161613131P12,.,sp pp12 ,.,rq qq例prprprpprprprpp1.11.1.111.11强对称信道信息论与编码基础信息论与编码基础离散信道离散信道有噪声的打字机信道考虑26个键的打字机1）如果每敲击一个键，它就准确地输出相应的字符，那么该容量C是多少？2）如果假设敲击一个键都会导致输出该键对应的字母或者下一个字母等概率出现，即敲A可

24、能输出A或B，敲Z可能输出Z或A。那么此时的容量如何？信息论与编码基础信息论与编码基础离散信道离散信道一、信道疑义度与平均互信息二、信道容量二、信道容量三、有噪信道编码定理定义简单离散信道的信道容量对称离散信道的信道容量扩展信道的信道容量扩展信道的信道容量香农公式信息论与编码基础信息论与编码基础离散信道离散信道信息论与编码基础信息论与编码基础离散信道离散信道信道信道X12: ( , ,., )rXa aaY12: ( ,.,)sYb bb( | )P y xrsrrssPPPPPPPPPP.212222111211),.2 , 1( 10riPsjij信道信道X1212(,.,): ( , ,

25、., )NirXX XXXa aaY1212( ,.,): ( ,.,)NisYY YYYb bb( | )P y x 离散无记忆离散无记忆N次扩展信道模型次扩展信道模型1 1、信道模型、信道模型信道转移矩阵NNNNNNsrrrss.2122221112111212(.|.)NNkhhhhkkkP b bba aaNikhiiabP1)|(其中1 1、信道模型、信道模型BSC的二次扩展信道的二次扩展信道22222222pppppppppppppppppppppppp信息论与编码基础信息论与编码基础离散信道离散信道ppPpp2 2、平均互信息、平均互信息)|()();(NNNNNYXHXHYXI

26、)|()(NNNXYHYH( | )()log( )xyP y xP xyP y NNYXyx,( | )()log( )xyP x yP xyP x ()()log( ) ( )xyP xyP xyP x P ybit/N-sig信息论与编码基础信息论与编码基础离散信道离散信道定理定理对于离散无记忆信道，有NiiiNNYXIYXI1);();(;)()(|)NNNNNI XYH YH YX证明：证明：1()(|)NNiiiH YH YX111(;)( )(|)NNNiiiiiiiiI X YH YH YX信息论与编码基础信息论与编码基础离散信道离散信道12111(|)(|)(|).(|.)N

27、NNNNNNH YXH YXH YY XH YYYXNiiiNNXYHXYH1)|()|(2 2、平均互信息、平均互信息信息论与编码基础信息论与编码基础离散信道离散信道例例DMC的输入为NNXXX.1，输出为NNYYY.1且有XYXYXYXNN.2211。其中X的熵为H,计算);(NNYXI和NiiiYXI1);(HYXINN);(NiiiNHYXI1);(信息论与编码基础信息论与编码基础离散信道离散信道定理定理对于无记忆信源，则NiiiNNYXIYXI1);();(;)()(|)NNNNNI XYH YH YX1()(|)NNiiiH YH YX111(;)( )(|)NNNiiiiiiii

28、I X YH YH YX证明：证明：NiiiNNXYHXYH1)|()|(2 2、平均互信息、平均互信息信息论与编码基础信息论与编码基础离散信道离散信道例例 设无记忆信源X的熵为H，X的5次扩展源为5X信道为如下面矩阵所示的置换信道 1 2 3 4 5 3 2 5 1 4计算51);(iiiYXI);(55YXINiiixPNNxPNYXIYXIC1)()();(max);(maxCCiNCCN达到的条件：只有当信源无记忆时，每一输入变量Xi的分布P(x)各自达到最佳分布时。3 3、信道容量、信道容量信息论与编码基础信息论与编码基础离散信道离散信道一、信道疑义度与平均互信息二、信道容量二、信道

29、容量三、有噪信道编码定理定义简单离散信道的信道容量对称离散信道的信道容量扩展信道的信道容量香农公式信息论与编码基础信息论与编码基础离散信道离散信道1 1、连续消息的信息度量、连续消息的信息度量1)(,)(),()(badxxpxpbaxPX1)(,)()(dxxpxpRxPX()( )log( ( )niiiH Xp xp x 0 0()( )log( )limlogbaH Xp xp x dx 连续信源的可能取值数是无限多个，若设取值是等概率分布，那么，信源的不确定为无限大。()h X连续信源的熵1）与离散信源的熵在形式上统一；2）实际问题中常常讨论熵之间差值问题。相对熵、差熵、微分熵相对熵、差熵、微分熵信息论与编码基础信息论与编码基础离散信道离散信道1212.()().()nnnXxxxp xp xp xP(1)11( )( )( )1nna