信息论与编码傅祖云讲义第三章

信息论与编码傅祖云讲义第三章第1页，共63页。第三章离散信道及其信道容量本章的重、难点内容：了解信道的分类及基本数学模型掌握平均互信息和平均条件互信息的概念和意义知道平均互信息的特征掌握信道容量及其一般计算方法*第2页，共63页。3.1信道的数学模型及分类在广义的通信系统中，信道是很重要的一部分。信道的任务是以信号方式传输信息和存储信息。研究信道的目的就是研究信道中能够传送或存储的最大信息量，即信道容量问题。本章首先讨论离散信道的统计特性和数学模型，然后定量地研究信道传输的平均互信息及其性质，并导出信道容量及其计算方法。本章只限于研究一个输入端和一个输出端即单用户信道，以无记忆、无反馈、恒参离散信道为重点。第3页，共63页。信道的分类根据信道的用户多少根据信道输入输出的关联根据信道参数与时间的关系根据输入输出信号的特点两端（单用户）信道多端（多用户）信道无反馈信道反馈信道固定参数信道时变参数信道离散信道连续信道半离散或半连续信道波形信道第4页，共63页。离散信道的数学模型离散信道的数学模型如下图所示信道XY图3.1离散信道数学模型根据信道的统计特性即条件概率的不同，离散信道又可分成三种情况。第5页，共63页。离散信道的数学模型无干扰（无噪）信道有干扰无记忆信道：离散无记忆信道的充要条件对任意N值和任意x、y的取值，上式都成立。有干扰有记忆信道：即有干扰（噪声）又有记忆，实际信道往往是这种类型。信道输出不但与输入有关，还与其它时刻的输入和输出有关，这样的信道称为有记忆信道。第6页，共63页。单符号离散信道的数学模型单符号离散信道的输入变量为X，取值于；输出变量为Y，取值于。并有条件概率这一组条件概率称为信道的传递概率或转移概率一般简单的单符号离散信道的数学模型可以用概率空间[X,p(y|x),Y]来描述。第7页，共63页。两种重要的二元信道BSC和BEC例3.1

二元对称信道BSC（BinarySymmetricChannel）这是很重要的一种特殊信道。输入符号X取值于｛0，1｝；输出符号也取值于｛0，1｝。传递概率：传递矩阵：a1=0a2=1b1=0b2=11-p1-pppXY第8页，共63页。两种重要的二元信道BSC和BEC例3.2

二元删除信道BEC（BinaryErasureChannel）这也是很重要的一种特殊信道。输入符号X取值于｛0，1｝；输出符号取值于｛0，2，1｝。信道传递矩阵：0101pq1-p1-q2第9页，共63页。二元删除信道BEC的说明这种信道实际是存在的，当信号波形传输中失真较大时，我们在接收端不是对接收信号硬性判为0和1，而是根据最佳接收机额外给出的信道失真信息增加一个中间状态2（称为删除符号），采用特定的纠删编码，可有效的恢复出这个中间状态的正确取值。如果信道干扰不是很严重的话，和的可能性要比和的可能性小得多，所以，假设是较合理的。

第10页，共63页。单符号离散信道的数学模型由此可见，一般单符号离散信道的转移概率可用信道转移矩阵P来表示：关于信道矩阵的几点说明：1、输入和输出符号的联合概率为第11页，共63页。单符号离散信道的数学模型其中是信道传递概率，通常称为前向概率，它是由于噪声引起的，描述了信道噪声的特性。而称为后向概率。也把称为先验概率，而把称为后验概率。2、根据联合概率可得输出符号的概率3、根据贝叶斯公式得后验概率上式说明，在信道输出端接收到任一符号一定是输入符号,…中的一个输入信道。第12页，共63页。3.2平均互信息及平均条件互信息信道疑义度信源输入信道的熵—先验熵H(X)信道中有干扰(噪声)存在，接收到符号

