离散信道及其信道容量.ppt

1 第三章 离散信道及其信道容量 第一节 信道的数学模型及分类 第二节 平均互信息 第三节 平均互信息的特性 第四节 信道容量及其一般计算方法 第五节 离散无记忆扩展信道及其信道容量 第七节 信源与信道的匹配 信道的功能：以 信号形式传输和 存储信息。 信道传输信息的 速率：与物理信 道本身的特性、 载荷信息的信号 形式和信源输出 信号的统计特性 有关。 信道容量研究内 容：在什么条件 下，通过信道的 信息量最大。 第六节 级联信道 2 o信号在信道中传输会引入噪声或干扰，它 使信号通过信道后产生错误和失真； o信道的输入和输出之间一般不是确定的函 数关系，而是统计依赖关系； o知道了信道的输入信号、输出信号以及它 们之间的依赖关系，信道的全部特性就确 定了。一般来说，输入和输出信号都是广义的时 间连续的随机信号，可用随机过程来描述。 第一节 信道的数学模型及分类 3 规定一个离散信道应有三个参数： 输入符号集： X = x1，x2， 输出符号集： Y = y1，y2， 信道转移概率：P(Y/X)=p(y1/x1),p(y2/x1),p( /x1),p(y1/ )p( / ) 1、离散信道的基本数学模型 设离散信道的输入为一个随机变量X，相应的输出的随机变量为Y ，如图所示： 第一节 信道的数学模型及分类 4 第一节 信道的数学模型及分类 2、信道的分类： 根据信道用户的多少： 根据输入端和输出端的关联： 单用户信道：只有一个输入端和一个输出端。 多用户信道：至少有一端有两个以上的用户，双向通信。 无反馈信道：输出端信号对输入端信号无影响、无作用。 有反馈信道：输出端信号会影响输入端信号变化。 根据输入输出随机变量个数的多少： 单符号信道：输入和输出端都只用一个随机变量表示。 多符号信道：输入和输出端用随机变量序列/随机矢量表示。 5 根据信道参数与时间的关系： 固定参数信道：信道的统计特性不随时间变化而变化。 时变参数信道：信道的统计特性随时间变化而变化。 根据信道输入和输出的关系： 离散信道：输入、输出随机变量都取离散值。 连续信道：输入、输出随机变量都取连续值。 半离散半连续信道：输入变量取离散值而输出变量取连续值 ，或反之。 波形信道 第一节 信道的数学模型及分类 6 第一节 信道的数学模型及分类 根据信道上有无干扰关系： 根据信道上有无记忆关系： 无记忆信道：输出仅与当前输入有关，而与过去输入无关的信道。 有记忆信道：信道输出不仅与当前输入有关，还与过去输入和（或 ）过去输出有关。 有干扰信道：存在干扰或噪声或两者都有的信道。实际信道一 般都是有干扰信道。 无干扰信道：不存在干扰或噪声，或干扰和噪声可忽略不计的 信道。计算机和外存设备之间的信道可看作是无干扰信道。 以下我们只研究无反馈、固定参数的单用户离散信道。 7 （1）无干扰信道：输入信号与输出信号有一一对应关系 （2）有干扰无记忆信道：输入与输出无一一对应关 系，输出只与当前输入有关； 根据这一模型，可对信道分类如下： （3）有干扰有记忆信道：这是最一般的信道。 第一节 信道的数学模型及分类 8 第一节 信道的数学模型及分类 3、单符号离散信道的数学模型 o设输入Xx1,x2,xi,xn o输出 Yy1,y2,yj,ym o信道转移概率/信道传递概率：条件概率p(yj /xi)。 o其信道模型如图所示。 9 P= y1y2 ym x1 p(y1/x 1) p(y2/x 1) p(ym/x1 ) x2 p(y1/x 2) p(y2/x 2) p(ym/x2 ) xn p(y1/x n) p(y2/x n) p(ym/xn ) 条件概率p(yj/xi)表示成矩阵形式： 第一节 信道的数学模型及分类 10 单符号离散信道的输入变量为X，取值于 输出变量为Y，取值于 。 并有条件概率 条件概率被称为信道的传递概率或转移概率。 第一节 信道的数学模型及分类 11 例1 二元对称信道（BSC） X=0,1; Y=0,1; p(0/0)=p(1/1)=1-p; p(0/1)=p(1/0)=p; 第一节 信道的数学模型及分类 12 例2 二元删除信道(BEC) X=0,1； Y=0,2,1。 0 p 0 1-q 1-p 1 q 1 2 第一节 信道的数学模型及分类 13 由此可见，一般单符号离散信道的传递概率可 以用矩阵表示: 第一节 信道的数学模型及分类 14 （1）联合概率: （2）输出符号的概率: （3）后验概率: 其中称为前向概率，描述信道的噪声特性 称为后向概率； 有时也把 称为先验 概率，把 称为后验概率。 表明输出端收到任一符号，必定是输入端某一符号输入所致。 第一节 信道的数学模型及分类 15 第二节 平均互信息 互信息: oyj对xi的互信息量定义为后验概率与先验概率比值的对 数。 o信源发出某符号xi，由于受噪声的随机干扰，在信道的 输出端输出xi某种变型yj，这个过程中信道所传送的信 息量，即信宿收到yj后，从yj中获取关于xi的信息量I(xi; yj )。 16 互信息的性质 对称性：I(xi;yj)=I(yj; xi) l两个随机事件的可能结果，xi和yj之间的统计约束程度； l从yj得到的关于xi的信息量I(xi;yj)与从xi得到的关于yj的信息量I(yj; xi) 是一样的，只是观察的角度不同而已。 当统计独立时，表明xi和yj之间不存在统计约束关系，从yj得 不到关于的xi任何信息，反之亦然。 互信息量可为正值或负值 当后验概率大于先验概率时，互信息量为正。 当后验概率小于先验概率时，互信息量为负。 当后验概率与先验概率相等时，互信息量为零。这就是两个随机事 件相互独立的情况。 平均互信息量 o如果将信道的发送和接收端分别看成是两个“信 源”，则两者之间的统计依赖关系，即信道输入 和输出之间的统计依赖关系描述了信道的特性。 o互信息量I(xi;yj)是定量研究信息流通问题的重 要基础。它是一个随机变量，不能从整体上作为 信道中信息流通的测度。 o以下介绍 n平均互信息量的定义 n平均互信息量的物理含义 n平均互信息量的性质 平均互信息量的定义 o平均互信息量定义：互信息量I(xi;yj)在联合概率空间 P(XY)中的统计平均值。 o称I(X;Y)是Y对X的平均互信息量（简称平均互信息/平 均交互信息量/交互熵）。 oX对Y的平均互信息定义为 平均互信息量的物理含义 o观察者站在输出端 o观察者站在输入端 o观察者站在通信系统总体立场上 20 自信息量：对yj一无所知的情况下xi存在的不确定度； l条件自信息量：已知yj 的条件下xi 仍然存在的不确定度； l互信息量：两个不确定度之差是不确定度被消除的部分， 即等于自信息量减去条件自信息量。 1.观察者站在输出端 oH(X/Y) 信道疑义度/损失熵。 Y关于X的后验不 确定度。表示收到变量Y后，对随机变量X仍然存在 的不确定度。代表了在信道中损失的信息。 oH(X) X的先验不确定度/无条件熵。 oI(X;Y)收到Y前、后关于X的不确定度减少的量。 从Y获得的关于X的平均信息量。 2.观察者站在输入端 观察者得知输入端发出xi前、后对输出端出现yj的不确定 度的差。 oH(Y/X)噪声熵。表示发出随机变量X后，对随机变量 Y仍然存在的平均不确定度。如果信道中不存在任何噪 声，发送端和接收端必存在确定的对应关系，发出X后 必能确定对应的Y，而现在不能完全确定对应的Y，这 显然是由信道噪声所引起的。 oI(Y;X) 发出X前、后关于Y的先验不确定度减少的量 。 24 l通信前：输入随机变量X和输出随机变量Y之间没有任何关 联关系，即X，Y统计独立：p(xi yj)=p(xi)p(yj) 先验不确定度 l通信后：输入随机变量X和输出随机变量Y之间由信道的统 计特性相联系，其联合概率密度： p(xi yj)=p(xi)p(yj /xi )= p(yj)p(xi / yj) 后验不确定度 l通信后的互信息量，等于前后不确定度的差 l这三种表达式实际上是等效的，在实际应用中可根据具体 情况选用一种较为方便的表达式。 3.观察者站在通信系统总体立场上 H(XY)联合熵。表示输入随机变量X，经信道传输到达信宿 ，输出随机变量Y。即收、发双方通信后，整个系统仍然存在 的不确定度。 I(X;Y) 通信前、后整个系统不确定度减少量。在通信前把X 和Y看成两个相互独立的随机变量，整个系统的先验不确定度 为X和Y的联合熵H(X)+H(Y)；通信后把信道两端出现X和Y看 成是由信道的传递统计特性联系起来的、具有一定统计关联关 系的两个随机变量，这时整个系统的后验不确定度由H(XY)描 述。 结论 o以上三种不同的角度说明：从一个事件获得另一 个事件的平均互信息需要消除不确定度，一旦消 除了不确定度，就获得了信息。 小结 28 平均互信息是信道传递信息的度量，从总体上反 映信道每传递一个符号，所传递的平均信息量。 I(X;Y)=H(X)-H(X/Y) =H(X)+H(Y)-H(XY) =H(Y)-H(Y/X) (3.34) 也可以得到：H(XY)=H(X)+H(Y/X)=H(Y)+H(X/Y) 29 信道疑义度 这是收到 后关于X的后验熵，表示收到 后关于输 入符号的信息测度。 这是关于X的先验熵，表示收到输出前关于X的不确定性度量。 第二节 平均互信息 30 这个条件熵称为信道疑义度，表示输出端在收到一个符 号后，对输入符号尚存的不确定性，这是由信道干扰造成的 如果没有干扰，H(X/Y)=0。 一般情况下H(X/Y)小于H(X)，说明经过信道传输，总能 消除一些信源的不确定性，从而获得一些信息。 第二节 平均互信息 将后验熵对随机 变量Y求数学期望 31 平均互信息 与各类熵之 间的关系： H(XY) H(X/Y) H(Y/X) H(X) H(Y) 第二节 平均互信息 H(X/Y)即信道疑义度，也表示通过有噪信道造成的损失，故也 称为损失熵，因此信源的熵等于收到的信息量加上损失的熵； 而H(Y/X)表示已知输入的情况下，对输出端还残留的不确定性 ，这个不确定性是由噪声引起的，故也称之为噪声熵。 I(X;Y) 32 （1）无噪一一对应信道： 此时可以计算得：H(X/Y)=H(Y/X)=0 在上图中表示就是两圆重合 （2）输入输出完全统计独立： 此时I(X;Y)=0 H(X/Y)=H(X) H(Y/X)=H(Y) 下面讨论两种极端情况： 第二节 平均互信息 33 第三节 平均互信息的特性 1、平均互信息的非负性：I(X;Y)=0 一般来说，信道疑义度总是大于0，所以互信息总是小于信 源的熵，只有当信道是无损信道时，信道疑义度等于0，互 信息等于信源的熵。 该性质表明，通过一个信道总能传递一些信息，最差的条 件下，输入输出完全独立，不传递任何信息，互信息等于 0，但决不会失去已知的信息。 2、平均互信息的极值性： I(X;Y)H(Y)。 45 第四节 信道容量及其一般计算方法 1、离散无噪信道的信道容量 结 论 o无损信道的C决定于信道的输入符号数r o无噪信道的C只决定于信道的输出符号数s 在求信道容量时，调整的始终是输入端的概率分布p(xi)， 尽管信道容量式子中平均互信息I(X;Y)等于输出端符号熵 H(Y)，但是在求极大值时调整的仍然是输入端的概率分布 p(xi) ，而不能用输出端的概率分布p(yj)来代替。 注 意 46 如果一个离散信道的信道转移矩阵中的每一行都是由同一 组元素的不同组合构成的，并且每一列也是由这一组元素组成 的，则称为对称信道。 第四节 信道容量及其一般计算方法 2、对称离散信道的信道容量 o输入对称：矩阵的每一行都是第一行的置换 o输出对称：矩阵的每一列都是第一列的置换 47 下面我们来计算对称离散信道的信道容量：I(X;Y)=H(Y)-H(Y/X) H(Y/X=x)是对矩阵的行求和，而由于对称信道定义，我们 知道，此值是一个与x无关的一个常数，即 因此 可以看出，当输出等概分布时，即H(Y)=logs时信道容量达到最 大。 第四节 信道容量及其一般计算方法 2、对称离散信道的信道容量 48 那么，在什么样的信源输出情况下，信道输出能等概分 布呢？可以证明，输入等概分布时，输出也等概分布 可以看出，信道的输出也是等概分布的 第四节 信道容量及其一般计算方法 2、对称离散信道的信道容量 49 例： 二元对称信道： 第四节 信道容量及其一般计算方法 2、对称离散信道的信道容量 50 如果离散信道的转移矩阵如下 则称此信道为强对称信道或均匀信道，它是对称离散信道 的一种特例。 第四节 信道容量及其一般计算方法 2、对称离散信道的信道容量 u信道中总的错误 概率是p，对称平均 地分配给(n-1)个输 出符号。 u信道矩阵中每行 之和等于1，每列之 和也等于1。 ur*r阶矩阵 51 根据对称离散信道信道容量的计算方法，强对称信道其信道容量 为： 第四节 信道容量及其一般计算方法 2、对称离散信道的信道容量 结论：当信道输入呈等概率分布时，强对称离散信道能够传输 最大的平均信息量，即达到信道容量。这个信道容量只与信道 的输出符号数n和相应信道矩阵中的任一行矢量有关。 52 若信道的列可以划分成若干个互不相交的子集，每一个子集 都是对称信道，则称该信道为准对称信道， 如： 第四节 信道容量及其一般计算方法 3、准对称离散信道的信道容量 53 可以证明达到信道容量的输入分布是等概分布，也可 计算准对称信道的信道容量为： 其中r是输入符号集的个数， 为矩阵中的行元 素; 是第k各矩阵中的行元素只和， 是第k个矩阵的 列元素之和。 第四节 信道容量及其一般计算方法 3、准对称离散信道的信道容量 54 例： 可分成： 第四节 信道容量及其一般计算方法 3、准对称离散信道的信道容量 行之和：N1=1-p-q+p=1-q；N2=q； 列之和：M1=1-q-p+p=1-q，M2=2q 55 我们可以对输入分布求极值，得到 而： 第四节 信道容量及其一般计算方法 4、一般离散信道的信道容量 56 定理3.3 一般离散信道达到信道容量的充要条件 是输入概率分布满足 该定理说明，当平均互信息达到信道容量时，信源每一个 符号都对输出端输出相同的互信息。 第四节 信道容量及其一般计算方法 4、一般离散信道的信道容量 57 可以利用该定理对一些特殊信道求得它的信道容量 例：输入符号集为:0,1,2 第四节 信道容量及其一般计算方法 4、一般离散信道的信道容量 假设P(0)=P(2)=1/2，P(1)=0，则： 59 所以： 第四节 信道容量及其一般计算方法 4、一般离散信道的信道容量 60 对于一般信道的求解方法，就是求解方程组 移项得： 令则 若r=s，此方程有解，可以解出s各未知数 ，再根据 得 从而 第四节 信道容量及其一般计算方法 4、一般离散信道的信道容量 61 例： 可列方程组： 第四节 信道容量及其一般计算方法 4、一般离散信道的信道容量 62 解之得： 第四节 信道容量及其一般计算方法 4、一般离散信道的信道容量 63 第五节 离散无记忆扩展信道及其信道容量 l多符号离散信道定义 定义：多符号离散信源X =X1X2XN在N个不同时刻分别 通过单符号离散信道X P(Y/X) Y，则在输出端出现 相应的随机序列Y =Y1Y2YN，这样形成一个新的信道称 为多符号离散信道。 64 第五节 离散无记忆扩展信道及其信道容量 离散无记忆信道的N次扩展信道的传递概率等于各单位时刻 相应的单符号离散无记忆信道的传递概率的连乘。 65 第五节 离散无记忆扩展信道及其信道容量 离散无记忆信道为： 则它的N次扩展信道为： 为N次扩展信源中的一个符号 为N次扩展接收符号集中的一个符号 66 我们首先从一个例子开始 例：二元无记忆对称信道得二次扩展信道 二元记忆对称信道为 ： 第五节 离散无记忆扩展信道及其信道容量 67 可以将信道的扩展和信源的扩展联系起来看，当信 源扩展以后，信道也就称为了扩展信道。 则它的二次扩展信道为： 第五节 离散无记忆扩展信道及其信道容量 68 根据平均互信息的定义 定理3.5 如果信道是无记忆的，即 则： 定理3.6 如果信源是无记忆的 第五节 离散无记忆扩展信道及其信道容量 69 因此，如果信源、信道都是无记忆的 这就是离散无记忆扩展信道得信道容量，该信道容 量在信源是无记忆信源且每一个输入变量Xi达到最佳分 布时达到。 第五节 离散无记忆扩展信道及其信道容量 第六节 级联信道 o在通信系统中,信息的传输往往要依次 通过若干个信道。 这些信道通常采用 级联的形式。 o级联的含义是被连接的信道输入只依赖 于前面相邻信道的输出而和前面的其它 信道的输出无直接关系。 我们可以把通信系统模型看成各部分的级联，如 下图所示。信源发出L长的序列UL，通过编码后得到 N长的码序列XN， 经信道传输后，译码器收到N长序 列为YN，译码后传给信宿的消息序列为VN。 通信系统模型各部分的级联 随机序列X,Y,Z ，当Y给定时,Z不依赖于X,即： P(z/y)=P(z/xy)，则X,Y,Z构成马氏链。 则信道X-Y与Y-Z构成的信道是级联信道，满足马氏链。 如图所示： 级联信道 若（X,Y,Z）构成马氏链, 则： o定理3.7 定理3.8 若X,Y,Z构成一马氏链，则 证： 即： 同理可证明 。 数据处理定理 数据处理定理的推广 信道2信道3信道1 XYZW 经过数据处理，信息量一般会有丢失，最多保持原有 信息，绝对不会有信息增强。（又称信息不增性原理。） 该定理表明：信息处理（如：编译