信息论基础离散信道及其信道容量

1、信息论基础离散信道及其信道容量1第1页，共101页，2022年，5月20日，1点20分，星期一3离散信道及其信道容量3.1 信道的数字模型及分类3.2 平均互信息及平均条件互信息3.3 平均互信息的特性3.4 信道容量及其一般计算方法3.5信道容量的迭代算法3.6离散无记忆扩展信道及其信道容量3.7独立并联信道及其信道容量2第2页，共101页，2022年，5月20日，1点20分，星期一3离散信道及其信道容量3.8 串联信道的互信息和数据处理定理3.9信源与信道的匹配3第3页，共101页，2022年，5月20日，1点20分，星期一3.1 信道的数字模型及分类在信息论中，信道中指信息传输的通道。它

2、是信息论中与信源并列的另一个主要研究对象。典型例子：实际通信中物理通道：电缆、光纤、电波传布空间、载波线路等；在时间上将信息进行传输的信道：磁带、光盘等；为了某种目的而使信息不得不经过的通道：分类器、缓冲器等。4第4页，共101页，2022年，5月20日，1点20分，星期一信道分类根据信道的用户多少：两端(单用户)信道 多端(多用户)信道根据信道输入端和输出端的关联：无反馈信道 反馈信道根据信道的参数与时间的关系：固定参数信道 时变参数信道根据输入和输出信号的特点：(表2.2)5第5页，共101页，2022年，5月20日，1点20分，星期一表2.2幅度时间信道名称离散离散离散信道( Discr

3、ete channel )/ 数字信道(Digital channel)连续连续波形信道( Waveform channel )/ 模拟信道( Analog channel )连续离散连续信道( Continuous channel )离散连续（理论和实用价值均很小）6第6页，共101页，2022年，5月20日，1点20分，星期一信道按其输入输出之间关系的记忆性来划分：有记忆信道无记忆信道信道按其输入输出信号之间的关系是否是确定关系来划分：有噪声信道无噪声信道7第7页，共101页，2022年，5月20日，1点20分，星期一本章我们只讨论无反馈、固定参数的单用户无扰和有扰离散信道。8第8页，共1

4、01页，2022年，5月20日，1点20分，星期一信道模型信息论不研究信道传输特性的获得问题，而假定传输特性是已经知道的，并在此基础上研究信道的传输问题。输入输出统计关系输入量X(随机过程)输出量Y(随机过程)信道9第9页，共101页，2022年，5月20日，1点20分，星期一离散信道的数学模型输入输出统计关系输入量X(随机矢量)输出量Y(随机矢量)信道10第10页，共101页，2022年，5月20日，1点20分，星期一根据信道的统计特性即条件概率的不同，离散信道又可分成如下几种情况11第11页，共101页，2022年，5月20日，1点20分，星期一无干扰(无噪)信道：有噪信道： 不是0，1分

5、布，称为有噪信道12第12页，共101页，2022年，5月20日，1点20分，星期一 这种信道存在干扰，为实际中常见的信道类型，其输出符号与输入符号之间没有确定的对应关系，但信道任一时刻的输出符号仅统计依赖于对应时刻的输入符号，而与非对应时刻的输入符号及其它任何时刻的输出符号无关，是无记忆信道。离散有干扰无记忆信道：简称DMC13第13页，共101页，2022年，5月20日，1点20分，星期一 单符号离散信道的数学模型用图描述:可以用概率空间 描述，其中 称为信道的(前向)转移概率.14第14页，共101页，2022年，5月20日，1点20分，星期一信道的转移概率：信道的(前向)转移概率矩阵：

6、15第15页，共101页，2022年，5月20日，1点20分，星期一记 则信道传递矩阵为该矩阵又称信道矩阵，可作为单符号离散信道的另一种数学模型的形式。16第16页，共101页，2022年，5月20日，1点20分，星期一几个重要的单符号离散信道对称离散信道：信道矩阵中的行元素集合相同，列元素集合也相同的信道，称为对称信道。 17第17页，共101页，2022年，5月20日，1点20分，星期一例：二元对称信道Binary Symmetric Channel (BSC)001118第18页，共101页，2022年，5月20日，1点20分，星期一几个重要的单符号离散信道准对称信道：若信道转移矩阵按列

