[理学]3--第3章信息论课件.ppt

信道与信道容量,第三章,信息论与编码,2,2019/5/3 西北大学信息学院,内容,D,3.1 信道数学模型和分类,3.3 离散单个符号信道及其容量,3.4 离散序列信道及其容量,3.5 信源于信道的匹配,第三章 信道与信道容量,结束,3.2 平均互信息,重点,信息论与编码,3,2019/5/3 西北大学信息学院,信道的功能：以信号形式传输和存储信息。 信道传输信息的速率：与物理信道本身的特性、载荷信息的信号形式和信源输出信号的统计特性有关。 信道容量研究内容：在什么条件下，通过信道的信息量最大。,信息论与编码,4,2019/5/3 西北大学信息学院,3.1 信道数学模型和分类,3.1.1 信道分类,3.1.2 信道数学模型,信息论与编码,5,2019/5/3 西北大学信息学院,信道,信道：信息传输的通道 在通信中,信道按其物理组成常被分成微波信道、光纤信道、电缆信道等。信号在这些信道中传输的过程遵循不同的物理规律, 通信技术必须研究信号在这些信道中传输时的特性 信息论不研究信号在信道中传输的物理过程,并假定信道的传输特性已知,这样信息论就可以抽象地将信道用下图所示的模型来描述。,信 道,输入量X (随机过程),输出量Y (随机过程),p(Y|X),6,根据信道用户的多少：,根据输入端和输出端的关联：,根据输入输出随机变量个数的多少：,3.1.1信道分类,7,根据信道参数与时间的关系：,根据信道输入和输出的关系：,信道分类,8,根据信道上有无干扰关系：,根据信道上有无记忆关系：,以下我们只研究无反馈、固定参数的单用户离散信道。,信道分类,信息论与编码,9,2019/5/3 西北大学信息学院,信道分类,按输入输出信号之间的关系是否是确定关系: 无干扰信道： 输入/输出符号之间有确定的一一对应关系 有干扰信道： 输入/输出之间关系是一种统计依存的关系 输入/输出的统计关系： 离散无记忆信道： 用条件概率矩阵来描述。 离散有记忆信道： 可像有记忆信源中那样引入状态的概念。,信息论与编码,10,2019/5/3 西北大学信息学院,无干扰(无噪声)信道,无干扰(无噪声)信道 信道的输出信号Y与输入信号X之间有确定的关系Y=f (X),已知X后就确知Y 转移概率:,信息论与编码,11,2019/5/3 西北大学信息学院,有干扰无记忆信道 信道的输出信号Y与输入信号X之间没有确定的关系,但转移概率满足:,有干扰无记忆信道可分为: 二进制离散信道 离散无记忆信道 离散输入、连续输出信道 波形信道,信息论与编码,12,2019/5/3 西北大学信息学院,有干扰有记忆信道 一般情况都是如此，例如实际得数字信道中，当信道特性不理想，存在码间干扰时，输入信号不但与当前得输入信号有关，还和以前的输入信号有关。,13,单符号离散信道的数学模型,设输入Xa1 an 输出 Yb1 bm 信道转移概率/信道传递概率：条件概率p(bj /ai)。 其信道模型如图所示。,3.1.2 信道参数,14,条件概率p(bj/ai)表示成矩阵形式：,15,例1 二元对称信道（BSC） X=0,1; Y=0,1; p(0/0)=p(1/1)=1-p; p(0/1)=p(1/0)=p;,16,例2 二元删除信道(BEC) X=0,1； Y=0,2,1。,17,由此可见，一般单符号离散信道的传递概率可以用矩阵表示:,西北大学信息学院,18,2019/5/3,3.2平均互信息,设有两个随机事件X和Y ,X取值于信源发出的离散消息集合, Y取值于信宿收到的离散符号集合,有扰信道,干扰源,信源X,信宿Y,西北大学信息学院,19,2019/5/3,互信息,如果信道是无噪的,当信源发出消息xi后,信宿必能准确无误地收到该消息,彻底消除对xi的不确定度,所获得的信息量就是xi的不确定度I(xi),即xi本身含有的全部信息。 一般而言,信道中总是存在着噪声和干扰,信源发出消息xi,通过信道后信宿只可能收到由于干扰作用引起的某种变型yj 。 信宿收到yj 后推测信源发出xi的概率p(xi|yj)称为后验概率。 信源发出消息xi的概率p(xi) 称为先验概率。,西北大学信息学院,20,2019/5/3,互信息,互信息 定义为 xi的后验概率与先验概率比值的对数,互信息I(xi;yj)表示接收到某消息yj后获得的关于事件xi的信息量。,互信息量的三种不同表达式,观察者站在输出端 自信息量：对yj一无所知的情况下xi存在的不确定度； 条件自信息量：已知yj 的条件下xi 仍然存在的不确定度； 互信息量：两个不确定度之差是不确定度被消除的部分， 即等于自信息量减去条件自信息量。 观察者站在输入端 观察者得知输入端发出xi前、后对输出端出现yj的不确定度的差。,观察者站在通信系统总体立场上 通信前：输入随机变量X和输出随机变量Y之间没有任何关联关系，即X，Y统计独立：p(xi yj)=p(xi)p(yj) 先验不确定度 通信后：输入随机变量X和输出随机变量Y之间由信道的统计特性相联系，其联合概率密度： p(xi yj)=p(xi)p(yj /xi )= p(yj)p(xi / yj) 后验不确定度 通信后的互信息量，等于前后不确定度的差 这三种表达式实际上是等效的，在实际应用中可根据具体情况选用一种较为方便的表达式。,互信息的性质,对称性 相互独立时的X和Y 互信息量可为正值或负值,对称性,I(xi;yj)=I(yj; xi) 互信息量的对称性表明： 两个随机事件的可能结果xi和yj之间的统计约束程度； 从yj得到的关于xi的信息量I(xi;yj)与从xi得到的关于yj的信息量I(yj; xi)是一样的，只是观察的角度不同而已。,相互独立时的X和Y,这时 p(xi yj)=p(xi)p(yj) 互信息量为 表明xi和yj之间不存在统计约束关系，从yj得不到关于的xi任何信息，反之亦然。,互信息量可为正值或负值,当后验概率大于先验概率时，互信息量为正。 当后验概率小于先验概率时，互信息量为负。 说明收信者未收到yj以前，对消息xi的是否出现的猜测难疑程度较小，但由于噪声的存在，接收到消息yj后对xi是否出现的猜测的难疑程度增加了，也就是收信者接收到消息yj后对xi出现的不确定性反而增加，所以获得的信息量为负值。 当后验概率与先验概率相等时，互信息量为零。这就是两个随机事件相互独立的情况。,西北大学信息学院,27,2019/5/3,例3某地二月份天气 构成的信源为：,若得知“今天不是晴天”,把这句话作为收到的消息y1 当收到y1后,各种天气发生的概率变成后验概率了 p(x1|y1) = 0, p(x2|y1) = 1/2 , p(x3|y1) = 1/4 , p(x4|y1) = 1/4,求得自信息量分别为,计算y1与各种天气之间的互信息量 对天气x1，不必再考虑 对天气x2， 对天气x3, 对天气x4 结果表明从y1分别得到了各1比特的信息量； 或者说y1 使x2，x3，x4的不确定度各减少量1比特。,信息论与编码,29,2019/5/3 西北大学信息学院,30,信道疑义度,这是收到ai后关于X的后验熵，表示收到bj后关于输入符号的信息测度。,这是关于X的先验熵，表示收到输出前关于X的不确定性度量。,31,这个条件熵称为信道疑义度，表示输出端在收到一个符号后，对输入符号尚存的不确定性，这是由信道干扰造成的，如果没有干扰，H(X/Y)=0。 一般情况下H(X/Y)小于H(X)，说明经过信道传输，总能消除一些信源的不确定性，从而获得一些信息。,将后验熵对随机 变量Y求数学期望,西北大学信息学院,32,2019/5/3,平均互信息,平均互信息定义,信息= 先验不确定性后验不确定性 = 不确定性减少的量,Y未知,X 的不确定度为H(X) Y已知,X 的不确定度变为H(X |Y),西北大学信息学院,2019/5/3,平均互信息,通信系统中,若发端的符号为X ,收端的符号为Y 如果是一一对应信道,接收到Y后,对X的不确定性将完全消除：H(X|Y) = 0 一般情况： H(X |Y) H(X),即了解Y后对X的不确定度的将减少 通过信道传输消除了一些不确定性,获得了一定的信息。,西北大学信息学院,34,2019/5/3,平均互信息,平均互信息的另一种定义方法：,西北大学信息学院,35,2019/5/3,例假设一条电线上串联了8个灯泡x1, x2，x8如图，这8个灯泡损坏的概率相等p(xi) = 1/8，现假设只有一个灯泡已损坏，致使串联灯泡都不能点亮。,未测量前,8个灯泡都有可能损坏,它们损坏的先验概率: p(xi)=1/8,这时存在的不确定性：,西北大学信息学院,36,2019/5/3,第1次测量后,可知4个灯泡是好的,另4个灯泡中有一个是坏的,这时后验概率p(xi|y) =1/4 尚存在的不确定性,所获得的信息量就是测量前后不确定性减少的量, 第1次测量获得的信息量：,西北大学信息学院,37,2019/5/3,第2次测量后变成猜测哪2个灯泡中一个是损坏的,这时后验概率为： p(xi|yz) = 1/2 尚存在的不确定性：,第2次测量获得的信息量：,第3次测量完全消除了不确定性，能获知哪个灯泡是坏了的。尚存在的不确定性等于零。 第3次测量获得的信息量：,西北大学信息学院,38,2019/5/3,要从8个等可能损坏的串联灯泡中确定哪个灯泡是坏的,至少要获得3个bit的信息量,西北大学信息学院,39,2019/5/3,方法2：逐个检查 第1次: x1坏,获得信息量=3bit,可能性较小1/8； x1通,其余7只中1只坏,坏灯泡的不确定性：log27=2.8073bit 获得信息量=3-2.8073=0.1927bit,可能性较大7/8 第1次所获得的平均信息量:,“对半开” 第1次所获得的平均信息量:,西北大学信息学院,40,2019/5/3,互信息量,在有3个变量的情况下,符号xi与符号yj , zk之间的互信息量定义为,同理,西北大学信息学院,41,2019/5/3,条件互信息,我们定义在已知事件zk的条件下,接收到yj后获得关于某事件xi的条件互信息,西北大学信息学院,42,2019/5/3,平均互信息与各类熵的关系,熵只是平均不确定性的描述; 不确定性的消除(两熵之差)才等于接收端所获得的信息量。 获得的信息量不应该和不确定性混为一谈,西北大学信息学院,43,2019/5/3,维拉图,H(X|Y),H(X),H(Y),H(XY),H(Y|X),I(X;Y),西北大学信息学院,44,2019/5/3,条件熵,H(X|Y)：信道疑义度，损失熵 信源符号通过有噪信道传输后所引起的信息量的损失。 信源X的熵等于接收到的信息量加上损失掉的信息量。 H(Y|X)：噪声熵，散布熵 它反映了信道中噪声源的不确定性。 输出端信源Y 的熵H(Y)等于接收到关于X的信息量I(X;Y)加上H(Y|X),这完全是由于信道中噪声引起的。,西北大学信息学院,45,2019/5/3,若信道是无噪一一对应信道,信道传递概率：,计算得:,西北大学信息学院,46,2019/5/3,若信道输入端X与输出端Y完全统计独立,则:,平均互信息量的性质, 对称性 非负性 极值性 凸函数性 数据处理定理, 对称性,I(X;Y)= I(Y;X) 证明：根据互信息量的对称性I(xi;yj)= I(yj;xi) 结论：由Y提取到的关于X的信息量与从X中提取到的关于Y的信息量是一样的。I(X;Y)和 I(Y;X)只是观察者的立足点不同。,自然对数性质：lnxx-1，x0，当且仅当x=1时取等号。, 非负性,I(X;Y)0,即 I(X;Y)0 当且仅当X和Y相互独立，即p(xiyj)= p(xi) p(yj) I(X;Y)=0 式中 结论： 平均互信息量不是从两个具体消息出发，而是从随机变量X和Y的整体角度出发，并在平均意义上观察问题，所以平均互信息量不会出现负值。 或者说从一个事件提取关于另一个事件的信息，最坏的情况是0，不会由于知道了一个事件，反而使另一个事件的不确定度增加。, 极值性,I(X;Y)H(X) I(Y;X)H(Y) 证明：由于 I(X;Y)=H(X)- H(X/Y)0， I(Y;X)=H(Y)- H(Y/X)0, H(Y/X)0， H(X/Y)0, 所以 I(X;Y)H(X)，I(Y;X)H(Y) 从一个事件提取关于另一个事件的信息量，至多是另一个事件的熵那么多，不会超过另一个事件自身所含的信息量。 当X和Y是一一对应关系时：I(X;Y)=H(X)，这时H(X/Y)=0。从一个事件可以充分获得关于另一个事件的信息，从平均意义上来说，代表信源的信息量可全部通过信道。 当X和Y相互独立时：H(X/Y) =H(X)， I(Y;X)=0。从一个事件不能得到另一个事件的任何信息，这等效于信道中断的情况。, 凸函数性,平均互信息量的数学特性 平均互信息量I(X;Y)是输入信源概率分布p(xi)的上凸函数 平均互信息量I(X;Y)是输入转移概率分布p(yj /xi)的下凸函数,平均互信息量的数学特性,信息论与编码,54,2019/5/3 西北大学信息学院,平均互信息量是p(xi)和p(yj /xi)的函数， 即I(X;Y)=f p(xi), p(yj /xi)； 若固定信道，调整信源， 则平均互信息量I(X;Y)是p(xi)的函数，即I(X;Y)=f p(xi)； 若固定信源，调整信道， 则平均互信息量I(X;Y)是p(yj /xi)的函数，即I(X;Y)=f p (yj /xi)。,I(X;Y)是 p(xi)的上凸函数,上凸函数：同一信源集合x1,x2,xn，对应两个不同的概率分布p1(xi)和p2(xi)(i=1,2, ,n)，若有小于1的正数01，使不等式 fp1(xi)+(1-)p2(xi)fp1(xi)+(1-)fp2(xi) 成立，则称函数f为p(xi)的上凸函数。如果式中仅有大于号成立，则称f为严格的上凸函数。,I(X;Y)是 p(yj/xi)的下凸函数,下凸函数： Ip1(yj /xi)+(1-)p2(yj /xi)Ip1(yj /xi)+(1-)Ip2(yj /xi),信息论与编码,56,2019/5/3 西北大学信息学院,信息论与编码,57,2019/5/3 西北大学信息学院,结论1： 当q不变/固定信道特性时，可得I(X;Y)随输入概率分布p变化的曲线，如图2.1.9所示； 二进制对称信道特性固定后，输入呈等概率分布时，平均而言在接收端可获得最大信息量。,结论2： 当固定信源特性p时，I(X;Y)就是信道特性q的函数，如图2.1.10所示； 当二进制对称信道特性q=/q=1/2时，信道输出端获得信息量最小，即等于0。说明信源的全部信息信息都损失在信道中了。这是一种最差的信道。,60,作业,P134 3.1 P135 3.3,信息论与编码,61,2019/5/3 西北大学信息学院,3.3离散单个符号信道及其容量,62,信道容量C：在信道中最大的信息传输速率，单位是比特/信道符号。 单位时间的信道容量Ct：若信道平均传输一个符号需要t秒钟，则单位时间的信道容量为： Ct实际是信道的最大信息传输速率。,信息传输率：R=I(X,Y)=H(X)-H(X/Y)=H(Y)-H(Y/X) bit/符号 由定理3.1可知，对于每一个确定信道，都有一个信源分布，使得信息传输率达到最大值，我们把这个最大值称为该信道的信道容量。,信道容量,63,C和Ct都是求平均互信息I(X;Y)的条件极大值问题，当输入信源概率分布p(xi)调整好以后， C和Ct已与p(xi)无关，而仅仅是信道转移概率的函数，只与信道统计特性有关；它是信道的特征参数，反应的是信道的最大的信息传输能力。 信道容量是完全描述信道特性的参量； 信道容量是信道能够传送的最大信息量。,结 论,对于二元对称信道，由图可以看出信道容量等于 1-H(P),信息论与编码,64,2019/5/3 西北大学信息学院,3.2.1 无干扰离散信道,设信道的输入XA=a1 an,输出YB=b1 bm 无噪无损信道 输入和输出符号之间有确定的一一对应关系,X,a1 Y b1 a2 b2 a3 b3,1,1,1,信息论与编码,65,2019/5/3 西北大学信息学院,无干扰离散信道,无噪无损信道,X,a1 b1 Y a2 b2 an-1 bn-1 an bn,1,1,信息论与编码,66,2019/5/3 西北大学信息学院,无干扰离散信道,无噪无损信道 由,计算得： 噪声熵H(Y|X) = 0 损失熵H(X|Y) = 0,信息论与编码,67,2019/5/3 西北大学信息学院,无干扰离散信道,无噪有损信道 多个输入变成一个输出(nm),X,a1 Y a2 b1 a3 a4 b2 a5,1,1,1,1,1,输出Y是输入X的确定函数,但不是一一对应,而是多一对应关系。,信息论与编码,68,2019/5/3 西北大学信息学院,无干扰离散信道,无噪有损信道 多个输入变成一个输出(nm),噪声熵H(Y|X) 0 损失熵H(X|Y) 0,信道中接收到符号Y后不能完全消除对X的不确定性,信息有损失。但输出端Y的平均不确定性因噪声熵等于零而没有增加。,信息论与编码,69,2019/5/3 西北大学信息学院,无干扰离散信道,有噪无损信道 一个输入对应多个输出(nm),X,b1 Y a1 b2 b3 a2 b4 b5,1/3,1/3,1/3,1/4,3/4,计算得,同理,由,信息论与编码,70,2019/5/3 西北大学信息学院,无干扰离散信道,有噪无损信道 一个输入对应多个输出(nm),接收到符号Y后,对发送的X符号是完全确定的。 噪声熵H(Y|X) 0 损失熵H(X|Y) = 0,信息论与编码,71,2019/5/3 西北大学信息学院,无干扰离散信道,无噪无损信道,无噪有损信道,有噪无损信道,信息论与编码,72,2019/5/3 西北大学信息学院,3.3.2 对称DMC信道,对称离散信道： 对称性: 每一行都是由同一集p1, p2,pm 的诸元素不同排列组成输入对称 每一列都是由集q1, q2,qn的诸元素不同排列组成输出对称,满足对称性,所对应的信道是对称离散信道。,信息论与编码,73,2019/5/3 西北大学信息学院,对称DMC信道,信道矩阵,不具有对称性,因而所对应的信道不是对称离散信道。,信息论与编码,74,2019/5/3 西北大学信息学院,对称DMC信道,若输入符号和输出符号个数相同,都等于n,且信道矩阵为,此信道称为强对称信道 (均匀信道) 信道矩阵中各列之和也等于1,信息论与编码,75,2019/5/3 西北大学信息学院,对称DMC信道,对称离散信道的平均互信息为,信息论与编码,76,2019/5/3 西北大学信息学院,对称DMC信道,对称DMC信道的容量：,上式是对称离散信道能够传输的最大的平均信息量,它只与对称信道矩阵中行矢量p1, p2,pm 和输出符号集的个数m有关。,强对称信道的信道容量：,信息论与编码,77,2019/5/3 西北大学信息学院,设二进制对称信道的输入概率空间 信道矩阵：,BSC信道容量,信息论与编码,78,2019/5/3 西北大学信息学院,信息论与编码,79,2019/5/3 西北大学信息学院,p,C,当固定信源的概率分布时,I (X,Y) 是p的 下凸函数。,信道无噪声,当p = 0, C =10 = 1bit = H(X),当p =1/2,信道强噪声,BSC信道容量,BSC信道容量,信息论与编码,80,2019/5/3 西北大学信息学院,信道容量,定理： 给定转移概率矩阵P后,平均互信息I (X;Y)是输入信源的概率分布p(ai)的 型上凸函数。,定理： 平均互信息I (X;Y)是信道传递概率p(bj|ai)的 型凸函数。,信道容量是完全描述信道特性的参量,是信道能够传输的最大信息量。,信息论与编码,81,2019/5/3 西北大学信息学院,当信源输入符号的速率为rs(符/秒),信道容量,BSC信道容量,实际信息传输速率Rt为,进入信道输入端的信息速率,信息论与编码,82,2019/5/3 西北大学信息学院,串联信道,例3-3 设有两个离散BSC信道,串接如图,两个BSC信道的转移矩阵为:,X0,0Z,Y,1,1,1-p,1-p,1-p,p,串联信道的转移矩阵为:,1-p,p,信息论与编码,83,2019/5/3 西北大学信息学院,串联信道,X0,0Z,Y,1,1,求得:,在实际通信系统中,信号往往要通过几个环节的传输,或多步的处理,这些传输或处理都可看成是信道,它们串接成一个串联信道。,p,p,1-p,1-p,1-p,1-p,信息论与编码,84,2019/5/3 西北大学信息学院,串联信道,由信息不增原理,信道2,信道m,信道1,可以看出,串接的信道越多,其信道容量可能会越小,当串接信道数无限大时,信道容量可能会趋于0,X,Y,Z,信息论与编码,85,2019/5/3 西北大学信息学院,3.3.3 准对称DMC信道,准对称信道 转移概率矩阵P是输入对称而输出不对称 将信道矩阵P的列划分成若干个互不相交的子集mk,由mk为列组成的矩阵Pk是对称矩阵。,它们满定对称性,所以P1所对应的信道为准对称信道。,信息论与编码,86,2019/5/3 西北大学信息学院,准对称信道的信道容量,准对称信道,准对称信道容量,信息论与编码,87,2019/5/3 西北大学信息学院,准对称信道的信道容量,当输入分布为等概率时：,其中n是输入符号集的个数,(p1, p2,pm)为准对称信道矩阵中的行元素。 设矩阵可划分成r个互不相交的子集。 Nk是第k个子矩阵Pk中行元素之和, Mk是第k个子矩阵Pk中列元素之和。,信息论与编码,88,2019/5/3 西北大学信息学院,例：设信道传递矩阵为,计算得：N1 =3/4, N2 = 1/4, M1=3/4, M2 = 1/4,将它分成,信息论与编码,89,2019/5/3 西北大学信息学院,3.3.4 一般DMC信道,定理： 一般离散信道的平均互信息I(X;Y)达到极大值的充分和必要条件是输入概率p(ai)必须满足: I (ai;Y) = C 对于所有ai其p(ai)0 I (ai;Y) C 对于所有ai其p(ai) = 0,上式说明： 当信道的平均互信息I(X;Y)达到信道容量时,输入符号概率集p(ai)中每一个符号ai对输出端Y提供相同的互信息,只是概率为0的除外。,90,可以利用该定理对一些特殊信道求得它的信道容量,例：输入符号集为:0,1,2,假设P(0)=P(2)=1/2，P(1)=0，则：,91,所以：,92,对于一般信道的求解方法，就是求解方程组,移项得：,令,则,若r=s，此方程有解，可以解出s各未知数 ，再根据,得,从而,93,例：,可列方程组：,解之得：,信息论与编码,94,2019/5/3 西北大学信息学院,3.4 离散序列信道及容量,信息论与编码,95,2019/5/3 西北大