信息论 总复习

1总复习1绪论2信源的信息量3离散信源4离散信源的无失真编码5离散信道及其编码定理6连续信道及其容量8信息率失真理论及其应用10线性分组码2编码器信宿信道消息干扰消息通信系统模型信源信号解码器信号+干扰噪声源信息论的研究对象:通信系统模型.信源信道加密信源信道解密通信系统的基本任务要求可靠:要使信源发出的消息经过传输后，尽可能准确地、不失真或限定失真地再现在接收端有效:用尽可能短的时间和尽可能少的设备来传输最大的消息3单符号离散信源自信息量用概率测度定义信息量，设离散信源X，其概率空间为如果知道事件xi已发生，则该事件所含有的自信息定义为信源熵4联合自信息量当X和Y相互独立时，p(xiyj)=p(xi)p(yj)5条件自信息量：已知yj

的条件下xi

仍然存在的不确定度。自信息量、条件自信息量和联合自信息量之间的关系6互信息量：yj对xi的互信息量定义为的后验概率与先验概率比值的对数。两个不确定度之差是不确定度被消除的部分，即等于自信息量减去条件自信息量。7平均信息量—信源熵：自信息的数学期望。也称为信源的信息熵/信源熵/无条件熵/熵。信息熵的意义：信源的信息熵H是从整个信源的统计特性来考虑的。它是从平均意义上来表征信源的总体特性的。对于某特定的信源，其信息熵是唯一的。不同的信源因统计特性不同，其熵也不同。8条件熵：是在联合符号集合XY上的条件自信息的数学期望。联合熵H(XY)：表示输入随机变量X，经信道传输到达信宿，输出随机变量Y。即收、发双方通信后，整个系统仍然存在的不确定度。9信道疑义度—H(X|Y)：表示信宿在收到Y后，信源X仍然存在的不确定度。是通过有噪信道传输后引起的信息量的损失，故也可称为损失熵。噪声熵—H(Y|X)：表示在已知X的条件下，对于符号集Y尚存在的不确定性，这完全是由于信道中噪声引起的。唯一确定信道噪声所需要的平均信息量。10平均互信息量定义：互信息量I(xi;yj)在联合概率空间P(XY)中的统计平均值。从一个事件获得另一个事件的平均互信息需要消除不确定度，一旦消除了不确定度，就获得了信息。11熵H(X)H(X)>=H(X|Y)H(X)=H(X|Y)+I(X;Y)XY条件熵H(X|Y)H(X|Y)=H(XY)-H(Y)=H(X)-I(X;Y)XY联合熵H(XY)=H(YX)H(XY)=H(X)+H(Y|X)=H(X|Y)+H(Y|X)+I(X;Y)XY平均互信息I(X;Y)=I(Y;X)I(X;Y)=H(X)-H(X|Y)=H(X)+H(Y)-H(X,Y)XY平均互信息和熵的关系12数据处理定理（信息不增原理）当消息通过多级处理器时,随着处理器数目的增多,输入消息和输出消息之间的平均互信息量趋于变小。信息不增I(X;Z)≥I(X;f(Z))=I(X;Y)H(X|Z)≤H(X|f(Z))=H(X|Y)13最大离散熵定理(极值性)：离散无记忆信源输出n个不同的信息符号，当且仅当各个符号出现概率相等时(即p(xi)=1/n)，熵最大。H[p(x1),p(x2),…,p(xn)]≤logn14二进制信源的熵函数H(p)为15BSC信道的平均互信息量设二进制对称信道的输入概率空间为1617连续信源的熵为定义的熵在形式上和离散信源相似。连续信源熵并不是实际信源输出的信息量(绝对熵)；Hc(X)也称为相对熵连续信源的信息量为无限大；Hc(X)已不能代表信源的平均不确定度，也不能代表连续信源输出的信息量。18离散信源的无失真编码实质上是一种统计匹配编码。信息论指出信源中的统计多余度主要决定于以下两个主要因素：一是消息概率分布的非均匀性，另一个是消息间的相关性。对无记忆信源主要决定于概率分布的非均匀性，但是，对于有记忆信源，两者都起作用，且后者相关性更加重要。信源编码19Def.可达速率：对于给定的信源和编码速率R及任意δ>0，若存在L0、ξ()、D()，使当码长L>L0时，Pe<δ，就称R是可达的，否则R是不可达的。Th.若R>H(U)，则R是可达的；若R<H(U)，则R是不可达的。20凡是能载荷一定的信息量,且码字的平均长度最短,可分离的变长码的码字集合就称为最佳变长码.

