《信息论总复习》PPT课件.ppt

1,总 复 习,1 概论2 信源及信息熵3 信源编码4 信道及信道容量5 信道编码6 信息率失真函数7 考试情况,2,信息与消息和信号的区别消息：是指包含有信息的语言、文字和图像等，可表达客观物质运动和主观思维活动的状态。信号：把消息变换成适合信道传输的物理量，这种物理量称为信号（如电信号、光信号、声音信号等）。信息是事物运动状态和状态改变的方式。,第1章 概论,3,信息信息是事物运动状态和状态改变的方式。研究信息论的目的：它的主要目的是提高信息系统的可靠性、有效性和安全性以便达到系统最优化。在通信系统中形式上传输的是消息，但实质上传输的是信息。消息只是表达信息的工具，载荷信息的客体。,4,编码器,信宿,信道,消息,干扰,消息,通信系统模型,信源,信号,解码器,信号+干扰,噪声源,信息论的研究对象:通信系统模型.,信源信道加密,信源信道解密,通信系统的基本任务要求可靠:要使信源发出的消息经过传输后，尽可能准确地、不失真或限定失真地再现在接收端有效:用尽可能短的时间和尽可能少的设备来传输最大的消息,5,单符号离散信源自信息量用概率测度定义信息量，设离散信源 X，其概率空间为如果知道事件 xi 已发生，则该事件所含有的自信息定义为,第2章 信源熵,6,联合自信息量当 X 和 Y 相互独立时，p(xiyj)=p(xi)p(yj),7,条件自信息量：已知yj 的条件下xi 仍然存在的不确定度。自信息量、条件自信息量和联合自信息量之间的关系,8,互信息量：yj 对 xi 的互信息量定义为的后验概率与先验概率比值的对数。,两个不确定度之差是不确定度被消除的部分，即等于自信息量减去条件自信息量。,9,平均信息量信源熵：自信息的数学期望。也称为信源的信息熵/信源熵/熵。信息熵的意义：信源的信息熵 H 是从整个信源的统计特性来考虑的。它是从平均意义上来表征信源的总体特性的。对于某特定的信源，其信息熵是唯一的。不同的信源因统计特性不同，其熵也不同。,10,条件熵：是在联合符号集合 XY 上的条件自信息的数学期望。,联合熵 H(XY)：表示输入随机变量 X，经信道传输到达信宿，输出随机变量 Y。即收、发双方通信后，整个系统仍然存在的不确定度。,11,信道疑义度H(X|Y)：表示信宿在收到 Y 后，信源 X 仍然存在的不确定度。是通过有噪信道传输后引起的信息量的损失，故也可称为损失熵。噪声熵H(Y|X)：表示在已知 X 的条件下，对于符号集 Y 尚存在的不确定性，这完全是由于信道中噪声引起的。唯一确定信道噪声所需要的平均信息量。,12,平均互信息量定义：互信息量 I(xi;yj)在联合概率空间 P(XY)中的统计平均值。从一个事件获得另一个事件的平均互信息需要消除不确定度，一旦消除了不确定度，就获得了信息。,13,平均互信息和熵的关系,14,数据处理定理（信息不增原理）,当消息通过多级处理器时,随着处理器数目的增多,输入消息和输出消息之间的平均互信息量趋于变小。信息不增,I(X;Z)I(X;f(Z)=I(X;Y)H(X|Z)H(X|f(Z)=H(X|Y),15,最大离散熵定理(极值性)：离散无记忆信源输出 n 个不同的信息符号，当且仅当各个符号出现概率相等时(即p(xi)=1/n)，熵最大。Hp(x1),p(x2),p(xn)logn,16,二进制信源的熵函数 H(p)为,17,BSC信道的平均互信息量 设二进制对称信道的输入概率空间为,18,19,连续信源的熵为,定义的熵在形式上和离散信源相似。连续信源熵并不是实际信源输出的信息量(绝对熵)；Hc(X)也称为相对熵,连续信源的信息量为无限大；Hc(X)已不能代表信源的平均不确定度，也不能代表连续信源输出的信息量。,20,限峰值的最大熵定理:若信源的N维随机变量的取值在一定的范围之内，则在有限的定义域内，均匀分布的连续信源具有最大熵。限平均功率的最大熵定理：若信源输出信号的平均功率P或方差受限，则其输出信号幅度的概率密度函数为高斯分布时，信源具有最大熵值。限均值的最大连续熵定理：若连续信源X输出非负信号的均值受限，则其输出信号幅度呈指数分布时，连续信源X具有最大熵值。,21,离散信源的无失真编码实质上是一种统计匹配编码。信息论指出信源中的统计多余度主要决定于以下两个主要因素：一是消息概率分布的非均匀性，另一个是消息间的相关性。对无记忆信源主要决定于概率分布的非均匀性，但是，对于有记忆信源，两者都起作用，且后者相关性更加重要。,第3章 信源编码,22,Def.可达速率：对于给定的信源和编码速率R及任意0，若存在L0、()、D()，使当码长LL0时，Pe，就称R是可达的，否则R是不可达的。,23,Th.若RH(U)，则R是可达的；若RH(U)，则R是不可达的。对于给定的离散无记忆信源，若D元码的速率R超过信源的熵，即NlogD/L H（U）+，则存在编码方法，当L足够大时能使译码错误概率任意小。logD：一个码符号所能载荷的最大信息量。H(U)：信源输出一个符号所给出的信息量。H(U)/logD：每个信源符号所需的最小的码符号数以等长码实现源编码时的理论极限。,24,离散无记忆信源的等长编码,译码错误概率 pe,契比雪夫不等式,无扰编码定理的含义 RH(U),契比雪夫不等式的右边是理论上的误码率的上限，必须小于给定的误码率才能保证到达编码性能要求,25,定长编码定理,其中差错率满足如下式子,26,凡是能载荷一定的信息量,且码字的平均长度最短,可分离的变长码的码字集合就称为最佳变长码.必须将概率大的信息符号以短的码字,将概率小的信息符号以长的码字.主要有:香农-费诺(Shannon-Fano),哈夫曼(Huffman)编码等,唯一可译性的两种解决方法Def.逗点码Def.异字头码,27,2香农费诺编码,费诺编码步骤如下：a.将概率按从大到小的顺序排列，令b.按编码进制数将概率分组，使每组概率尽可能接近或相等。c.给每一组分配一位码元。d.将每一分组再按同样原则划分，重复步骤b和c，直至概率不再可分为止。,28,3 哈夫曼编码,a.将信源符号按概率从大到小的顺序排列，令b.给两个概率最小的信源符号p(xn-1)和p(xn)各分配一个码位0和1，将这两个符号合并成一个新符号，其概率之和作为新符号的概率，得到(n1)个符号。c.将缩减信源符号按概率排列，重复步骤a,b。直至缩减信源只剩两个符号为止。d.从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。,注意3进制编码？,29,4 算术编码,算术编码是计算序列的累计分布，用累计分布值表示序列，所以称为算术编码以二元信源输出序列的编码为例01110,u对应区间的宽度等于符号序列的概率,30,算术编码,递推公式编码P(u=bbbbbbaa)=0.7560.252=F(a)=0,F(b)=0.25,H=HP(ul+1),G=G+HF(al+1),31,LZ编码,利用字典编码方法信源符号A=(a1aK)将序列分为不同的段取最短长度的连续符号构成段，保证互不相同。先取一个符号分段，若与前面段相同，就再取一个符号，直至序列结束得到字典表，码字由段号加后一个符号组成。单符号的码字，段号为0,32,LZ编码的特点特点一 编码效率可以接近信息熵的上限。特点二 不需要事先知道信源的概率分布。特点三 用一种巧妙的方式使用字典技术。特点四 文件越小，压缩比例越小；文件越大，压缩比例越大。LZ编码的应用领域几乎垄断了整个通用数据压缩领域，如PKZIP、WinZIP、WinRAR、gzip等压缩工具以及ZIP、GIF、PNG等文件格式都是LZ系列算法的受益者。,33,我们学习了几种信源编码：香农费诺编码、哈夫曼编码、游程编码、算术编码、LZ编码等。游程编码和算术编码是非分组编码；游程编码是限失真信源编码。本章介绍的都是离散信源变长编码。优点：提高编码效率；缺点：需要大量缓冲设备来存储这些变长码，然后再以恒定的码率进行传送；如果出现了误码，容易引起错误扩散，所以要求有优质的信道。,34,信道容量 C：在信道中最大的信息传输速率，单位是比特/符号。单位时间的信道容量 Ct：若信道平均传输一个符号需要 t 秒钟，则单位时间的信道容量为 Ct 实际是信道的最大信息传输速率。,第3章 信道容量,35,根据信道中所受噪声种类的不同,可分为随机差错信道和突发差错信道.在有记忆信道中，噪声干扰的影响往往是前后相关的，错误是成串出现的，一般在编码中我们称这类信道为突发差错信道。实际的衰落信道、码间干扰信道均属于这类信道。有些实际信道既有独立随机差错,也有突发性成串差错，我们称它为混合信道。,36,求信道容量的方法当信道特性 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)无关，而仅仅是信道转移概率的函数，只与信道统计特性有关；信道容量是完全描述信道特性的参量；信道容量是信道能够传送的最大信息量。,37,当 n=2 时的强对称离散信道就是二进制均匀信道。二进制均匀信道 的信道容量为：二进制均匀信道容量 曲线如图所示。,38,对称DMC容量的计算,结论 实现对称DMC信道容量的输入分布为等概分布,信道只关于输入对称的话（输入分布为等概分布）,39,一般DMC的容量计算,40,一般DMC的容量计算,这是K个未知量0,1,K-1=C+logw(0),C+logw(1),C+logw(K-1)的线性方程组，系数矩阵是可逆方阵，因此唯一解出0,1,K-1,41,一般DMC的容量计算,另一个等式：w(0)+w(1)+w(K-1)=1。于是,i=C+logw(i),42,积信道或独立并行信道,C1maxI(X1,Y1)，C2maxI(X2,Y2)信道1和信道2同时传递消息，输入集X=X1X2，输出集Y=Y1Y2，转移概率p(jj|kk)=p(j|k)p(j|k)称这样组合成的信道为1和2的积信道或独立并行信道,积信道的容量 C=C1+C2,43,和信道或并信道,单位时间内可以且只能随机选用信道1和信道2中的一个，选用信道1的概率为p1，选用信道2的概率为p2，p1p21输入空间X=X1+X2，Y=Y1+Y2，,44,级联信道或串行信道,信道1的输出作为信道2的输入,（3）令自级连的次数N+，则级连信道的转移概率矩阵趋向于,信道容量趋向于0。,45,香农公式当信道容量一定时，增大信道带宽，可以降低对信噪功率比的要求；反之，当信道频带较窄时，可以通过提高信噪功率比来补偿。当信道频带无限时，其信道容量与信号功率成正比。,46,差错控制的基本方式前向纠错(FEC)：发送端的信道编码器将信息码组编成具有一定纠错能力的码。接收端信道译码器对接收码字进行译码，若传输中产生的差错数目在码的纠错能力之内时，译码器对差错进行定位并加以纠正。自动请求重发(ARQ)：用于检测的纠错码在译码器输出端只给出当前码字传输是否可能出错的指示，当有错时按某种协议通过一个反向信道请求发送端重传已发送的码字全部或部分。,第6章 信道编码,47,混合纠错(HEC)：是 FEC 与 ARQ 方式的结合。发端发送同时具有自动纠错和检测能力的码组，收端收到码组后，检查差错情况，如果差错在码的纠错能力以内，则自动进行纠正。如果信道干扰很严重，错误很多，超过了码的纠错能力，但能检测出来，则经反馈信道请求发端重发这组数据。,48,最佳译码准则（最大似然译码）通信是一个统计过程，纠、检错能力最终要反映到差错概率上。对于FEC方式，采用纠错码后的码字差错概率为pwe，p(C)：发送码字C 的先验概率p(C/R)：后验概率若码字数为 2k，对充分随机的消息源有p(C)=1/2k，所以最小化的pwe等价为最小化p(CCR)，又等价为最大化p(C=CR)；,49,对于 BSC 信道：最大化的 p(C=CR)等价于最大化的 p(RC)，最大化的p(RC)又等价于最小化 d(R,C)，所以使差错概率最小的译码是使接收向量 R 与输出码字 C 距离最小的译码。,50,对给定离散无记忆信道和任意e 0，若有一种编码速率为R 的码，在N足够大时，能使pee，就称R 是可达的。,定理(Shannon信道编码定理)，给定容量为C的离散无记忆信道X，p(x|y)，Y，若编码速率RC，则R是可达的。,51,线性分组码,码字重量：码字中非0码元符号的个数，汉明重量。在二元线性码中，码字重量是码字中含“1”的个数。汉明距离：在(n,k)分组码中，两个码字 U、V 之间对应码元位上符号取值不同的个数。最小距离dmin：任意两个码字间距离最小值.,线性分组码：ci,cj是GF(q)上(n,k)分组码中的两个码字,a,b GF(q)上两个元素,如果aci+bcj也是一个码字,称码为线性分组码。(包含全0码字),52,生成矩阵,线性系统分组码:通过行初等变换，将 G 化为前 k 列是单位子阵的标准形式,线性系统分组码：用标准生成矩阵Gkn 编成的码字，这种信息数字(k位)在前,校验数字(r=nk位)在后的线性分组码称为线性系统分组码。,kbit信息位,(n-k)bit校验位,53,校验矩阵,54,1.最小距离与纠错能力：(n,k)线性码能纠t个错误的充要条件是码的最小距离为,55,伴随式和错误检测 用监督矩阵编码，也用监督矩阵译码：接收到一个接收字 R 后，校验 HRT=0T 是否成立：若关系成立，则认为 R 是一个码字；否则判为码字在传输中发生了错误；伴随式/监督子/校验子：S=RHT或ST=HRT。如何纠错？设发送码矢 C=(Cn1,Cn2,C0)信道错误图样为 E=(En1,En2,E0)，其中Ei=0，表示第i位无错；Ei=1，表示第i位有错。i=n1,n2,0。,56,接收字 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的列。代入式得到,57,总结伴随式仅与错误图样有关，而与发送的具体码字无关，即伴随式仅由错误图样决定；伴随式是错误的判别式：若S=0，则判为没有出错，接收字是一个码字；若S0，则判为有错。不同的错误图样具有不同的伴随式，它们是一一对应的。对二元码，伴随式是 H 阵中与错误码元对应列之和。,58,(1)循环码的定义循环码：如果(n,k)线性分组码的任意码矢C=(C0,C1,Cn-1)的1次循环移位，所得矢量C(1)=(Cn-1,C0,Cn-2)仍是一个码字，则称此线性码为(n,k)循环码。,码多项式：为了运算的方便，将码字的各分量作为多项式的系数，把码矢表示成多项式，称为码多项式C(x)=C0+C1x+Cn1xn1,59,定理：在(n,k)循环码中，每个码多项式c(x)都是 生成多项式g(x)的倍式；而每个为g(x)倍式且次数小于或等于(n1)的多项式，必是一个码多项式。,定理：循环码的生成多项式g(x)是(xn-1)的因式，即 xn-1=h(x)g(x)。反之若循环码的多项式g(x)是(xn-1)的因式，则 g(x)是生成多项式。,60,系统循环码,待编码的消息序列表示为多项式,61,系统循环码的编码步骤：,设g(x)为(n,k)循环码的生成多项式，则有xn-1=h(x)g(x)，式中h(x)为k次多项式，称h(x)的反多项式h*(x)为(n,k)循环码的校验多项式。,62,第4章 信息率失真函数,平均失真度信息率失真函数离散信息X：概率分布为P(X)，失真度为d(xi,yj),63,信息率失真函数的性质定义域(Dmin,Dmax)：Dmin是最小允许失真度，Dmax是最大允许失真度信息率失真函数的物理意义是：对于给定信源，在平均失真不超过失真限度D的条件下，信息率容许压缩的最小值为R(D)函数特点:下凸性,单调递减和连续性.,64,对偶问题：信道容量和信息率失真函数的问题，都是求平均互信息极值问题。分三个方面说明：求极值问题平均互信息I(X;Y)是信源概率分布p(xi)(i=1,2,n)的上凸函数，信道容量就是在固定信道情况下，求平均互信息极大值的问题，即I(X;Y)又是信道转移概率分布 p(yj|xi)(i=1,2,n;j=1,2,m)的下凸函数，信息率失真函数就是在试验信道（满足保真度准则的信道）中寻找平均互信息极小值的问题，即,65,特 性信道容量C 求出后，就只与信道转移概率p(yj/xi)有关，反映信道特性，与信源特性无关；率失真函数R(D)求出后，就只与信源概率分布p(xi)有关，反映信源特性，与信道特性无关。解决的问题信道容量是解决通信的可靠性问题，是信息传输的理论基础，通过信道编码增加信息的冗余度来实现；信息率失真函数是解决通信的有效性问题，是信源压缩的理论基础，通过信源编码减少信息的冗余度来实现。,66,DMS 求R(D)步骤,j=1,2,3,J,解出,2.由,解出,1.,3.由,解出S,4.代入,67,三个编码定理1,1）无失真信源编码定理：在无失真意义下,实现通信系统与信源统计特性相匹配：即当系统中传信率RH(U)(信源熵)时，最优的信源编、译码存在；反之，当RH(U)时，最优信源编、译码不存在。称它为Shannon编码第一定理。,3）限失真信源编码定理：在限失真意义下，实现通信系统与信源统计特性相匹配:即当RR(D)（信息率失真函数）时，最优的信源编、译码存在；反之，当RR(D)时，最优信源编、译码不存在，称它为Shannon编码第三定理。,2）信道编码定理：在均方误差意义下，实现通信系统与信道统计特性相匹配；即当RC时，最优信道编，译码不存在；称它为Shannon编码第二定理。,68,时间：地点：闭卷带计算器，计算题写成对数形式，或精确到小数点后至少两位有效数字.认真答题，字迹清楚，论述详实，计算题须有中间过程,考试情况,69,祝大家好运,