《叶中行信息论课件第五章.ppt》由会员分享，可在线阅读，更多相关《叶中行信息论课件第五章.ppt（67页珍藏版）》请在三一办公上搜索。
1、第5章 限失真信源编码和率失真函数,无失真信源编码和有噪信道编码表明：只要信道的信息传输速率小于信道容量，总能找到一种编码方法，使得在该信道上的信息传输的差错概率任意小；反之，若信道的信息传输速率大于信道容量，则不可能使信息传输差错概率任意小但是，无失真的编码并非总是必要的：例如在传送语音信号时，由于人耳接受的带宽和分辨率是有限的，从而可以把频谱范围从20Hz8kHz的语音信号去掉低端和高端的频率，视为带宽只有从300Hz3400Hz的信号；这样，即使传输的语音信号有一些失真，人耳还是可以分辨或感觉出来，已满足语音信号传输的要求,在允许一定程度失真的条件下，能够把信源信息压缩到什么程度，即最少
2、需要多少比特数才能描述信源，是本章将要讨论的问题,5.1 限失真信源编码模型和率失真函数,一、失真测度从直观感觉可知，若允许失真越大，信息传输率可 越小；若允许失真越小，信息传输率需越大所以信息传输率与信源编码所引起的失真(或误差)是有关的,1.定义信源编码器输入X x1,x2,xi,xn 输出（复制）X x1,x2,xj,xn 若xi=xj 则无失真若xi xj 则有失真定义含义 衡量用 x代替 x所引起的失真程度,通常较小的d代表较小的失真，d0表示没有失真单符号失真度！,若信源变量X有n个符号，接收变量X有n个符号，则d(x,x)就有nn个,它可以排列成矩阵形式，即：,它为失真矩阵D,例
3、1 离散对称信源信源变量xx1,x2,xn，接收变量X x 1,x 2,x。定义单个符号失真度：,这种失真称为汉明失真汉明失真矩阵对角线上的元素为零，即：,对二元对称信源(n2)，信源X0,1，接收变量X 0,1在汉明失真定义下，失真矩阵为：,例 对称信源信源变量1,2,，接收变量 1,2,。失真度定义为：,若信源符号代表信源输出信号的幅度值，这就是一种以方差表示的失真度。它意味着幅度差值大的要比幅度差值小的所引起的失真更为严重，严重程度用平方来表示。当 3时，0,1,2，0,1,2，则失真矩阵为：,上述例子说明了具体失真度的定义一般情况下根据实际信源的失真，可以定义不同的失真和误差的度量另外
4、还可以按其他标准，如引起的损失、风险、主观感觉上的差别大小等来定义失真度d(,),须强调:假设是信源，是信宿，那么两者之间必有信道：转移概率p(|)实际这里指的是原始的未失真信源，而是指失真以后的信源有时又把p(|)称为试验信道的转移概率，如图所示：,二、平均失真测度,信源和信宿都是随机变量，故单个符号失真度d(,)也是随机变量显然，规定了单个符号失真度后，传输一个符号引起的平均失真，即信源平均失真度：,在离散情况下，信源x1,x2,xn，其概率分布P(x)P(x1),P(x2),P(xn)，信宿X X 1,X 2,X n 若已知试验信道的传递概率为P(x|x)时，则平均失真度为：,若平均失真
5、度D不大于我们所允许的失真D，即：D D 称此为保真度准则（）,信源固定(给定P(x)，单个符号失真度固定时(给定d(x,x)，选择不同试验信道，相当于不同的编码方法，所得的平均失真度是不同的。有些试验信道满足D D，而有些试验信道DD.凡满足保真度准则-平均失真度D D的试验信通称为-D失真许可的试验信道,平均失真是对给定信源分布,在给定转移概率分布的信道中传输时的失真的总体量度,说明是在平均意义上，对系统失真的总体描述是信源统计特性p(x)的函数 是信道统计特性p(x/x)的函数 是规定失真度 d(x,x)的函数若保持p(x)、d(x,x)不变，则平均失真度就是信道特性p(x/x)的函数研
6、究：在满足保真度准则前提下，求信息率最小值,三、信息率失真函数的定义,1.率失真函数问题产生?对于信息容量为C的信道传输信息传输率为R的信源时，如果RC，就必须对信源压缩，使其压缩后信息传输率R小于信道容量C，但同时要保证压缩所引人的失真不超过预先规定的限度信息压缩问题就是对于给定的信源，在满足平均失真 的前提下，使信息率尽可能小。,三、信息率失真函数的定义,信源给定，且又具体定义了失真函数以后，总希望在满足一定失真的情况下，使信源传输给收信者的信息传输率R尽可能地小即在满足保真度准则下，寻找信源必须传输给收信者的信息率R的下限值-这个下限值与D有关从接收端来看，就是在满足保真度准则下，寻找再
7、现信源消息所必须获得的最低平均信息量而接收端获得的平均信息量可用平均互信息I(X;X)来表示，这就变成了在满足保真度准则的条件下，寻找平均互信息I(X;X)的最小值,R(D)-信息率失真函数或简称率失真函数。单位是奈特信源符号 或 比特信源符号,率失真函数与信道容量的比较,四、信息率失真函数的性质,允许失真度D的下限可以是零，即不允许任何失真的情况.,1、R(D)的定义域,R(D)的定义域为 且：,当失真矩阵中每行至少一个零元,解：,例 设试验信道输入符号集，各符号对应概率分别为)=1/3,1/3,1/3，失真矩阵如下所示，求 和 以及相应的试验信道的转移概率矩阵。,令对应最小失真度 的，其它
8、为“0”，可得对应 的试验信道转移概率矩阵为,上式中第二项最小，所以令，可得对应 的试验信道转移概率矩阵为,4.1.3 率失真函数R(D)性质(续),计算例离散二元信源，求Dmax解,2、R(D)是关于平均失真度D的（下）凸函数,设 为任意两个平均失真，则有：,3、R(D)是 区间上的连续和严格单调递减函数 由信息率失真函数的下凸性可知，R(D)在 上连续；又由R(D)函数的非增性且不为常数知，R(D)是区间 上的严格单调递减函数。,R(D)的值域 R(D)min=0 R(D)max=R(0)，D=0即无失真传输 熵保持编码(1)对离散信源、无噪信道，R(D)max=H(X)(2)对连续信源，
9、R(D)maxH,当且仅当D不小于Dmax,信息率失真函数的一般形状,5.2离散信源率失真函数的计算,已知信源的概率分布P(X)和失真函数d(x,x)，就可求得信源的R(D)函数；原则上它与信道容量一样，即在有约束条件下求极小值的问题 也就是适当选取试验信道P(x|x)使平均互信息最小化：,其约束条件为：,一、信息率失真函数的参量表述,应用拉格朗日乘子法，原则上可以求出解来,但是，如果要求得到明显的解析表达式，则比较困难，通常只能用参量形式来表达即便如此，除简单情况外，实际计算仍然是相当困难的尤其是第三个约束条件，它是求解 R(D)函数最主要的障碍因为应用拉格朗日乘子法解得的一个或某几个P(x
10、|x)很可能是负的在这情况下，必须假设某些P(x|x)=0，然后重新计算，这就使得计算复杂化了目前，可采用收敛的迭代算法在电子计算机上求解R(D)函数下面介绍用拉格朗日乘子法求解R(D)函数，并用作为参量来表述率失真函数R(D)和失真函数D()：,由式(1)知，当信源的概率分布P(x)固定，平均互信息仅仅是试验信道P(x|x)的函数.若先不考虑式(2)的约束，约束条件式(3)包含n个等式，取拉格朗日乘子分别与之对应；并取拉氏乘子 与式(4)对应.由此构成辅助函数：,求极值，就是求辅助函数一阶导数等于零的方程组的解.即求：,所以原则上只需求解式(6)、(3)和(4)的方程组，即可求出I(U;V)
11、在约束条件下的极小值,令,代入（6）得到,对x求和，得,将（*）代入（*）得到,乘P(x),对x求和，最后同除以P(x)得到,解方程组可以求得P(x).从而，代入（*）式求出(x),从而将其代入（*）式得到P(x|x).,由式(1)知，当信源的概率分布P(x)固定，平均互信息仅仅是试验信道P(x|x)的函数。若先不考虑式(2)的约束，约束条件式(3)包含n个等式，取拉格朗日乘子分别与之对应；并取拉氏乘子 与式(4)对应.由此构成辅助函数：,得到率失真函数和平均失真函数：,注：这时所得的结果是以为参量的表达式，而不是显式表达式，因而所得到的R(D)的表达式也是以为参量的表达式参量对应的限制条件为
12、式(4)，它与允许的失真度D有关，所以以为参量就相当于以D为参量,例题 设信源，相应的概率分布为,汉明失真,求此信源,的，并给出其率失真分布,解：利用式子计算,范例展示,对x求和，得,将（*）代入（*）得到,乘P(X),对x求和，最后同除以P(x)得到,两端同乘P(x)，对x求和：,解得：,利用结果（*），可得,对x求和，得,将（*）代入（*）得到,乘P(X),对x求和，最后同除以P(x)得到,解得：,利用结果（*），可得,将上述结果代入式子中，得,得到率失真函数和平均失真函数：,将上述结果代入式子中，得,由于取负值，所以,.又要满足 解得,而,.所以，当,时，必有,因此分两个区间计算率失真函
13、数.,1）,2）,利用结果（*），可得,计算得：,综上所述，得,二、二进对称信源的率失真函数,它的率失真函数：,对应的率失真分布：,三、r元等概分布对称信源的率失真函数,对应的率失真分布：,习题：一个四元对称信道接收符号为其失真矩阵为求信源的R(D)函数,因为是四元对称信道，又是等概率分布，所以根据四元离散对称信源可得,5.3 限失真信源编码定理,(限失真信源编码定理，香农第三极限定理)设R(D)为一离散无记忆信源的率失真函数，并且有有限的失真测度D对于任意，以及任意长的码长n，一定存在一种信源编码C，其码字个数为 使编码后码的平均失真度,定理的含义是：只要码长n足够长，总可以找到一种信源编码
14、，使编码后的信息传输率略大于(直至无限逼近)率失真函数R(D)，而码的平均失真度不大于给定的允许失真度，即：,由于R(D)为给定D前提下信源编码可能达到的下限，所以香农第三定理即说明了：达到此下限的最佳信源编码是存在的,实际的信源编码(无失真编码或先限失真编码后无失真编码)的最终目标是尽量接近最佳编码，使编码信息传输率接近最大值log r，而同时又保证译码后能无失真地恢复信源的全部信息量H(X)或限失真条件下的必要信息量R(D)编码后信息传输率的提高使每个编码符号能携带尽可能多的信息量，-使得传输同样多的信源总信息量所需的码符号数大大减少；-使信道容量C不变的前提下使传输时间大大缩短，从而提高
15、了通信的效率,香农第三定理仍然只是个存在性定理，至于最佳编码方法如何寻找，定理中并没有给出，因此有关理论的实际应用有待于进一步研究如何计算符合实际信源的信息率失真函数R(D)?如何寻找最佳编码方法才能达到信息压缩的极限值R(D)?这是该定理在实际应用中存在的两大问题，它们的彻底解决还有赖于继续的努力尽管如此，香农第三定理毕竟对最佳限失真信源编码方法的存在给出了肯定的回答，它为今后人们在该领域的不断深入探索提供了坚定的信心,香农信息论三个基本概念信源熵、信道容量、率失真函数，都是临界值三个极限定理无失真信源编码定理、限失真信源编码定理、信道编码定理，都是存在性定理,平均损失和信息价值,香农信息论
16、的信息量客观信息量的重要性因人而异主观把平均失真理解为平均损失，便可衡量价值;一、例某厂生产：合格品x1，p(x1)=0.99 废 品x2，p(x2)=0.01检验：合格品y1，合格品报废损失1元 废 品y2，废品出厂损失100元建模型检验不正确引起的损失信道传输失真,信息量相同，但价值不同,1.产品未经检验全部出厂p(y1/x1)=p(y1/x2)=1 p(y2/x1)=p(y2/x2)=0 结论产品未经检验全部出厂引起损失1元,平均损失和信息价值,2.产品未经检验全部报废p(y1/x1)=p(y1/x2)=0 p(y2/x1)=p(y2/x2)=1结论产品未经检验全部报废引起损失0.99元
17、出厂一个废品比报废99个合格品的损失大根据Dmax定义，Dmax=0.99若允许损失为0.99元，则无需检验，把产品报废即可,平均损失和信息价值,3.检验完全正确p(y1/x1)=p(y2/x2)=1 p(y2/x1)=p(y1/x2)=0结论为达无错检验，需要0.081bit信息量 0.081bit信息量避免了0.99元的损失每bit价值=0.99/0.081=12.2元/bit,平均损失和信息价值,4.检验有一定误差(设错判概率为0.1)p(y1/x1)=p(y2/x2)=0.9 p(y2/x1)=p(y1/x2)=0.1结论1 比最大损失(0.99元)减少了0.791元，原因是检验获得了
18、信息量I(X;Y),平均损失和信息价值,结论1每bit价值=0.791/0.025=31.6元/bit,平均损失和信息价值,结论2 有差检验的信息价值比无差检验的高！可画出信息(R)损失(D)曲线反之，D(R)信息率为R时的平均损失,平均损失和信息价值,所谓3G，其实它的全称为3rd Generation，是指第三代数字通信.1995年问世的第一代模拟制式手机（1G）只能进行语音通话；1996到1997年出现的第二代GSM等数字制式手机（2G）便增加了接收数据的功能，如接受电子邮件或网页；第三代与前两代的主要区别是在传输声音和数据的速度上的提升，它能够要能在全球范围内更好地实现无缝漫游，并处理
19、图像、音乐、视频流等多种媒体形式，同时也要考虑与已有第二代系统的良好兼容性;,避免信号的盲区,基站控制器,无线基站子系统,公用陆地移动通信网,公共交换电话网络,国际电信联盟（ITU）在2000年5月确定WCDMA、CDMA2000和TD-SCDMA三大主流无线接口标准，写入3G技术指导性文2000年国际移动通讯计划（简称IMT2000）。CDMA是Code Division Multiple Access(码分多址)的缩写，是第三代移动通信系统的技术基础。Time Division Synchronous CDMA(时分同步CDMA)；,目前已经进行商业应用的2.5G移动通信技术是从2G迈向3
20、G的衔接性技术;GPRS、WAP、蓝牙(Bluetooth)等技术都是2.5G技术.,GPRS由于具备立即联机的特性，对于使用者而言，可说是随时都在上线的状态GPRS技术也让服务业者能够依据数据传输量来收费，而不是单纯的以联机时间计费;,WAP（Wireless Application Protocol，无线应用通讯协议）是移动通信与互联网结合的第一阶段性产物，也是大家听说最多的。这项技术让使用者可以用手机之类的无线装置上网，透过小型屏幕遍游在各个同站之间;,Bluetooth（蓝牙）蓝牙是一种短距的无线通讯技术，电子装置彼此可以透过蓝牙而连接起来;透过芯片上的无线接收器，配有蓝牙技术的电子产品能够在十公尺的距离内彼此相通，传输速度可以达到每秒钟1兆字节。,
