通信原理第八章离散信道及信道容量 一般离散信道的信道容量

通信原理第八章离散信道及信道容量 一般离散信道的信道容量 第八章 离散信道及信道容量 信道，顾名思义就是信号的通道。图8.1中位于调制器和解调器之间的信道指用来传输电信号的传输介质，如电缆，光缆，自由空间等，我们把这样的信道称为狭义信道。狭义信道的输入为波形信号，输出为连续信号。还有一种定义即凡是信号经过的路径都称为信道，这就是广义信道的概念。如图8.1所示，由调制器，信道和解调器构成了一个广义编码信道。 编码信道的输入和输出均为数字信号，因此，我们也将这类信道称为离散信道。 编码信道 图8.1 信道的定义 本章首先讨论离散信道的统计特性和数学模型，然后定量地研究信道传输的平均互及其性质，并导出信道容量及其计算方法。 8.1 离散信道的数学模型及分类 我们已知信源输出的是携带着信息的消息，而消息必须首先转换成能在信道中传输或存储的信号，然后通过信道传送到收信者。信道会引入噪声或干扰，它使信号通过信道后产生错误和失真。故信道的输入和输出信号之间一般不是确定的函数关系，而是统计依赖的关系。 离散信道的数学模型一般如图8.1所示。图中输入和输出信号用随机矢量表示。输入信号X =(X 1,X i, , X N) ，输出信号Y =(Y 1,Y i, , Y N) ，其中i =(1,N) 表示时间或空间的离散值。而每个随机变量X i和Y i又分别取值于符号集A =a 1,a r和B =b 1,b s，其中r 不一定等于s 。图中条件概率P =(y|x) 描述了输入信号和输出信号的依赖关系，它由调制器、信道和解调器的性能共同决定。 图 8.1 离散信道模型 X Y 根据信道的统计特性即条件概率P (y|x) 的不同，离散信道又可分为三种情况。 (1)无干扰（无噪）信道。信道中没有随机性的干扰或者干扰很小，输出信号Y 与输入信 号X 之间有确定的一一对应的关系。即，y =f(x) 1 y=f(x) 并且 P (y|x) = （8.1） 0 yf(x) (2)有干扰无记忆信道。实际信道中常有干扰（噪声），即输出符号与输人符号之间无确 定的对应关系。若信道任一时刻输出符号只统计依赖于对应时刻的输人符号，而与非对应时刻的输入符号及其他任何时刻的输出符号无关，则这种信道称为无记忆信道。满足离散无记忆信道的充要条件是 P(y|x) =P (y 1y 2yN|x1x2xN) =Ni=1P (y i|xi) (8.2) (3)有干扰有记忆信道。这是更一般的情况，即有干扰(噪声) 又有记忆。实际信道往往 是这种类型。例如在数字信道中，由于信道滤波使频率特性不理想时造成了码字之间的干扰。在这一类信道中某一瞬间的输出符号不但与对应时刻的输入符号有关，而且还与此以前其他时刻信道的输入符号及输出符号有关，这样的信道称为有记忆信道。这时信道的条件概率P (y?x) 不再满足式(8.2)。 下面我们着重研究离散无记忆信道，并且先从简单的单符号信道人手。设单符号离散信 道的输入变量为x，可能取值的集合为a 1, a 2,a r；输出变量为Y，取值于b 1, b 2,b s。并有条件概率 P (y |x) =P(y=b j|x=a i) =P(bj|ai) i=(1,2, r; j=1,2, , s) 这一组条件概率称为信道的传递概率或者转移概率。 因为信道中有干扰（噪声）存在，若信道输入为x=a i时，输出是哪一个符号事先无法 确定。但信道输出一定是b 1, b 2,b s中的一个。即有 s P(bj|ai) =1 i=(1,2, , r ) (8.3) j=1 由于信道的干扰使输入的符号x，在传输中发生错误，所以可以用传递概率P(bj|ai) （i = (1,2, r; j=1,2, , s) 来描述干扰影响的大小。因此，一般简单的单符号的离散信道的数 学模型可以用概率空间X, P (y |x) , Y加以描述。如图8.2所示. ?a 1?a ?2 ?. ?X ?. ?. ?a r P b j |ai b 1?b 2?. ?Y . ?. ?b s ? 图8.2 单符号概率空间模型 图8.3 二元对称信道 下面介绍一种重要的特殊信道，即 二元对称信道，简称BSC 。二元对称信道的的输入符号X 取值于0,1；输出符号Y 取值于0,1。此时，r=s=2，信道传递概率为 P (b 1|a 1) =P (0|0) =1?p=p? P (b 2|a 2) =P (1|1) =1?p=p? P (b 1|a 2) =P (0|1) =p P (b 2|a 1) =P (1|0) =p 如图8.3所示，P (1|0) 表示信道输入符号为0而接收到符号为1的概率，而P (0|1) 表示信道输入符号为1而接收到的符号为0的概率。它们都是单个符号传输发生错误的概率，通常用p 表示。而P (0|0) 和P (1|1) 是无错误传输的概率，通常用1?p=p?表示。 信道传递概率可用矩阵来表示，由此得到二元对称信道的传递矩阵为 1 设信道的输入概率空间为： 1p ? 1-p ?1-p ?p ? 下面来推导一般单符号离散信道的一些概率关系。 a 2, ?a r a 1, X =P (a ) , P (a ) , ?P (a ) P (x ) 12r r 并 P (a i) =1 0 P（a i) 1 i=(1,2, r) i=1 又设输出Y 的符号集为B=b 1, b 2,b s。给定信道转移矩阵为 ?P(b P(b?P =?P(b 1a ) 1P(ba ) 211a ) 2P(ba ) 22P(ba ) ?s 2P(ba ) ?s 11a ) r P(ba ) 2r P(ba s r ? （8.4） ) ? （1）输入和输出的联合概率为 P(aib j) =P (a i) P(bj|ai) =P(bj)P(ai|bj) （8.5） 其中 P(bj|ai) 是信道传递概率，即发送为a i，通过信道传输接收到为b j的概率。通常称为前向概率。它是由于信道噪声引起的，所以描述了信道噪声的特性。而P(ai|bj) 是已知信道输出端接收到符号为b j而发送的输入符号为a i的概率，又被称为后向概率。 （2）根据联合概率可得输出符号的概率 P(bj) =r i=1P (a i ) P(bj |ai ) (j=1, , s) （8.6） (3)根据贝叶斯定律可得后验概率 P(ai|bj) = 8.2平均互信息及平均条件互信息 在阐明了离散单符号信道的数学模型，即给出了信道输入与输出的统计依赖关P(aib j) P(bj) =P (a i) P(bj|ai) i=1P (a i) P(bj|ai) (i=1,2, , r j=1,2, s) （8.7） 系以后，我们将深入研究在此信道中信息传输的问题。 8.2.1 损失熵和噪声熵 信道输入信号x 的熵为 H(X ) =ri=1P (a i) logP (a ) （8.8） i1 H (X ) 是在接收到输出Y 以前，关于输入变量X 的先验不确定性的度量，所以称为先验熵。 如果信道中无干扰(噪声) ，信道输出符号与输入符号一一对应，那么，接收到传送过来的符号后就消除了对发送符号的先验不确定性。但一般信道中有干扰(噪声) 存在，接收到输出Y 后对发送的是什么符号仍有不确定性。那么，怎样来度量接收到Y 后关于X 的不确定性呢? 接收到输出符号y =b j后，关于X 的平均不确定性为 r H(X|bj) =P(ai|bj)log i=11P(ai|bj) =?P(x|bj) log P(x|bj) (8.9) X 这是接收到输出符号b j后关于X 的后验熵。后验熵在输出y 的取值范围内是个随机量， 将后验熵对随机变量Y 求期望，得条件熵为 ssr H (X|Y) =EH(X|bj)=P(bj)H(X|bj) =P(bj) P(ai|bj)log j=1 rsj=1i=11P(ai|bj) =P(aib j)log i=1j=11P(ai|bj) (8.10) 这个条件熵称为信道疑义度。它表示在输出端收到输出变量Y 后，对于输人端的变量X 尚存在的平均不确定性。它也表示信源符号通过有噪信道传输后所引起的信息量的损失，故也可称为损失熵。这个对X 尚存在的不确定性是由于干扰(噪声) 引起的。如果是一一对应信道，那么接收到输出Y 后，对X 的不确定性将完全消除，则信道疑义度H (X|Y) =0。由于一般情况下条件熵小于无条件熵，即有H (X|Y) H(Y|X) 表示在已知X 的条件下，对于随机变量Y 尚存在的不确定性。我们将H(Y|X) 称 为噪声熵，或散布度，它反映了信道中噪声源的不确定性。 H (Y X) =P (ai b j )log i =1j =1r s 1 P (b j a i ) (8.11) 8.2.2 平均互信息 根据上述，我们已知H(X)代表接收到输出符号以前关于输入变量X 的平均不确定性，而 H (X|Y) 代表接收到输出符号后关于输入变量X 的平均不确定性。可见，通过信道传输消除了一些不确定性，获得了一定的信息。所以定义 I(X, Y ) = H(X) ? H(X|Y) （8.12） I (X, Y ) 称为X 和Y 之间的平均互信息。它代表接收到输出符号后平均每个符号获得的关于X 的信息量。根据式（8.8）和式（8.11）得 I (X; Y ) =X,YP(xy) 根据熵的定义和表达式，可得以下关系 I (X; Y ) = H(X) ? H(X|Y) =H(X) +H(Y) ?H(XY) （8.13） =H(Y) ? H(Y|X) 由此，可以进一步理解熵只是平均不确定性的描述，而不确定性的消除(两熵之差) 才等于接收端所获得的信息量。 下面，我们观察二种极端情况的信道。 一种信道是输入符号与输出符号完全一一对应，即无噪信道。输入符号集 A =a 1, a 2,a r，输出符号集B =b 1, b 2,b r，它们的信道传递概率为 P(y=bj|x=ai) =0ij (8.14) 1i=jP (y|x) P(y) 它表示输入符号和输出符号之间有一一对应关系。根据（8.14）可推出 0P(x=ai|y=bj) =1 由式（8.10）和式（8.11）计算得 H(X|Y) =0 H(Y|X) =0 信道中损失熵和噪声熵都等于零。所以， I (X; Y ) =H(X) =H(Y) 在此信道中，因为输入和输出符号一一对应、所以接收到输出符号Y 后对于输入X 不存在何不确定性。这时，接收到的平均信息量就是输人信源所提供的信息量。 第二种极端情况，信道输人端X 与输出端Y 完全统计独立，即 ij (8.15) i=j P (y|x) =P(y) xX,yY P (x|y) =P(x) xX, yY 在这种信道中输入符号与输出符号没有任何依赖关系。接收到Y 后不可能消除输入端X 的任何不确定性，所以获得的信息量等于零。同样，也不能从X 中获得任何关于Y 的信息量。因此，平均互信息I (X; Y ) =0。 8.3 平均互信息特性 本节将介绍平均互信息I (X; Y ) 的一些特性。 1）平均互信息的非负性 离散信道输入概率空间为X ，输出概率空间为Y ，则I (X; Y ) 0，当X 和Y 统计独立 时，等式成立。 这个性质告诉我们：通过一个信道获得的平均信息量不会是负值。也就是说，观察一 个信道的输出，从平均的角度来看总能消除一些不确定性，接收到一定的信息。除非信道 输入和输出是统计独立时，才接收不到任何信息。 2）平均互信息的极值性 I (X; Y ) H(X) （8.16） 因为信道疑义度H(X|Y) 总大于零，所以平均互信息总是小于熵H(X)。只有当H(X|Y) =0, 即信道中传输信息无损失时，等号才成立。 在一般情况下，平均互信息必在零和H(X)值之间。 3）平均互信息的对称性 根据I(X;Y)的定义式可以证明， I(X; Y ) =I (Y; X ) (8.17) I (X; Y ) 表示从Y 中提取的关于X 的信息量，而I (Y; X ) 表示从X 中提取的关于Y 的信息量， 它们是相等的。 4）平均互信息I(X;Y) 的凸状性 平均互信息I (X; Y ) 是输入信号X 的概率分布函数P(X)和信道传递概率P (y|x) 的函数。关 于互信息I(X;Y)和P(X)，P (Y X) 的关系我们有如下结论： 定理8.1 平均互信息I (X; Y ) 是信道输入信号的概率分布P(x) 的形凸函数。 例8,1，设二元对称信道的输入概率空间为 8.3所示。可以算出 X0=P(x)1。而信道特性如图?=1? P (y=0) = p?+(1?) p=p?+?p P (y=1) = p+(1?) p?=p+?p? 因此，H (Y ) =(p?+?p) log(p?+(p+?p?) log(p+ ?p) ?p?) 11H(Y|X) = p log+p?log因此， I (X; Y ) =(p?+?p) log(p?+(p+?p?) log(p+?p logp+p?logp? ?p) ?p?) =H (p?+?p) ?H (p) （8.18） 在式（8.18）中当信道转移概率p固定时，可得I (X; Y ) 是的型凸函数，其曲线如图8.4所示。 从图中可知，当二元对称信道的矩阵固定后，输入变量X 的概率分布不同，在接收 端平均每个符号获得的信息量就不同。只有当输人变量X 是等概率分布，即P (x=0) = P (x=1) =2 定理8.1意味着，当固定某信道时，选择不同的信源与信道连接，在信道输出端接 收到每个符号后获得的信息量是不同的。而且对于每一个固定信道，一定存在有一种信 源(某一种概率分布P (x) ) ，使输出端获得的平均信息量为最大。 8.4 信道容量及其一般计算方法 我们研究信道的目的是要讨论信道中平均每个符号所能传递的信息量，即信道的信息传输率R 。由前已知，平均互信息I (X; Y ) 就是从信道输出符号Y 后中获得的关于X 的信息量。因此信道的信息传输率就是平均互信息。即 R =I (X; Y ) =H(X) ?H(X|Y) （比特/符号） （8.19) 1111111 1-H(p)图8.4 二元对称信道的互信息和输入信号概率分布的关系 有时我们所关心的是信道在时间内(一般以秒为单位) 平均传输的信息量。若平均传 输一个符号需要t 秒钟，则信道每秒钟平均传输的信息量为 Rt=tI (X; Y ) =tH(X) ?tH(X|Y) (比特/秒) (8.20) 一般称此为信息传输速率。 由定理8.1知，I (X; Y ) 是输人随机变量X 的概率分布P(x) 的型凸函数。因此对于一个 固定的信道，总存在一种信源(某种概率分布P(x) ，使传输每个符号平均获得的信息量最大。也就是每个固定信道都有一个最大的信息传输率。定义这个最大的信息传输率为信道容量C ，即 111C=max I (X;Y) （8.21） p (x ) 其单位是比特/符号，而对应的输入信号概率分布称为最佳输入分布。若平均传输一个符号需要t 秒钟，则信道单位时间内平均传输的最大信息量为 1C = t m ax I(X;Y) （比特/秒） （8.22） t p (x ) 信道容量C 与输入信源的概率分布无关，它只与信道的转移概率有关。所以，信道容量是完全描述信道特性的参量，是信道能够传输的最大信息量。 如例8.2中，二元对称信道的平均互信息I (X; Y ) = H(p?+?p) ?H (p) 。由图8.4看出， 当=?=2时，I(X;Y)取得最大值。因而平均互信息的极大值为 I (X; Y ) =1?H(p) 因此，二元对称信道的信道容量为 由此可见，二元对称信道的信道容量只是信道传输概率p的函数，而与输入符号X 的概率分布无关。 下面我们讨论一些特殊类型信道的信道容量。 8.4.1 三类特殊信道容量 信道输人和输出间有确定的一一对应关系的信道，称为无噪无损信道。无噪无损信道的 疑义度H(X|Y) 和信道的噪声熵H(Y|X) 都等于零，所以 I (X; Y ) =H(X) =H(Y) (8.24) 因此，无噪无损信道的信道容量为 1 C=1?H(p) （比特/符号） （8.23） C=max H(X)=logr （比特/符号） （8.25） p (x ) （8.25）表明当信道输入等概分布时，信道的传输速率达到信道容量。 另一类信道是输入一个X 值对应有几个输出Y 值，而且每个X 值所对应的Y 值不重合， 如图8.5(b)所示。这类信道被称为有噪无损信道。在这类信道中，输入符号通过传输变成若 干输出符号，虽它们不是一一对应关系，但这些输出符号仍可分成互不相交的一些集合。所以接收到符号Y 后，对发送的X 符号是完全确定的，即损失熵H(X|Y) =0，但噪声熵H(Y|X) 0。 X (a) 无 噪无损信 道(b)有噪无损信道 图8.5 无损信道 因此这类信道的平均互信息为： I (X; Y ) =H(X) 其信道容量 C=max H(X)=logr p (x ) 比特/符号 （8.27） 第三类特殊信道如图3.14所示。信道的一个输出值Y 对应好几个信道的输入，而且每个Y 值所对应的X 值不重合。这类信道被称为有噪无损信道。 图8.6 无噪有损信道 这类信道的噪声熵H(Y|X) =0，而信道疑义度H(X|Y) 0。它的平均互信息是 I (X; Y ) =H(Y) 信道容量为 C=max H(Y)=logs （比特/符号） （8.29） p (x ) (8.29)假设一定能找到一种输入分布使输出符号Y 达到等概率分布。 8.4.2 对称离散信道的信道容量 离散信道中有一类特殊的信道，其特点是信道矩阵具有很强的对称性。所谓对称性，就是指信道矩阵P中每一行都是由同一p 1, p 2, 都是由同一q 1, q 2, 对称离散信道。 例如，信道矩阵 , p s 集合的各元素的不同排列组成，并且每一列也 , q r 集合的各元素的不同排列组成。具有这种对称性信道矩阵的信道称为 ?1 ?3?P =? ?1?6 是对称离散信道。 1316 1613 1?1 ?26? 1? 和P =?6 1?13? 1 31216 ?3 1?6?1? 3?1?2? 若输入符号和输出符号个数相同，都等于r，且信道矩阵为 ?p ?p P =?r -1 ?p ?r -1 p r -1p p r -1 p r -1p r -1p r -1p ?r -1? ? r -1 ? （8.30） ?p ? 其中p+p?=1，则此信道称为强对称信道或者均匀信道。这类信道中的错误概率为p，对称地平均分配给r?1个输出符号。它是对称离散信道的一类特例。二元对称信道就是r=2的均匀信道。 对称离散信道的平均互信息为 I (X; Y ) =H (Y ) ? H(Y|X) H(Y|X) =XP(x)H(Y|X=x) =H(Y|X=x) = H(p1, p2, , ps) （8.31） 因此得 I(X; Y ) =H (Y ) ? H(p1, p2, , ps) （8.32） 可得信道容量 C=max ? ?H(Y )-H (p 1, p 2, ?, p s )? （8.33） p (x ) 现已知输出Y 的符号集共有s个符号，则H (Y ) log s。只有当P (y) = s等概率分布) 时，H (Y) 才达到最大值log s。一般情况下，不一定存在一种输入符号的概率分布P (x) ，能使输出符号达到等概率分布。但对于对称离散信道，其信道矩阵中每一列都是由同一q1, q2, , qr集的诸元素的不同排列组成，所以保证了当输入符号是等概率分布，即P(x)= rY 一定也是等概率分布，这时H (Y ) =log s。即 1 1 1? P （y 1）=P (x )P (y 1|x )=(y 1|x )? r X X Y ?1 P （y 2）=P (x )P (y 2|x )=(y 2|x )? ? （8.34）r X X Y ?1 P （y s ）=P (x )P (y s |x )=(y s |x )? r X X Y ? 由于信道矩阵的对称性，可推出 P(y1) = P(y2) =?=P(ys) (8.35) 对于对称离散信道，当输入符号X 达到等于等概率分布，则输出符号Y 一定也达到等概率分布。 由此得对称离散信道的信道容量为 C=log s?H(p1, p2, , ps) （比特/符号） （8.36） 例8.3， 强对称信道（均匀信道）的信道矩阵是rr阶矩阵，信道转移矩阵为（8.30）。根据式（8.36）得强对称信道的信道容量为 C=log r?H(p?, r?1, r?1, , r?1) =log r+plogr?1=logr?log (r?1) ?H(p) （8.37） 式中p是总的错误传递概率，p?是正确的传递概率。 8.4.3 准对称信道的信道容量 若信道矩阵Q 的列可以划分为若干个互不相交的子集Bk, 即B1B2Bn=?，B1B2Bn=Y，由Bk为列组成的矩阵Qk是对称矩阵，则称信道矩阵Q 所对应的信道为 p p p p 准对称信道。 例如信道矩阵 ?1?3P 1=? ?1?6 1 16 1 3 1 1313 1 16161? ?0. 7 6? ? P 2=?1? ?0. 2?3? 0. 1?0. 2 ? 0. 1?0. 7 都是准对称信道。在信道矩阵P1中Y 可以划分为三个子集，由子集的列组成矩阵为 31 6 3 ， 61 ，1。它们满足对称性，所以P1所对应的信道为准对称信道。同理P2可划 6 3 0.70.20.1 和。 0.20.70.1 我们可以证明达到准对称离散信道信道容量的输入分布（最佳输入分布）是等概分布准对称离散信道的信道容量为 分为两个对称阵 n C=log r?H(p1, p2, , ps) ?Nklog Mk (8.38) k=1 其中r 是输入符号集的个数，(p1, p2, , ps) 为准对称信道矩阵中的行元素。设矩阵可划分成 n 个互不相交的子集。Nk 是第k 个子矩阵Qk中行元素之和，Mk是第k 个子矩阵Qk中列元素之和。 例8.4， 设信道传输矩阵为 P= 1?p?q p qq p 1?p?q 可表示成如图8.7所示。根据式（8.38）可计算得 N1=1?q, N2=q M1=1?q, M2=2q 因此，信道容量为 C=plogp?(1?p?q) log (1?p?q) +(1?q) log 2 (8.39) 图8.7 例8.4的信道模型 8.5 离散无记忆扩展信道及其信道容量 前几节讨论了最简单的离散信道，即信道的输入和输出都只是单个随机变量的信道。然而一般离散信道的输人和输出却是一系列时间(或空间) 离散的随机变量，即为随机序列。在离散无记忆信道中，输入随机序列与输出随机序列之间的传递概率等于对应时刻的随机变量的传递概率的乘积。 设离散无记忆信道的输入符号集输入符号集A=a1, , ar，输出符号集B=b1, , bs，信道矩阵为（8.4）。则此无记忆信道的N次扩展信道的数学模型如图8.8所示。 X N Y N 1=(b 1b 1b 1）?（a 1a 1a 1）=1 ?（a a a ）=(b b b ）?222 2222? ? ?a r a r a r ）=r N ?（s N =(b s b s b s ）? 图8.8 离散无记忆信道的N 次扩展信道 因为在输入随机序列X=(X1, X2, XN) 中，每一个随机变量Xi有r 种可能的取值，所以随机矢量X 的可能取值有rN个。同理，随机矢量Y 的可能取值有sN个。根据信道无记忆的特性，可得対N次扩展信道的信道矩阵 ?11?21?=?r N 1 12 22r N 2 ? ?r N S N ? 1S ?2S ? N N 图8.9 离散无记忆信道N 次扩展信道的信道矩阵 式中k?=P(?|k) ( k=1,2， , rN ?=1,2， , sN) 并满足 sN k?=1 (k=1,2, , rN ?=1 并且， k?=P(?|k) =P(b?1b?2b?N |ak1ak2akN ) N =P(b?i|aki) (k=1,2, , rN ?=1,2, , sN) (8.40) i=1 例8.5，求例8.1中二元无记忆对称信道的二次扩展信道。 因为二次扩展信道的输入符号集为和输出变量X 和Y 的取值都是0或1，因此，二次扩展信道的输人符号集为A2=00,01,10,11。输出符号集为B2=00,01,10,11。根据无记忆信道的特性，求得二次扩展信道的传递概率为 P(1|1) =P(00|00) = P(0|0) P(0|0) =p?2 P(2|1) =P(01|00) = P(0|0) P(1|0) =p?p P(3|1) =P(10|00) = P(1|0) P(0|0) =pp? P(4|1) =P(11|00) = P(1|0) P(1|0) =p2 同理求得其他传递概率k?，最后得二次扩展信道，即 = p?p pp?p2 根据平均互信息的定义，可得无记忆信信道的N 次扩展信