叶中行信息论课件第五章

第5章

限失真信源编码和率失真函数1叶中行信息论课件第五章共67页，您现在浏览的是第1页!无失真信源编码和有噪信道编码表明：只要信道的信息传输速率小于信道容量，总能找到一种编码方法，使得在该信道上的信息传输的差错概率任意小；反之，若信道的信息传输速率大于信道容量，则不可能使信息传输差错概率任意小．但是，无失真的编码并非总是必要的：例如在传送语音信号时，由于人耳接受的带宽和分辨率是有限的，从而可以把频谱范围从20Hz~8kHz的语音信号去掉低端和高端的频率，视为带宽只有从300Hz~3400Hz的信号；这样，即使传输的语音信号有一些失真，人耳还是可以分辨或感觉出来，已满足语音信号传输的要求．2叶中行信息论课件第五章共67页，您现在浏览的是第2页!在允许一定程度失真的条件下，能够把信源信息压缩到什么程度，即最少需要多少比特数才能描述信源，是本章将要讨论的问题．3叶中行信息论课件第五章共67页，您现在浏览的是第3页!

5.1限失真信源编码模型和率失真函数一、失真测度从直观感觉可知，若允许失真越大，信息传输率可越小；若允许失真越小，信息传输率需越大．所以信息传输率与信源编码所引起的失真(或误差)是有关的．4叶中行信息论课件第五章共67页，您现在浏览的是第4页!若信源变量X有n个符号，接收变量X^有n个符号，则d(x,x^)就有n×n个,它可以排列成矩阵形式，即：它为失真矩阵D．5叶中行信息论课件第五章共67页，您现在浏览的是第5页![例２]对称信源．信源变量Ｘ＝{ｘ1,ｘ2,…ｘｎ}，接收变量Ｘ^＝{ｘ^1,ｘ^2,…ｘ^ｎ}。失真度定义为：若信源符号代表信源输出信号的幅度值，这就是一种以方差表示的失真度。它意味着幅度差值大的要比幅度差值小的所引起的失真更为严重，严重程度用平方来表示。当ｎ＝3时，Ｘ＝{0,1,2}，Ｘ^＝{0,1,2}，则失真矩阵为：上述例子说明了具体失真度的定义．一般情况下根据实际信源的失真，可以定义不同的失真和误差的度量．另外还可以按其他标准，如引起的损失、风险、主观感觉上的差别大小等来定义失真度d(ｘ,ｘ^)．6叶中行信息论课件第五章共67页，您现在浏览的是第6页!二、平均失真测度信源Ｘ和信宿Ｘ^都是随机变量，故单个符号失真度d(ｘ,ｘ^)也是随机变量．显然，规定了单个符号失真度后，传输一个符号引起的平均失真，即信源平均失真度：在离散情况下，信源Ｘ＝{x1,x2,…xn}，其概率分布P(x)＝[P(x1),P(x2),…P(xn)]，信宿X^＝{X^1,X^2,…X^n}．若已知试验信道的传递概率为P(x|x^)时，则平均失真度为：7叶中行信息论课件第五章共67页，您现在浏览的是第7页![说明]①是在平均意义上，对系统失真的总体描述②是信源统计特性p(x)的函数是信道统计特性p(x/x^)的函数是规定失真度d(x,x^)的函数若保持p(x)、d(x,x^)不变，则平均失真度就是信道特性p(x/x^)的函数研究：在满足保真度准则前提下，求信息率最小值8叶中行信息论课件第五章共67页，您现在浏览的是第8页!三、信息率失真函数的定义