必须将概率大的信息符号以短的码字,将概率小的信息符号以长的码字.主要有:香农-费诺(Shannon-Fano),哈夫曼(Huffman)编码等唯一可译性的两种解决方法Def.逗点码Def.异字头码212香农费诺编码费诺编码步骤如下：a.将概率按从大到小的顺序排列，令b.按编码进制数将概率分组，使每组概率尽可能接近或相等。c.给每一组分配一位码元。d.将每一分组再按同样原则划分，重复步骤b和c，直至概率不再可分为止。223哈夫曼编码a.将信源符号按概率从大到小的顺序排列，令b.给两个概率最小的信源符号p(xn-1)和p(xn)各分配一个码位0和1，将这两个符号合并成一个新符号，其概率之和作为新符号的概率，得到(n－1)个符号。c.将缩减信源符号按概率排列，重复步骤a,b。直至缩减信源只剩两个符号为止。d.从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。注意3进制编码？23信道容量C：在信道中最大的信息传输速率，单位是比特/符号。单位时间的信道容量Ct：若信道平均传输一个符号需要t秒钟，则单位时间的信道容量为

Ct实际是信道的最大信息传输速率。第3章信道容量24求信道容量的方法当信道特性p(yj|xi)固定后，I(X;Y)随信源概率分布p(xi)的变化而变化。调整p(xi)，在接收端就能获得不同的信息量。由平均互信息的性质已知，I(X;Y)是p(xi)的上凸函数，因此总能找到一种概率分布p(xi)（即某一种信源），使信道所能传送的信息率为最大。C和Ct都是求平均互信息I(X;Y)的条件极大值问题，当输入信源概率分布p(xi)调整好以后，C和Ct已与p(xi)无关，而仅仅是信道转移概率的函数，只与信道统计特性有关；信道容量是完全描述信道特性的参量；信道容量是信道能够传送的最大信息量。25当n=2时的强对称离散信道就是二进制均匀信道。二进制均匀信道的信道容量为：二进制均匀信道容量曲线如图所示。26对称DMC容量的计算结论

实现对称DMC信道容量的输入分布为等概分布信道只关于输入对称的话（输入分布为等概分布）27香农公式当信道容量一定时，增大信道带宽，可以降低对信噪功率比的要求；反之，当信道频带较窄时，可以通过提高信噪功率比来补偿。当信道频带无限时，其信道容量与信号功率成正比。连续信道的容量28最佳译码准则（最大似然译码）通信是一个统计过程，纠、检错能力最终要反映到差错概率上。对于FEC方式，采用纠错码后的码字差错概率为pwe，p(C)：发送码字C的先验概率p(C/R)：后验概率若码字数为2k，对充分随机的消息源有p(C)=1/2k，所以最小化的pwe等价为最小化p(C’≠C│R)，又等价为最大化p(C’=C│R)；信道编码29对于BSC信道：最大化的p(C’=C│R)等价于最大化的p(R│C)，最大化的p(R│C)又等价于最小化d(R,C)，所以使差错概率最小的译码是使接收向量R与输出码字C’距离最小的译码。30对给定离散无记忆信道和任意e>0，若有一种编码速率为R的码，在N足够大时，能使pe<e，就称R是可达的。定理(Shannon信道编码定理)，给定容量为C的离散无记忆信道{X，p(x|y)，Y}，若编码速率R<C，则R是可达的。31线性分组码码字重量：码字中非0码元符号的个数，汉明重量。在二元线性码中，码字重量是码字中含“1”的个数。汉明距离：在(n,k)分组码中，两个码字U、V之间对应码元位上符号取值不同的个数。最小距离dmin：任意两个码字间距离最小值.线性分组码：ci,cj是GF(q)上(n,k)分组码中的两个码字,a,bGF(q)上两个元素,如果aci+bcj也是一个码字,称码为线性分组码。(包含全0码字)32生成矩阵线性系统分组码:通过行初等变换，将G化为前k列是单位子阵的标准形式