7、可以划分成几个互不相交的子集合，而每个子矩阵（由子集所对应的信道转移矩阵中的列所组成）具有下述性质：（1） 每一行都是第一行的一种排列（2） 每一列都是第一列的一种排列例：19第19页，共101页，2022年，5月20日，1点20分，星期一几个重要的单符号离散信道强对称信道（均匀信道）r=s=n20第20页，共101页，2022年，5月20日，1点20分，星期一几个重要的单符号离散信道二进制删除信道（Binary Erasure Channel,简称BEC）“删除”是指在信宿中，见“e”就删去，既不作“1”，也不作“0” 21第21页，共101页，2022年，5月20日，1点20分，星期一例：

8、二元删除信道Binary Erasure Channel (BEC)0011e22第22页，共101页，2022年，5月20日，1点20分，星期一单符号离散信道的一些概率关系对于信道 X, P, Y ，输入和输出符号的联合概率根据联合概率可得输出符号的概率 其矩阵形式：根据贝叶斯定律可得后验概率先验概率后验概率23第23页，共101页，2022年，5月20日，1点20分，星期一3.2平均互信息在阐明了离散单符号信道的数学模型，即给出了信道输入与输出的统计依赖关系后，我们将深入研究在此信道中信息传输的问题24第24页，共101页，2022年，5月20日，1点20分，星期一信道疑义度（损失熵） 信

9、道输入信源 X 的熵（先验熵）： 是在接收输出 Y 以前，关于输入变量 X 先验不确定性的度量，所以称为先验熵。25第25页，共101页，2022年，5月20日，1点20分，星期一接收到输出符号bj后关于X的后验熵：当没有收到输出Y 时，已知输入变量X 的概率分布为P(x)；而当接收到输出符号y=bj 后，输入符号的概率分布发生了变化，变成后验概率P(x|bj )。那么，接收到输出符号y=bj 后，关于X的平均不确定性为26第26页，共101页，2022年，5月20日，1点20分，星期一后验熵在输出Y 的取值范围内是个随机量，将后验熵对随机变量Y 求期望，得条件熵为（即信道疑义度）27第27页

10、，共101页，2022年，5月20日，1点20分，星期一信道疑义度的物理含义：信道疑义度表示在输出端收到输出变量Y全部符号后，对于输入端的变量X尚存在的平均不确定性（存在疑义）。这个对X尚存在的不确定性是由于干扰（噪声）引起的，它表示信源符号通过有噪信道传输后所引起的信息量的损失，故也称为损失熵。28第28页，共101页，2022年，5月20日，1点20分，星期一噪声熵 定义条件熵H（Y/X）为该信道的噪声熵。29第29页，共101页，2022年，5月20日，1点20分，星期一噪声熵H（Y/X）表示在已知输入变量X的条件下，对随机变量Y尚存在的不确定性。噪声熵完全是由于信道中噪声引起的，也称为

11、散布度，它反映了信道中噪声源的不确定性。30第30页，共101页，2022年，5月20日，1点20分，星期一平均互信息互信息：信道输出端接收到某消息y（或某消息序列y）后获得关于输入端某消息x（或某消息序列x）的信息量 31第31页，共101页，2022年，5月20日，1点20分，星期一平均互信息：互信息在其概率空间中的数学期望32第32页，共101页，2022年，5月20日，1点20分，星期一平均互信息与各类熵的关系及含义： I (X; Y )=H( X ) - H(X |Y ) = H( Y ) - H(Y |X ) = H( X ) + H( Y ) - H(XY )平均互信息的物理含义

12、：33第33页，共101页，2022年，5月20日，1点20分，星期一平均互信息的特性（1）对称性：（2）非负性：（3）极值性：34第34页，共101页，2022年，5月20日，1点20分，星期一（4）凸函数性平均互信息量 I (X; Y ) 是输入信源概率分布 P(x) 的上凸函数（研究信道容量的理论基础）。 平均互信息量 I (X; Y ) 是信道转移概率 P(y|x)的下凸函数（研究信源的信息率失真函数的理论基础）。35第35页，共101页，2022年，5月20日，1点20分，星期一例：BSC的输入概率空间36第36页，共101页，2022年，5月20日，1点20分，星期一3.3 平均条

