教学课件：第6章-离散信道及其容量.ppt

1/78,离散信道及其容量,第 6 章,北京邮电大学 信息与通信工程学院 许文俊,2/78,信道是信号的传输媒介，是传送信息的物理通道。(举例)研究信道的目的主要是为了解决信息如何有效、可靠地传输的问题。本章重点解决某些特殊信道容量的计算问题。,第6章 离散信道及其容量,3/78,概述,单符号离散信道及其容量,级联信道及其容量,信道容量的迭代计算,本章主要内容,多维矢量信道及其容量,4/78,6.1 概述,信道的分类,离散信道的数学模型,信道容量的定义,5/78,6.1.1 信道的分类,数字通信系统的基本模型,依据不同的条件，不同模块之间的通道可以划分为不同的信道,6/78,6.1.1 信道的分类,按输入、输出集合的取值分类,按输入、输出集合的个数分类,按信道转移概率的性质分类,根据信道统计特性划分,根据信道噪声性质划分,7/78,6.1.1 信道的分类,1)离散信道：输入和输出均为离散集，如B-B,2)连续信道：输入和输出均为连续集，也称波形信道，其特点是时间与取值都连续，如C-C,3)半连续（或半离散）信道：输入和输出一个为连续、一个为离散，如B-C或C-B,4)时间离散连续信道：连续取值但时间离散，例如信道的输入和输出为模拟信号抽样的情况。,按输入、输出集合的取值分类,8/78,6.1.1 信道的分类,1)单用户信道：X,Y中各有一个事件集，称单路或单端信道,2)多用户信道：X,Y中至少有一端是多个事件集，也称多端信道。多用户信道包含两种特殊的信道，即多元接入信道和广播信道。多元接入信道就是多个输入、单个输出的信道广播信道就是单个输入、多个输出的信道,按输入、输出集合的个数分类,9/78,无损信道（每个输入对应多个输出）确定信道（多个输入对应单个输出）无扰信道（一个输入对应一个输出）,按信道转移概率的性质分类,6.1.1 信道的分类,1）无噪声信道,2）有噪声信道,无记忆信道 给定时间输出仅依赖于当前输入有记忆信道 输出值不仅依赖于当前输入又依赖于以前的输入,10/78,根据信道统计特性划分,1）恒参信道,6.1.1 信道的分类,2）变参信道,统计特性不随时间变化（也称平稳信道）例如：卫星通信信道,统计特性随时间变化。例如：短波，移动通信信道,11/78,根据信道噪声性质划分,1）高斯噪声信道,6.1.1 信道的分类,2）非高斯噪声信道,信道噪声为高斯分布（白噪声或有色噪声）,信道噪声分布不是高斯分布,12/78,6.1.2 离散信道的数学模型,13/78,离散无记忆信道,一般的信道数学模型,离散无记忆信道,平稳（或恒参）信道,单符号离散信道,14/78,一般信道的数学模型,信道模型,15/78,离散无记忆信道,则称为此信道为离散无记忆信道（DMC），其数学模型为：（Discrete Memoryless Channel),利用给定时刻的输出符号仅依赖于当前输入符号的条件可以推出。,若信道的转移概率满足,16/78,平稳(或恒参)信道,如果对于任意正整数m、n，和 离散无记忆信道的转移概率满足：,17/78,其中，信道的输入X与输出Y都是一维随机变量集合，xX，取自字母表,。yY，取自字母表,单符号离散信道,对于离散平稳无记忆信道，可以用一维条件概率描述,信道转移概率简记为：,18/78,单符号离散信道,信道转移概率矩阵,19/78,单符号离散信道,二元对称信道(BSC)，输入与输出符号集分别为，信道转移概率p(y/x)满足，称为错误率。写出信道的转移概率矩阵并画出转移概率图。,例,解：,转移概率矩阵,转移概率图,Binary Symmetric Channel,20/78,单符号离散信道,二元删除信道：其中A=0,1,B=0,2,1画出转移概率图和转移概率矩阵。,例,解：,转移概率矩阵,转移概率图,21/78,单符号离散信道,例,解：,四个等概消息，编成的码字为，当通过下图所示二进制对称无记忆信道传输时，求:,1)“接收到第一个数字为0”与“发M1”的互信息2)当“接收到第二个数字也为0”时，关于M1的附加信息3)当“接收到第三个数字也为0”时，又增加多少关于M1的信息？,1),22/78,2),3),单符号离散信道,23/78,6.1.3 信道容量的定义,平稳离散无记忆信道的容量C定义为输入与输出平均互信息I(X;Y)的最大值：,1）单位为:比特/信道符号（奈特/信道符号),2）当信道给定后,p(y|x)就固定3）C 仅与p(y|x)有关，而与p(x)无关,4）C是信道传输最大信息速率能力的度量,24/78,多维矢量信道,若 和 分别为信道的N维输入与输出随机矢量集合，则信道容量定义为：,其中，为信道输入矢量的联合概率,25/78,6.2 单符号离散信道及其容量,离散无噪信道的容量,一般离散信道的容量,离散对称信道的容量,26/78,6.2.1 离散无噪信道的容量,无损信道：,输出符号只对应一个输入符号。,其中r为输入符号集的大小,27/78,6.2.1 离散无噪信道的容量,确定信道：,每个输入符号都对应一个输出符号,其中s为输出符号集的大小,28/78,无损确定信道：,输入符号与输出符号是一一对应关系,其中r、s为输入与输出字母表的大小，且r=s,6.2.1 离散无噪信道的容量,结论：离散无噪信道的容量为,29/78,6.2.2 离散对称道的容量,例,分析下图信道的对称性,30/78,6.2.2 离散对称道的容量,解：,(a)可分成两个子矩阵,所以为 对称信道,(b)的概率转移矩阵为,所以不是对称信道,31/78,6.2.2 离散对称道的容量,定理6.2.1 对于离散对称信道，当输入等概率时达到信道容量：,H(Y)为输入等概率时输出的熵 H(p1,p2,ps)为信道转移概率矩阵某行元素注释:对强对称信道,输入等概率时达到容量，此时输出等概率。,32/78,6.2.2 离散对称道的容量,例,解：,一信道的转移概率矩阵如图，求信道容量和达到容量时的输出概率。,设输出概率为。由于信道为强对称信道，故当输入等概率时达到容量C，此时输出也等概率,33/78,6.2.2 离散对称道的容量,例,解：,一信道的转移概率矩阵如图，求信道容量和达到容量时的输入概率。,设输入输出概率为 由于信道为强对称信道，故当 时,达到容量。,特别是，当r=2时，信道容量为C=1-H(p)比特/符号。,34/78,6.2.2 离散对称道的容量,例,解：,一信道的转移概率矩阵如图，求信道容量和达到容量时的输出概率。,设输出概率为 准对称信道，当输入等概率时达到信道容量。可计算输出概率为,35/78,6.2.3 一般离散信道的容量,36/78,6.2.3 一般离散信道的容量,37/78,6.2.3 一般离散信道的容量,38/78,验证C的正确性,6.2.3 一般离散信道的容量,39/78,6.2.3 一般离散信道的容量,40/78,例,一信道的转移概率如图所示，求信道容量和达到容量时的输出概率。,6.2.3 一般离散信道的容量,41/78,解：,6.2.3 一般离散信道的容量,42/78,例,解：,利用 求例6.1.1中二元对称信道容量。,6.2.3 一般离散信道的容量,43/78,信道容量为,对应的输入概率为,6.2.3 一般离散信道的容量,44/78,定理6.2.2 对于离散无记忆信道，当且仅当,6.2.3 一般离散信道的容量,45/78,例,解：,信道的转移概率如下图所示，求信道容量和达到容量时的输入出概率。,设输入、输出概率为p0,p1,p2.q0,q1,1）达到容量时，若输入概率全不为零,解得，C=1比特，但将结果代入第2式，使该式左边的值为0，出现矛盾。,6.2.3 一般离散信道的容量,46/78,2）设p2=0，p0,p1,不为零,将结果代入第2式，该式左边的值为0C。所以，信道容量C=1比特/符号，达到容量时的输入概率为概率为,6.2.3 一般离散信道的容量,47/78,6.3 级联信道及其容量,若随机变量集合(X,Y,Z)构成马氏链，则称信道X-Y与Y-Z构成级联信道。由于当Y给定时，Z不依赖于X，即P(z|y)=P(z|xy),48/78,证,定理6.3.1 若X,Y,Z构成一马氏链，则：,6.3 级联信道及其容量,同理可证,49/78,通信系统模型各部分的级联,信道传输后，译码器收到N长序列为，译码后传给信宿的消息序列为。,6.3 级联信道及其容量,50/78,证,定理(数据处理定理),6.3 级联信道及其容量,51/78,级联信道为马氏链,级联信道的转移概率矩阵,一级级联相当于状态的一步转移,6.3 级联信道及其容量,级联信道的容量 根据级联信道的转移矩阵特点，按照前面介绍的离散信道容量的计算方法即可计算其信道容量。,52/78,给定二元对称信道其状态转移矩阵如下，计算两级级联信道的概率转移矩阵。如果信道输入 0、1 等概率，求在两级级联和三级级联情况下输入与输出的平均互信息。,例,解：,1)两级级联信道的概率转移矩阵,6.3 级联信道及其容量,53/78,2)设原信道输入与输出集分别为X、Y，两级级联和三级级联情况下输出集合分别为Z、U,其中,类似地,可计算三级信，级联的情况：,结论：信道串联后增加信息损失，串联级数越多，损失越大。,6.3 级联信道及其容量,54/78,设错误概率为1/3，计算两级级联信道的容量及达到容量时的输出概率。,6.3.1(续),例,解：,两级级联信道的转移矩阵为,6.3 级联信道及其容量,该级联信道是一个强对称信道，因此当输入等概时达到信道容量，此时输出也等概。所以,比特/符号,55/78,多维矢量信道输入与输出的性质,并联信道及其容量,离散无记忆扩展信道及其容量,6.4 多维矢量信道及其容量,和信道及其容量,56/78,6.4.1 多维矢量信道输入与输出的性质,对于多维矢量信道，输入与输出平均互信息为:,57/78,引理6.4.1,设信道的输入输出分别为，其中，则：,1）,2）,6.4.1 多维矢量信道输入与输出的性质,58/78,定理6.4.1 对于离散无记忆信道，有：,证,仅当输出独立时等式成立。,6.4.1 多维矢量信道输入与输出的性质,59/78,当输入独立时,即当信源信道都无记忆时，等式成立。,6.4.1 多维矢量信道输入与输出的性质,60/78,证,定理6.4.2 对于无记忆信源，有：,等式成立条件：,6.4.1 多维矢量信道输入与输出的性质,61/78,当信道无记忆时,即当信源信道都无记忆时，等式成立。,6.4.1 多维矢量信道输入与输出的性质,62/78,结论：,1）对于无记忆信源和无记忆信道，有：,2）对于平稳信源，因为Xi、Yi同分布,因此：,对于平稳离散无记忆信道(DMC)的N次扩展信道，当信源无记忆时,有,6.4.1 多维矢量信道输入与输出的性质,63/78,设无记忆信源X的熵为H，X的5次扩展源为X5，信道为下面矩阵所示的置换信道，其中第1行为输入的序号，第2行为信道输出的序号，例如X1输出到Y4(P120)，X2输出到Y2等。计算,例,解：,6.4.1 多维矢量信道输入与输出的性质,64/78,例,解：,设离散无记忆信道的输入，输出，且有计算,6.4.1 多维矢量信道输入与输出的性质,65/78,N次扩展信道,单符号离散信道,N长的随机序列,N长的随机序列,新信道,原序列的N次扩展信道,6.4.2 离散无记忆扩展信道及其容量,66/78,N次扩展信道的描述要满足一般的信道数学模型的描述，但符号集为同分布符号的扩展，即各Xi的分布都相同,信道可通过下式来计算,信道的输入和输出集合分别为 和，所包含的矢量分别为,6.4.2 离散无记忆扩展信道及其容量,67/78,一个信道的N次扩展信道是N个原信道的Kroneck乘积,例,设输入与输出符号集的尺寸分别为r、s，则N次扩展信道的输入与输出符号集的尺寸分别为,则，信道的转移概率为：,6.4.2 离散无记忆扩展信道及其容量,68/78,求错误概率为p的二元对称信道的二次扩展信道的转移概率矩阵。,例,解：,2次扩展信道的转移概率矩阵：,6.4.2 离散无记忆扩展信道及其容量,69/78,6.4.2 离散无记忆扩展信道及其容量,当信源为无记忆时，等式成立,离散无记忆N次扩展信道的容量,当信道平稳时：,70/78,求该二次扩展信道的容量。,6.4.3(续),例,解：,由例可得，错误概率为p的二元对称信道的容量，根据式(6.4.6),该信道的二次扩展信道容量为,6.4.2 离散无记忆扩展信道及其容量,71/78,6.4.3 并联信道及其容量,并联信道的定义,由若干并行的单符号子信道组成 在每单位时间，发送端都同时通过每个子信道发送不同符号集的消息 每子信道的输出仅与该子信道的输入有关,各子信道输入相互独立时达到信道容量,72/78,求下图信道的容量和达到容量时的输入概率分布。,例,解：,从信道的转移概率图可以看出，两个子信道是独立的，所以构成一个二维并联信道。所求信道容量为,6.4.3 并联信道及其容量,比特/符号,达到容量时，输入 相互独立，且均为等概率分布。,73/78,6.4.4 和信道及其容量,和信道的定义,一个信道分为若干子信道，且各子信道输入之间互不相交，输出之间也互不相交信道总的输出与输入集合分别为各子信道输出与输入之并集每次传输只能用一个子信道,74/78,定理6.4.3,对于和信道，信道容量为 比特/符号，其中 Ci 为每个子信道的容量，第i个子信道使用概率为，达到容量的输入概率为各子信道达到容量时的概率再乘以。,6.4.4 和信道及其容量,75/78,例,一信道的转移概率如图所示，求信道容量和达到容量时的输入概率。,解：,其中p为不大于1的正数,6.4.4 和信道及其容量,76/78,信道达到容量时的输入概率分布不一定唯一。（对于对称信道是唯一的),关于信道容量的注释,对应于信道容量的输出概率是唯一的。,达到容量时的输出概率严格为正。,对于任意的离散信道的转移概率分布，要利用迭代算法进行计算。,77/78,本 章 小 结,1平稳离散无记忆信道模型：,2平稳离散无记忆信道的容量：,3特殊离散无记忆信道的容量的计算,对称信道：输入等概率时达到容量，且,一般离散信道,P有逆阵时,78/78,本 章 小 结,利用定理列方程组求解,和信道,并联信道,离散平稳无记忆N次扩展信道,当信源无记忆时信道达到容量,级联信道：转移概率矩阵为各级联信道矩阵的乘积，再计算容量。,达到容量的输入概率为各子信道达到容量时的概率再乘以,