信息论与编码-第章信道容量ppt课件

1、网络网络工程系工程系- -Information Theory and Coding第三章信道容量赵永斌石家庄铁道大学信息科学与技术学院 2021年5月27日网络网络工程系工程系- -Information Theory and Coding信道及其容量3.1 信道容量的数学模型和分类3.2 单符号离散信源3.3 多符号离散信源3.4 连续信道3.5 信道编码定理网络网络工程系工程系- -Information Theory and Coding回忆信道是传输信息的媒质或通道。（输入信道是传输信息的媒质或通道。（输入信道信道输出）输出）说明说明（1信道输入是随机过程。信道输入是随机过程。（2信

2、道响应特性是条件概率信道响应特性是条件概率P(输出值为输出值为y|输入值为输入值为x)，又称为转移概率。又称为转移概率。（3信道输出是随机过程，输出的概率分布可以由输入信道输出是随机过程，输出的概率分布可以由输入的概率分布和信道的响应特性得到。（全概率公式）的概率分布和信道的响应特性得到。（全概率公式）（4根据信道输入、信道响应特性、信道输出的情况，根据信道输入、信道响应特性、信道输出的情况，可将信道分类：离散信道又称为数字信道）；连续信可将信道分类：离散信道又称为数字信道）；连续信道又称为模拟信道）；特殊的连续信道道又称为模拟信道）；特殊的连续信道波形信道；波形信道；恒参信道和随参信道；无记

3、忆信道和有记忆信道等恒参信道和随参信道；无记忆信道和有记忆信道等网络网络工程系工程系- -Information Theory and Coding回忆“离散的含义是时间离散，事件离散。即：信道的输入、输出时刻是离散的，且输入随机变量和输出随机变量都是离散型的随机变量。“无记忆的含义是信道响应没有时间延迟，当时的输出只依赖于当时的输入。“平稳的含义是信道在不同时刻的响应特性是相同的。网络网络工程系工程系- -Information Theory and Coding无干扰无干扰信道信道有干扰有干扰信道信道3.1 信道容量的数学模型和分类信道的分类信道的分类有记忆信道有记忆信道无记忆信道无记忆信

4、道单符号单符号 信道信道多符号多符号信道信道单用户信道单用户信道多用户信道多用户信道连续信道连续信道半离散信道半离散信道离散信道离散信道网络网络工程系工程系- -Information Theory and Coding62022-2-1信道分类定义定义:假如假如（1信道的输入为随机变量序列信道的输入为随机变量序列X1, X2, X3, ，其，其中每个随机变量中每个随机变量Xu的事件集合都是的事件集合都是0, 1, , K-1，（2信道的输出为随机变量序列信道的输出为随机变量序列Y1, Y2, Y3, ，其，其中每个随机变量中每个随机变量Yu的事件集合都是的事件集合都是0, 1, , J-1，

5、则称该信道为离散信道。则称该信道为离散信道。网络网络工程系工程系- -Information Theory and Coding72022-2-1信道分类如果更有（3P(Y1Y2YN)=(y1y2yN)|(X1X2XN)=(x1x2xN)=P(Y1=y1|X1=x1)P(Y2=y2|X2=x2)P(YN=yN|XN=xN)，则称该信道为离散无记忆信道DMC）。如果更有（4对任意x0, 1, , K-1，y0, 1, , J-1，任意两个时刻u和v，还有P(Yu=y|Xu=x)=P(Yv=y|Xv=x)，则称该信道为离散无记忆平稳信道或恒参信道。 网络网络工程系工程系- -Information

6、 Theory and Coding 信道容量的数学模型噪声噪声介质缺陷介质缺陷XY信源信源编码编码信道信道编码器编码器调制器调制器（写入头）（写入头）信信 道道（存储介质）（存储介质）解调器解调器（写入（写入头）头）信道信道译码器译码器信源信源译码译码转移转移概率概率矩阵矩阵p(Y|X)p(Y|X)XY网络网络工程系工程系- -Information Theory and Coding信道容量的数学模型P(Y/X)xY信道的数学模型：信道的数学模型： X P(Y/X) Y信道在某一时刻u的响应特性P(Yu=y|Xu=x)； x0, 1, , K-1，y0, 1, , J-1，网络网络工程系工

