第3章 离散信道及其信道容量.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,3,章 离散信道及其信道容量,赵 越,2011.9.,信道的任务是以信号方式传输信息和存储信息。,研究信道中能够传送或存储的最大信息量，即信道容量。,数字通信系统的一般模型,2,3.1,信道的数学模型及分类,我们认为噪声或干扰主要从信道中引入，它使信号通过信道传输后产生错误和失真。,所以，信道的输入和输出信号之间一般不是确定的函数关系，而是统计依赖的关系。,3,3.1.1,信道的分类,根据载荷消息的媒体不同,根据信息传输的方式,邮递信道,电信道,光信道,声信道,输入和输出信号的形式,信道的统计特性,信道的用户多少,4,根据信道的用户多少,：,（,1,）两端,(,单用户,),信道,-,只有一个输入端和一个输出端的单向通信的信道；,（,2,）多端,(,多用户,),信道,-,输入端和输出端中至少有两个以上的用户，并且可以双向通信的信道。,5,根据信道输入端和输出端的关联,：,（,1,）无反馈信道,-,信道输出端无信号反馈到输入端，即输出端信号对输入端信号无影响、无作用；,（,2,）反馈信道,-,输出端的信号反馈到输入端，对输入端信号起作用。,根据信道的参数与时间的关系,：,（,1,）固定参数信道,-,信道参数不随时间变化而变化,（,2,）时变参数信道,-,信道参数随时间变化而变化,6,根据输入和输出信号的特点,：,（,1,）离散信道,-,输入输出的随机序列的取值都是离散的信道；,（,2,）连续信道,-,输入输出的随机序列的取值都是连续的信道；,（,3,）半离散或半连续信道,-,输入序列是离散型的，但相应的输出序列是连续的信道，或相反。,（,4,）波形信道,-,输入和输出都是一些时间上连续的随机信号。（又称模拟信道）,7,条件概率,P(y/x),描述了输入信号和输出信号之间统计依赖关系。反映了,信道的统计特性,。,3.1.2,离散信道的数学模型,8,根据信道的,统计特性即条件概率,P(y/x),的不同，离散信道又可分成三种情况：,无干扰信道,有干扰无记忆信道,有干扰有记忆信道,9,(1)无,干扰,(,无噪,),信道,信道中没有随机性的干扰或者干扰很小，输出信号,y,与,输入信号,x,之间有确定的、一 一对应的关系。即：,y,f,(,x,),10,(2),有干扰无,记忆信道,信道输入和输出之间的条件概率是一般的概率分布,。,如果任一时刻输出符号只统计依赖于对应时刻的输入符号，则这种信道称为无记忆信道。充要条件为：,11,(3),有,干扰,(,噪声,),有记忆信道,实际信道往往是既有干扰,(,噪声,),又有记忆的这种类型，这是更一般的情况。,在这一类信道中某一瞬间的输出符号不但与对应时刻的输入符号有关，而且还与此以前其他时刻信道的输入符号及输出符号有关，这样的信道称为,有记忆信道。,3.1.3,单符号离散信道,单符号离散信道：,输入符号为,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(b,j,/a,i,),这一组条件概率称为信道的,传递概率,或,转移概率,，可以用来描述信道干扰影响的大小。,13,信道中有干扰,(,噪声,),存在，可以用传递概率,P(b,j,/a,i,),来描述干扰影响的大小。,一般,简单的单符号离散信道,可以用,X,P(y/x),Y,三者加以描述。,其数学模型可以用概率空间,X,P(y/x),Y,描述。也可用下图来描述：,a,1,b,1,a,2,b,2,X,.,.,Y,.,a,r,b,s,P(b,j,/,a,i,),14,例,3.1,二元对称信道，,BSC,，,Binary Symmetrical Channel,一很重要的特殊信道，,X:0,1;Y:0,1;r=s=2,，,a,1,=b,1,=0,；,a,2,=b,2,=1,。,传递概率,:,p,是单个符号,传输发生错误,的概率。,（,1-p,）,表示是,无错误传输,的概率。,转移矩阵,:,0 1,0,1,1,p,a,1,=0,0=b,1,1,p,a,2,=1,1=b,2,p,p,15,符号“,2”,表示接收到了“,0”,、“,1”,以外的特殊符号,0 2 1,01,p,0,0,1,p,1,1,q,1,q,2,例,3.2,二元删除信道。,BEC,，,Binary Eliminated Channel,解：,X:0,，,1 Y:0,，,1,，,2,此时，,r,2,，,s,3,，,传递矩阵为：,16,一般离散单符号信道的传递概率可用矩阵形式表示，即,矩阵,P,完全描述了信道的特性，可用它作为离散单符号,信道的另一种数学模型,的形式。,P,中有些是信道干扰引起的错误概率，有些是信道正确传输的概率。所以该矩阵又称为,信道矩阵,（转移矩阵）,b,1,b,2,b,s,a,1,P,(,b,1,|,a,1,),P,(,b,2,|,a,1,),P,(,b,s,|,a,1,),a,2,P,(,b,1,|,a,2,),P,(,b,2,|,a,2,),P,(,b,s,|,a,2,),.,a,r,P,(,b,1,|,a,r,),P,(,b,2,|,a,r,),P,(,b,s,|,a,r,),17,3.2,平均互信息及平均条件互信息,本节进一步研究离散单符号信道的数学模型下的信息传输问题。,18,3.2.1,信道疑义度,信道输入信源,X,的熵,H(X),是在接收到输出,Y,以前，关于输入变量,X,的先验不确定性，称为,先验熵,。,如果信道中无干扰，信道输出符号与输入符号一一对应，接收到传送过来的符号就消除了对发送符号的先验不确定性。,19,接受到,b,j,后，关于,X,的不确定性为,这是接收到输出符号,b,j,后关于,X,的,后验熵,。,但一般信道中有干扰存在，接收到输,Y,后，对发送的是什么符号仍有不确定性。,怎样度量接收到,Y,后关于,X,的不确定性呢？,20,后验熵在输出符号集,Y,范围内是个随机量，对后验熵在符号集,Y,中求数学期望，得条件熵,-,信道疑义度,：,后验熵是当信道接收端接收到输出符号,b,j,后，关于输入符号的信息测度。,21,信道疑义度表示在输出端收到输出变量,Y,的符号后，对于输入端的变量,X,尚存在的平均不确定性。,这个对,X,尚存的不确定性是由于干扰引起的。,如果是一一对应信道，接收到输出,Y,后，对,X,的不确定性将完全消除，则信道疑义度为零。,22,已知，代表接收到输出符号以前关于输入量,X,的平均不确定性，而 代表接收到输出符号后关于输入变量,X,的平均不确定性。通过信道传输消除了一些不确定性，获得了一定的信息。所以定义,3.2.2,平均互信息,它代表接收到输出符号后平均每个符号获得的关于,X,的信息量。也表明，输入与输出两个随机变量之间的统计约束程度。,23,平均互信息就是,互信息,在两个概率空间,X,和,Y,中求,统计平均,的结果。,24,即：互信息量表示先验的不确定性减去尚存的不确定性，这就是,收信者获得的信息量,对于无干扰信道，,I(x,i,;,y,j,)=,I(x,i,),；,对于全损信道，,I(x,i,;,y,j,)=0,；,互信息量,I(x,i,;,y,j,),：,收到消息,y,后获得关于,x,的信息量,互信息可取正值，也可取负值,。取负值说明在为收到消息,y,之前对消息,x,是否出现的猜测的难易程度较小。由于噪声的存在，接收到消息,y,后，反而是收信者对消息,x,是否出现的猜测难疑度增加。,25,平均互信息,I(X;Y),：,I,(x,i,;,y,j,),的,统计平均,所以，平均互信息,I(X;Y),永远不会取负值。,最差的情况是平均互信息为零，即信道输出端接收到输出符号,Y,后不获得任何关于输入符号,X,的信息量。,26,关于平均互信息,I(X,;,Y),互信息,I(,x,;,y,),代表收到某消息,y,后获得关于某事件,x,的信息量。它可取正值，也可取负值。,若互信息,I(,x,;,y,)=0,。,若,I(X,;,Y),=0,，,表示,在,信道,输出端接收到输出符号,Y,后不获得任何关于,输,入符号,X,的信息量,-,全损信道,。,27,I(X;Y)=H(X)-H(X|Y),I(X;Y)=H(Y)-H(Y|X),I(X;Y)=H(X)+H(Y)-H(XY),其中：,平均互信息与各类熵的关系,28,平均互信息与各类熵之间关系的集合图（,维拉图,）表示：,H(X|Y,)=H(X)-I(X,;,Y),H(Y|X,)=H(Y)-I(X,;,Y),H(XY,)=H(X)+HY)-I(X,;,Y),H(X),H(Y),H(X/Y),H(Y/X),H(XY),图中，左边的圆代表随机变量,X,的熵，右边的圆代表随机变量,Y,的熵，两个圆重叠部分是平均互信息,I(X,;,Y),。,每个圆减去,I(X,;,Y),后剩余的部分代表两个疑义度。,I(X,;,Y),表示信源符号通过有噪信道传输后引起的信息量的损失,损失熵,由信道中噪声引起的,噪声熵,29,两种特殊信道,（,1,）离散无干扰信道,(,无损信道,),信道的输入和输出一一对应，信息无损失地传输，称为,无损信道,。,H(X|Y)=H(Y|X)=0,损失熵和噪声熵都为“,0”,由于噪声熵等于零，因此，输出端接收的信息就等于平均互信息,:,I(X;Y)=H(X)=H(Y),30,（,2,）输入输出独立信道,(,全损信道,),信道输入端,X,与输出端,Y,完全统计独立,H(X|Y)=H(X),H(Y|X)=H(Y),所以,I(X;Y)=0,I(X;Y)=H(X)-H(X|Y),信道的输入和输出没有,依赖,关系，信息无法传输，称为,全损信道,。,接收到,Y,后不可能消除有关输入端,X,的任何不确定性，所以获得的信息量等于零。同样，也不能从,X,中获得任何关于,Y,的信息量。,平均互信息,I(X,;,Y),等于零，表明了,信道两端随机变量的统计约束程度等于零,。,31,二种极限信道各类熵与平均互信息之间的关系,H(X|Y)=H(X),H(Y|X)=H(Y),I(X;Y)=0,H(X|Y)=H(Y|X)=0,I(X;Y)=H(X)=H(Y),无损信道：完全重迭,全损信道：完全独立,无损信道：,全损信道：,32,3.3,平均互信息的特性,平均互信息,I,(X,;,Y),具有以下特性：,（,1,）,非负性,即,I,(X,;,Y)=0,当,X,、,Y,统计独立时等式成立。,（,2,）极值性,即,I,(X,;,Y)=H(X),当,H(X/Y)=0,时，即信道中传输信息无损时，等式成立。,观察一个信道的输出，从平均的角度来看总能消除一些不确定性，接收到一定的信息。,从一个事件提取另一事件的信息量，最多只有另一事件的信息熵那么多，不会超过该事件自身所含有的信息量。,33,（,3,）交互性（对称性）,即,I,(X;Y)=,I,(Y;X),当,X,、,Y,统计独立时,I,(X;Y)=,I,(Y;X)=0,当信道无干扰，一一对应时,I,(X;Y)=,I,(Y;X)=H(X)=H(Y),34,（,4,）凸状性,所以，,平均互信息,I(X,;,Y),只是信源,X,的概率分布,P(,x,),和信道的传递概率,P(,y/x,),的函数，,即：,I(X;Y)=,f,P(x,),P(y|x),35,36,定理,3.1,平均互信息,I,(X,;,Y),是输入信源的概率分布,P(,x,),的,型凸函数。,（,1,）,对固定信道选择不同的信源,(,其概率分布不同,),与信道连接，在信道输出端接收到每个符号后获得的信息量是不同的。,（,2,）,对于每一个固定信道，一定存在有一种信源,(,某一种概率分布,P(x),，,使输出端获得的平均信息量为最大。,37,定理,3.2,平均互信息,I,(X;Y),是信道传递的概率,P(,y/x,),的,型凸函数。,当信源固定后，选择不同的信道来传输同一信源符号，在信道输出端获得关于信源的信息量是不同的。,对每一种信源都存在一种最差的信道，此时干扰,(,噪声,),最大，而输出端获得的信息量最小。,38,小结：各种熵之间的关系,39,信道对于信息率的容纳并不是无限制的，它不仅与物理信道本身的特性有关，还与信道输入信号的统计特性有关，它有一个极限值，即,信道容量,。,3.4,信道容量及其一般计算方法,信道的功能,：以信号形式传输和存储信息。,信道传输信息的速率,：与物理信道本身的特性、载荷信息的信号形式和信源输出信号的统计特性有关。,信道容量研究内容,：在什么条件下，通过信道的信息量最大。,40,什么是信道？,信道是传送信息的载体,信号所通过的通道。信息是抽象的，信道则是具体的。比如：二人对话，二人间的空气就是信道；打电话，电话线就是信道；看电视，听收音机，收、发间的空间就是信道。,信道的作用,在信息系统中信道主要用于传输与存储信息，而在通信系统中则主要用于传输。,研究信道目的在通信系统中研究信道，主要是为了描述、度量、分析不同类型信道，计算其容量，即极限传输能力，并分析其特性。,41,研究信道是要讨论信道中平均每个符号所能传送的信息量,-,信息传,输率,R,平均互信息,I(X;Y),就是接收到符号,Y,后平均每个符号获得的关于,X,的信息,量。,所以：,R,=I(X;Y)=H(X)H(X|Y),(,比特,/,符号,),信道中每秒平均传输的信息量,-,信息传输速率,R,t,R,t,R/t=I(X;Y)/t=H(X)/t H(X|Y)/t,（比特,/,秒）,42,由于平均互信息,I,(X;Y),是输入随机变量的,型凸函数，所以对一固定的信道，总存在一种信源，使传输每个符号平均获得的信息量最大。,即存在一个最大的信息传输率,-,定义为,信道容量,C,（比特,/,符号）,(Bit/s),C,t,仍称为,信道容量,若平均传输一个符号需要,t,秒钟，则信道在单位时间内平均传输的最大信息量为,C,t,：,43,即：,例,3.5,信道容量的计算,因此，二元对称信道的信道容量为：,二元对称信道，,I(X;Y),时，,I(X;Y),最大。,当,(,比特符号,),44,1.,无噪无损信道,3.4.1,离散无噪信道的信道容量,例如：,其信道矩阵是单位矩阵：,满足：,I(X;Y)=H(X)=H(Y),45,2.,有噪无损信道：,接收到符号,Y,后，对,X,符号是完全确定的。,损失熵,H(X/Y)=0,，,但噪声熵,H(Y/X),0,其信道矩阵：,所以：,I(X;Y)=H(X)H(Y),信道的传递矩阵中每一列有一个且仅有一个非零元素时，此信道一定是,有噪无损信道,。,46,3.,无噪有损信道,满足：,I(X;Y)=H(Y)H(X),47,48,综上所述：,损失熵等于零的信道称为,无损信道,；,噪声熵等于零的信道称为,无噪信道,；,一一对应的的无噪信道则为,无噪无损信道,。,求这三类信道的信道容量,C,的问题，已经从求平均互信息,I,（,X,；,Y),的极限问题退化为求信息熵,H(X),或,H,（,Y,）的极值问题,49,所谓,对称,信道，是指信道矩阵,P,中每一行都是由同一集合,p,1,，,p,2,，,，,p,s,中的诸元素不同排列组成，且每一列也都是由,q,1,，,q,2,，,，,q,r,中的诸元素不同排列组成。,具有这种对称信道矩阵的信道称为,对称离散信道,。,一般,s,r,。,3.4.2,对称离散信道的信道容量,例如：,都是对称离散信道,50,都不是对称离散信道,51,若输入和输出符号个数相同，都等于,r,，,且信道矩阵为：,则此信道称为,强对称信道或均匀信道,。,这类信道中总的错误概率为,p,，,对称地平均分配给,r-1,个输出符号。,它是对称离散信道的特例。,52,这一项是固定,X,x,时对,Y,求和，即对信道矩阵的行求和。,由于信道的对称性，所以,H(Y/X=,x,),与,x,无关,，为一常数，即,因此,对称离散信道,的信道容量,：,对称离散信道的平均互信息为,：,I(X;Y)=H(Y)-H(Y/X),53,54,55,56,在这个信道中，每个符号平均能够传输的最大信息为,0.0817,比特。,只有当信道的输入符号是等概率分布时才能达到这个最大值。,例,3.6,某对称离散信道的信道矩阵如下，求其信道容量。,解：,s=4,r=2,57,3.4.3,准对称信道的信道容量,58,59,信道矩阵 可以划分成三个子集，由子集的列组成的矩阵为,它们满足对称性，所以 所对应的信道为,准对称信道,。,同理，信道矩阵 可以划分成,60,61,62,3.4.4,一般离散信道的信道容量,63,若 即可结束，前面计算的,C,即为信道容量，否则要重新计算。,64,65,66,67,68,3.6,离散无记忆扩展信道及其信道容量,离散无记忆信道,(DMC,，,Discrete,Memoryless,Channel),，,其,传递概率满足,：,仍可用,X,，,P(,y,/,x,),，,Y,概率空间来描述。,不同的只是当信道传输消息序列时，输入随机序列与输出随机序列之间的传递概率等于对应时刻的随机变量的,传递概率的乘积,。,69,设离散无记忆信道的,输入符号集,A,a,1,，,，,a,r,，,输出符号集,B,b,1,，,，,b,s,，,信道矩阵为,:,70,则此无记忆信道的,N,次扩展信道,的数学模型如图所示,:,而,信道矩阵,：,其中：,71,例,3.12,求二元无记忆对称,信,道,（,BSC,）,的二次扩展信道。,解：,BSC,的输入和输出变量,X,和,Y,的取值都是,0,或1，因此,，,二次扩展信道的输入符号集为,A,00，01,，,10，11,，,共有2,2,4个符号,，,输出符号集为,B,00，01,，,10，11,。,由于是,无记忆信道,，可,求得,二次扩展信道的传递概率,：,信道矩阵,：,72,根据平均互信息的定义，可得,无记忆信道的,N,次扩展信道的平均互信息,：,73,若信道的输入随机序列为,X=(X,1,X,2,X,N,),，,通过信道传输，接收到的随机序列为,Y,(Y,1,Y,2,Y,N,),。,假若信道是无记忆的,，即信道传递概率满足：,则有：,式中,X,i,Y,i,是对应第,i,位的随机变量。,若信源是无记忆的，则等式成立。,直观分析,：如果信源有记忆，前面传送的符号带有后面符号的信息，使得后面传送的符号的互信息减少,74,若信道的输入随机序列为,X=(X,1,X,2,X,N,),，,通过信道传输，接收到的随机序列为,Y,(Y,1,Y,2,Y,N,),。,假若信源是无记忆的,，则有：,其中,X,i,和,Y,i,是随机序列,X,和,Y,中的第,i,位随机变量。,直观分析,：如果信道有记忆，后面传送的符号带有前面符号的信息，使得前面传送的符号的互信息增加。,若,信道和信源都是无记忆的,，则：,75,所以，对于,一般的离散无记忆信道的,N,次扩展信道,，其,信道容量,是：,一般离散无记忆信道的,N,次扩展信道,76,一般情况下,，消息序列在离散无记忆的,N,次扩展信道中传输的信息量：,I,（,X;Y,）,NC,即：,C,N,=NC,77,3.7,独立并联信道及其信道容量,一般独立并联信道如图，设有,N,个信道，它们的输入、输出、传递概率如图。,在这,N,个独立并联信道中，每一个信道的输出只与本信道的输入有关，而与其他信道的输入和输出都无关。,也称为,并用信道,。,78,可推广得：,即,联合,平均互信息不大于各自信道的平均互信息之和。,设,N,个信道,联合,传递概率满足：,相当于信道是无记忆时应满足的条件。,79,因此得独立并联信道的信道容量,即,独立并联信道的信道容量不大于各自信道的信道容量之和,。,只有当输入符号相互独立，且输入符号的概率分布达到各信道容量的最佳输入分布时，独立并联信道的信道容量才等于各信道容量之和。,80,3.8,串联信道的互信息和数据处理定理,81,82,83,表明二元对称信道串联后会增加信息的损失。,串联级数增加信息的损失增加。,84,85,3.9,信源与信道的匹配,在一般情况下，当信源与信道相连接时，其信息传输率并未达到最大。我们总希望能使信息传输率越大越好，能达到或尽可能接近于信道容量，由前面的分析可知，信息传输率接近于信道容量只有在信源取最佳分布时才能实现。,由此可见，当信道确定后，信道的信息传输率与信源分布是密切相关的。当达到信道容量时，我们称信源与信道达到,匹配,，否则认为信道有剩余。,86,信道剩余度定义为：,信道剩余度,=,相对信道剩余度,=,表示信道的实际传信率和信道容量之差。,信道剩余度,可以用来衡量信道利用率的高低。,87,在无损,信,道中，,信,道容量,C,log,r,(r是信道输入符号数)。而,I,(,X,;,Y,),H(X,)，因而,：,无损,信,道,的相对,剩余度,=,上式说明提高无损信道信息传输率就等于减少信源的剩余度。对于无损信道，可以通过信源编码、减少信源的剩余度，使信息传输率达到信道容量。,88,因此引入问题,：在一般通信系统中，如何将信源发出的消息,(,符号,),转换成适合信道传输的符号,(,信号,),从而达到信源与信道的匹配。,注：,信道容量,C,和输入信号的概率分布无关，它只是信道传输概率的函数，只与信道的统计特性有关。,89,例如,，某离散无记忆信源,通过一个无噪无损二元离散信道进行传输。,对,二元离散信道的信道容量,为：,C,1(,比特信道符号,),对本信源的信息熵为,H(X),1.937(,比特信源符号,),要使信源在此二元信道中传输，必须对,X,进行二元编码：,90,因此，,必须通过合适的信源编码，使信道的信息传输率接近或等于信道容量。,对于码,(,比特信道符号,),对于码,(,比特信道符号,),91,总结：,92,