13、件互信息设三个离散概率空间X、Y、Z； 满足37第37页，共101页，2022年，5月20日，1点20分，星期一38第38页，共101页，2022年，5月20日，1点20分，星期一定义：对于三个离散随机变量X、Y、Z，在已知Z的条件下，X和Y之间的平均条件互信息为：39第39页，共101页，2022年，5月20日，1点20分，星期一书例3.3：四个等概分布消息M1、M2、M3、M4被送入一个二元无记忆对称信道进行传送。通过编码使M1=00，M2=01，M3=10，M4=11。而BSC信道如图所示。试问，输入是M1和输出是符号0的互信息是多少？如果知道第二个符号也是0，这时带来多少附加信息量？4

14、0第40页，共101页，2022年，5月20日，1点20分，星期一3.4信道容量及其一般计算方法信息传输率(比特/符号)：信息传输速率(比特/秒)：41第41页，共101页，2022年，5月20日，1点20分，星期一信道容量：最大信息传输率42第42页，共101页，2022年，5月20日，1点20分，星期一一、无噪无损信道的信道容量无噪无损信道：输入输出一一对应，信道矩阵为单位阵疑义度H（X/Y）=0，噪声熵H（Y/X）=043第43页，共101页，2022年，5月20日，1点20分，星期一a1a2anb1b2bn信道容量：I（X；Y）= H（X）= H（Y） ，则 C = max H（X）=

15、 max H（Y）44第44页，共101页，2022年，5月20日，1点20分，星期一二、无噪有损信道（确定信道）： H（X/Y）0，H（Y/X）=0信道输出端接收到某个bj后不能判定是哪个输入符号ai a1a2a3a4a5b1b245第45页，共101页，2022年，5月20日，1点20分，星期一信道容量： I（X；Y）= H（Y） ，则 C = max H（Y）,这时的输入分布应该是使得信道输出分布为等概分布。46第46页，共101页，2022年，5月20日，1点20分，星期一三、有噪无损信道： H（X/Y）= 0，H（Y/X）0a1a2b1b2b3b4b50.30.60.10.50.54

16、7第47页，共101页，2022年，5月20日，1点20分，星期一信道容量： I（X；Y）= H（X），则 C = max H（X）。 这时的输入分布为等概分布。48第48页，共101页，2022年，5月20日，1点20分，星期一一般离散信道是既有噪又有损的。这种情况下信道容量的计算将十分复杂。我们先讨论一种特殊的有损有噪信道对称离散信道的信道容量。然后讨论一般离散信道的信道容量。结论：凡损失熵等于零的信道称为无损信道；凡噪声熵等于零的信道称为无噪信道。49第49页，共101页，2022年，5月20日，1点20分，星期一1、定义：如果转移概率矩阵P的每一行包含同样元素，则为输入对称矩阵；如果转

17、移概率矩阵P的每一列包含同样元素，则为输出对称矩阵；如果输入输出都对称，则为对称DMC信道。3.4.2 对称DMC信道例如：50第50页，共101页，2022年，5月20日，1点20分，星期一2、信道容量前提：输入符号和输出符号均等概。51第51页，共101页，2022年，5月20日，1点20分，星期一例题3.5：已知信道转移矩阵为计算信道容量。解：52第52页，共101页，2022年，5月20日，1点20分，星期一例题：已知信道转移矩阵为该信道输入符号和输出符号的个数相同，都为n，且正确的传输概率为1-，错误概率被均匀分给n-1个输出符号，此类信道称为强对称信道或均匀信道，计算信道容量。解：

18、53第53页，共101页，2022年，5月20日，1点20分，星期一3.4.3、准对称DMC信道例如：1、定义：如果转移概率矩阵P是输入对称而输出不对称，即转移概率矩阵的每一行包含同样元素，而各列的元素可以不同，则为准对称矩阵。54第54页，共101页，2022年，5月20日，1点20分，星期一准对称信道另一种定义：若信道转移矩阵按列可以划分成几个互不相交的子集合，而每个子矩阵（由子集所对应的信道转移矩阵中的列所组成）具有下述性质：（1） 每一行都是第一行的一种排列（2） 每一列都是第一列的一种排列55第55页，共101页，2022年，5月20日，1点20分，星期一方法二：将转移概率矩阵划分为