7、程系- -Information Theory and Coding信道容量的数学模型l 二元对称信道BSCl当N1时lp(0/0)=p(1/1)=0.9,p(1/0)=p(0/1)=0.1l 当N=2时，l p(00/00)=p(11/11)= p(0/0) p(0/0)= 0.9*0.9=0.81l P(10/00)=p(01/00)=p(01/11)=p(10/11)=0.1*0.9 =0.09l P(11/00)=p(00/11)=0.1*0.1=0.010.90.900110.10.1网络网络工程系工程系- -Information Theory and Coding112022-2

8、-1信道容量的数学模型（1转移概率矩阵的每一行都是一个概率向量。 ) 1| 1() 1| 1 () 1| 0 () 1 | 1() 1 | 1 () 1 | 0 () 0 | 1() 0 | 1 () 0 | 0 (KJpKpKpJpppJppp1)| 1, 1 , 0()|(10 xXJYPxypxJy，对任意网络网络工程系工程系- -Information Theory and Coding12信道容量的数学模型（2对任意y0, 1, , J-1，由全概率公式有10)|()()(Kxxypxqyw) 1| 1() 1| 1 () 1| 0 () 1 | 1() 1 | 1 () 1 | 0

9、 () 0| 1() 0| 1 () 0| 0 ()1(,),1 (),0 ()1(,),1 (),0 (KJpKpKpJpppJpppKqqqJwww网络网络工程系工程系- -Information Theory and Coding3.2 单符号离散信道的信道容量单符号离散信道的信道容量网络网络工程系工程系- -Information Theory and Coding信道容量的定义信道容量的定义I(X; Y)是概率向量q(x), x0, 1, , K-1和转移概率矩阵p(y|x)，x0, 1, , K-1，y0, 1, , J-1的函数。 1100111000( | )(; )()()l

10、og( )( | )( ) ( | )log( ) ( | )KJxyKJKxyzp y xI X YPXYxyp yp y xp x p y xp z p y z网络网络工程系工程系- -Information Theory and Coding信道容量的定义信道容量的定义设转移概率矩阵p(y|x)，x0, 1, , K-1，y0, 1, , J-1（是信道的响应特性确定，希望选择概率向量q(x), x0, 1, , K-1使I(X; Y) 达到最大。网络网络工程系工程系- -Information Theory and Coding信道容量信道容量)()(max )()(max );(ma

11、x)()()(XYHYHYXHXHYXICiiixpxpxp);(max1)(YXItCiapt信道单位时间传信道单位时间传输的最大信息量输的最大信息量网络网络工程系工程系- -Information Theory and Coding定义离散无记忆信道的信道容量定义为如下的定义离散无记忆信道的信道容量定义为如下的C。达到信道容量的输入概率分布达到信道容量的输入概率分布x, p(x), x0, 1, , K-1称为最佳输入分布。称为最佳输入分布。 其中其中 ( ),0,1, ,1 max( ; )pp x xKKCI X Y跑遍所有的 维概率向量L信道容量表示了信道传送信息的最大能力，这个量在

12、信息论信道容量表示了信道传送信息的最大能力，这个量在信息论研究中有重要意义。传送的信息量必须小于信道容量研究中有重要意义。传送的信息量必须小于信道容量C信道容量的定义信道容量的定义网络网络工程系工程系- -Information Theory and Coding3.2.2 几种特殊离散信道的容量几种特殊离散信道的容量定义：DMC的转移概率矩阵为 若P的任一行是第一行的置换，则称信道是关于输入为对称的。若P的任一列是第一列的置换，则称信道是关于输出为对称的。若信道是关于输入为对称的，又是关于输出为对称的，则称信道为对称信道。) 1| 1() 1|0() 1|0() 1 | 1() 1 | 1