后输入的是什么符号仍存在有不确定性—后验熵。意义：后验熵是当信道接收端接收到输出符号后，关于输入符号的信息测度。第13页，共63页。信道疑义度后验熵在输出符号集Y范围内是个随机量，对后验熵在符号集Y中求数学期望，得条件熵为—信道疑义度(含糊度)：意义：信道疑义度表示在输出端收到输出变量Y的符号后，对于输入端的变量X尚存在的平均不确定性（存在疑义）。这是由于信道干扰（噪声）引起的。第14页，共63页。信道疑义度的说明对于一一对应信道，接收到输出Y后，对X的不确定性将完全消除，信道疑义度。一般情况下条件熵小于无条件熵，有。说明接收到变量Y的所有符号后，关于输入变量X的平均不确定性将减少，即总能消除一些关于输入端X的不确定性，从而获得了一些信息。第15页，共63页。平均互信息通过信道传输消除了一些不确定性，获得了一定的信息。我们定义：称为X和Y之间的平均互信息。物理意义：它代表接收到输出符号后平均每个符号获得的关于X的信息量。它也表明，输入与输出两个随机变量之间的统计约束程度。互信息是代表收到某消息y后获得关于某事件x的信息量。它可取正值，也可取负值。

是

的统计平均,所以。第16页，共63页。平均互信息与各类熵之间的关系熵只是平均不确定性的描述，而不确定性的消除（两熵之差）才等于接收端所获得的信息量。因此，获得的信息量不应该和不确定性混为一谈。维拉图表示的各类熵之间的关系：H(X|Y)H(Y|X)I(X;Y)H(X)H(Y)H(XY)第17页，共63页。平均互信息与各类熵之间的关系每个圆减去平均互信息后剩余的部分代表两个疑义度是信道疑义度，又称为损失熵反映了信道中噪声源的不确定性，又称噪声熵或散布度H(X|Y)H(Y|X)I(X;Y)H(X)H(Y)H(XY)第18页，共63页。平均互信息与各类熵之间的关系下面讨论两种极端情况1、无噪一一对应信道（无损信道）此时可以计算得：在图中就表示是两圆重合。信道中损失熵和噪声熵都为零。有2、输入输出完全统计独立（全损信道）第19页，共63页。3.3平均互信息的特性1、平均互信息的非负性该性质表明，通过信道总能传递一些信息，最差的条件下，输入输出完全独立，不传递任何信息，互信息等于0，但决不会失去已知的信息。2、平均互信息的极值性一般来说，信道疑义度总是大于0，所以互信息总是小于信源的熵，只有当信道是无损信道时，信道疑义度等于0，互信息等于信源的熵。第20页，共63页。平均互信息的特征3、平均互信息的交互性（对称性）实际上I(X;Y)和I(Y;X)只是观察者的立足点不同，对信道的输入X和输出Y的总体测度的两种表达形式。正因为有交互性，所以命名为互信息。