线性系统分组码：用标准生成矩阵Gk×n编成的码字，这种信息数字(k位)在前,校验数字(r=n－k位)在后的线性分组码称为线性系统分组码。kbit信息位(n-k)bit校验位33校验矩阵341.最小距离与纠错能力：(n,k)线性码能纠t个错误的充要条件是码的最小距离为35伴随式和错误检测①用监督矩阵编码，也用监督矩阵译码：接收到一个接收字R后，校验HRT=0T是否成立：若关系成立，则认为R是一个码字；否则判为码字在传输中发生了错误；②伴随式/监督子/校验子：S=RHT或ST=HRT。③如何纠错？设发送码矢C=(Cn－1,Cn－2,…,C0)信道错误图样为E=(En－1,En－2,…,E0)，其中Ei=0，表示第i位无错；Ei=1，表示第i位有错。i=n－1,n－2,…,0。36接收字R为

R=(Rn-1,Rn-2,…,R0)=C+E=(Cn-1+En-1,Cn-2+En-2,…,C0+E0)求接收字的伴随式（接收字用监督矩阵进行检验ST=HRT=H(C+E)T=HCT+HET

由于HCT=0T，所以ST=HET设H=(h1,h2,…,hn)，其中hi表示H的列。代入式得到37④总结伴随式仅与错误图样有关，而与发送的具体码字无关，即伴随式仅由错误图样决定；伴随式是错误的判别式：若S=0，则判为没有出错，接收字是一个码字；若S≠0，则判为有错。不同的错误图样具有不同的伴随式，它们是一一对应的。对二元码，伴随式是H阵中与错误码元对应列之和。38伴随式译码(6,3)码的标准阵陪集首伴随式39伴随式译码第l个陪集首的重量重量为i的陪集首的数量BSC下，二元线性码正确译码的概率：40伴随式译码译码步骤：计算接收矢量的伴随式由伴随式确定陪集首将陪集首作为错误图样e将v译为c=v-e例：设有码如下所示：信息码字0000000010110110101111111010(1)找出生成矩阵G与监督矩阵H；(2)在二元对称信道下给出最大似然译码的译码表；(3)求正确译码的概率。41解：(1)42(2)

4344信息率失真函数平均失真度信息率失真函数离散信息X：概率分布为P(X)，失真度为d(xi,yj)45信息率失真函数的性质定义域(Dmin,Dmax)：Dmin是最小允许失真度，Dmax是最大允许失真度信息率失真函数的物理意义是：对于给定信源，在平均失真不超过失真限度D的条件下，信息率容许压缩的最小值为R(D)函数特点:下凸性,单调递减和连续性.例：接收符号Y={1/2,1/2}求：Dmax和Dmin及达到Dmax和Dmin时的转移概率矩阵。解：当x1→y1,x2→y1/y2,x3→y2时，平均失真取最小值，对应的当X和Y统计独立，即p(yj/xi)=p(yj）时，I=0,4647对偶问题：信道容量和信息率失真函数的问题，都是求平均互信息极值问题。分三个方面说明：求极值问题平均互信息I(X;Y)是信源概率分布p(xi)(i=1,2,…,n)

的上凸函数，信道容量就是在固定信道情况下，求平均互信息极大值的问题，即I(X;Y)又是信道转移概率分布p(yj|xi)(i=1,2,…,n;j=1,2,…,m)

的