信源给定，且又具体定义了失真函数以后，总希望在满足一定失真的情况下，使信源传输给收信者的信息传输率R尽可能地小．即在满足保真度准则下，寻找信源必须传输给收信者的信息率R的下限值-------------这个下限值与D有关．从接收端来看，就是在满足保真度准则下，寻找再现信源消息所必须获得的最低平均信息量．而接收端获得的平均信息量可用平均互信息I(X;X^)来表示，这就变成了在满足保真度准则的条件下，寻找平均互信息I(X;X^)的最小值．9叶中行信息论课件第五章共67页，您现在浏览的是第9页!率失真函数与信道容量的比较信道容量C率失真函数R(D)数学上固定p(x^/x),改变p(x),求得I(X;X^)最大值固定p(x),改变p(x^/xi),求得I(X;X^)最小值概念上(反映)固定信道，改变信源，使信息率最大（信道传输能力）固定信源，改变信道，使信息率最小（信源可压缩程度）通信上使传输信息量最大，Pe→0——信道编码用尽可能少的码符号传送——信源编码10叶中行信息论课件第五章共67页，您现在浏览的是第10页!11叶中行信息论课件第五章共67页，您现在浏览的是第11页!上式中第二项最小，所以令，，可得对应的试验信道转移概率矩阵为12叶中行信息论课件第五章共67页，您现在浏览的是第12页!

2、R(D)是关于平均失真度D的（下）凸函数

设为任意两个平均失真，，则有：3、R(D)是区间上的连续和严格单调递减函数由信息率失真函数的下凸性可知，R(D)在上连续；又由R(D)函数的非增性且不为常数知，R(D)是区间上的严格单调递减函数。13叶中行信息论课件第五章共67页，您现在浏览的是第13页!信息率失真函数的一般形状14叶中行信息论课件第五章共67页，您现在浏览的是第14页!一、信息率失真函数的参量表述应用拉格朗日乘子法，原则上可以求出解来．15叶中行信息论课件第五章共67页，您现在浏览的是第15页!

由式(1)知，当信源的概率分布P(x)固定，平均互信息仅仅是试验信道P(x^|x)的函数.若先不考虑式(2)的约束，约束条件式(3)包含n个等式，取拉格朗日乘子α分别与之对应；并取拉氏乘子λ与式(4)对应.由此构成辅助函数：(2)(3)(4)16叶中行信息论课件第五章共67页，您现在浏览的是第16页!对x^求和，得将（**）代入（*）得到乘P(x),对x求和，最后同除以P(x^)得到17叶中行信息论课件第五章共67页，您现在浏览的是第17页!

