信息论第七讲率失真函数概要

2020/1/2014.4率失真函数(RateDistortionFunction)引言上面我们介绍的编码也称为无失真编码（无损编码），另外一类编码称为限失真编码（有损编码）。率失真理论研究的就是在允许一定失真的前提下，对信源的压缩编码。率失真信源编码定理（香农第三定理）指出：率失真函数R(D)就是在给定失真测度条件下，对信源压缩的最低程度。也就是说：为了提高传输效率，可以给定一个失真度，求出在平均失真小于给定值的条件下，信源所能压缩的程度的极限值，即率失真函数R(D)。2020/1/2024.4率失真函数4.4.1失真度与平均失真度(1)符号失真度设单符号离散无记忆信源、信宿及信道为：1212,,,()(),(),,()ninXxxxpxpxpxpx1212,,,()(),(),,()mjmYyyypypypypy112111222212(/)(/)(/)(/)(/)(/)(/)(/)(/)(/)mmnnmnpyxpyxpyxpyxpyxpyxpYXpyxpyxpyxDMCXY2020/1/2034.4率失真函数定义：对每一对(xi,yj)，指定一个非负函数d(xi,yj)≥0i=1,2,…,nj=1,2,…,m称d(xi,yj)为符号失真度(失真函数)。符号失真度表示信源发出一个符号xi，在接收端再现yj所引起的误差或失真。2020/1/2044.4率失真函数(2)平均失真度d(xi,yj)只能表示两个特定的具体符号xi和yj之间的失真。平均失真度：平均失真度为失真度的数学期望。2020/1/2054.4率失真函数(3)平均失真度意义它是在平均意义上，对整个系统失真情况的总体描述。它是信源统计特性p(xi)、信道统计特性p(yj/xi)和失真度d(xi,yj)的函数。当p(xi)，p(yj/xi)和d(xi,yj)给定后，平均失真度就是一个确定的量。如果信源和失真度一定，它就只是信道统计特性的函数。信道不同，平均失真度随之改变。2020/1/2064.4率失真函数(4)失真度描述失真度一般用失真度矩阵来描述。111212122212(,)mmijnnnmdddddddxyddd2020/1/2074.4率失真函数例：汉明（Hamming）失真度X={x1,x2,…,xn}，Y={y1,y2,…,yn}，约定失真度用矩阵表示为式中dij≥0i,j=1,2,…,n为信源方发送符号xi而信宿方判为yj引起的失真度。Kjidjixydxyijijiiii,,2,1,1)(0误码无误码011101110ijd2020/1/2084.4率失真函数例:平方误差失真度X={0,1,2}，Y={0,1,2}，给出失真度dij=(xi-yj)2i,j=0,1,2则失真度矩阵为014101410ijd2020/1/2094.4率失真函数例:绝对误差失真度X={0,1,2}，Y={0,1,2}，给出失真度dij=︱xi-yj︱i,j=0,1,2则失真度矩阵为:012101210ijd2020/1/20104.4.2率失真函数(1)允许失真度D对于单符号离散无记忆信源X、信宿Y及信道P(Y/X)：给定信源X概率分布p(x)和失真度矩阵[d]=[dij]，如果信道转移概率矩阵[P]=[p(Y/X)]满足如下关系，则式中的D则称为允许失真度，关系式称为保真度准则。4.4率失真函数()()ijiijijDpxpyxdD2020/1/20114.4率失真函数(2)率失真函数R(D)我们知道：当信源p(x)一定时，平均交互信息量I(X;Y)是信道转移概率函数p(y/x)的下凸函数。也就是说：平均互信息量I(X;Y)关于p(y/x)存在极小值。定义：平均交互信息量关于信道转移概率的极小值为率失真函数R(D)，即：(/)min;:pyxRDIXYDD2020/1/20124.4率失真函数(/)min;:pyxRDIXYDD(3)率失真函数的含义通过选择合适的信道转移概率p(y/x)（实际上选择某种信道编码方法），在满足一定的失真度要求前提下（平均失真度允许失真度D），使平均交互信息量达到最小值R(D)。率失真函数表明了在满足平均失真度小于D条件下，信源传输信息量（信息速率）可压缩的最低程度。在信源和失真度给定以后，存在满足保真度准则的信道集合，一定有某个信道，使I(X;Y)达到最小。2020/1/20134.4率失真函数(4)率失真函数的定义域R(D)的值域率失真函数的值域为0R（D）H（X）D的最小值Dmin在给定的失真度矩阵中，对每一个xi，找一个最小的dij，然后对所有的i=1,2,…,n求统计平均值，就是D的最小值，即DDmax0DminH（X）R(D)min()minjiijyiDpxd2020/1/20144.4率失真函数D的最大值Dmax当R(D)达到其最小值Rmin（D）=0时，对应的失真最大，这种情况下D对应着R(D)函数定义域的上界值Dmax。maxmin:0min{:(;)0}DDRDDIXYDDmax0DminH（X）R(D)2020/1/20154.4率失真函数(5)率失真函数的性质率失真函数R(D)是D的下凸函数。分别给定两个失真度D1和D2（DminD1,D2Dmax），则下式成立：R(α1D1+α2D2)≤α1R(D1)+α2R(D2)率失真函数R(D)是连续单调函数2020/1/20164.4率失真函数例:求率失真函数已知信源{x1=0，x2=1}，概率分布为（δ，1-δ),δ0.5，信道输出符号Y={y1=0，y2=1}，失真测度为汉明（Hamming）失真测度，求率失真函数R(D)。(1)求出R(D)的定义域Dmin=0·δ+0·(1-δ)=0Dmax=min{1-δ,δ}=δ0110ijdmin()minjiijyiDpxdmaxmin:0min{:(;)0}DDRDDIXY2020/1/2017(2)求出R(D)的值域R(Dmin=0)=H(X)=-δlogδ-(1-δ)log(1-δ)=H(δ)R(Dmax)=R(δ)=0(3)在0Dδ的范围内，计算R(D）根据熵的性质：H(X,Y)H(X)H(X/Y)又由：H(X)＝H()则平均互信息量I(X;Y)＝H(X)-H(X／Y)，得到I(X;Y)＝H(δ)-H(X／Y)4.4率失真函数2020/1/20184.4率失真函数对于汉明失真度，平均失真度为：在R(D)的定义中，要求满足平均失真度小于等于D，取等号则：H(X/Y)≤H(Pe)=H(D)则：I(X;Y)H(δ)-H(D)根据定义:2211(,)(0,1)(1,0)ijijeijDpxydppP0110ijd()min;:()()pyxRDIXYDDHHD(信道误码率）可知：0≤Pe≤D≤δ(Fano不等式）2020/1/20194.4率失真函数Fano不等式设X，Y为离散随机变量，分别取值为:X:(x1,x2,……xn)Y:(y1,y2,……yn)Pe=P{X≠Y}.则:)1log()()/(nPPHYXHee2020/1/20204.4率失真函数(4)求出P(Y/X)找到一个信道转移概率矩阵为[P]的信道，使H(X/Y)=H(D)，且[P]中的每一个元素p(yj︱xi)都满足p(yj︱xi)0i,j=1,2根据[d]的对称性，假设一个反向信道(Y→X)1[(/)]1DDqxyDD由假设的反向信道计算平均失真度，得（满足失真准则）221211(/)()[()()]ijjijijDqxypydpypyDD2020/1/20214.4率失真函数这时计算条件熵（反向信道噪声上）2211/()()log()log(1)log(1)()jijijijHXYpyqxyqxyDDDDHD则平均互信息量I(X;Y)=H(X)-H(X/Y)=H(δ)-H(D)，假设的[q(x/y)]确实在满足失真准则条件下，使I(X;Y)=H(δ)-H(D)从而有()00HHDDRDD2020/1/2022求正向信道转移概率可得:由上面方程组解出，由P(X),P(Y)和P(X/Y)就可以求出相应的P(Y/X).以一个特例说明存在这样的信道转移概率矩阵[P].4.4率失真函数21()(/)()iijjjpxqxypy1212(1)()()1()(1)()DpyDpyDpyDpy1()12DpyD21()12DpyD2020/1/20234.4.3限失真信源编码定理香农第三编码定理设离散无记忆信源的信息率失真函数为R(D)，只要满足RR(D)，当信源序列足够长时，一定存在一种编码方法，其译码失真小于或等于D+ε，其中ε是任意小的正数；反之，若RR(D)，则无论采用什么样的编码方法，其译码失真必大于D。这个定理给出了限失真信源编码的极限。只要允许一定的失真就可以降低熵速率。4.4率失真函数2020/1/20244.4率失真函数率失真函数的理解(Rate+Distortion=Function)信息率失真函数是在满足平均失真不大于D的条件下，信源必须输出的最小信息量。如果信源输出信息速率R小于R(D)，则无论对于什么信道，无法找到编码方法使信宿收到的信息保证失真度要求。如果信源输出信息速率R不小于R(D)，则无论对于什么信道，总可以找到编码方法使信宿收到的信息保证失真度要求。(/)min;:pyxRDIXYDD2020/1/20254.4率失真函数R(D)与C的比较信道容量C表示一个信道的最大传输能力。它反映的是信道本身的特性，与信源无关。或者说信道容量是在最好的参考信源条件下的信道转移概率的函数。不同的信道有不同的信道容量。信息率失真函数R(D)是保真度条件下一个信源的信息速率可以被压缩的最低限度。它反映的是信源本身的特性，与信道无关。或者说信息率失真函数是在最差的参考信道条件下的信源先验概率和D的函数。不同的信源有不同的率失真函数。I(X,Y)P(Y/X)R(D)2020/1/20264.5信源编码综述4.5.1信源编码概述在通信系统模型中，编码的目的就是实现有效、可靠和安全的信息传输、交换、存储和识别。广义地讲，针对三个目的有三大类编码，分别是信源编码、信道编码和保密编码（密码学）。（常存在矛盾）从信息论角度讲，信源编码分为无失真信源编码和限失真信源编码。无失真编码：主要用于离散信源（数字信号）；限失真编码：主要用于连续信源（模拟信号）；信源编码的主要性能指标是编码效率，它的本质就是理论码率和实际码率的比。2020/1/20274.5信源编码综述无失真编码也称为可逆编码（信源符号经过编码后，可以从编码中无失真地恢复信源符号）。已知符号概率即可计算信源熵H，就可以使平均码长任意接近H。编码的方法的基本思想就是概率与码长的匹配。对于符号概率不可知，或者非平稳，或长相关信源无法应用。限失真编码也称为不可逆编码（连续信源编码后无法无失真的恢复）。根据率失真理论进行限失真编码；在失真小于D的条件下码率可以压缩到R(D)，但是定理没有给出实现途径。现有的方法就是最佳量化问题，标量量化不行，需要矢量量化（多个符号合成一个矢量再编码）。有记忆信源的熵小，去掉相关性可以降低码率，解决的方法就是预测编码和变换编码。2020/1/20284.5信源编码综述4.5.2信源编码方法无失真信源编码可逆编码，无损编码