第三章 信道容量

1、第第1章：概述章：概述第第2章：信源熵章：信源熵第第3 3章：信道容量章：信道容量第第4章：信息率失真函数章：信息率失真函数第第5章：信源编码章：信源编码第第6章：信道编码章：信道编码第第7 7章：密码体制的安全性测度章：密码体制的安全性测度3.1 单符号离散信道的数学模型单符号离散信道的数学模型3.2 单单符号离散信道的信道容量符号离散信道的信道容量3.3 多多符号离散信道的信道容量符号离散信道的信道容量3.4 网络信息理论网络信息理论3.5 连续信道连续信道3.6 信道编码定理信道编码定理3.1 单符号离散信道的数学模型单符号离散信道的数学模型P(Y/X)xY信道的数学模型：信道的数学模型

2、： X P(Y/X) Y信道的分类信道的分类无干扰无干扰信道信道有干扰有干扰信道信道信道的分类信道的分类有记忆有记忆信道信道无记忆无记忆信道信道信道的分类信道的分类单符号单符号 信道信道多符号多符号信道信道信道的分类信道的分类单用户单用户信道信道多用户多用户信道信道信道的分类信道的分类连续连续信道信道半离散半离散信道信道离散离散信道信道3.1 单符号离散信道的数学模型单符号离散信道的数学模型3.2 单单符号离散信道的信道容量符号离散信道的信道容量3.3 多多符号离散信道的信道容量符号离散信道的信道容量3.4 网络信息理论网络信息理论3.5 连续信道连续信道3.6 信道编码定理信道编码定理3.2

