信息论第七讲率失真函数

4.4率失真函数(RateDistortionFunction)引言上面我们介绍的编码也称为无失真编码（无损编码），另外一类编码称为限失真编码（有损编码）。率失真理论研究的就是在允许一定失真的前提下，对信源的压缩编码。率失真信源编码定理（香农第三定理）指出：率失真函数R(D)就是在给定失真测度条件下，对信源压缩的最低程度。也就是说：为了提高传输效率，可以给定一个失真度，求出在平均失真小于给定值的条件下，信源所能压缩的程度的极限值，即率失真函数R(D)。2/3/202314.4率失真函数4.4.1失真度与平均失真度(1)符号失真度设单符号离散无记忆信源、信宿及信道为：DMCXY2/3/202324.4率失真函数定义：对每一对(xi,yj)，指定一个非负函数

d(xi,yj)≥0

i=1,2,…,n

j=1,2,…,m称d(xi,yj)为符号失真度(失真函数)。符号失真度表示信源发出一个符号xi，在接收端再现yj

所引起的误差或失真。2/3/202334.4率失真函数(2)平均失真度d(xi,yj)只能表示两个特定的具体符号xi和yj之间的失真。平均失真度：平均失真度为失真度的数学期望。2/3/202344.4率失真函数(3)平均失真度意义它是在平均意义上，对整个系统失真情况的总体描述。它是信源统计特性p(xi)、信道统计特性p(yj/xi)和失真度d(xi,yj)的函数。当p(xi)，p(yj/xi)和d(xi,yj)给定后，平均失真度就是一个确定的量。如果信源和失真度一定，它就只是信道统计特性的函数。信道不同，平均失真度随之改变。2/3/202354.4率失真函数(4)失真度描述失真度一般用失真度矩阵来描述。2/3/202364.4率失真函数例：汉明（Hamming）失真度X={x1,x2,…,xn}，Y={y1,y2,…,yn}，约定失真度用矩阵表示为式中dij≥0i,j=1,2,…,n为信源方发送符号xi而信宿方判为yj引起的失真度。2/3/202374.4率失真函数例:平方误差失真度X={0,1,2}，Y={0,1,2}

，给出失真度dij=(xi-yj)2

i,j=0,1,2则失真度矩阵为

2/3/202384.4率失真函数例:绝对误差失真度X={0,1,2}，Y={0,1,2}

，给出失真度dij=︱xi-yj︱

i,j=0,1,2则失真度矩阵为:

2/3/202394.4.2率失真函数(1)允许失真度D对于单符号离散无记忆信源X、信宿Y及信道P(Y/X)：给定信源X概率分布p(x)和失真度矩阵[d]=[dij]，如果信道转移概率矩阵[P]=[p(Y/X)]满足如下关系，则式中的D则称为允许失真度，关系式称为保真度准则。4.4率失真函数2/3/2023104.4率失真函数(2)率失真函数R(D)我们知道：当信源p(x)一定时，平均交互信息量I(X;Y)是信道转移概率函数p(y/x)的下凸函数。也就是说：平均互信息量I(X;Y)关于p(y/x)存在极小值。定义：平均交互信息量关于信道转移概率的极小值为率失真函数R(D)，即：2/3/2023114.4率失真函数(3)率失真函数的含义通过选择合适的信道转移概率p(y/x)（实际上选择某种信道编码方法），在满足一定的失真度要求前提下（平均失真度<允许失真度D），使平均交互信息量达到最小值R(D)。率失真函数表明了在满足平均失真度小于D条件下，信源传输信息量（信息速率）可压缩的最低程度。在信源和失真度给定以后，存在满足保真度准则的信道集合，一定有某个信道，使I(X;Y)达到最小。2/3/2023124.4率失真函数(4)率失真函数的定义域R(D)的值域率失真函数的值域为0

R（D）

H（X）D的最小值Dmin在给定的失真度矩阵中，对每一个xi，找一个最小的dij，然后对所有的i=1,2,…,n求统计平均值，就是D的最小值，即DDmax0DminH（X）R(D)2/3/2023134.4率失真函数D的最大值Dmax当R(D)达到其最小值Rmin（D）=0时，对应的失真最大，这种情况下D对应着R(D)函数定义域的上界值Dmax。DDmax0DminH（X）R(D)2/3/2023144.4率失真函数(5)率失真函数的性质率失真函数R(D)是D的下凸函数。分别给定两个失真度D1和D2（Dmin

D1,D2

Dmax），则下式成立：

R(α1D1+α2D2)≤α1R(D1)+α2

