信息论与编码理论基础（第四章）课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,西安电子科技大学,*,第四章：,信道及其容量,4.1,信道分类,4.2,离散无记忆信道,4.5,信道的组合,4.6,时间离散的无记忆连续信道,4.7,波形信道,2024/9/4,1,第四章：信道及其容量4.1 信道分类2023/9/101,4.1,信道分类,信道是传输信息的媒质或通道。（输入,信道,输出）,说明,（,1,）信道输入是随机过程。,（,2,）信道响应特性是条件概率,P,(,输出值为,y,|,输入值为,x,),，又称为转移概率。,（,3,）信道输出是随机过程，输出的概率分布可以由输入的概率分布和信道的响应特性得到。（全概率公式）,（,4,）根据信道输入、信道响应特性、信道输出的情况，可将信道分类：离散信道（又称为数字信道）；连续信道（又称为模拟信道）；特殊的连续信道,波形信道；恒参信道和随参信道；无记忆信道和有记忆信道；等等。,2024/9/4,2,4.1 信道分类信道是传输信息的媒质或通道。（输入信道,4.2,离散无记忆信道,定义,4.2.1,和定义,4.2.2,(p104),如果,（,1,）信道的输入为随机变量序列,X,1,X,2,X,3, ,，其中每个随机变量,X,u,的事件集合都是,0, 1, ,K,-1,，,（,2,）信道的输出为随机变量序列,Y,1,Y,2,Y,3, ,，其中每个随机变量,Y,u,的事件集合都是,0, 1, ,J,-1,，,则称该信道为离散信道。如果更有,（,3,）,P,(,Y,1,Y,2,Y,N,)=(,y,1,y,2,y,N,)|(,X,1,X,2,X,N,)=(,x,1,x,2,x,N,),=,P,(,Y,1,=,y,1,|,X,1,=,x,1,),P,(,Y,2,=,y,2,|,X,2,=,x,2,),P,(,Y,N,=,y,N,|,X,N,=,x,N,),，,则称该信道为离散无记忆信道（,DMC,）。如果更有,（,4,）对任意,x,0, 1, ,K,-1,，,y,0, 1, ,J,-1,，任意两个时刻,u,和,v,，还有,P,(,Y,u,=,y,|,X,u,=,x,)=,P,(,Y,v,=,y,|,X,v,=,x,),，,则称该信道为离散无记忆平稳信道。,2024/9/4,3,4.2 离散无记忆信道定义4.2.1和定义4.2.2(p,4.2,离散无记忆信道,关于,定义,4.2.1,和定义,4.2.2,的注解,“离散”的含义是时间离散，事件离散。即：信道的输入、输出时刻是离散的，且输入随机变量和输出随机变量都是离散型的随机变量。,“无记忆”的含义是信道响应没有时间延迟，当时的输出只依赖于当时的输入。,“平稳”的含义是信道在不同时刻的响应特性是相同的。,“离散无记忆平稳信道”是最简单的信道，信道在某一时刻,u,的响应特性,P,(,Y,u,=,y,|,X,u,=,x,),；,x,0, 1, ,K,-1,，,y,0, 1, ,J,-1,，,就能很简单地计算出,信道在任意时间段的响应特性。,2024/9/4,4,4.2 离散无记忆信道关于定义4.2.1和定义4.2.2,4.2,离散无记忆信道,一、有关,DMC,的容量定理,（所说的,DMC,都是离散无记忆平稳信道）,设,DMC,在某个时刻输入随机变量为,X,，输出随机变量为,Y,。,信道响应特性为转移概率矩阵,p,(,y,|,x,),，,x,0, 1, ,K,-1,，,y,0, 1, ,J,-1,，,它是一个,K,J,阶矩阵（其中,p,(,y,|,x,)=,P,(,Y,=,y,|,X,=,x,),）。,X,的概率分布为,x,q,(,x,),x,0, 1, ,K,-1,。,Y,的概率分布为,y,w,(,y,),y,0, 1, ,J,-1,。,以下的结论是我们已知的。,2024/9/4,5,4.2 离散无记忆信道一、有关DMC的容量定理2023/,4.2,离散无记忆信道,（,1,）转移概率矩阵的每一行都是一个概率向量。,2024/9/4,6,4.2 离散无记忆信道（1）转移概率矩阵的每一行都是一个,4.2,离散无记忆信道,（,2,）对任意,y,0, 1, ,J,-1,，由全概率公式有,2024/9/4,7,4.2 离散无记忆信道（2）对任意y0, 1, ,4.2,离散无记忆信道,（,3,）,I,(,X,;,Y,),是概率向量,q,(,x,),x,0, 1, ,K,-1,和转移概率矩阵,p,(,y,|,x,),，,x,0, 1, ,K,-1,，,y,0, 1, ,J,-1,的函数。,2024/9/4,8,4.2 离散无记忆信道（3）I(X; Y)是概率向量q,4.2,离散无记忆信道,（,4,）设转移概率矩阵,p,(,y,|,x,),，,x,0, 1, ,K,-1,，,y,0, 1, ,J,-1,确定，希望选择概率向量,q,(,x,),x,0, 1, ,K,-1,使,I,(,X,;,Y,),达到最大。则见定理,2.6.2,。,定义,4.2.3,(p105),离散无记忆信道的,信道容量,定义为如下的,C,。达到信道容量的输入概率分布,x,q,(,x,),x,0, 1, ,K,-1,称为,最佳输入分布,。 其中,2024/9/4,9,4.2 离散无记忆信道（4）设转移概率矩阵p(y|x),4.2,离散无记忆信道,定理,4.2.2,(p106),（,1,）输入概率分布,x,q,(,x,),x,0, 1, ,K,-1,是最佳输入分布的充分必要条件为：对任何满足,q,(,k,)0,的,k,，,都取一个相同的值；对任何满足,q,(,k,)=0,的,k,，,I,(,X,=,k,;,Y,),此相同的值。,（,2,）此时此相同的值恰好就是信道容量,C,。,（定理,4.2.2,实际上叙述了定理,2.6.2,的含义。）,2024/9/4,10,4.2 离散无记忆信道定理4.2.2(p106) 20,4.2,离散无记忆信道,注解,给定一个,DMC,信道的响应特性，也就是说给定一个信道的转移概率矩阵,p,(,y,|,x,),，,x,0, 1, ,K,-1,，,y,0, 1, ,J,-1,，,达到信道容量时所对应的最佳输入分布是满足定理,4.2.2,条件的概率向量,q,(,x,),x,0, 1, ,K,-1,。,其信道容量是每个使得,q,(,k,)0,的,k,所对应的半平均互信息量,I,(,X,=,k,;,Y,),。,如果对,DMC,信道没有任何简化，要计算最佳输入分布并不容易。但是，通常使用的,DMC,是很简单的（比如，以下的准对称信道和对称信道），最佳输入分布很容易求出。,2024/9/4,11,4.2 离散无记忆信道注解2023/9/1011,4.2,离散无记忆信道,二、对称,DMC,和准对称,DMC,的,信道容量与最佳输入分布的计算,定义,4.2.45,(p108),设,DMC,的转移概率矩阵为,若,P,的任一行是第一行的置换，则称信道是,关于输入为对称的,。,若,P,的任一列是第一列的置换，则称信道是,关于输出为对称的,。,若信道是关于输入为对称的，又是关于输出为对称的，则称信道为,对称信道,。,2024/9/4,12,4.2 离散无记忆信道二、对称DMC和准对称DMC的20,4.2,离散无记忆信道,命题,1,若,DMC,关于输入为对称的，则,对任意,k,0, 1, ,K,-1,都成立。,证明,p,(,y,|,x,),，,y,=0,J,-1,与,p,(,y,|,k,),，,y,=0,J,-1,互为置换，所以,2024/9/4,13,4.2 离散无记忆信道命题1 若DMC关于输入为对称的,4.2,离散无记忆信道,命题,2,若,DMC,关于输出为对称的，则当输入分布等概时，输出分布等概。,证明 此时,p,(,y,|,x,),，,x,=0,K,-1,与,p,(0|,x,),，,x,=0,K,-1,互为置换。设,q,(,x,)=1/,K,，,x,0, 1, ,K,-1,。则,2024/9/4,14,4.2 离散无记忆信道命题2 若DMC关于输出为对称的,4.2,离散无记忆信道,定义,4.2.6,(p108),若,DMC,的转移概率矩阵,P,的列的全体可分成若干个列子集，每个列子集所对应的,P,的子阵都满足以下两条性质：,（,1,）任一行是第一行的置换，,（,2,）任一列是第一列的置换。,则称信道为,准对称信道,。,（特别若列子集只有一个，即转移概率矩阵,P,本身的任一行是第一行的置换，任一列是第一列的置换，则称信道为,对称信道,。 ）,例,4.2.2,准对称信道的例子。,(,见,p108109),2024/9/4,15,4.2 离散无记忆信道定义4.2.6(p108) 若D,4.2,离散无记忆信道,几个简单的结论：,（,1,）准对称信道一定是关于输入为对称的。,（,2,）对称信道不仅是关于输入为对称的，也是关于输出为对称的。,（,3,）对称,DMC,当输入分布等概时，输出分布等概。,（,4,）准对称,DMC,当输入分布等概时，输出分布局部等概。（准对称,DMC,当输入分布等概时，若,j,和,l,属于转移概率矩阵的同一个列子集，则,w,j,=,w,l,。）,（,5,）对称信道未必有,J,=,K,。,2024/9/4,16,4.2 离散无记忆信道几个简单的结论：2023/9/10,4.2,离散无记忆信道,定理,4.2.3,(p109),对于准对称,DMC,信道，,（,1,）达到信道容量的最佳输入分布为等概分布；,（,2,）信道容量为,2024/9/4,17,4.2 离散无记忆信道定理4.2.3(p109) 对于,4.2,离散无记忆信道,证明 根据定理,4.2.2,的含义，只需要证明：当输入分布为等概时，对任意,k,0, 1, ,K,-1,，半平均互信息量,I,(,X,=,k,;,Y,),都取相同的值。（此时，该相同的半平均互信息量,I,(,X,=,k,;,Y,),就是准对称信道容量,C,。）,换句话说，只需要证明：当输入分布为等概时，对任意,k,0, 1, ,K,-1,，,I,(,X,=,k,;,Y,),与,k,无关。,设转移概率矩阵,P,的列的全体被分成,S,个互不相交的列子集：,0, 1, ,J,-1=,Y,1,Y,2,Y,S,；,Y,1,、,Y,2,、,、,Y,S,互不相交；,对任意,s,1, 2, ,S,，列子集,Y,s,所对应的子阵都满足：任一行是第一行的置换，任一列是第一列的置换。自然有以下三个结论。,2024/9/4,18,4.2 离散无记忆信道证明 根据定理4.2.2的含义，,4.2,离散无记忆信道,结论一：准对称信道是关于输入为对称的，所以对任意,k,0, 1, ,K,-1,，,结论二：对每个列子集,Y,s,，,结论三：对每个列子集,Y,s,，取定,y,s,Y,s,。则对任意,y,Y,s,，,2024/9/4,19,4.2 离散无记忆信道结论一：准对称信道是关于输入为对称,4.2,离散无记忆信道,于是,2024/9/4,20,4.2 离散无记忆信道于是2023/9/1020,4.2,离散无记忆信道,于是,2024/9/4,21,4.2 离散无记忆信道于是2023/9/1021,4.2,离散无记忆信道,例,4.2.3,特殊的对称,DMC,：,KSC,（,p109,）,其中,0,p,1,。,称,p,为错误概率。,特别当,K,=2,时，记为,BSC,2024/9/4,22,4.2 离散无记忆信道例4.2.3 特殊的对称DMC：,4.2,离散无记忆信道,此时有：,达到信道容量时的最佳输入分布为等概分布；,对应的输出分布也是等概分布；,信道容量是转移概率矩阵任何一行所对应的半平均互信息量，即,2024/9/4,23,4.2 离散无记忆信道此时有：2023/9/1023,4.2,离散无记忆信道,其中,0,p,1,，,0,q,1,。,当,q,=0,时，,2,元对称删除信道就成为,BSC,。,当,p,=0,时，,2,元对称删除信道就成为,2,元纯删除信道。,达到信道容量时的最佳输入分布为等概分布。,信道容量是转移概率矩阵任何一行所对应的半平均互信息量。（见,p111,）,例,4.2.4,特殊的准对称,DMC,：,2,元对称删除信道（,p110,）,输入事件集为,0,，,1,；输出事件集为,0,，？，,1,；转移概率矩阵为,2024/9/4,24,4.2 离散无记忆信道 其中0p1，0q0,。在这个假设下，,求出信道容量,C,；,然后求出最佳输入分布对应的“最佳输出分布”,w,(,y,),y,0, 1, ,K,-1,；,然后求出最佳输入分布,q,(,x,),x,0, 1, ,K,-1,。,2024/9/4,28,4.2 离散无记忆信道三、一般DMC的信道容量与最佳输入,4.2,离散无记忆信道,此时，,2024/9/4,29,4.2 离散无记忆信道此时，2023/9/1029,4.2,离散无记忆信道,2024/9/4,30,4.2 离散无记忆信道2023/9/1030,4.2,离散无记忆信道,这是,K,个未知量,0,1, ,K,-1,=,C,+log,w,(0),C,+log,w,(1), ,C,+log,w,(,K,-1),的线性方程组，系数矩阵是可逆方阵，因此唯一解出,0,1, ,K,-1,为,2024/9/4,31,4.2 离散无记忆信道这是K个未知量2023/9/103,4.2,离散无记忆信道,求出了,0,1, ,K,-1,=,C,+log,w,(0),C,+log,w,(1), ,C,+log,w,(,K,-1),，,还不能确定,C,和,w,(0),w,(1), ,w,(,K,-1),的值。但是我们还有另一个等式：,w,(0)+,w,(1)+,w,(,K,-1)=1,。,于是,2024/9/4,32,4.2 离散无记忆信道求出了0, 1, , K,4.2,离散无记忆信道,求出了信道容量,C,，立即得到了“最佳输出分布”,w,(,y,),y,0, 1, ,K,-1,和对应的最佳输入分布,q,(,x,),x,0, 1, ,K,-1,。,2024/9/4,33,4.2 离散无记忆信道求出了信道容量C，立即得到了“最佳,4.2,离散无记忆信道,例,设,DMC,的输入事件为,0, 1,，输出事件为,0, 1,，转移概率矩阵为,求信道容量和最佳输入分布。先假设最佳输入分布,q,(0),q,(1),满足,q,(0)0,，,q,(1)0,。因此,2024/9/4,34,4.2 离散无记忆信道例 设DMC的输入事件为0,4.2,离散无记忆信道,因此,2024/9/4,35,4.2 离散无记忆信道因此2023/9/1035,4.2,离散无记忆信道,例,特殊的,DMC,，称为,Z,信道：输入事件为,0, 1,，输出事件为,0, 1,，转移概率矩阵为,其中,00,，,q,(1)0,。因此,2024/9/4,36,4.2 离散无记忆信道例 特殊的DMC，称为Z信道：输,2024/9/4,37,2023/9/1037,4.2,离散无记忆信道,容易验证：,q,(1)0,；,q,(0)+,q,(1)=1,。,需要验证：,q,(0)0,。,2024/9/4,38,4.2 离散无记忆信道容易验证： q(1)0； q(0,4.5,信道的组合,总设有如下两个,DMC,，分别称为信道,1,和信道,2,。,信道,1,的输入事件为全体,x,，共有,K,个输入事件；,信道,1,的输出事件为全体,y,，共有,J,个输出事件；,信道,1,的转移概率矩阵为,p,1,(,y,|,x,),K,J,；,信道,1,的信道容量为,C,1,，最佳输入分布为,x,q,1,(,x,),。,信道,2,的输入事件为全体,u,，共有,N,个输入事件；,信道,2,的输出事件为全体,v,，共有,M,个输出事件；,信道,2,的转移概率矩阵为,p,2,(,v,|,u,),N,M,；,信道,2,的信道容量为,C,2,，最佳输入分布为,u,q,2,(,u,),。,2024/9/4,39,4.5 信道的组合总设有如下两个DMC，分别称为信道1和,4.5,信道的组合,定义,4.5.1,（,p121,）,信道的输入事件为全体,(,x,u,),，共有,KN,个输入事件；,信道的输出事件为全体,(,y,v,),，共有,JM,个输出事件；,转移概率矩阵为,p,(,y,v,)|(,x,u,),(,KN,)(,JM,),，,其中,p,(,y,v,)|(,x,u,)=,p,1,(,y,|,x,),p,2,(,v,|,u,),。,则称该信道为信道,1,与信道,2,的积信道。（又称该信道为信道,1,与信道,2,的独立并行信道）,（在物理上，积信道是两个信道的并行使用）,2024/9/4,40,4.5 信道的组合定义4.5.1（p121） 2023,4.5,信道的组合,定理,4.5.1,（,p122,） 积信道的,信道容量为,C,=,C,1,+,C,2,，,最佳输入分布为,(,x,u,),q,(,x,u,),，其中,q,(,x,u,)=,q,1,(,x,),q,2,(,u,),。,证明 此时,2024/9/4,41,4.5 信道的组合定理4.5.1（p122） 积信道的,4.5,信道的组合,2024/9/4,42,4.5 信道的组合2023/9/1042,4.5,信道的组合,2024/9/4,43,4.5 信道的组合2023/9/1043,4.5,信道的组合,所以,I,(,XU,)=(,xu,); (,YV,)=,I,(,X,=,x,;,Y,)+,I,(,U,=,u,;,V,),。注意到,对任何满足,q,1,(,x,) 0,的,x,，,I,(,X,=,x,;,Y,)=,C,1,；,对任何满足,q,1,(,x,) =0,的,x,，,I,(,X,=,x,;,Y,),C,1,；,对任何满足,q,2,(,u,) 0,的,u,，,I,(,U,=,u,;,V,)=,C,2,；,对任何满足,q,2,(,u,) =0,的,u,，,I,(,U,=,u,;,V,),C,2,。,于是,对任何满足,q,1,(,x,),q,2,(,u,)0,的,(,xu,),，,I,(,XU,)=(,xu,); (,YV,)=,C,1,+,C,2,；,对任何满足,q,1,(,x,),q,2,(,u,)=0,的,(,xu,),，,I,(,XU,)=(,xu,); (,YV,),C,1,+,C,2,。,根据定理,4.2.2(p84),，积信道的信道容量为,C,=,C,1,+,C,2,，最佳输入分布为,(,x,u,),q,1,(,x,),q,2,(,u,),。,2024/9/4,44,4.5 信道的组合所以I(XU)=(xu); (YV),4.5,信道的组合,定义,4.5.2,（,p123,）,信道的输入事件为全体,x,u,，其中,x,与,u,不相交；共有,K+N,个输入事件；,信道的输出事件为全体,y,v,，其中,y,与,v,不相交；共有,J+M,个输出事件；,信道的转移概率矩阵为,则称该信道为信道,1,与信道,2,的和信道。,2024/9/4,45,4.5 信道的组合定义4.5.2（p123） 2023,4.5,信道的组合,定理,4.5.2,（,p123,） （证略）,2024/9/4,46,4.5 信道的组合定理4.5.2（p123） （证略）,4.5,信道的组合,定义,4.5.3,（,p124,） 构造一个信道，使得,该信道的输入是信道,1,的输入；,信道,1,的输出再输入信道,2,；,信道,2,的输出就是该信道的输出。,则称该信道为信道,1,与信道,2,的级连信道（串联信道）。,请注意：此时,信道,1,的输出事件全体恰好是信道,2,的输入事件全体，即,y,=,u,，,J,=,N,。,2024/9/4,47,4.5 信道的组合定义4.5.3（p124） 构造一个,4.5,信道的组合,注：,（,1,）级连信道的转移概率矩阵为,p,(,v,|,x,),K,M,=,p,1,(,y,|,x,),K,J,p,2,(,v,|,y,),J,M,，,即,这一结果来自于全概率公式和马尔可夫性。,（,2,）级连信道的信道容量,C,满足,C,min,C,1,C,2,。这一结果也容易证明。,2024/9/4,48,4.5 信道的组合注：2023/9/1048,4.5,信道的组合,例,设信道,1,的转移概率矩阵为,其中,0,p,0,，则需要验证“,I,(,X,=0;,Y,)=,I,(,X,=1;,Y,),”。前者更容易验证。,问题三：为什么不猜想“最佳输入分布”中的两个概率等于,0,？,答 如果“最佳输入分布”中的两个概率等于,0,，则第三个概率等于,1,。此时输入随机变量,X,实际上是一个常数，其平均自信息量（熵）等于,0,。因此,0,I,(,X,;,Y,),H,(,X,)=0,，即“信道容量”为,C,=,I,(,X,;,Y,)=0,，矛盾。,2024/9/4,74,习题课问题一：凭什么猜想q(0)=q(2)？2023/9/1,(,b,),这是准对称信道。因此,最佳输入分布为,q,(0),q,(1),q,(2)= 1/3, 1/3,1/3,，,对应的最佳输出分布为,2024/9/4,75,(b)2023/9/1075,习题课,此时信道容量为,2024/9/4,76,习题课此时信道容量为2023/9/1076,习题课,4.8,一,PCM,语音通信系统，若信号带宽为,W,=4000Hz,，采样频率为,2W,，且采用,8,级幅度量化，各级出现的概率为,1/2,，,1/4,，,1/8,，,1/16,，,1/32,，,1/64,，,1/128,，,1/128,。试求所需的信息速率,(bits/s),。,（这是什么类型的习题？似乎与信道及信道容量没有关系）,4.8,的解答,每次采样获得的信息量，是随机变量的平均自信息量（熵），为,(1/2)log2+(1/4)log4+(1/8)log8+(1/16)log16,+(1/32)log32+(1/64)log64+(1/128)log128+(1/128)log128,= (1/2)+(2/4)+(3/8)+(4/16)+(5/32)+(6/64)+(7/128)+(7/128),=127/64(bits),。,信息速率为,127/64(bits)8000=15875(bits/s),。,2024/9/4,77,习题课4.8 一PCM语音通信系统，若信号带宽为W=400,习题课,4.12,若要以,R,=10,5,bit/s,的速率通过一个带宽为,8kHz,、信噪比为,31,的连续信道传送，可否实现,?,4.12,的解答,连续信道的带宽为,8kHz,，说明该连续信道可以通过采样频率不超过,16kHz,的采样，变成一个“时间离散的无记忆连续信道”。,进一步简化：我们把该“时间离散的无记忆连续信道”看作是一个“高斯可加噪声信道”,(p126),。,因此，在每次采样中传送的信息量为,(1/2)log(1+ 31)=(5/2)(bits),。,带宽为,8kHz,，说明每秒种的采样次数不能超过,16kHz,。,因此，每秒种传送的信息量不能超过,(5/2)(bits)16k=40k (bits/s),。,40k10,5,，因此不能实现,R,=10,5,bit/s,的信息速率。,2024/9/4,78,习题课4.12 若要以R=105 bit/s的速率通过一个,