由式(1)知，当信源的概率分布P(x)固定，平均互信息仅仅是试验信道P(x^|x)的函数。若先不考虑式(2)的约束，约束条件式(3)包含n个等式，取拉格朗日乘子α分别与之对应；并取拉氏乘子λ与式(4)对应.由此构成辅助函数：(2)(3)(4)18叶中行信息论课件第五章共67页，您现在浏览的是第18页!注：这时所得的结果是以λ为参量的表达式，而不是显式表达式，因而所得到的R(D)的表达式也是以λ为参量的表达式．参量λ对应的限制条件为式(4)，它与允许的失真度D有关，所以以λ为参量就相当于以D为参量．19叶中行信息论课件第五章共67页，您现在浏览的是第19页!对x^求和，得将（**）代入（*）得到乘P(X),对x求和，最后同除以P(x^)得到两端同乘P(x)，对x求和：20叶中行信息论课件第五章共67页，您现在浏览的是第20页!对x^求和，得将（**）代入（*）得到乘P(X),对x求和，最后同除以P(x^)得到21叶中行信息论课件第五章共67页，您现在浏览的是第21页!将上述结果代入式子中，得22叶中行信息论课件第五章共67页，您现在浏览的是第22页!将上述结果代入式子中，得由于λ取负值，所以.又要满足解得而.所以，当时，必有因此分两个区间计算率失真函数.1）23叶中行信息论课件第五章共67页，您现在浏览的是第23页!计算得：综上所述，得24叶中行信息论课件第五章共67页，您现在浏览的是第24页!三、r元等概分布对称信源的率失真函数对应的率失真分布：25叶中行信息论课件第五章共67页，您现在浏览的是第25页!因为是四元对称信道，又是等概率分布，所以根据四元离散对称信源可得26叶中行信息论课件第五章共67页，您现在浏览的是第26页!定理的含义是：只要码长n足够长，总可以找到一种信源编码，使编码后的信息传输率略大于(直至无限逼近)率失真函数R(D)，而码的平均失真度不大于给定的允许失真度，即：由于R(D)为给定D前提下信源编码可能达到的下限，所以香农第三定理即说明了：达到此下限的最佳信源编码是存在的．27叶中行信息论课件第五章共67页，您现在浏览的是第27页!香农第三定理仍然只是个存在性定理，至于最佳编码方法如何寻找，定理中并没有给出，因此有关理论的实际应用有待于进一步研究．如何计算符合实际信源的信息率失真函数R(D)?如何寻找最佳编码方法才能达到信息压缩的极限值R(D)?这是该定理在实际应用中存在的两大问题，它们的彻底解决还有赖于继续的努力．尽管如此，香农第三定理毕竟对最佳限失真信源编码方法的存在给出了肯定的回答，它为今后人们在该领域的不断深入探索提供了坚定的信心．28叶中行信息论课件第五章共67页，您现在浏览的是第28页!平均损失和信息价值香农信息论的信息量——客观信息量的重要性因人而异——主观把平均失真理解为平均损失，便可衡量价值;一、例——某厂生产：合格品—x1，p(x1)=0.99废品—x2，p(x2)=0.01检验：合格品—y1，合格品报废—损失1元废品—y2，废品出厂—损失100元建模型检验不正确引起的损失——信道传输失真信息量相同，但价值不同信源信道X(生产)(检验)Y29叶中行信息论课件第五章共67页，您现在浏览的是第29页!2.产品未经检验全部报废p(y1/x1)=p(y1/x2)=0p(y2/x1)=p(y2/x2)=1[结论]①产品未经检验全部报废引起损失0.99元②出厂一个废品比报废99个合格品的损失大③根据Dmax定义，Dmax=0.99④若允许损失为0.99元，则无需检验，把产品报废即可信源信道X(生产)(检验)Y平均损失和信息价值30叶中行信息论课件第五章共67页，您现在浏览的是第30页!4.检验有一定误差(设错判概率为0.1)p(y1/x1)=p(y2/x2)=0.9p(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平均损失和信息价值31叶中行信息论课件第五章共67页，您现在浏览的是第31页![结论2]有差检验的信息价值比无差检验的高！可画出信息(R)～损失(D)曲线反之，D(R)——信息率为R时的平均损失00.199

0.99

D(元)R(D)(bit)H(X)0.0810.025Dmax平均损失和信息价值32叶中行信息论课件第五章共67页，您现在浏览的是第32页!基站控制器

无线基站子系统公用陆地移动通信网

公共交换电话网络33叶中行信息论课件第五章共67页，您现在浏览的是第33页!目前已经进行商业应用的2.5G移动通信技术是从2G迈向3G的衔接性技术;GPRS、WAP、蓝牙(Bluetooth)等技术都是2.5G技术.

34叶中行信息论课件第五章共67页，您现在浏览的是第34页!WAP（WirelessApplicationProtocol，无线应用通讯协议）是移动通信与互联网结合的阶段性产物，也是大家听说最多的。这项技术让使用者可以用手机之类的无线装置上网，透过小型屏幕遍游在各个同站之间;35叶中行信息论课件第五章共67页，您现在浏览的是第35页!1.定义信源编码器输入X∈{x1,x2,…,xi,…,xn}输出（复制）X^∈{x^1,x^2,…,x^j,…,x^n}若xi=x^j——则无失真若xi≠x^j——则有失真[定义][含义]衡量用x^代替x所引起的失真程度．

通常较小的d代表较小的失真，d＝0表示没有失真—单符号失真度！36叶中行信息论课件第五章共67页，您现在浏览的是第36页![例1]

离散对称信源．信源变量x＝{x1,x2,…xn}，接收变量X^＝{x^1,x^2,…x^ｎ}。定义单个符号失真度：这种失真称为汉明失真．汉明失真矩阵＿对角线上的元素为零，即：对二元对称信源(n＝2)，信源X＝{0,1}，接收变量X^＝{0,1}．在汉明失真定义下，失真矩阵为：37叶中行信息论课件第五章共67页，您现在浏览的是第37页!须强调:假设Ｘ是信源，Ｘ^是信宿，那么两者之间必有信道：转移概率p(ｘ^|ｘ)实际这里Ｘ指的是原始的未失真信源，而Ｘ^是指失真以后的信源．有时又把p(ｘ^|ｘ)称为试验信道的转移概率，如图所示：原始信源失真信源试验信道信道ＸＸ^p(ｘ^|ｘ)38叶中行信息论课件第五章共67页，您现在浏览的是第38页!若平均失真度D不大于我们所允许的失真D，即：DD称此为保真度准则（定义5.1.2）．信源固定(给定P(x))，单个符号失真度固定时(给定d(x,x^))，选择不同试验信道，相当于不同的编码方法，所得的平均失真度是不同的。有些试验信道满足DD，而有些试验信道D＞D.凡满足保真度准则----平均失真度DD的试验信通称为---D失真许可的试验信道．平均失真是对给定信源分布,在给定转移概率分布的信道中传输时的失真的总体量度39叶中行信息论课件第五章共67页，您现在浏览的是第39页!三、信息率失真函数的定义1.率失真函数问题产生?

对于信息容量为C的信道传输信息传输率为R的信源时，如果R＞C，就必须对信源压缩，使其压缩后信息传输率R’小于信道容量C，但同时要保证压缩所引人的失真不超过预先规定的限度——信息压缩问题就是对于给定的信源，在满足平均失真

的前提下，使信息率尽可能小。40叶中行信息论课件第五章共67页，您现在浏览的是第40页!由于平均互信息I(U;V)是P(x^/

x)的凹函数，所以极小值存在．这个最小值就是在D¯D的条件下，信源必须传输的最小平均信息量．即：R(D)-------信息率失真函数或简称率失真函数。单位是奈特／信源符号或比特／信源符号41叶中行信息论课件第五章共67页，您现在浏览的是第41页!四、信息率失真函数的性质允许失真度D的下限可以是零，即不允许任何失真的情况.1、R(D)的定义域R(D)的定义域为且：当失真矩阵中每行至少一个零元．42叶中行信息论课件第五章共67页，您现在浏览的是第42页!解：[例３]

设试验信道输入符号集，各符号对应概率分别为)={1/3,1/3,1/3}，失真矩阵如下所示，求和以及相应的试验信道的转移概率矩阵。

