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