13、() 1 |0()0| 1()0| 1 ()0|0(JKpJpJpKpppKpppP网络网络工程系工程系- -Information Theory and Coding3.2.2 几种特殊离散信道的容量几种特殊离散信道的容量一、离散无噪信道一、离散无噪信道1、一一对应的无噪信道、一一对应的无噪信道an bna1 b1a2 b21.000.0.0100.100naaaX,21nbbbY,21网络网络工程系工程系- -Information Theory and Codinga1 b1a2 b2an-1 bn-1an bn00.10000.010.10.00001.000X、Y一一对应一一对应Cm

14、ax I(X;Y)log np(ai)网络网络工程系工程系- -Information Theory and Codinga1 b1 b2 b32、具有扩展功能的无噪信道、具有扩展功能的无噪信道a2 b4 b5 b6a3 b7 b8 38372625241312110000000000000000ababababababababppppppp网络网络工程系工程系- -Information Theory and Coding此时，此时，H(X/Y)=0，H(Y/X) 0，且且 H(X) H(Y)。此时，此时，C = max H(X) = log n p(ai)一个输入对应多个输出一个输入对应多

15、个输出网络网络工程系工程系- -Information Theory and Coding3、具有归并性的无噪信道、具有归并性的无噪信道x1 y1x2 x3 y2x4100010010001001x5 y3C = max H(Y) = log mp(ai)H(X/Y) 0，H(Y/X) = 0多个输入变成一个输出多个输入变成一个输出网络网络工程系工程系- -Information Theory and Coding二、强对称二、强对称(均匀均匀)离散信道的信道容量离散信道的信道容量 p：总体错误概率：总体错误概率naaaX,21mbbbY,21pnpnpnpnppnpnpnpp1111.1.1

16、11.11n n网络网络工程系工程系- -Information Theory and Coding( | )( ) (/)log (/)( )(/)log (/)Remark:(1)log(1)(log)(1)11( )(1)log(1)log1(1)log(1)log1nnijijiijnnijijiijniiniH Y Xp a p bap bap ap bap bappppnnnpp apppnppppnH 网络网络工程系工程系- -Information Theory and Codingnapi1)(相应的相应的()()()max (; ) max( )(|) max( ) log

17、iiiip ap anp aniCI X YH YH Y XH YHnH网络网络工程系工程系- -Information Theory and Coding二进制均匀信道容量二进制均匀信道容量 C1H(p),其中其中 H(p)=-(1-p)log(1-p)+plogp)二进制均匀信道容量曲线二进制均匀信道容量曲线网络网络工程系工程系- -Information Theory and Coding三、对称离散信道的信道容量三、对称离散信道的信道容量矩阵中的每行都矩阵中的每行都 是集合是集合P = p1, p2, , pn中的诸元素的不同排列，中的诸元素的不同排列，称矩阵的行是可排列的。称矩阵的行

18、是可排列的。矩阵中的每列都是集合矩阵中的每列都是集合Q = q1, q2, ,qm中的诸元素的不同排列，中的诸元素的不同排列，称矩阵的列是可排列的。称矩阵的列是可排列的。网络网络工程系工程系- -Information Theory and Coding如果矩阵的行和列都是可排列的，称矩阵是可排列的。如果一个信道矩阵具有可排列性，则它所表示的信道称为对称信道中，当对称信道中，当nm，Q是是P的子集；当的子集；当n=m时，时，P=Q。对称信道对称信道网络网络工程系工程系- -Information Theory and Coding练习：判断下列矩阵表示的信道是否是对称信道练习：判断下列矩阵表示

19、的信道是否是对称信道 61316131616131313p 40.7 0.2 0.10.1 0.2 0.7p 31316161616131311p3121612161316131212p网络网络工程系工程系- -Information Theory and Codingnapi1)(相应的相应的1111(|)( ) (/)log (/) ( )(/)log (/) nmijijiijnmijijiijmiH Y Xp a p bap bap ap bap baH mimiapHmHYHCilog)(max)(网络网络工程系工程系- -Information Theory and CodingC

20、H1 1 1 1log4(,)3 3 6 611112log3log3log6log633660.817 P1111336611116633 信道的转移概率矩阵为:例网络网络工程系工程系- -Information Theory and Coding强对称信道与对称信道比较：强对称信道与对称信道比较： 强对称强对称 对称对称 n=m n与与m未必相等未必相等 矩阵对称矩阵对称 矩阵未必对称矩阵未必对称 P=Q P与与Q未必相等未必相等行之和，列之和均为行之和，列之和均为1行之和为行之和为1网络网络工程系工程系- -Information Theory and Coding四、准对称信道离散信道

21、的信道容量四、准对称信道离散信道的信道容量若信道矩阵的行是可排列的，但列不可排列，如果把列分成若干个不相交的子集，且由n行和各子集的诸列构成的各个子矩阵都是可排列的，则称相应的信道为准对称信道。例如下面的矩阵：网络网络工程系工程系- -Information Theory and Coding8181214181814121miHXYH)/()()max( )max( )iimimip ap aCH YHH YH网络网络工程系工程系- -Information Theory and Coding假设此时将矩阵的列分为S个子集，每个子集的元素个数分别是m1，m2，ms。准对称信道离散信道的信道容