令对应最小失真度的，其它为“0”，可得对应的试验信道转移概率矩阵为

43叶中行信息论课件第五章共67页，您现在浏览的是第43页!4.1.3率失真函数R(D)性质(续)[计算][例４]离散二元信源，求Dmax[解]44叶中行信息论课件第五章共67页，您现在浏览的是第44页!

４R(D)的值域

①

R(D)min=0

②

R(D)max=R(0)，D=0即无失真传输——熵保持编码(1)对离散信源、无噪信道，R(D)max=H(X)(2)对连续信源，R(D)max→H∞

当且仅当D不小于Dmax45叶中行信息论课件第五章共67页，您现在浏览的是第45页!5.2离散信源率失真函数的计算已知信源的概率分布P(X)和失真函数d(x,x^)，就可求得信源的R(D)函数；原则上它与信道容量一样，即在有约束条件下求极小值的问题．

也就是适当选取试验信道P(x^|x)使平均互信息最小化：其约束条件为：

46叶中行信息论课件第五章共67页，您现在浏览的是第46页!但是，如果要求得到明显的解析表达式，则比较困难，通常只能用参量形式来表达．即便如此，除简单情况外，实际计算仍然是相当困难的．尤其是第三个约束条件，它是求解R(D)函数最主要的障碍．因为应用拉格朗日乘子法解得的一个或某几个P(x^|x)很可能是负的．在这情况下，必须假设某些P(x^|x)=0，然后重新计算，这就使得计算复杂化了．目前，可采用收敛的迭代算法在电子计算机上求解R(D)函数．下面介绍用拉格朗日乘子法求解R(D)函数，并用λ作为参量来表述率失真函数R(D)和失真函数D(λ)：47叶中行信息论课件第五章共67页，您现在浏览的是第47页!求极值，就是求辅助函数一阶导数等于零的方程组的解.即求：所以原则上只需求解式(6)、(3)和(4)的方程组，即可求出I(U;V)在约束条件下的极小值．令代入（6）得到48叶中行信息论课件第五章共67页，您现在浏览的是第48页!解方程组可以求得P(x^).从而，代入（**）式求出β(x),从而将其代入（*）式得到P(x^|x).

