2009-应用信息论基础-张林-Chap-3-442009020

第三章信道及其容量第三章信道及其容量ChannelsandChannelCapacity2009年11月9日2009年11月16日2009年11月16日©THU2009–Allrightsreserved清华大学电子系－张林本章课程脉络本章课程脉络©THU2009–Allrightsreserved23.1信道容量的定义和性质信道容量的定义和性质„通信是什么？…物理实体A的作用引发了物理实体B的状态变化…若A与B的状态变化存在一致性，称A与B通信成功„从信息角度看通信的本质…比特流的端到端无差错复制…比特流的端到端无差错复制„香农抽象的信道模型©THU2009–Allrightsreserved3信道的分类信道的分类„类似信源分类方法：按照输入输出的形式和时间取值来划分…按照输入输出的形式和时间取值来划分取值时间信道分类取值时间信道分类离散离散离散信道（DiscreteChannel）、数字信道（DigitalChl）离散离散Channel）连续离散连续信道（ContinuousChannel）连续连续模拟信道（AnalogChannel）离散连续离散连续©THU2009–Allrightsreserved4信道的统计表示信道的统计表示„按照信道随机过程的特点分类…信道可以表示为n-阶转移概率矩阵{}12n12n12ntttttttttq()=Qyx…无记忆信道：{}n()()∏…一般认为信道是平稳的：12n12niii1q(yy...yxx...x)q(yx)==∏q(yi|xi)=q(y|x)©THU2009–Allrightsreserved5离散无记忆信道的定义离散无记忆信道的定义„定义3.1：称具有输入字母表X和输出字母表Y，以及转移概率矩阵Q={q(y|x)}的系统为离散无记忆信道。其中，q(y|x)表示系统输入为x时观察到输出为y的条件概率。关于信道的注释关于信道的注释9信道转移概率矩阵Q为|X|行、|Y|列的矩阵9称一个信道时无记忆的，若某一时刻的输出仅和当时的称个信道时无记忆的，若某时刻的输出仅和当时的Bb输入有关，而与过去的输入和输出无关。©THU2009–Allrightsreserved6离散无记忆信道的输入和输出离散无记忆信道的输入和输出定理3.1：设信道输入为X=(X1,X2,…Xn)，输出为Y=(Y1,Y2,…Yn)。对于离散无记忆信道，有：(;)(;)≤∑XYnIIXY1(;)(;)=≤∑XYiiiIIXY证明见板书证明见板书©THU2009–Allrightsreserved7信道容量的定义信道容量的定义„定义3.2：对于离散无记忆信道，信道容量为：C=maxI(X;Y)＝maxI(pQ)C=maxI(X;Y)＝maxI(p,Q)p(x)p(x)关于信道容量：9C的量纲是什么？9最大值是跑遍所有可能的输入分布的条件下获得的9该信道容量可以取到吗？9香农第二定理将回答这个问题本章我们先解决求解该9香农第二定理将回答这个问题，本章我们先解决求解该Bb最大值的方法。©THU2009–Allrightsreserved8信道容量的性质信道容量的性质„定理3.2：信道容量具有以下的性质…C0…C≤log|X|…C≤log|Y|„另外，我们还注意到：…I(X;Y)是()的连续函数这两条性质允许我们…I(X;Y)是p(x)的连续函数…I(X;Y)是p(x)的上凸函数直接使用凸规划的方法求I(X;Y)的极值，从而得到从而得到C©THU2009–Allrightsreserved93.2离散无记忆信道容量离散无记忆信道容量„先从简单的例子出发例3.1:无噪声二元信道，输入X，输出Y…观察1：由于传输无差错，所以每次传输都传递了1比特的无差错信息，所以直观地信容量道为所以，直观地，信容量道为1bit。…观察2：C=maxI(X;Y)=maxH(X)=1bit，当p(x)=(0.5,0.5)时取到。…如果符号变为m个情况如何？©THU2009–Allrightsreserved10…如果符号变为m个，情况如何？例3.2:输出不重叠的噪声信道例输噪声信…信道存在噪声，因而输出不确定；…但是不确定性不影响正确估计输入；…但是不确定性不影响正确估计输入；…因此，信道实际是无差错的。…X到Y是一对多映射：C=maxI(X;Y)=maxmin{H(X),H(Y)}=maxH(X)=1bitmaxH(X)1bit…信道容量在p(x)=(0.5,0.5)的时候取到。思考：输出不重叠的噪声信道无噪声＝无差错？©THU2009–Allrightsreserved11例3.3：混乱的打字机例字机„混乱的打字机把每个字母以0.5的概率映射为其本身或下一个字母映射为其本身或下一个字母„计算其信道容量：C=maxI(X;Y)CmaxI(X;Y)=maxH(Y)–H(Y|X)=maxH(Y)–1=log26–1=log13„获得信道容量的输入分布是均匀分布。思考：考有噪声信道可以通过降低码率，变成无差错的。这有什么启示？©THU2009–Allrightsreserved12混乱的打字机无重叠约化简单的离散信道容量（1）简单的离散信道容量（）„定理3.3:二进制对称信道的容量为C=1–H(p)。1pp−⎛⎞⎜⎟ppp1p⎜⎟−⎝⎠进制对称信道的二进制对称信道二进制对称信道的转移概率矩阵证明见板书证明见板书©THU2009–Allrightsreserved13简单的离散信道容量（2）简单的离散信道容量（）„定理3.4:二进制删除信道的容量为C=1–α。⎛⎞1001−αα⎛⎞⎜⎟−αα⎝⎠进制删除信道二进制删除信道的转移概率矩阵二进制删除信道证明见板书证明见板书©THU2009–Allrightsreserved14离散无记忆对称信道容量离散无记忆对称信道容量„定义3.3：若信道的转移概率矩阵的行互为置换，列互为置换，称该信道对称；若行互为置换，各列之和相等，称该信道弱对称。111236111⎡⎤⎢⎥⎢⎥⎢⎥111362⎡⎤⎢⎥⎢⎥111623111⎢⎥⎢⎥⎢⎥⎢⎥362111326⎢⎥⎢⎥⎢⎥⎣⎦362⎢⎥⎢⎥⎣⎦对称信道弱对称信道（但非对称）©THU2009–Allrightsreserved15弱对称信道的容量弱对称信道的容量„定理3.5：弱对称信道Q的容量为C=log|Y|–H(Q的行向量对应的分布)容量在输入为等概分布的时候取得容量在输入为等概分布的时候取得。证明见板书证明见板书证明见板书证明见板书思考：如果信道再“弱”一些列和不等如果信道再“弱”一些，列和不等，以上定理形式如何变化？©THU2009–Allrightsreserved16一般无记忆离散信道的容量问题的表述般无记忆离散信道的容量问题的表述„由于I(p,Q)是p的上凸函数，求信道容量问题可以表述称一个约束极值问题max()IpQmax()()1Ipxst⎧=⎪⎨∑pp,QX..()0stpx⎨⎪≥⎩X„求解方法…拉格朗日乘数法…梯度搜索法©THU2009–Allrightsreserved17…迭代解法一般约束凸规划问题的求解般约束凸规划问题的求解„定理3.6(Kuhn-Tucker条件)：义在维穷集12(){(,...,):0,1,2,...,}NifxNSSxxxxxiN==≥=设为定义在维无穷凸集12(,,...,),()NxxxxSfxxxS∗∗∗∗∗=∈=上的可微上凸函数，设则在达到上的极大值的充要条件是()0,0nxxnfxxx∗∗=∂=∂如果()0,0nxxnfxxx∗∗=∂≤∂如果＝12(,,...,),00NnnxxxxxxSxx∗∗∗∗∗∗∗=∃=注：时，为的内点，时，S∗为的边界点。©THU2009–Allrightsreserved18K-T条件的图形解释条件的图形解释„求minf(x,y)=ax2－blog2y，0x100，0y100¾用拉格朗日乘子法求解¾用K-T条件验证¾最小值由两个要素决定:¾原优化目标函数的凸性¾取值在可行域边缘时¾取值在可行域边缘时候方向导数的符号KTKT证略证略©THU2009–Allrightsreserved19离散无记忆信道容量离散无记忆信道容量定理3.7：对于信道矩阵为Q的离散无记忆信道，其输入分布p*能使互信息I(pQ)取得最大值的充要条件是：p能使互信息I(p,Q)取得最大值的充要条件是：(;),:()0kkkIXxYCxpx∗==对(;),:()0{1,2,...,}kkkIXxYCxpxkK∗=≤=∈对其中，()(;)()logJjkqyxIXxYqyx=∑＝1(;)()log()kjkjjIXxYqyxpy==∑＝表示的是信源字母xk传送的平均互信息，C为信道容量。证明见板书证明见板书©THU2009–Allrightsreserved20信道容量求解的直观解释信道容量求解的直观解释„求解信道容量过程实际信源的概率分布进行调节的过程(;):(;)IXYIXxY=的平均值布进行调节的过程。„通过不断调节信源的概率分布找到1.(;)IXxYx=步骤：找使最大的应的概率使的概率分布，找到信道对应的最大信息传输速率。2.()Xxpx↑↓调整对应的概率，使增大以提高总的互信息量，但是息传输速率。()(;)XpxIXxY↑⇒=↓©THU2009–Allrightsreserved21例3.4：计算如图所示信道的容量例计算如图所示信道的容量00431310⎛⎞⎜⎟1131413131044111333⎜⎟⎜⎟⎜⎟⎜⎟⎜⎟22414333113044⎜⎟⎜⎟⎜⎟⎝⎠…最佳分布p*(0)=p*(2)=0.5,p*(1)=0…最佳分布p(0)p(2)0.5,p(1)0…I(X=0;Y)=I(X=2;Y)=0.75I(X=1;Y)=0.0251…C=075…C0.75证明见板书证明见板书©THU2009–Allrightsreserved22达到信道容量时分布的唯一性达到信道容量时分布的唯性„达到信道容量C的时候，输入字母分布唯一吗？„反例：‡令p=0.5‡则C=1－H(p)=0‡输入任何分布，输出都达到C„又一例：又例：121200012120⎡⎤⎢⎥⎢⎥‡令p=(0.5,0,0.5,0),I(X;Y)=C‡令p=(0.25,0.25,0.25,0.25),I(X;Y)=C达到信道容量时，012120001212120012⎢⎥⎢⎥⎢⎥⎣⎦‡最优输入分布不唯一©THU2009–Allrightsreserved23达到信道容量时输入分布不唯一120012⎣⎦输出字母的唯一性输出字母的唯性„定理3.8：达到信道容量时的输出分布是唯一的。任何导致这输出分布的输入分布都是最佳分布可致这一输出分布的输入分布都是最佳分布，可以使互信息达到信道容量。达到信道容量时输出分布唯一达到信道容量时，输出分布唯一例如：对称信道，输出唯一（等概）证明见板书证明见板书©THU2009–Allrightsreserved24输入字母在什么条件下唯一？输入字母在什么条件下唯„定理3.9：对于含有最大数目零概率分量的最佳分布，其非零概率分量是唯一确定的，且非零概率分量的数目不超过输出字母的总数。„再看这个例子…令p=0.5…则C=1－H(p)=0…输入任何分布，输出都达到C…但可以最大化输入0概率字母的个数最…但可以最大化输入0概率字母的个数，最大值为1，此时输入分布唯一。••定理定理3.93.9不是说具有最大数目零概率的最佳分布是唯一的。不是说具有最大数目零概率的最佳分布是唯一的。••定理定理3.93.9只说明概率分布由同一组包含零的数字的不同排列构成。只说明概率分布由同一组包含零的数字的不同排列构成。••对应特定符号的概率仍可能不唯一。对应特定符号的概率仍可能不唯一。©THU2009–Allrightsreserved25对应特定符号的概率仍可能不唯对应特定符号的概率仍可能不唯例3.5：计算输入输出字母表大小相等的信道容量例计算输入输出字母表大小相等的信道容量„设输入、输出字母表大小为K„I(p,Q)是p的上凸函数