4、平均互信息的凸状性（两个定理）定理3.1平均互信息是信源概率分布p(x)的∩型凸函数。第21页，共63页。平均互信息的特征定理3.1的意义：对于每一个固定信道，一定存在一种信源（某一概率分布P(X)），使输出端获得的平均信息量为最大Imax（∩型凸函数存在极大值）。这时称这个信源为该信道的匹配信源。定理3.2平均互信息是信道传递概率的∪型凸函数。定理3.2的意义：对每一种信源都存在一种最差的信道，此信道的干扰（噪声）最大，而输出端获得的信息量最小Imin。第22页，共63页。二元对称信道BSC的平均互信息[例3.4]设二元对称信道的输入概率空间为信道特性如图所示,求平均互信息解：根据平均互信息的定义得：a1=0a2=1b1=0b2=11-p1-pppXY第23页，共63页。二元对称信道BSC的平均互信息输出符号的概率：则所以第24页，共63页。二元对称信道BSC的平均互信息其中也是区域上的熵函数。当信道固定即固定p时，可得是ω的∩型函数，如图所示。10ωI(X;Y)1－H(p)0.50.510pI(X;Y)H(ω)0.51H(ω)第25页，共63页。3.4信道容量及其一般计算方法预备知识及几个定义：研究信道的目的是要讨论信道中平均每个符号所能传送的信息量，即信道的信息传输率R。定义信息的传输率就是平均互信息。即定义单位时间内平均传输的信息量为信息传输速率。第26页，共63页。信道容量及其一般计算方法每个固定信道都有一个最大的信息传输率，定义这个最大的信息传输率为信道容量C，即其单位为或，而相应的输入概率分布称为最佳输入分布。单位时间内平均传输的最大信息量为一般仍称为信道容量。第27页，共63页。信道容量及其一般计算方法信道容量的含义：信道容量与已输入信源的概率分布无关，它是信道的特征的参量，反映的是信道的最大信息传输能力。由上节知识得对于二元信道平均互信息为当时，平均互信息的极大值为因此，二元对称信道的信道容量为与X概率分布ω无关。计算信道容量就是求极大值问题。第28页，共63页。1、离散无噪无损信道无噪：一个输入对应一个输出，噪声熵无损：一个输出对应一个输入，损失熵所以这类信道的平均互信息为信道容量为a1a2a3b2b1b3111信道矩阵第29页，共63页。离散无噪信道的信道容量2、离散有噪无损信道特点:信道矩阵中每一列有且仅有一个非零元素有噪：一个X对应多个Y，无损：接收到Y后X完全确定，信道容量b1a1a2a3b2b3b4b5b611/21/23/53/101/10信道矩阵第30页，共63页。离散无噪信道的信道容量3、离散无噪有损信道（确定信道）信道容量：此类信道接收到符号Y后不能完全消除对X的不确定性，信息有损失。但输出端Y的平均不确定性因噪声熵等于零而没有增加。a1a2a3aiai+1arb1b2b3无噪：有损：一个X对应一个Y，前向概率非0即1，一个Y对应多个X，后向概率不等于0或1，第31页，共63页。离散无噪信道的信道容量我们可以用维拉图来表述有噪无损信道和无噪有损信道中平均互信息、损失熵、噪声熵以及信源熵之间的关系。I(X;Y)H(X)=I(X;Y)H(Y)H(Y|X)有噪无损信道I(X;Y)H(Y)=I(X;Y)H(X)H(X|Y)有损无噪信道第32页，共63页。如果信道转移矩阵P中每一行都是由同一组元素的不同排列构成的，并且每一列也是由这一组元素不同排列组成的，则称这种信道为对称离散信道。例如而不是对称信道第33页，共63页。对称离散信道的信道容量若输入符号和输出符号个数相同，都等于r，且信道矩阵为其中，则称此信道为强对称信道或均匀信道。该信道矩阵中各列之和也等于1。第34页，共63页。对称离散信道的信道容量对于对称离散信道，当输入符号X达到等概率分布，则输出符号Y一定也达到等概率分布。由此得对称离散信道的信道容量为对称离散信道能够传输的最大的平均信息量，它只与对称信道矩阵中行矢量和输出符号集的个数s有关。第35页，共63页。对称离散信道容量的计算[例3.5]某对称离散信道的信道矩阵为解：每个符号平均能够传输的最大信息为0.0817

bit,只有当输入符号等概分布时才达到这个最大值。第36页，共63页。对称离散信道容量的计算[例3.6]对于强对称信道，其信道容量为对于二元信道r=2由上式得第37页，共63页。对称离散信道容量的计算二元对称信道讨论：当p=1/2时，二元对称信道的信道容量C=0，不管输入概率分布如何都能达到信道容量。该信道输入端不能传递任何信息到输出端。这种信道是没有任何实际意义的，但它从理论上说明了信道的最佳输入分布不一定是惟一的。