22、量准对称信道离散信道的信道容量ssmjjsjsmjjjmjjjbPbPbPbPbPbPYH)(log)(.)(log)()(log)()(1111网络网络工程系工程系- -Information Theory and Coding准对称信道离散信道的信道容量准对称信道离散信道的信道容量21()logskkkkH Ym p bp b 2121( ) log,skkkmkH Ym p bp bH q qq网络网络工程系工程系- -Information Theory and Coding网络网络工程系工程系- -Information Theory and Coding3.2.3 离散信道容量的一

23、般计算方法离散信道容量的一般计算方法 对一般离散信道而言，求信道容量，就是在固定信对一般离散信道而言，求信道容量，就是在固定信道的条件下，对所有可能的输入概率分布道的条件下，对所有可能的输入概率分布p(xi)，求平，求平均互信息的极大值。采用拉各朗日乘子法来计算。均互信息的极大值。采用拉各朗日乘子法来计算。(;)()1|()1niiniiIXYP aHYHYXP a设:,0)(则有令iaP原因？原因？网络网络工程系工程系- -Information Theory and Coding()()(/)njijiip bp ap ba()(/)()jjiidp bp badp aexxloglnlo

24、gnimjniiijijimjjjiapabpabpapbpbpap11111)()/(log)/()()(log)()(网络网络工程系工程系- -Information Theory and Coding(/)log()(/)log()(/)log(/)0 mjijjijimjijijp bap bp baep ap bap ba11(/)log(/)(/)log()log0mmjijijijjjp bap bap bap be 网络网络工程系工程系- -Information Theory and Coding11(/)log(/)(/)log()logmjijijmjijjp bap b

25、ap bap be (1)两边乘两边乘p(ai)，并求和，则有：，并求和，则有：网络网络工程系工程系- -Information Theory and Coding2112112()() log()()() log()lognmijijiijnmijijijp ap bap bap ap bap be 2(;)logIXYe2logCe(2)网络网络工程系工程系- -Information Theory and Coding将将2 2代入代入1 1），则有：），则有：（3）(/) log(/)(/) log()(/)log()mjijijmjijjmjijjp bap bap bap bCp

26、bap bC网络网络工程系工程系- -Information Theory and Codinglo g()jjpbC令（4）(/)log(/)(/)mmjjijijijjp bap bap ba那么那么3变为：变为：网络网络工程系工程系- -Information Theory and Coding:2(4)log()()2122log2jjjjjmmCjjjmCjmjjp bCp bC由解 方 程 ， 求 出（5） （6）（7）网络网络工程系工程系- -Information Theory and Coding1(5)()2()()(/)()jCjnjijiiip bp bp ap bap

27、 a由求出由求出（8）（9）网络网络工程系工程系- -Information Theory and Coding离散信道容量的一般计算方法离散信道容量的一般计算方法l总结总结C的求法，过程如下：的求法，过程如下：l1.求求jl2.求求Cl3.求求p(bj)l4.求求p(ai)(/)log (/)(/)mmjjijijijjp bap bap ba2log2mjjC()2jCjp b1()() (/)njijiip bp ap ba网络网络工程系工程系- -Information Theory and Coding101网络网络工程系工程系- -Information Theory and Co

28、ding12121 log1 0 log0 0111221(1)lo g(1) lo g (1)lo glo g (1)1lo g(1) 网络网络工程系工程系- -Information Theory and Coding1121 (1)log 2log 2mjjC 111()2()2211(1)jCjCCp bp b 23网络网络工程系工程系- -Information Theory and Coding2111()1()(1)1(1)p bp b 网络网络工程系工程系- -Information Theory and Coding1111212( )() ()() ()p bp a p b

29、 ap ap b a42121222()() (/)() (/)p bp ap bap ap ba11222()()()()(1)()p bp ap ap bp a网络网络工程系工程系- -Information Theory and Coding11111121()1(1)()1(1)p ap a100)(),(21apap网络网络工程系工程系- -Information Theory and Coding3.3 多符号离散信道多符号离散信道3.3.1 多符号离散信道的数学模型3.3.2 离散无记忆信道的N次扩展信道和独立并联信道的信道容量网络网络工程系工程系- -Information T

30、heory and Coding多符号离散信道多符号离散信道 多符号信源通过离散信道传输形多符号信源通过离散信道传输形成多符号离散信道。成多符号离散信道。3.3.1 多符号离散信道的数学模型网络网络工程系工程系- -Information Theory and Coding3.3.1 多符号离散信道的数学模型多符号离散信道的数学模型1212.NNXX XXYYYYYXYPX)(121 2KnKnXaaaYbbb12Niiiia aanii iN,.,2 , 1.21Nni,.,2,112NjjjjbbbNmj,.,2,1输入输入mjjjN,.,2 , 1.21输出输出网络网络工程系工程系- -

31、Information Theory and CodingYYXPX)(112111222212()().()()().().()() .()NNNNNNmmnmnnppppppppp 网络网络工程系工程系- -Information Theory and Coding3.3.2 离散无记忆信道的N次扩展信道 独立并联信道的信道容量无记忆：无记忆：YK仅与仅与XK有关有关121211221(/)(./.)(/)(/).(/)(/)NNNNNiiiP YXP Y YYX XXP YXP YXP YXP YX网络网络工程系工程系- -Information Theory and Coding)/(

32、)();(XYHYHYXI1X)(11XYP)(NNXYPNXXY1YNY网络网络工程系工程系- -Information Theory and Coding11121212121211112( /).(.) (.)log(.)NNNNNNNnnmmiiijjjiiiiijjjjjiiiH Y Xp a aap b bba aap b bba aa 1211111111112() ()()log()()NNNNNNNnnmmiiijijiiijjjijip a aap b ap bap b ap ba 网络网络工程系工程系- -Information Theory and Coding1111

33、1112222222222()() log()()() log().()() log() NNNNNNNnmijijiijnmijijiijnmijijiijp ap bap bap ap bap bap ap bap ba11221(/)(/).(/)(/)KKNKKKH YXH YXH YXH YX网络网络工程系工程系- -Information Theory and CodingNKKKYXIYXI1);();(a) NKKKNKKXYHYHYXI11)/()();(NKKNYHYYYH121 )().(NKKKNXYHYYYH121)/().(NKKKXYHYHYXI1)/()();(

34、网络网络工程系工程系- -Information Theory and Coding也是无记忆的要求等号成立相互独立，NCCYXNIYXIXaYYYKKN 2 121);();( .XX )( . 网络网络工程系工程系- -Information Theory and Coding652022-2-1(积信道积信道)定义信道的输入事件为全体定义信道的输入事件为全体(x, u)，共有，共有KN个输入事个输入事件；件；信道的输出事件为全体信道的输出事件为全体(y, v)，共有，共有JM个输出事件；个输出事件；转移概率矩阵为转移概率矩阵为p(y, v)|(x, u)(KN)(JM)，其中其中p(y,

35、 v)|(x, u)= p1(y|x)p2(v|u)。则称该信道为信道则称该信道为信道1与信道与信道2的积信道。（又称该信的积信道。（又称该信道为信道道为信道1与信道与信道2的独立并行信道）的独立并行信道）（在物理上，积信道是两个信道的并行使用）（在物理上，积信道是两个信道的并行使用） 网络网络工程系工程系- -Information Theory and Coding662022-2-1积信道积信道积信道的信道容量为积信道的信道容量为C=C1+C2，最佳输入分布为最佳输入分布为(x, u), q(x, u)，其中，其中q(x, u)=q1(x)q2(u)。网络网络工程系工程系- -Infor

36、mation Theory and Coding和信道定义信道的输入事件为全体定义信道的输入事件为全体xu，其中，其中x与与u不相交；共有不相交；共有K+N个输入事件；个输入事件；信道的输出事件为全体信道的输出事件为全体yv，其中，其中y与与v不不相交；共有相交；共有J+M个输出事件；个输出事件；信道的转移概率矩阵为信道的转移概率矩阵为)()(21)|(00)|(MJNKMNJKuvpxyp网络网络工程系工程系- -Information Theory and Coding和信道则称该信道为信道1与信道2的和信道或称并信道）。任一单位时间可随机地选用一个信道，而不能同时选用两个信道 。若选用信道1的概率为P1，选用信道2的概率为P2，则P1+ P2=1。网络网络工程系工程系- -Information Theory and Cod