3、 单单符号离散信符号离散信道的信道容量道的信道容量信道容量的定义信道容量的定义3.2.2 几种特殊离散信道的容量几种特殊离散信道的容量3.2 .3 离散信道容量的一般计算方法离散信道容量的一般计算方法3.2.1 信道容量的定义信道容量的定义naaaX,21p(yi/xi)xYi=1,2,n信道转移概率矩阵：（见下页）信道转移概率矩阵：（见下页）mbbbY,21 nmnnmmabababababababababppppppppp,212222111211信道容量信道容量)()(max )()(max );(max)()()(XYHYHYXHXHYXICiiixpxpxp);(max1)(YXIt

4、Ciapt3.2 单单符号离散信符号离散信道的信道容量道的信道容量3.2.1 信道容量的定义信道容量的定义3.2 .3 离散信道容量的一般计算方法离散信道容量的一般计算方法3.2.2 几种特殊离散信道的容量几种特殊离散信道的容量一、离散无噪信道一、离散无噪信道1、一一对应的无噪信道、一一对应的无噪信道an bna1 b1a2 b21.000.0.0100.100naaaX,21nbbbY,21a1 b1a2 b2an-1 bn-1an bn00.10000.010.10.00001.000X、Y一一对应一一对应 CmaxI(X;Y)log np(ai)a1 b1 b2 b32、具有扩展功能的无

5、噪信道、具有扩展功能的无噪信道a2 b4 b5 b6a3 b7 b8 31211156422278330000000000000000bbbaaabbbaaabbaapppppppp此时，此时，H(X/Y)=0，H(Y/X) 0，且且 H(X) H(Y)。此时，此时，C = max H(X) = log n p(ai)一个输入对应多个输出一个输入对应多个输出3、具有归并性的无噪信道、具有归并性的无噪信道x1 y1x2 x3 y2x4100010010001001x5 y3C = max H(Y) = log mp(ai)H(X/Y) 0，H(Y/X) = 0多个输入变成一个输出多个输入变成一个

6、输出二、强对称二、强对称(均匀均匀)离散信道的信道容量离散信道的信道容量pnpnpnpnppnpnpnpp1111.1.111.11n X nP：总体错误概率：总体错误概率naaaX,21mbbbY,21niniininjijijininjijijiHnppppnppppapnnpnpppabpabpapabpabpapXYH1log)1log()1(1log)1log()1)() 1)(1log1()1log()1 ()/(log)/()()/(log)/()()/(napi1)(相应的相应的ninapapapHnHYHXYHYHYXICiiiilog )(max )/()(max );(m

7、ax)()()(二进制均匀信道容量二进制均匀信道容量 C1H(p),其中 H(p)=-(1-p)log(1-p)+plogp)二进制均匀信道容量曲线二进制均匀信道容量曲线三、对称离散信道的信道容量三、对称离散信道的信道容量矩阵中的每行都矩阵中的每行都 是集合是集合P = p1, p2, , pn中的诸元素的不同排列，称中的诸元素的不同排列，称矩阵的行是可排列的。矩阵的行是可排列的。 矩阵中的每列都是集合矩阵中的每列都是集合Q = q1, q2, ,qm中的诸元素的不同排列，称中的诸元素的不同排列，称矩阵的列是可排列的。矩阵的列是可排列的。如果矩阵的行和列都是可排列的，如果矩阵的行和列都是可排列

8、的，称矩阵是可排列的。称矩阵是可排列的。如果一个信道矩阵具有可排列性，如果一个信道矩阵具有可排列性，则它所表示的信道称为则它所表示的信道称为对称信道中，当对称信道中，当nmnmnm，Q Q是是P P的子集；当的子集；当n=mn=m时，时，P=QP=Q。对称信道对称信道练习：判断下列矩阵表示的信道是否是对练习：判断下列矩阵表示的信道是否是对 称信道称信道 61316131616131313p 40.7 0.2 0.10.1 0.2 0.7p 31316161616131311p3121612161316131212pnapi1)(相应的相应的minimjijijinimjijijiHabpabp

9、apabpabpapXYH )/(log)/()( )/(log)/()()/(1111mimiapHmHYHCilog)(max)(强对称信道与对称信道强对称信道与对称信道比较比较： 强对称强对称 对称对称 n=m n与与m未必相等未必相等 矩阵对称矩阵对称 矩阵未必对称矩阵未必对称 P=Q P与与Q未必相等未必相等行之和，列之和均行之和，列之和均为为1行之和为行之和为1四、准对称信道离散信道的信道容量四、准对称信道离散信道的信道容量若信道矩阵的行是可排列的，但列不可若信道矩阵的行是可排列的，但列不可排列，如果把列分成若干个不相交的子集，排列，如果把列分成若干个不相交的子集，且由且由n n行

10、和各子集的诸列构成的各个子矩阵行和各子集的诸列构成的各个子矩阵都是可排列的，则称相应的信道为准对称都是可排列的，则称相应的信道为准对称信道。例如下面的矩阵：信道。例如下面的矩阵：8181214181814121miHXYH)/()(max)(miapHYHCi假设此时将矩阵的列分为假设此时将矩阵的列分为S S个子集，每个子集，每个子集的元素个数分别是个子集的元素个数分别是m m1 1，m m2 2，m ms s。ssmjjsjsmjjjmjjjbPbPbPbPbPbPYH)(log)(.)(log)()(log)()(11113.2 单单符号离散符号离散信道信道3.2.1 信道容量的定义信道容

11、量的定义3.2.2 几种特殊离散信道的容量几种特殊离散信道的容量3.2.3 3.2.3 离散信道容量的一般计算方法离散信道容量的一般计算方法 对一般离散信道而言，求信道容量，就是在固定信对一般离散信道而言，求信道容量，就是在固定信道的条件下，对所有可能的输入概率分布道的条件下，对所有可能的输入概率分布p(xi)，求平，求平均互信息的极大值。采用拉各朗日乘子法来计算。均互信息的极大值。采用拉各朗日乘子法来计算。niiaPYXI1)();(设:,0)(则有令iaP()() (/)njijiip bp ap ba()(/)()jjiidp bp badp aexxloglnlognimjniiiji

12、jimjjjiapabpabpapbpbpap11111)()/(log)/()()(log)()( / )log ( )( / )log( )( / )log ( / )0mjijjijimjijijp b ap bp b aep ap b ap b a11(/)log (/)(/)log ( )log0mmjijijijjjp b ap b ap b ap be11(/)log(/)(/)log()logmjijijmjijjp bap bap bap be (1)两边乘两边乘p(ai)，并求和，则有：，并求和，则有：2112112() ()log()() ()log()lognmijij

