离散信道及其容量

离散信道及其容量 第 6 章 北京邮电大学 信息工程学院 信道是信号的传输媒介 ， 是传送信息的物理通道 。 研究信道的目的主要是为了解决信息如何有效 、 可靠地传输的问题 。 本章重点解决某些特殊信道容量的计算问题 。 第 4章 离散信道及其容量 概述 单符号离散信道及其容量 级联信道及其容量 信道容量的迭代计算 本章主要内容 多维矢量信道及其容量 6.1 概述 信道的分类 离散 信道的数学模型 信道容量的定义 信源A信宿 译码器连续信道编码器 数字调制器数字解调器噪 声A CCBB 6.1.1 信道的分类 数字通信系统的基本模型 依据不同的条件，不同模块之间的通道可以划分为不同的信道 6.1.1 信道的分类 按输入、输出集合的取值分类 按输入、输出集合的个数分类 按信道转移概率的性质分类 根据信道统计特性划分 根据信道噪声性质划分 6.1.1 信道的分类 1) 离散信道：输入和输出均为离散集，如 B-B 2) 连续信道：输入和输出均为连续集，也称波形信道，其特点是时间与取值都连续，如 C-C 3) 半连续（或半离散）信道：输入和输出一个为连续、一个为离散，如 B-C 或 C-B 4) 时间离散连续信道：连续取值但时间离散，例如信道的输入和输出为模拟信号抽样的情况。 按输入、输出集合的取值分类 6.1.1 信道的分类 1) 单用户信道： X,Y中各有一个事件集，称单路或单端信道 2) 多用户信道： X,Y中至少有一端是多个事件集，也称多端信道。多用户信道包含两种特殊的信道，即多元接入信道和广播信道。 多元接入信道就是多个输入、单个输出的信道 广播信道就是单个输入、多个输出的信道 按输入、输出集合的个数分类 无损信道 （每个输入对应多个输出） 确定信道 （多个输入对应单个输出） 无扰信道 （一个输入对应一个输出） 按信道转移概率的性质分类 6.1.1 信道的分类 1）无噪声信道 2）有噪声信道 无记忆信道 给定时间输出仅依赖于当前输入 有记忆信道 输出值不仅依赖于当前输入又依赖于以前的输入 根据信道统计特性划分 1）恒参信道 6.1.1 信道的分类 2）变参信道 统计特性不随时间变化（也称平稳信道）例如：卫星通信信道 统计特性随时间变化。例如：短波，移动通信信道 根据信道噪声性质划分 1）高斯噪声信道 6.1.1 信道的分类 2）非高斯噪声信道 信道噪声为高斯分布（白噪声或有色噪声） 信道噪声分布不是高斯分布 信道噪 声X YP(y|x) 6.1.2 离散信道的数学模型 离散无记忆信道 一般的信道数学模型 离散无记忆信道 平稳（或恒参）信道 单符号离散信道 ),|,()|( 2121 NN xxxyyypxyp NN YxypX ),|(, 一般信道的数学模型 信道模型 NN XXXX 21 Nxxxx , 21 NXx NN YYYY 21 Nyyyy , 21 NYy Nnnn xypxyp1)|()|( ),|(, YxypX nn离散无记忆信道 则称为此信道为离散无记忆信道（ DMC），其数学模型为： 利用给定时刻的输出符号仅依赖于当前输入符号的条件可以推出。 若信道的转移概率满足 )|()|( imjminjn axbypaxbyp 平稳 (或恒参 )信道 BbAa ii , 如果对于任意正整数 m、 n，和 离散无记忆信道的转移概率满足： 则称为平稳或恒参信道 可见，对于平稳信道， 不随时间变化。这样，平稳信道的模型就是 )|( nn xyp , ( | ) , X p y x Y其中，信道的输入 X与输出 Y都是一维随机变量集合，xX ，取自字母表 , 。 yY ，取自字母表 ,., 1 raaA ,., 1 sbbB /( | ) ( | ) ( | )j i Y X j i i jp y x p y b x a P b a p 单符号离散信道 对于离散平稳无记忆信道，可以用一维条件概率描述 这种用一维条件概率描述的信道为为：单符号离散信道 信道转移概率简记为： rsrrsspppppppppP212222111211的概率转移到是由 jiij bap单符号离散信道 信道转移概率矩阵 单符号离散信道 二元对称信道 (BSC)，输入与输出符号集分别为 ，信道转移概率 p(y/x)满足 ， 称为错误率 。 写出信道的转移概率矩阵并画出转移概率图。 1,0,1,0 BA/( 0 | 0 ) ( 1 | 1 ) 1Y X Y XPP 11 P6.1.1 例 解： 转移概率矩阵 转移概率图 0 1- 1 0 1 1- qqppP1001单符号离散信道 二元删除信道：其中 A=0,1, B=0,2,1画 出转移概率图和转移概率矩阵。 6.1.2 例 解： 转移概率矩阵 转移概率图 0 1-p 1 0 1 1-q 2 q p 单符号离散信道 6.1.3 例 解： 四个等概消息，编成的码字为 ，当通过 下 图所示二进制对称无记忆信道传输时，求 : 0 1 10 0 0 21 ，MM110101 43 ，MM1)“ 接收到第一个数字为 0” 与 “ 发 M1” 的互信息 2)当 “ 接收到第二个数字也为 0” 时，关于 M1的附加信息 3)当 “ 接收到第三个数字也为 0” 时，又增加多少关于 M1的信息？ 1) 41 212)1(241)|0()()0(iii MpMpq )1(2l o g 2/11l o g)0()|0(l o g)0;( 11 qMpMI互信息)1(2l o g 24/1)1(l o g)00()|00(l o g)00;(211 qMpMI互信息)1(2log)1(2log)1(2log2 附加信息41)1(2)1(41 22 41)1|0()1|0()0|0()1|0()1|0()0|0()0|0()0|0(41)|00()()00(iii ppppppppMpMpq2) )124)(1(41)1(3)1(41)|000()()000( 24123 iii MpMpq)124l o g ( 2 又增加的信息)124l o g ()1(2l o g 2)000()|000(l o g)000;( 211 qMpMI互信息3) 单符号离散信道 );(m a x)(YXICxp 6.1.3 信道容量的定义 平稳离散无记忆信道的容量 C定义为输入与输出平均互信息 I(X;Y)的最大值： 1）单位为 : 比特 /信道符号（奈特 /信道符号 ) 2）当信道给定后 ,p(y|x)就固定，所以 C 仅与p(y|x)有关，而与 p(x)无关 3） C是信道传输最大信息速率能力的度量 多维矢量信道 );(m a x )(1NNxxp IC N YX 若 和 分别为信道的 N维输入与输出随机矢量集合，则信道容量定义为： NX NY其中， 为信道输入矢量的联合概率 )( 1 Nxxp 6.2 单符号离散信道及其容量 离散无噪信道的容量 一般离散信道的容量 离散对称信道的容量 )/( l og)(m a x 符号比特rXHC 6.2.1 离散无噪信道的容量 无损信道： 输出符号只对应一个输入符号。 其中 r为输入符号集的大小 a1a2b1b2b3b4b51 / 21 / 21 / 31 / 61 / 2X Y 6.2.1 离散无噪信道的容量 确定信道： 每个输出符号都对应一个输出符号 )/( l og)(m a x 符号比特sYHC 其中 s为输入符号集的大小 a1b1b2a2a3a4a511111X Y)/( l ogl og)(m a x 符号比特rsYHC 无损确定信道： 输入符号与输出符号是一一对应关系 其中 r、 s为输入与输出字母表的大小，且 r=s 6.2.1 离散无噪信道的容量 a1a2a3b1b2b3111X Y00.21020.210.70.70.10.100.21020.110.70.10.20.7(b)(a) 6.2.2 离散对称道的容量 若一个信道的转移概率矩阵按 输出 可分为若干子集，其中每个子集都有如下特性：即每一行是其他行的置换，每一列是其他列的置换，则信道称为 对称信道 6.2.1 例 分析 下 图信道的对称性 0 .20 .20 .7 0 .10 .1 0 .70 . 7 0 . 2 0 . 10 . 2 0 . 1 0 . 7 6.2.2 离散对称道的容量 解： (a)可分成两个子矩阵 所以为 对称信道 (b)的概率转移矩阵为 所以不是对称信道 有时将转移概率矩阵可分成多个子集的对称信道为准对称或弱对称信道 ，而只有一个子集的对称信道称 强对称信道 ), . . . ,(l o g 11211 spppHsC ), . . . ,()( 21 spppHYHC 6.2.2 离散对称道的容量 定理 6.2.1 对于离散对称信道，当输入等概率时达到信道容量： H(Y)为输入等概率时输出的熵 H(p1,p2, ,ps)为信道转移概率矩阵某行元素 注释 : 对强对称信道 ,输入等概率时达到容量，此时输出等概率。 2/16/13/13/12/16/16/13/12/1 6.2.2 离散对称道的容量 6.2.2 例 解： 一信道的转移概率矩阵 如图， 求信道容量和达到容量时的输出概率。 1 2 3,q q q设输出概率为 。由于信道为强对称信道，故当输入等概率时达到容量 C，此时输出也等概率 3/1321 qqq符号比特 / 126.1)61,31,21(3l og HCprprprpprprprpp1. . .11. . . . . . . . .1. . .111. . .11 6.2.2 离散对称道的容量 6.2.3 例 解： 一信道的转移概率矩阵 如图， 求信道容量和达到容量时的输 入 概率。 设输入输出概率为 由于信道为强对称信道，故当 时 ,达到容量。 r , , 2 , 1 i，q，p jirpp r /1.1 1l og1)1()1l og()1(l og r pr prpprC)1l o g ()(l o g rppHr特别是，当 r=2时，信道容量为 C=1-H(p)比特 /符号。 1 1 1 13 3 6 61 1 1 16 3 6 3413161211 q 313131212 q 616161213 q 414 q 6.2.2 离散对称道的容量 6.2.4 例 解： 一信道的转移概率矩阵 如图， 求信道容量和达到容量时的输出概率。 设输出概率为 准对称信道，当输入等概率时达到信道容量。可计算输出概率为 4321 , qqqq)61,61,31,31()41,61,31,41( HHC 符号比特 / 041.0上凸函数为 )();( xpYXI 6.2.3 一般离散信道的容量 极大值存在 件要满足非负且归一化条 )( xp求信道容量归结为求有约束极值的问题 )(q , )|( , )( j yqxyPpxpp iji 下的极值在约束求 0,1 l og);( , iiijijjiiji ppqpppYXI的极值求函数利用拉格朗日乘子法 iipYXIJ );(, 0并使其为计算kpJ , l o g l o g i i j i j j j ii j j ikkJ p p p q q ppp j jkjjkjkjkj epqppp 0)l o gl o g(l o g riijij ppq1考虑到 l o g l o gkjkjj jppeq 6.2.3 一般离散信道的容量 ( ; ) l o g 1 , . . . ,kjk k jj jpI a Y p k rq( ; ) ( ; )kkkp I a Y I X Y( ; ) l o gkkkC p I a Y e l o g l o gkjkjj jppeq 6.2.3 一般离散信道的容量 j j jjijijijjijij qcpppcqpp )l og(l ogl og j jijijjijjj pppqc l o gl o g 令jjcjjjjjj cqqc2l o g121l o gcjjq 2 iiijij pppq 验证 C的正确性 6.2.3 一般离散信道的容量 j jijijjij ppp l o g用矩阵表示 hP 1l o gsi i j i jjh p p 1 1 1 2 12 1 2 2 212. . . . . . . . . . . . .ssijr r r sp p pp p pPpp p p 1 hP 6.2.3 一般离散信道的容量 例 一信道的转移概率如图所示，求信道容量和达到容量时的输出概率。 0 1 2 0 1 2 1/2 1/2 1/4 1/4 1/4 1/4 1 6.2.3 一般离散信道的容量 214141414121010p202l o gl o gl o g0l o gl o gl o g3214141414121213212411412414141412121341241121符号比特 /585.0l og)222l og( 23202 c95192203216120pppqqq解： 6.2.3 一般离散信道的容量 例 解： 利 用 求例 6.1.1中二元对称信道容量。 1 hP 1 11112P ( 1 ) l o g ( 1 ) l o g( 1 ) l o g ( 1 ) l o gh 1 ( 1 ) l o g ( 1 ) l o g11 ( 1 ) l o g ( 1 ) l o g12 ( 1 ) l o g ( 1 ) l o g( 1 ) l o g ( 1 ) l o g 1 hP 2/111P 6.2.3 一般离散信道的容量 信道 容量 为 ) / ( )(1l o g)1l o g ()1(122l o g l og)1l og ()1(2 符号比特 HC 21 21 qq输出概率为对应的输入概率为 cjjq 2 iiijij pppq 21 21 pp输入概率为 6.2.3 一般离散信道的容量 0 , );( ii pCYaI 对于0 , );( ii pCYaI 对于 定理 6.2.2 对于离散无记忆信道，当且仅当 I(X;Y)达到最大值，此时 C为信道容量 6.2.3 一般离散信道的容量 000 1 211l o g ( 0 )11 l o g ( 0 )2l o g ( 0 )q C pq q C pq C p fff6.2.6 例 解： 信道的转移概率如 下图 所示，求信道容量和达到容量时的输入出概率。 设输入、输出概率为 p0,p1,p2.q0,q1 1）达到容量时，若输入概率全不为零 01 1 / 2qq解得 ， C=1比特，但将结果代入第 2式，使该式左边的值为 0，出现矛盾。 6.2.3 一般离散信道的容量 01l o g l o gq q C 0 1 21 ,02p p p 2）设 p2=0， p0,p1,不为零 符号比特 / 1 ， 2/110 Cqq将结果代入第 2式 ， 该式左边的值为 0C。所以，信道容量C=1比特 /符号，达到容量时的输入概率为概率为 6.2.3 一般离散信道的容量 6.3 级联信道及其容量 级联的含义是被连接的信道输入只依赖于前面相邻信道的输出而和前面的其它信道的输出无直接关系 P(y|x) P(z|y)X ZY( ; | ) 0I X Z Y ( ; ) ( ; )I X Y Z I Y Z 若随机变量集合 (X,Y,Z)构成马氏链，则称信道 X-Y与 Y-Z构成级联信道。由于当 Y给定时，Z不依赖于 X，即 P(z|y)=P(z|xy) );();( YXIZXI );();( ZYIZXI 证 定理 6.3.1 若 X,Y,Z构成一马氏链，则： )|;();()|;();();( ZYXIZXIYZXIYXIYZXI 0)|;( YZXI马氏链得证 );();( YXIZXI );();( ZXIZXI 同理可证 6.3 级联信道及其容量 U L译码器信道编码器X N Y N V L信源 通信系统模型各部分的级联 信道传输后，译码器收到 N长序列为 ，译码后传给信宿的消息序列为 。 NYNV 6.3 级联信道及其容量 );();( NNLL YXIVUI 构成马氏链),( NNL YXU ( ; ) ( ; )L N N NI U Y I X Y( ; ) ( ; )L L L NI U V I U Y证 定理 6.3.2(数据处理定理 ) 构成马氏链),( LNL VYU 定理的含义：从信宿得到的关于信源的信息经过编 译码器、信道的处理后会减少，而且处理的次数越 多，减少得越多。 6.3 级联信道及其容量 级联信道为马氏链 级联信道的转移概率矩阵 一级级联相当于状态的一步转移 级联信道的转移概率矩阵为级联信道中各矩阵依次相乘 6.3 级联信道及其容量 级联信道的容量 根据级联信道的转移矩阵特点，按照前面介绍的离散信道容量的计算方法即可计算其信道容量。 222211 ( 1 ) 2 ( 1 ) 11 2 ( 1 ) ( 1 )PP 给定二元对称信道其状态转移矩阵如下，计算两级级联信道的概率转移矩阵。如果信道输入 0、 1 等概率，求在两级级联和三级级联情况下输入与输出的平均互信息。 6.3.1 例 解： 11 P1)两级级联信道的概率转移矩阵 6.3 级联信道及其容量 011 / 2 1 / 2XXP 011 / 2 1 / 2YYP 011 / 2 1 / 2ZZP ( ; ) ( ) ( | ) 1 ( )( ; ) 1 ( | ) 1 2 ( 1 ) I X Y H Y H Y X HI X Z H Z X H 23( ; ) 1 3 ( 1 ) I X U H 2)设原信道输入与输出集分别为 X、 Y，两级级联和三级级联情况下输出集合分别为 Z、 U ( ) l o g ( 1 ) l o g ( 1 )H 其中 类似地 ,可计算三级信，级联的情况： 结论：信道串联后增加信息损失，串联级数越多，损失越大。 6.3 级联信道及其容量 设错误概率 为 1/3，计算两级级联信道的容量及达到容量时的输出概率。 6.3.1(续 ) 例 解： 两级级联信道的转移矩阵为 6.3 级联信道及其容量 9/59/49/49/53/23/13/13/23/23/13/13/2P该级联信道是一个强对称信道，因此当输入等概时达到信道容量，此时输出也等概。所以 2/121 qq991.1)94l og9495l og95(2l og)94,95(2l og HC 比特 /符号 多维矢量信道输入与输出的性质 并联信道及其容量 离散无记忆扩展信道及其容量 6.4 多维矢量信道及其容量 和信道及其容量 )|()();( NNNNN YXHXHYXI )|()( NNN XYHYH NN YX yqxypyxp, )()|(l o g)( 6.4.1 多维矢量信道输入与输出的性质 对于 多维矢量信道 ，输入与输出平均互信息为 : NiiiNN YXHYXH1)|()|(时等式成立当且仅当 )|()|( 1Niii yxpyxpNiiiNN XYHXYH1)|()|( 引理 6.4.1 NN YX , ,1 NN XXX 设信道的输入输出分别为 ，其中 ，则： NN YYY 11） 成立仅当信道无记忆时等式2） 6.4.1 多维矢量信道输入与输出的性质 NiiiNN YXIYXI1);();(NiiiNNNNNN XYHYHXYHYHYXI1)|()()|()();( 定理 6.4.1 对于离散无记忆信道，有： 证 1 1 1( ; ) ( ) ( | )N N Ni i i i ii i iI X Y H Y H Y X 11( ) ( . . . ) ( )NNNiiH Y H Y Y H Y 仅当输出独立时等式成立。 6.4.1 多维矢量信道输入与输出的性质 当输入独立时 即当信源信道都无记忆时，等式成立。 1( ) ( ) . . . ( )Np x p x p xr NiNiiXiiiXNiiiiXXypxypxpxypxpxypxpypiNN 1 11)()|()()|()()|()()(1 6.4.1 多维矢量信道输入与输出的性质 证 NiiiNN YXIYXI1);();( 定理 6.4.2 对于无记忆信源，有： )|()();( NNNNN YXHXHYXI NiiiNiiNiii YXHXHYXI111)|()();( 1( ) ( )NNiH X H X Niii yxpyxp1)|()|( 等式成立条件： 6.4.1 多维矢量信道输入与输出的性质 当信道无记忆时 即当信源信道都无记忆时，等式成立。 121 1 1 2 2 1,1 ( ) ( | )( ) ( | )( | )( ( ) ( | ) ( ) ( | ) . . .( ) ( | )( | )()Ni i iix x xi i i Niiiiiip x p y xp x p y xp x yp y p x p y x p x p y xp y p x yp x ypyLr r rrrr） 6.4.1 多维矢量信道输入与输出的性质 结论： 1） 对于无记忆信源和无记忆信道，有： NiiiNN YXIYXI1);();(2） 对于平稳信源，因为 Xi、 Yi同分布 ,因此： ( ; ) ( ; )iiI X Y I X Y1( ; ) ( ; )NiiiI X Y N I X Y对于平稳离散无记忆信道 (DMC)的 N次扩展信道，当信源无记忆时 ,有 ( ; ) ( ; )NNI X Y N I X Y 6.4.1 多维矢量信道输入与输出的性质 1 2 3 4 53 2 5 1 4设无记忆信源 X的 5次扩展源为 X5，信道为下面矩阵所示的置换信道，其中第 1行为输入的序号，第 2行为信道输出的序号，例如 X1输出到 Y4， X2输出到 Y2等 。 计算 6.4.1 例 解： 155 );( );(iji YXIYXI 和1 1 1 32 2 2 23 3 4 4 5 5( ; ) ( ; ) 0( ; ) ( ; )( ; ) ( ; ) ( ; ) 0I X Y I X XI X Y I X X HI X Y I X Y I X Y HXHYXI 5)();( 555 51( ; )iiiI X Y H 6.4.1 多维矢量信道输入与输出的性质 6.4.2 例 解： 设 离散 无记忆信 道的输入 ，输出 ，且有 计算 NN XXX .1NN YYY .1 1 1 2 2 , . . . , NNX Y X Y X Y X NijiNN YXIYXI1);( );( 和1( ; ) ( ) ( | ) ( ) ( | ) ( )NN N N N N N NiiiI X Y H Y H Y X H Y H Y X H Y ).|(.)|()().( 111211 NNN XXXHXXHXHXXH11( ) ( ) ( )H X H X N H X 1 1 1( ; ) ( ) ( | ) ( ) ( )N N Ni i i i i ii i iI X Y H X H X Y H X N H X NiiiNN YXIYXI1);();( 此时 6.4.1 多维矢量信道输入与输出的性质 N次扩展信道 单符号离散信道 N长的随机序列 N长的随机序列 新信道 原序列的 N次扩展信道 6.4.2 离散无记忆扩展信道及其容量 11/1( | ) ( | ) ( . . . | . . . ) ( | )NNNk l l k N N i iYXiP y x p y x p y y x x p y x r r r r N次扩展信道的描述要满足一般的信道数学模型的描述，但符号集为同分布符号的扩展，即各 Xi的分布都相同 信道可通过下式来计算 ,.1 Nxxx 信道的输入和输出集合分别为 和 ，所包含的矢量分别为 12N NX X X X L12N NY Y Y Y LNyyy .1 6.4.2 离散无记忆扩展信道及其容量 RSRRSS.212222111211 一个信道的 N次扩展信道是 N个原信道的 Kroneck乘积 例 设输入与输出符号集的尺寸分别为 r、 s， 则 N次扩展信道的输入与输出符号集的尺寸分别为 NN sSrR ,则， 信道的转移概率为： NslNkl rk，1,.,11 对所有满足 6.4.2 离散无记忆扩展信道及其容量 pppppppp1111求错误概率为 p的二元对称信道的二次扩展信道的转移概率矩阵。 6.4.3 例 解： 2次扩展信道的转移概率矩阵： )|()|()|(11,10,01,0011,10,01,002211| 22 xypxypxyP，klXYkllk22222222)1()1()1()1()1()1()1()1()1()1()1()1(pppppppppppppppppppppppp 6.4.2 离散无记忆扩展信道及其容量 NiNiiiixpNNxpN CYXIYXICi1 1)()();(m a x);(m a x);(m a x )( iixpi YXICiCC i NCC N 6.4.2 离散无记忆扩展信道及其容量 当信源为无记忆时，等式成立 离散无记忆 N次扩展信道的容量 求该二次扩展信道的容量 。 6.4.3(续 ) 例 解： 由例 6.2.3可得，错误概率为 p的二元对称信道的容量 ，根据式 (6.4.6),该信道的二次扩展信道容量为 6.4.2 离散无记忆扩展信道及其容量 )(2222 pHCC 1 .N NX X