信息论与编码ppt

信息论与编码信息论与编码香农信息论香农信息论理论体系理论体系主讲：肖主讲：肖竹竹信息论期末的考试内容3香农信息论•三个基本概念•信源熵、信道容量、率失真函数，都是临界值•三个极限定理无失真信源编码定理、限失真信源编码定理、信道编码定理，都是存在性定理Shannon’s编码定理体系(TheShannon’sCodingTheoremSystem)信源Source信道Channel信宿DestinationXYObjectiveexistence客观存在性H(X)Possibility最大可能性CPracticalrequirement实际需求性R(D)编码极限定理——CodingLimitedTheorem()RHX存在性保证，且构造性给出。RC存在性保证。()RRD存在性保证。名称符号关系图示无条件熵条件熵条件熵联合熵交互熵)/()()();()/()/()(XYHXYHXHYXIYXHYXHXH)(XH)(YH)/(YXH)/(XYH)()(YXHXYH);();(XYIYXI)/()()();()/()/()(YXHXYHYHYXIXYHXYHYH);()()()()/(YXIXHYHXYHYXH);()()()()/(YXIYHXHXYHXYH);()/()/();()()()/()()/()()(YXIXYHYXHYXIYHXHYXHYHXYHXHXYH)()()()/()/()()/()()/()();(XYHYHXHYXHXYHXYHXYHYHYXHXHYXIYXYXYXYXYXYX各种熵之间的关系将定理3.3推广到L次扩展信源---香农第一定理：变长编码定理1loglogLHXHXnDLDL定理3.4给定熵为H(X)的离散无记忆信源定理3.3是定理3.4在L=1时的特例(3-23)1212,,...,X,,...,p()MMxxxpxpxpxXL1212x,x,...,xX=x,x,...,xp()p()LLMLMpppX其L次扩展信源的熵记为H(X)给定有D个元素的码符号集，对扩展信源编码，总可以找到一种唯一可译码，使码长满足：LnShannon第一定理的物理意义：信源编码时，应使编码后的码集中各码字尽可能等概分布，若将该码集看成一个新的信源，此时新信源所含信息量最大。11;loglogloglogLHXHXHXHXnnDLDLDDL这是信息传输速率能达到的极限值，对应于等概分布。DR由定理3.4的证明过程：信息传输速率,limloglogDLHXHULnRDDn信源符号对应的平均码字数LnnLShannon第一定理的物理意义：信源编码时，应使编码后的码集中各码字尽可能等概分布，若将该码集看成一个新的信源，此时新信源所含信息量最大。最大化的去除统计冗余性可以作为一种编码方法的指导：对离散信源进行适当变换，码符号信源(信道的输入)尽可能等概率分布,所含信息量达到最大,从而使信道的信息传输率R达到信道容量C,实现信源与信道理想的统计匹配。同样用编码效率来衡量编码情况是否理想。用比值定义：回顾等长编码的编码效率：logHXnD一般情况下，log=logHXDHXnnD=loglogLHXHXnDnLD该式中即：信源每个符号所对应的平均码字数，因此等长编码和变长编码这两种情况的编码效率一致。nL(3-26)是理想情况1平均不确定度，信源提供的信息量平均不确定性的消除量1max(;)()IXYpa最大传信率—信道容量Cmin(;)jiIXYP满足失真要求下的最小传信率;/IXYHXHYXHX()RD信道容量与率失真函数①.有关对信源的客观描述即H(X)问题，注意这种描述是与信道、信宿无关，它仅反映信源本身含有信息的度量和它发送信息的能力。②.指如何描述给定信道的功能特征，这也是在与信源、信宿无关的条件下，纯客观地评价一个信道固有特性问题。即，C是反映当给定信道后与某种信源处于最佳匹配时的最大信息传输量问题。③.指了解信宿与信源之间的某种需求并且体现与信道无关的客观描述——R(D)信息率失真函数。从系统模型来看：信源Source信道Channel信宿DestinationXY()RD()HXC•数据压缩是信息传输和处理的重要研究内容。•率失真理论研究的就是在允许一定失真的前提下，对信源的压缩编码。•率失真信源编码定理（香农第三定理）指出：率失真函数R(D)就是在给定失真测度条件下，对信源熵可压缩的最低程度。信道容量C率失真函数R(D)研究对象信道信源给定条件信道转移概率p(y|x)信源分布p(x)选择参数信源分布p(x)信源编码器映射关系p(y|x)结论噪声干扰消失的信息量H(X|Y)压缩损失的信息量H(X|Y));(max)(YXICiap);(min)(YXIDRDP)|()();(YXHXHYXIC表示信道的最大传输能力，信道本身特征，是无差错传输的上限在保真度条件下信源信息率能被压缩的最低限度，属于信源本身特性率失真函数与信道容量的比较（1）14率失真函数与信道容量的比较（2）信道容量C率失真函数R(D)数学上固定p(y/x),改变p(x),求得I(X;Y)最大值固定p(x),改变p(y/xi),求得I(X;Y)最小值概念上(反映)固定信道，改变信源，使信息率最大（信道传输能力）固定信源，改变信道，使信息率最小（信源可压缩程度）通信上使传输信息量最大，Pe→0——信道编码用尽可能少的码符号传送——信源编码()DD香农第二定理：有噪信道编码定理离散、无记忆、平稳信道，信道容量为C，只要待传送的信息率RC，就一定能找到一种信道编码方法，使得码长N足够大时，平均差错率Pe任意接近于零。香农（1948）第二定理是存在性定理，它指出在RC时，肯定存在一种好的信道编码方法，使Pe逼近零。但并没有给出编码的具体方法。提高数据传输可靠性的方向有噪信道编码逆定理离散、无记忆、平稳信道，信道容量为C，如果信息率RC，则肯定找不到一种信道编码方法，使得码长N足够大时，平均差错率任意接近于零。信道编码的指导意义当取信道容量C以下的信息传输率时，以指数趋进于0；当取分界点以下的信息传输率时，以指数趋进于1；因此在任何信道中:信道容量都是可达的、最大的可靠信息传输率。存在定理，它没有给出一个具体可构造的编码方法，但有助于指导各种通信系统的设计，有助于评价各种系统及编码的效率。EPEP离散无记忆平稳信源的信息率失真函数为R(D),只要满足R＞R(D),当信源序列L足够长时，一定存在一种编码方法（存在一种试验信道），其译码失真（平均失真）小于或等于D＋ε，其中ε是任意小的正数；反之，若R＜R(D),则无论采用什么样的编码方法，其译码失真必大于D.DD香农第三定理：定理包括两部分，RR(D)的情况称为保真度准则下的率失真编码定理，RR(D)的情况称之为逆定理。香农第三定理：限失真信源编码定理19限失真信源编码定理限失真信源编码定理限失真信源编码定理，香农第三极限定理设R(D)为一离散无记忆信源的率失真函数，并且有有限的失真测度D。当信息传输率RR(D)时，对于任意，以及任意长的码长n，一定存在一种信源编码C，其码字个数为使编码后码的平均失真度。0,0D[()]2nRDMDD20定理的含义是：只要码长n足够长，总可以找到一种信源编码，使编码后的信息传输率略大于(直至无限逼近)率失真函数R(D)，而码的平均失真度不大于给定的允许失真，即：DDR(D)为给定D前提下信源编码可能达到的下限，所以香农第三定理说明了：达到此下限的最佳信源编码是存在的．21实际的信源编码(无失真编码或先限失真编码后无失真编码)的最终目标是尽量接近最佳编码，使编码信息传输率接近最大值logr，而同时又保证译码后能无失真地恢复信源的全部信息量H(X)或限失真条件下的必要信息量R(D)．编码后信息传输率的提高使每个编码符号能携带尽可能多的信息量，-----使得传输同样多的信源总信息量所需的码符号数大大减少；------使信道容量C不变的前提下使传输时间大大缩短，从而提高了通信的效率．22香农第三定理仍然只是个存在性定理。至于最佳编码方法如何寻找，定理中并没有给出。因此有关理论的实际应用有待于进一步研究．该定理在实际应用中存在的两大问题：如何计算符合实际信源的信息率失真函数R(D)?如何寻找最佳编码方法才能达到信息压缩的极限值R(D)?Shannon’s编码定理体制以上三个不等式分别代表了三类编码极限定理：1.Shannon’s1stlimitingtheorem为无失真信源编码定理。2.Shannon’s2ndlimitingtheorem为信道编码定理。3.Shannon’s3rdlimitingtheorem为限失真信源编码定理。这三个极限定理构成了Shannon’编码定理体系。极限定理都有其共性，也有个性。所给出的指导作用也各不相同，但其证明方式都采用随机编码方式证明。所谓存在性，是指定理仅给出是否存在着一种(至少一种)编码方式可以满足要求；但如何编码则无可奉告。它们的逆定理则给出了不存在性，这是它们的共性。所谓构造性，是指定理不仅指出了存在性，而且还给出了最佳码字的结构特性，如码长、代码形式等。千万不要提前交卷：别忘了有人在最后的35s内得了13分！！！通信工程!!!