13、iijnmijijijp a p bap bap a p bap be2(; )logI X Ye2logCe(2)将（将（2 2）代入（）代入（1 1），则有：），则有：(/)log(/)(/)log()(/)log()mjijijmjijjmjijjp bap bap bap bCp bap bC（3）log()jjp bC令（4）(/)log (/)(/)mjijijmjjijp bap bap ba则（则（3）变为：）变为：:22(4)log()()2122logjjjmjjjjmmCjjjmCjp bCp bC由求出（5） （6）（7）1(5)()2()() (/)()jCjnjij

14、iiip bp bp ap bap a由求出由求出（8）（9）并验证。求由求由求由求由)()9(.4);()8(.3;)7(.2;)4(.1ijjaPbPC：信道矩阵如下，求：信道矩阵如下，求C C。101121221(1)log(1) log(1)loglog(1)1log(1) 0log01log121210111121 (1)log2log2mjjC 111()2()2211(1)jCjCCp bp b 232111()1()(1)1(1)p bp b )()()()()( 2121111abpapabpapbp42121222( )( ) ( / )( ) ( /)p bp a p b

15、 ap a p b a11222()()()()(1) ()p bp ap ap bp a11111121()1(1)()1(1)p ap a 100)(),(21apap3.1 单符号离散信道的数学模型单符号离散信道的数学模型3.2 单单符号离散信道的信道容量符号离散信道的信道容量3.3 多多符号离散信道的信道容量符号离散信道的信道容量3.4 网络信息理论网络信息理论3.5 连续信道连续信道3.6 信道编码定理信道编码定理3.3 多多符号离散信符号离散信道的信道容量道的信道容量3.3.2 离散无记忆扩展信道的信离散无记忆扩展信道的信道容量道容量3.3.3 独立并联信道的信道容量独立并联信道的

16、信道容量多符号离散信道多符号离散信道 多符号信源通过离散信道传输形多符号信源通过离散信道传输形成多符号离散信道。成多符号离散信道。3.3.1 多符号离散信道的数学模型多符号离散信道的数学模型1212.NNXX XXYYYYYXYPX)(121 2KnKnXaaaYbbb12Niiiia aanii iN,.,2 , 1.21Nni,.,2,112Njjjjb bbNmj,.,2,1mjjjN,.,2 , 1.21YYXPX)(112111222212()().()()().().()() .()NNNNNNmmnmnnppppppppp 3.3 多多符号离散信符号离散信道的信道容量道的信道容量

17、3.3.2 离散无记忆扩展信道的信离散无记忆扩展信道的信道容量道容量3.3.3 独立并联信道的信道容量独立并联信道的信道容量3.3.2 离散无记忆扩展信道的信道容量离散无记忆扩展信道的信道容量无记忆：无记忆：YK仅与仅与XK有关有关121211221(/)(./.)(/)(/).(/)(/)NNNNNiiiP YXP Y YYX XXP YXP YXP YXP YX)/()();(XYHYHYXI1X)(11XYP)(NNXYPNXXY1YNY11121212121211112( /).(.) (.)log(.)NNNNNNNnnmmiiijjjiiiiijjjjjiiiH Y Xp a aa

18、p b bba aap b bba aa 1211111111112() ()()log()()NNNNNNNnnmmiiijijiiijjjijip a aap b ap bap b ap ba 11111112222222222() ()log()() ()log().() ()log()NNNNNNNnmijijiijnmijijiijnmijijiijp ap bap bap ap bap bap ap bap ba 11221(/)(/).(/)(/)KKNKKKH YXH YXH YXH YXNKKKYXIYXI1);();(a)NKKKNKKNKKNNKKKNNKKKXYHYHY