19、若干个互不相交的对称的子集。方法一：根据信道容量的定义式来计算。2、准对称DMC信道信道容量的求解方法：可以证明：计算准对称DMC信道的信道容量即为输入等概时的平均互信息量。56第56页，共101页，2022年，5月20日，1点20分，星期一根据下面的公式来计算。57第57页，共101页，2022年，5月20日，1点20分，星期一例题：已知信道转移矩阵为，计算信道容量。方法一： 该信道为准对称DMC信道，计算信道容量即为输入等概时的平均互信息量。P(x,y) y1 y2 y3x1x20.25 0.15 0.10.15 0.25 0.1 输入等概时，由信道转移矩阵可得联合概率：由信道转移矩阵可得

20、条件熵容易得到输出符号的概率分别为 0.4，0.4，0.2。所以 58第58页，共101页，2022年，5月20日，1点20分，星期一所以，59第59页，共101页，2022年，5月20日，1点20分，星期一例题：已知信道转移矩阵为，计算信道容量。方法二：将上面的信道矩阵分解为两个子集：根据下面的公式60第60页，共101页，2022年，5月20日，1点20分，星期一所以，信道容量为61第61页，共101页，2022年，5月20日，1点20分，星期一例3.7：设某信道的转移矩阵为：求其信到容量。解：分析该转移矩阵，可知这是一个准对称信道。 62第62页，共101页，2022年，5月20日，1点

21、20分，星期一一般离散信道的信道容量分析根据信道容量定义就是在固定信道的条件下，对所有可能的输入概率分布P（x）求平均信息的极大值。63第63页，共101页，2022年，5月20日，1点20分，星期一定理：一般离散信道的平均互信息 达到极大值（即等于信道容量）的充要条件是输入概率分布 满足： 这时C就是所求的信道容量。信道容量的定理64第64页，共101页，2022年，5月20日，1点20分，星期一对于一般离散信道，我们很难利用上面定理来求信道容量和对应的输入概率分布。介绍一种求方程组的方法： 65第65页，共101页，2022年，5月20日，1点20分，星期一前提：设r=s，信道传递矩阵P是

22、非奇异矩阵，则信道容量的求解方法如下：由方程组：求出由求出C由求出由求出最佳输入概率分布 信道容量的方程组解法：66第66页，共101页，2022年，5月20日，1点20分，星期一例：设某离散无记忆信道的输入X的符号集为0,1,2,输出Y的符号集为0,1,2，如图所示， 其信道转移矩阵为求其信道容量及其最佳的输入概率分布。并求当 时的信道容量C。 67第67页，共101页，2022年，5月20日，1点20分，星期一3.6离散无记忆扩展信道及其信道容量前几节讨论了最简单的离散信道，即信道的输入和输出都只是单个随机变量的信道。然而一般离散信道的输入和输出却是一系列时间(或空间)离散的随机变量，即为

23、随机序列。本节讨论多符号离散信道的数学模型。68第68页，共101页，2022年，5月20日，1点20分，星期一多符号离散信道的定义：若多符号离散信源在N个不同的时刻分别通过单符号离散信道 ，则在输出端输出随机矢量 。于是形成一个新的信道，称为多符号离散信道。同时，我们也可以把这种信道称之为单符号离散信道的N次扩展信道。多符号离散信道（单符号离散信道的N次扩展信道）的数学模型仍用概率空间来描述。其数学模型如图所示。69第69页，共101页，2022年，5月20日，1点20分，星期一多符号离散信道的数学模型 70第70页，共101页，2022年，5月20日，1点20分，星期一71第71页，共10