49叶中行信息论课件第五章共67页，您现在浏览的是第49页!得到率失真函数和平均失真函数：50叶中行信息论课件第五章共67页，您现在浏览的是第50页!例题

设信源，相应的概率分布为汉明失真求此信源的，并给出其率失真分布．解：利用式子计算范例展示51叶中行信息论课件第五章共67页，您现在浏览的是第51页!解得：利用结果（**），可得52叶中行信息论课件第五章共67页，您现在浏览的是第52页!解得：利用结果（**），可得53叶中行信息论课件第五章共67页，您现在浏览的是第53页!得到率失真函数和平均失真函数：54叶中行信息论课件第五章共67页，您现在浏览的是第54页!2）利用结果（**），可得55叶中行信息论课件第五章共67页，您现在浏览的是第55页!二、二进对称信源的率失真函数它的率失真函数：对应的率失真分布：56叶中行信息论课件第五章共67页，您现在浏览的是第56页!习题：一个四元对称信道接收符号为其失真矩阵为求信源的R(D)函数57叶中行信息论课件第五章共67页，您现在浏览的是第57页!5.3限失真信源编码定理

定理5.3.1(限失真信源编码定理，香农第三极限定理)设R(D)为一离散无记忆信源的率失真函数，并且有有限的失真测度D．对于任意，以及任意长的码长n，一定存在一种信源编码C，其码字个数为使编码后码的平均失真度．58叶中行信息论课件第五章共67页，您现在浏览的是第58页!实际的信源编码(无失真编码或先限失真编码后无失真编码)的最终目标是尽量接近最佳编码，使编码信息传输率接近最大值logr，而同时又保证译码后能无失真地恢复信源的全部信息量H(X)或限失真条件下的必要信息量R(D)．编码后信息传输率的提高使每个编码符号能携带尽可能多的信息量，-----使得传输同样多的信源总信息量所需的码符号数大大减少；------使信道容量C不变的前提下使传输时间大大缩短，从而提高了通信的效率．59叶中行信息论课件第五章共67页，您现在浏览的是第59页!香农信息论三个基本概念——信源熵、信道容量、率失真函数，都是临界值三个极限定理——无失真信源编码定理、限失真信源编码定理、信道编码定理，都是存在性定理60叶中行信息论课件第五章共67页，您现在浏览的是第60页!1.产品未经检验全部出厂p(y1/x1)=p(y1/x2)=1p(y2/x1)=p(y2/x2)=0

[结论]产品未经检验全部出厂引起损失1元信源信道X(生产)(检验)Y平均损失和信息价值61叶中行信息论课件第五章共67页，您现在浏览的是第61页!3.检验完全正确p(y1/x1)=p(y2/x2)=1