19、XIYHYYYHXYHYYYHXYHYHYXI111211211 )/()();()().()/().()/()();(也是无记忆的要求等号成立相互独立，NCCYXNIYXIXaYYYKKN 2 121);();( .XX )( . 3.3 多多符号离散信符号离散信道的信道容量道的信道容量3.3.2 离散无记忆扩展信道的信离散无记忆扩展信道的信道容量道容量3.3.3 独立并联信道的信道容量独立并联信道的信道容量3.3.3 独立并联信道的信道容量 将离散无记忆信道的N次扩展信道加以推广，也就是令信道的输入个输出随机变量序列中的各随机变量分别取值去不同的符号集合，就构成了独立并联信道，也称独立并列

20、信道、独立平行信道或积信道。NkCNCk如果用表示 个独立并联信道的容量，表示第 个单符号离散无记忆信道的信道容量，则有121.NNNkkCCCCCkNkNXCC当 个输入随机变量之间统计独立，且每个输入随机变量的概率分布为达到各自信道容量的最佳分布时，达到最大值m ax1NNkkCC3.1 单符号离散信道的数学模型单符号离散信道的数学模型3.2 单单符号离散信道的信道容量符号离散信道的信道容量3.3 多多符号离散信道的信道容量符号离散信道的信道容量3.4 网络信息理论网络信息理论3.5 连续信道连续信道3.6 信道编码定理信道编码定理3.4 3.4 网络信息理论网络信息理论3.4.2 广播信

21、道的信道容量广播信道的信道容量3.4 .3 相关信源的边信息和公信相关信源的边信息和公信息息3.4.1 多址接入信道的信道容量多址接入信道的信道容量多入单出信道多入单出信道信源信源1 1信源信源2 21 u2 u编码器编码器1 1编码器编码器2 21u2u信道信道译码译码12CY1a2a二址接入信道模型1 111121.nXaaa1 221222.nXaaa121222 nYb bb11uu11RC112(;/)RI X Y X12112()()max(;/)P XP XCI X YX22RC12221()()max(;/)P XP XCI X YX121212()()max(; )P XP

22、XCI X X Y1212RRC121212max(,)C CCCCR2 C20 C1 C12C1+C2R13.4 3.4 网络信息理论网络信息理论3.4.2 广播信道的信道容量广播信道的信道容量3.4 .3 相关信源的边信息和公信相关信源的边信息和公信息息3.4.2 3.4.2 广播信道的信道容量广播信道的信道容量广播信道广播信道具有单个输入和多个输出的信道。1U信源信源1 1编码器编码器信道信道信源信源2 2译码器译码器2 2译码器译码器1 12U1U2UX1Y2Y图3.4.4 单输入双输出广播信道模型退化广播信道（串联）编码器编码器信道信道1 11U2UX1Y2Y信道信道2 21()P

23、Y X21()P Y Y图3.4.5 退化的广播信道模型)/()()/(12121bbpxbpxbbp2121(/)(/)p bb xp bb)/()/(1212YYHXYYH21YYX、构成马尔可夫链);();(121YXIYYXI)(xp)(xp不变)()(21upup、，保持);(1YXI最大)/;(211uYXIR )/;(122uYXIR );(121YXIRR3.4 3.4 网络信息理论网络信息理论3.4.2 广播信道的信道容量广播信道的信道容量3.4 .3 相关信源的边信息和公信相关信源的边信息和公信息息模型13.4.3 3.4.3 相关信源的边信息与公信息相关信源的边信息与公信

24、息1X信信源源2X编码器编码器1 1编码器编码器2 2信道信道1 1信道信道2 2译码器译码器1 1译码器译码器2 22X1X相关信源多用户信道)/(211XXHC )/(122XXHC )(2121XXHCCC2)(21XXH)(21XXH)/(21XXH)(1XH)(2XH)/(12XXHC1E1C1D1x1x21x)/(21XXH边信息边信息模型模型2RE1E2C1C2D1D2x1x21x2xE0C0w012(;)RI X X WW:公信息公信息11(/)RH XW22(/)RH XW要求要求R0尽可能小，并且在尽可能小，并且在W条件下，条件下，X1X2无关无关);(min21WXXIW3.1 单符号离散信道的数学模型单符号离散信道的数学模型3.2 单