R(D2)率失真函数R(D)是连续单调函数2/3/2023154.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-δ,δ}=δ

2/3/202316(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率失真函数2/3/2023174.4率失真函数对于汉明失真度，平均失真度为：在R(D)的定义中，要求满足平均失真度小于等于D，取等号则：

H(X/Y)≤H(Pe)=H(D)则：I(X;Y)

H(δ)-H(D)

根据定义:(信道误码率）可知：0≤Pe≤D≤δ(Fano不等式）2/3/2023184.4率失真函数Fano不等式设X，Y为离散随机变量，分别取值为:X:(x1,x2,……xn)Y:(y1,y2,……yn)Pe=P{X≠Y}.则:2/3/2023194.4率失真函数(4)求出P(Y/X)找到一个信道转移概率矩阵为[P]的信道，使H(X/Y)=H(D)，且[P]中的每一个元素p(yj︱xi)都满足p(yj︱xi)0

i,j=1,2根据[d]的对称性，假设一个反向信道(Y→X)由假设的反向信道计算平均失真度，得（满足失真准则）2/3/2023204.4率失真函数这时计算条件熵（反向信道噪声上）则平均互信息量I(X;Y)=H(X)-H(X/Y)=H(δ)-H(D)，假设的[q(x/y)]确实在满足失真准则条件下，使

I(X;Y)=H(δ)-H(D)从而有

2/3/202321求正向信道转移概率可得:由上面方程组解出，由P(X),P(Y)和P(X/Y)就可以求出相应的P(Y/X).以一个特例说明存在这样的信道转移概率矩阵[P].4.4率失真函数2/3/2023224.4.3限失真信源编码定理香农第三编码定理设离散无记忆信源的信息率失真函数为R(D)，只要满足R>R(D)，当信源序列足够长时，一定存在一种编码方法，其译码失真小于或等于D+ε，其中ε是任意小的正数；反之，若R<R(D)，则无论采用什么样的编码方法，其译码失真必大于D。这个定理给出了限失真信源编码的极限。只要允许一定的失真就可以降低熵速率。4.4率失真函数2/3/2023234.4率失真函数率失真函数的理解(Rate+Distortion=Function)信息率失真函数是在满足平均失真不大于D的条件下，信源必须输出的最小信息量。如果信源输出信息速率R小于R(D)，则无论对于什么信道，无法找到编码方法使信宿收到的信息保证失真度要求。如果信源输出信息速率R不小于R(D)，则无论对于什么信道，总可以找到编码方法使信宿收到的信息保证失真度要求。2/3/2023244.4率失真函数R(D)与C的比较信道容量C表示一个信道的最大传输能力。它反映的是信道本身的特性，与信源无关。或者说信道容量是在最好的参考信源条件下的信道转移概率的函数。不同的信道有不同的信道容量。信息率失真函数R(D)是保真度条件下一个信源的信息速率可以被压缩的最低限度。它反映的是信源本身的特性，与信道无关。或者说信息率失真函数是在最差的参考信道条件下的信源先验概率和D的函数。不同的信源有不同的率失真函数。I(X,Y)P(Y/X)R(D)2/3/2023254.5信源编码综述4.5.1信源编码概述在通信系统模型中，编码的目的就是实现有效、可靠和安全的信息传输、交换、存储和识别。广义地讲，针对三个目的有三大类编码，分别是信源编码、信道编码和保密编码（密码学）。（常存在矛盾）从信息论角度讲，信源编码分为无失真信源编码和限失真信源编码。无失真编码：主要用于离散信源（数字信号）；限失真编码：主要用于连续信源（模拟信号）；信源编码的主要性能指标是编码效率，它的本质就是理论码率和实际码率的比。2/3/2023264.5信源编码综述无失真编码也称为可逆编码（信源符号经过编码后，可以从编码中无失真地恢复信源符号）。已知符号概率即可计算信源熵H，就可以使平均码长任意接近H。编码的方法的基本思想就是概率与码长的匹配。对于符号概率不可知，或者非平稳，或长相关信源无法应用。限失真编码也称为不可逆编码（连续信源编码后无法无失真的恢复）。根据率失真理论进行限失真编码；在失真小于D的条件下码率可以压缩到R(D)，但是定理没有给出实现途径。现有的方法就是最佳量化问题，标量量化不行，需要矢量量化（多个符号合成一个矢量再编码）。有记忆信源的熵小，去掉相关性可以降低码率，解决的方法就是预测编码和变换编码。2/3/2023274.5信源编码综述4.5.2信源编码方法无失真信源编码可逆编码，无损编码、熵编码(EntropyCoding）Huffman编码，算术编码，游程编码，LZW编码等。限失真信源编码不可逆编码，有损编码、源编码(SourceCoding

）预测编码：利用过去和当前的数据对在时间或空间上将来的数据进行预测，从而达到压缩的目的，如DM、ADPCM。变换编码：利用数学变换方法，将原时域或空域的数据变换到频率域或其它域，利用数据在变换域中的冗余或人类感觉的冗余特征实现的压缩，如DCT、DWT。分层编码：将原数据在时空域或频域上分成若干子区域，利用人类感觉的特征进行压缩编码，然后再合并，如子带编码其他编码：如矢量量化、运动补偿、音感编码。2/3/2023284.5信源编码综述混合编码方法(HybridCoding)熵编码+源编码大多数压缩标准都采用混合编码的方法，一般是先利用源编码进行有损压缩，再利用熵编码做进一步的无损压缩。如H.26X、JPEG、MPEG等。2/3/2023294.5信源编码综述4.5.3信源编码与数据压缩技术以山农信源编码为基础，结合信号处理和多媒体通信技术的发展，逐步形成了系统的数据压缩技术。信源数据压缩的基本条件是信源消息符号原始存在的状态冗余。1）信源数据中存在或多或少的冗余，这种冗余既存在信源本身的相关性中，也存在于信源概率分布的不均匀中；如空间冗余、时间冗余、结构冗余、知识冗余及纹理统计冗余；2）对于图像、音频和视频等特殊信源，人的感知可容忍某些细节信息的丢失（失真）（感知冗余）。2/3/2023304.5信源编码综述4.5.4算术编码(arithmeticcoding)算术编码引出：算术编码和Huffman编码一样，也是一种熵编码，无失真编码。Huffman编码是建立了一种原始信源符号Si与信道码字Wi的一一对应的映射关系。因此也称为块码(Block)，或者分组码(Group)。Huffman编码的不足：不太适合二进制信源；符号相关性没有充分考虑；码长必须为整数位，码长与符号概率匹配性不是太好。2/3/2023314.5信源编码综述算术编码思想：针对序列进行编码，建立递推关系。不用二整数代码来表示符号，而改用[0，1)半开区间中实数的二元小数序列来表示。[0，1)可以分为n个子区间，每个宽度值等于一个符号的先验概率，符号表中的所有符号刚好布满整个[0，1)区间（概率和为1）。编码过程就是把输入符号串（数据流）映射成[0，1)区间中对应子区间中的一个实数值。2/3/2023324.5信源编码综述算术编码在图像数据压缩标准(如JPEG，JBIG)中扮演了重要的角色。在算术编码中，消息用0到1之间的实数进行编码。算术编码用到两个基本的参数：符号概率和它的编码间隔。编码效率取决于符号概率和编码间隔，编码间隔取决于符号概率和符号相关性，而这些间隔包含在0到1之间。2/3/2023334.5信源编码综述编码举例

假设信源符号为{00,01,10,11}，这些符号的先验概率分别为{0.1,0.4,0.2,0.3}，根据这些先验概率可把间隔[0,1)分成4个子间隔：[0,0.1),[0.1,0.5),[0.5,0.7),[0.7,1)，二进制序列的输入为：10001100101101。2/3/2023344.5信源编码综述2/3/2023354.5信源编码综述算术编码是一种二元码的编码方法。在不考虑信源统计的情况下，不管统计是平稳的或非平稳的，编码的码率总能趋近于信源熵，每次迭代时的编码算法只处理一个数据符号，并且只有算术运算。随着被编码数据流符号的输入，子区间宽度逐渐缩小。表示为数值精度逐渐提高，二进制代码逐渐加长。2/3/2023364.5信源编码综述新子区间的起始位置=前子区间的起始位置+当前符号的区间左端×前子区间长度；0.5=0.5+0X0.2;0.514=0.5+0.7X0.022/3/2023374.5信源编码综述新子区间的长度=前子区间的长度×当前符号的概率（等价于范围长度）；0.02=0.2X0.1;0.0006=0.006X0.12/3/2023384.5信源编码综述最后得到的子区间的长度(一个小数）决定了表示该区域内的某一个数所需的位数。算术编码在编、译码的过程中，子区间的起始位置和长度值的小数点后的位数越来越长，实际中无法实现。因此较实用的改进算法是限制小数点后的位数。2/3/2023394.5信源编码综述例如：已知信源X=(0,1);(0.25,0.75)试对1011进行算术编码.0.01.00.2510110.251.00.250.43750.2968750.43750.332031250.4375输出2/3/2023404.5信源编码综述最后的子区间起始位置C＝（0.332