24、1页，2022年，5月20日，1点20分，星期一与单符号离散信道相比，N次扩展信道的输入符号数由r种扩展为 种；输出符号数由s种扩展为 72第72页，共101页，2022年，5月20日，1点20分，星期一构成N次扩展信道的传递矩阵它表示在输入消息 的条件下，输出消息 的传递概率73第73页，共101页，2022年，5月20日，1点20分，星期一且满足74第74页，共101页，2022年，5月20日，1点20分，星期一若N次扩展信道的传递概率等于N个时刻单符号离散信道的传递概率的连乘即 则单符号离散信道称为离散无记忆信道，相应的N次扩展信道称为离散无记忆信道的N次扩展信道。75第75页，共101

25、页，2022年，5月20日，1点20分，星期一离散无记忆N次扩展信道的信道容量76第76页，共101页，2022年，5月20日，1点20分，星期一例题注意单位！容易看出，上述信道均为对称信道，容易计算求得。二次扩展信道：单符号信道：假设，可以求得：已知单符号信道的转移矩阵为则该BSC信道的二次扩展无记忆信道的转移矩阵为计算它们的信道容量，并比较结果。解：77第77页，共101页，2022年，5月20日，1点20分，星期一结论：二次扩展无记忆信道的信道容量正好是单符号信道的信道容量的2倍。78第78页，共101页，2022年，5月20日，1点20分，星期一离散无记忆扩展信道的信道容量 对于多符号

26、离散信道来说，就会产生这样一个问题：从总体上看，离散无记忆信道的N次扩展信道把输入随机矢量传输为输出随机矢量的传输过程种，传递的平均互信息量 ， 与其中各随机变量的平均互信息之和 之间有什么关系？这是本节要讨论的问题。79第79页，共101页，2022年，5月20日，1点20分，星期一在一般离散信道中，关于传输长为N的随机序列所获得的平均信息量，有下述两个定理。80第80页，共101页，2022年，5月20日，1点20分，星期一定理3.5 若信道的输入随机序列为X，通过信道传输，接收到的随机序列为Y。假若信道是无记忆的，即信道转移概率满足或写成 则存在 式中 和 是随机序列X和Y中对应的第i位

27、随机变量。 81第81页，共101页，2022年，5月20日，1点20分，星期一 证明： 另一方面 82第82页，共101页，2022年，5月20日，1点20分，星期一所以所以所以所以则83第83页，共101页，2022年，5月20日，1点20分，星期一根据詹森不等式，得 证得84第84页，共101页，2022年，5月20日，1点20分，星期一定理3.6 若信道的输入随机序列为X，通过信道传输，接收到的随机序列为Y，而信道的传递概率为 ，假若信源是无记忆的，则存在上述两个定理说明了离散信道中随机矢量的平均互信息与其中各随机变量的平均互信息之和之间的关系。85第85页，共101页，2022年，5

28、月20日，1点20分，星期一从定理3.5和定理3.6的证明可知，若信源与信道都是无记忆的，则式（3.141）和（3.142）同时满足，即它们的等式成立：对于离散无记忆信道的N次扩展信道来说，若信源也是无记忆的话，则有此式说明当信源是无记忆时，无记忆的N次扩展信道的平均互信息等于原来信道的平均互信息的N倍。 86第86页，共101页，2022年，5月20日，1点20分，星期一离散无记忆的N次扩展信道的信道容量等于原单符号离散信道的信道容量的N倍 。且只有当输入信源是无记忆的及每一输入变量的分布各自达到最佳分布时，才能达到这个信道容量NC。一般情况下，信息序列在离散无记忆的N次扩展信道中传输的信息

29、量为87第87页，共101页，2022年，5月20日，1点20分，星期一3.7 独立并联信道及其信道容量 N个独立并联信道88第88页，共101页，2022年，5月20日，1点20分，星期一这N个信道的联合概率传递概率满足故定理3.5推广得：即联合平均互信息不大于各自信道的平均互信息之和。因此得独立并联信道的信道容量89第89页，共101页，2022年，5月20日，1点20分，星期一结论：独立并联信道的信道容量不大于各个信道的信道容量之和。只有当输入符号相互独立，且输入符号的概率分布达到各信道容量的最佳输入分布时，独立并联信道的信道容量才等于各信道容量之和，即90第90页，共101页，2022年，5月20日，1点20分，星期一3.8串联信道及其信道容量若信道II的