第38页，共63页。准对称信道的概念：若信道的列可以划分成若干个互不相交的子集，每一个子集都是对称信道，则称该信道为准对称信道，如：可划分为可划分为第39页，共63页。准对称信道的信道容量可以证明达到准对称离散信道信道容量的输入分布（最佳输入分布）是等概分布，也可计算得准对称离散信道的信道容量为：其中r是输入符号集的个数，为准对称信道矩阵中的行元素。而是第k个子矩阵中行元素之和，是第k个子矩阵中列元素之和。即第40页，共63页。一般离散信道的信道容量的计算：就是对所有可能的输入概率分布求平均互信息的极大值。对一般信道有定理3.3:一般离散信道的平均互信息达到极大值（即等于信道容量）的充要条件是输入概率分布满足这时C就是所求的信道容量。第41页，共63页。一般离散信道的信道容量在定理3.3中是输出端接收到Y后，获得关于的信息量，即是信源符号对输出端Y平均提供的互信息。一般值与有关，且有令第42页，共63页。一般离散信道的信道容量该定理说明：当平均互信息达到信道容量时，输入信源每一个符号x输出相同的互信息。可以利用该定理对一些特殊信道求它的信道容量[例3.8]输入符号集，输出符号集。信道传递矩阵为求该信道的信道容量。01201111/21/2第43页，共63页。一般离散信道的信道容量解：假设输入概率分布为检验是否满足定理3.3，若满足就找到了最佳分布。由式得第44页，共63页。一般离散信道的信道容量由以上可见此输入分布满足定理3.3因此可得这个信道的信道容量为而达到信道容量的输入概率分布就是前面假设的分布第45页，共63页。一般离散信道的信道容量例3.9信道如图，输入符号集为，输出符号集为。信道矩阵为,求信道容量。解：设输入概率分布b1a1a2a3b2110.5a4a5110.5第46页，共63页。由式及式计算得此假设分布满足定理3.3。因此信道容量为最佳分布是第47页，共63页。若设输入分布为同理可得也有根据定理3.3可知，输入分布也是最佳分布，还有其它最佳分布，这说明信道的最佳输入分布不是唯一的。而输出分布是唯一的。第48页，共63页。一般离散信道的信道容量计算对于一般离散信道，很难利用定理3.3来求信道容量和对应的输入概率分布，只能采用求解如下方程组的方法。于是把方程组中前r个方程改写成：第49页，共63页。一般离散信道的信道容量计算移项后可得：令代入上式，得：这是含有s个未知数βj，有r个方程的非齐次线性方程组。第50页，共63页。一般离散信道的信道容量计算如果设r=s，信道转移矩阵P是非奇异方阵，则此方程组有解，并且可以求出βj的数值，然后根据的条件求得信道容量：由这个C值就可解得对应的输出概率分布p(bj)再根据就可解出达到信道容量的最佳输入概率分布{p(ai)}。第51页，共63页。一般离散信道的信道容量计算[例3.10]设离散无记忆信道如图，输入X的符号集为输出Y的符号集传递矩阵为求其信道容量及其最佳的输入概率分布。a11/21/2111/41/41/41/4a2a3a4b1b2b3b4第52页，共63页。一般离散信道的信道容量计算此信道是非对称信道，无法利用定理3.3来计算信道容量。但这信道矩阵为方阵r=s,且为非奇异矩阵，所以可得方程组：解方程组，得第53页，共63页。一般离散信道的信道容量计算得信道容量输出符号概为由此可得最佳输入分布为第54页，共63页。一般离散信道的信道容量计算几点说明：有时所求出的{P(ai)}不一定能满足概率的条件（因为采用拉格朗日乘子法时没有加入P(ai)>0

的条件限制），所以必须对解进行检查。如果所有解都满足P(ai)>0,则解是正确的。否则解无效。第55页，共63页。一般离散信道的信道容量计