信息论第四章 信息率失真函数(1)

1、第第2 2章：信源熵章：信源熵第第3 3章：信道容量章：信道容量第第4 4章：信息率失真函数章：信息率失真函数第第5 5章：信源编码章：信源编码第第6 6章：信道编码章：信道编码第第7 7章：密码体制的安全性测度章：密码体制的安全性测度4.1 4.1 信息率失真函数信息率失真函数4.2 离散信源的信息率失真函数离散信源的信息率失真函数4.3 连续信息的率失真函数连续信息的率失真函数4.4 保真度准则下的信源编码定理保真度准则下的信源编码定理第四章信息率失真函数基本概念在前面几章的讨论中，其基本出发点都是如何保证信息的无失真传输。但在许多实际应用中，人们并不要求完全无失真地恢复消息，而是只要满足

2、一定的条件，近似地恢复信源发出的消息就可以了。然而，什么是允许的失真？如何对失真进行描述？信源输出信息率被压缩的最大程度是多少？信息率失真理论回答了这些问题，其中香农的限失真编码定理定量地描述了失真，研究了信息率与失真的关系，论述了在限失真范围内的信源编码问题，已成为量化、数据转换、频带压缩和数据压缩等现代通信技术的理论基础。第四章信息率失真函数(1) “消息完全无失真传送”的可实现性信道编码定理：无论何种信道，只要信息率R小于信道容量C，总能找到一种编码，使在信道上能以任意小的错误概率和任意接近于C的传输率来传送信息。反之，若RC，则传输总要失真。完全无失真传送不可实现：实际的信源常常是连续

3、的，信息率无限大，要无失真传送要求信息率R为无穷大；实际信道带宽是有限的，所以信道容量受限制。要想无失真传输，所需的信息率大大超过信道容量RC。4.1.1 引言4.1基本概念第四章信息率失真函数技术发展的需要随着科学技术的发展，数字系统应用得越来越广泛，这就需要传送、存储和处理大量的数据。为了提高传输和处理效率，往往需要对数据压缩，这样也会带来一定的信息损失。人类社会已进入信息时代，信息爆炸的结果要求人们解决如何对浩如烟海的数据有效的压缩，减少数据的存储容量(如各种数据库、电子出版物、多媒体娱乐)、传输时间(如数据通信和遥测)、或占有带宽(如多媒体通信、数字音频广播、高清晰度电视)，要想方设法

4、压缩给定消息 集合占用的空间域、时间域和频率域资源。如海洋地球物理勘探遥测数据，用60路传感器，每路信号1KHz，16位A/D量化，每航测1Km就需记录1盘0.5英寸的磁带，一条测量船每年就可勘测15000Km，数据流之大可见一斑。4.1 (2) 实际中允许一定程度的失真基本概念4.1.1 引言第四章信息率失真函数实际生活中的需要实际生活中，人们一般并不要求获得完全无失真的消息，通常只要求近似地再现原始消息，即允许一定的失真存在。例如打电话：即使语音信号有一些失真，接电话的人也能听懂。人耳接收信号的带宽和分辨率是有限的。放电影：理论上需要无穷多幅静态画面，由于人眼的“视觉暂留性”，实际上只要每

5、秒放映24幅静态画面。有些失真没有必要完全消除。4.1基本概念4.1.1 引言实际通信系统允许一定的失真存在。1打电话；2放电影，视觉暂留性。允许压缩信源输出的信息率。研究内容：信息率 允许失真第四章信息率失真函数(3) 信息率失真理论信息率失真函数香农定义了信息率失真函数R(D)。定理指出：在允许一定失真度D的情况下，信源输出的信息率可压缩到R(D)。信息率失真理论是量化（模数转换）、数模转换、频带压缩和数据压缩的理论基础。4.1.1 引言4.1基本概念第四章信息率失真函数信息率失真函数极小值问题I(X;Y)是P(X)和P(Y/X)的二元函数；在讨论信道容量时：规定了P(Y/X) ， I(X

6、;Y)变成了P(X)的函数。在离散情况下，因为I(X;Y)对p(ai)是上凸函数，所以变更p(ai)所求极值一定是I(X;Y)的极大值；在连续情况下，变更信源P(X)求出的也是极大值，但求极值时还要一些其它的限制条件。在讨论信息率时可规定：p(xi) ，变更p(yj /xi)来求平均互信息的极值，称为信道容量对偶问题。由于I(X;Y)是p(bj /ai)的下凸函数，所求的极值一定是极小值。但若X和Y相互统计独立(p(bj /ai)=p(bj )，这个极小值就是0，因为I(X;Y)是非负的，0必为极小值，这样求极小值就没意义了。引入一个失真函数，计算在失真度一定的情况下信息率的极小值就变得有意义

7、了。4.1基本概念4.1.1 引言4.1.1 信息率失真函数和平均失真度信息率失真函数和平均失真度4.1.2 信息率失真函数定义信息率失真函数定义4.1 .3 信息率失真函数性质信息率失真函数性质第四章信息率失真函数4.1.1 失真度与平均失真度(1) 信息率与失真的关系(2) 失真度(3) 常用的失真函数(4) 平均失真度(5) N次扩展信道的平均失真度4.1基本概念第四章信息率失真函数(1) 信息率与失真的关信道中固有的噪声和不可避免的干扰，使信源的消息通过信道传输后造成误差和失真误差或失真越大，接收者收到消息后对信源存在的不确定性就越大，获得的信息量就越小，信道传输消息所需的信息率也越小

8、。4.1.1 失真度与平均失真度4.1基本概念第四章信息率失真函数4.1.1 失真度与平均失真度(2) 失真度失真度设离散无记忆信源为信源符号通过信道传送到接收端Y4.1基本概念信道的传递概率矩阵1212 , , , , ( )( ), (), ( ), ()ininaaaaXP Xp ap ap ap a1212 , , , , Y(Y)( ), (), ( ), ()jmimbbbbPp bp bp bp b112111222212,(/),mmnnmnp b ap bap bap b ap bap baP YXp b ap bap ba第四章信息率失真函数4.1.1 失真度与平均失真度对

9、每一对(ai,bj)，指定一个非负函数d(ai,bj)0i=1,2,nj=1,2,m称d(ai,bj)为单个符号的失真度/失真函数。表示信源发出一个符号ai，在接收端再现bj所引起的误差或失真。4.1基本概念第四章信息率失真函数4.1.1 失真度与平均失真度称D为失真矩阵。它是nm阶矩阵。连续信源和连续信道的失真函数在连续信源和连续信道情况下，失真度定义为d(x,y)0失真矩阵失真度还可表示成矩阵的形式4.1基本概念111212122212(,)(,).(,)(,)(,).(,).(,)(,).(,)mmnnnmd a bd a bd a bd abd abd abDd abd abd ab第

10、四章信息率失真函数4.1.1 失真度与平均失真度当i=j时，X与Y的取值一样，用Y来代表X就没有误差，所以定义失真度为0；当ij时，用Y代表X就有误差。这种定义认为对所有不同的i和j引起的误差都一样，所以定义失真度常数a。失真矩阵的特点是对角线上的元素均为0，对角线以外的其它元素都为常数a。(3) 常用的失真函数第一种4.1基本概念0(,)ijijd abaij0.0.0aaaaDaa第四章信息率失真函数4.1.1 失真度与平均失真度第二种：d(ai,bj)=(bjai)2这种函数称为平方误差失真函数，失真矩阵称为平方误差失真矩阵。若信源符号代表输出信号的幅度值，则较大的幅度失真比较小的幅度失

11、真引起的错误更为严重，严重程度用平方表示。失真函数是根据人们的实际需要和失真引起的损失、风险、主观感觉上的差别大小等因素人为规定的。4.1基本概念当a=1时的失真函数称为汉明失真函数10(,)1ijijd abij01.110.1.11.0D平均失真度平均失真度第四章信息率失真函数4.1.1 失真度与平均失真度(4) 平均失真度平均失真度定义d(ai,bj)只能表示两个特定的具体符号ai和bj之间的失真。平均失真度：平均失真度为失真度的数学期望，4.1基本概念即，d ( ai , bj )在X和Y的联合概率空间P( XY )中的统计平均值D Ed (ai , bj )由数学期望的定义11 (,

12、)()(/) (,)nmijijiijijDE d a bp ap bad a b 第四章信息率失真函数4.1.1 失真度与平均失真度平均失真度意义4.1基本概念D 是在平均意义上，从总体上对整个系统失真情况的描述。它是信源统计特性p(ai) 、信道统计特性p(bj/ai )和失真度d(ai,bj)的函数 。当p(ai)，p(bj/ai )和d(ai,bj)给定后，平均失真度就不是一个随机变量了，而是一个确定的量。如果信源和失真度一定， D 就只是信道统计特性的函数。信道传递概率不同，平均失真度随之改变。保真度准则人们所允许的失真指的都是平均意义上的失真。保真度准则：规定平均失真度 D 不能超

13、过某一限定的值D，即 D D，则D就是允许失真的上界。该式称为保真度准则。第四章信息率失真函数4.1.1 失真度与平均失真度信道的输出共有mN个不同的符号4.1基本概念(5) N 次扩展信道的平均失真度N次扩展单符号离散无记忆信源X a1,a2,an的N次扩展信源XN=X1X2XN ，在信道中的传递作用相当于单符号离散无记忆信道的N次扩展信道，输出也是一个随机变量序列YN=Y1Y2YN 。此时输入共有nN个不同的符号121212N12, ,=1,2,i=1,2,NNiiiiiiinNa aaa aaa aai iinn，1212j12N12,=1,2,i=1,2,NNiiiiiimNb bbb

14、 bbb bbj jjmm，第四章信息率失真函数4.1.1 失真度与平均失真度定义离散无记忆信道X P(Y/X) Y的N次扩展信道的输入序列ai和输出序列bj之间的失真函数为上式说明：离散无记忆信道的N次扩展信道输入输出之间的失真，等于输入序列ai中N个信源符号 各自通过信道X P(Y/X) Y ，分别输出对应的N个信宿符号yj1,yj2,yjN后所引起的N个单符号失真d(aik ,bjk)(k=1,2, ,N)之和。4.1基本概念121211221(,)(,=d(,)d(,)d(,)(,)NNNNkkijiiijjjijijijNijkdda aab bba ba babd a b ，12N

15、iiia aa第四章信息率失真函数N次扩展的失真度定义N次离散无记忆扩展信源和信道的平均失真度为 D(N) ，则4.1.1 失真度与平均失真度4.1基本概念11() (/) (,)NNnmijiijijDppd 第四章信息率失真函数“N次扩展”与“单符号”平均失真度的关系由扩展信源和扩展信道的无记忆性有4.1.1 失真度与平均失真度4.1基本概念1()()kNiikpp a1(/)(/)1,2,j1,2,mkkNNNjijikpp bain，1111N1N11111222221122N11nmi1i1 j1j11i1 j1i1 j1j()(/)(,)=()()(/)(/)(,)() (/)(,

16、)() (/)(,)()NNNNNkkNnmijiijijnmNiijijiijknmnmijiijijiijiDppdp ap ap bap bad abp ap bad abp ap bad abp a Ni11121(/)(,)NNNNnmjiijNNkkp bad abDDDD ii1111()1(/)1() (/) (,)NNkkkkknnnmjiijiijjijp ap baDppd 其中第四章信息率失真函数上式说明：离 散 无 记 忆N次 扩 展 信 源 通 过 离 散 无 记 忆N次 扩 展 信 道 的 平 均 失 真 度 是 单 符 号 信 源 通 过 单 符 号信道的平均失

17、真度的N倍。实际上， D k (k=1,2, ,N)是同一信源X在N个不同时刻通过同一信道X P(Y/X) Y所造成的平均失真度，因此都等于单符号信源X通过信道X P(Y/X) Y所造成的平均失真度，即因此4.1.1 失真度与平均失真度4.1基本概念11() (/) (,)NNnmkijiijijDDppd ()D NND第四章信息率失真函数N次扩展的保真度准则离散无记忆N次扩展信源通过离散无记忆N次扩展信道的保真度准则为D( N ) ND4.1.1 失真度与平均失真度4.1基本概念4.1.1失真函数和平均失真度失真函数和平均失真度4.1.2 信息率失真函数定义信息率失真函数定义4.1.3 率

18、失真函数性质率失真函数性质naaax,21信源编码器信源编码器mbbby,21XY假想信道假想信道将信源编码器看作信道将信源编码器看作信道DD DD D失真许可的 试验信道试验信道: )/(DDabpPijD称)/(ijabp调整 使第四章信息率失真函数4.1.2 信息率失真函数的定义N次扩展的试验信道对于离散无记忆信源的N次扩展信源和离散无记忆信道4.1基本概念(1) 试验信道单符号信源和单符号信道的试验信道当固定信源（ P(X)已知），单个符号失真度也给定时，选择信道使 D D 。凡满足要求的信道称为D失 真 许 可 的 试 验信道，简称试验信道。所有试验信道构成的集合用PD来表示，即PD

19、 p( b j / ai ) : D D i 1,2, , n, j 1,2, , m, m N的N次扩展信道，其试验信道集合PD(N)为PD ( N ) p(b j / ai ) : D( N ) ND; i 1,2, , n N , j 1,2,i);(min)()/(YXIDRDijPabpR(D) min I ( X ;Y)第四章信息率失真函数(2) 信息率失真函数单符号信源和单符号信道的信息率失真函数试验信道集合，平均互信息I(X;Y)是信道传递概率p(bj /ai)的下凸函数，所以在PD中一定可以找到某个试验信道，使I(X;Y)达到最小，即p( y j / xi )PD4.1.2

20、信息率失真函数的定义4.1基本概念这个最小值R(D)称为信息率失真函数，简称率失真函数。在信源给定以后，总希望在允许一定失真的情况下，传送信源所必须的信息率越小越好。从接收端来看，就是在满足保真度准则 D D 的条件下，寻找再现信源消息必须的最低平均信息量，即平均互信息的最小值。在信源和失真度给定以后，PD是满足保真度准则 D D 的第四章信息率失真函数信息率失真函数的示意图4.1.2 信息率失真函数的定义第四章信息率失真函数信息率失真函数的物理意义信息率失真函数是在 D D 的前提下，信宿必须获得的平均信息量的最小值，是信源必须输出的最小信息率。信息传输速率本质上是描述信源特性的，因此R(D

21、)也应该是仅仅用于描述信源。若信源消息经无失真编码后的信息传输速率为R，则在保真度准则下信源编码输出的信息率就是R(D)，且R(D) Dmax时，从数学意义上讲，因为R(D)是非负函数，所以它仍只能等于0。这相当于输入X和输出Y统计独立。意味着在接收端收不到信源发送的任何信息，与信 源 不发送任何信息等效。或者说传送信源符号的信息率可以压缩至0。4.1基本概念第四章信息率失真函数4.1.3 信息率失真函数的性质计算Dmax的值令试验信道特性 p(bj /ai)= p(bj) (i=1,2,n) 这时X和Y相互独立，等效于通信中断，因此I(X;Y) =0，即R(D)=0。满足上式的试验信道有许多

22、，相应地可求出许多平均失真值，从中选取最小的一个，就是这类平均失真值的下界Dmax 。上式是用不同的概率分布p(yj)对Dj求数学期望，取数学期望当中最小的一个作为Dmax 。4.1基本概念max()()1111min( ) () ( ,)min()( ) ( ,)jjnmmnijijjiijp bp bijjiDp a p b d a bp bp a d a b1() (,)njiijiDp a d a b令max()1= min()jmjjp bjDp bD第四章信息率失真函数4.1.3 信息率失真函数的性质实际是用p(bj)对Dj进行线性分配，使线性分配的结果最小。当p(ai)和d(ai

23、 , bj)给定时，必可计算出Dj ，Dj随j的变化而变化，p(bj)是任选的，只需满足非负性和归一性。若Ds是所有Dj当中最小的一个，可取p(bs)=1 ，其它p(bj)为0，这时Dj的线性分配（数学期望）必然最小，即4.1基本概念max()()1111min( ) ( ) ( ,)min( )( ) ( ,)jjnmmnijijjiijp bp bijjiDp a p b d a bp bp a d a b1() (,)njiijiDp a d a b令max()1= min()jmjjp bjDp bDjmax121p(b )0 jmin(,)mjssDD DD，线性分配a1a21021

24、)1 (aammnmnnDDDbadbadbadbadbadbad.211221111),(.),(.),(.),(),(.),(假定所有Dj中，Ds最小，令sjsjbpj01)(jjDDminmax第四章信息率失真函数4.1.3 信息率失真函数的性质4.1基本概念例4.1.1 二元信源第四章信息率失真函数4.1.3 信息率失真函数的性质，相应的失真矩阵，先计算Dj ：D10.4D2=0.6所以Dmax=min(D1 , D2)=0.4计算Dmax 。4.1基本概念120.4 0.6aa001() (,)njiijiDp ad a b第四章信息率失真函数4.1.3 信息率失真函数的性质结 论R

25、(D)的定义域为(Dmin, Dmax)；一般情况下Dmin =0， R(Dmin)=H(X)；当DDmax时，R(D)=0；当DminDDmax时， 0R(D)H(X)。4.1基本概念第四章信息率失真函数4.1.3 信息率失真函数的性质(2) 率失真函数对允许平均失真度的下凸性对任一01和任意平均失真度D1，D2Dmax，有RD1 +(1) D2R(D1)+(1)R(D2)(3) 率失真函数的单调递减和连续型由于函数R(D)具有凸状性，保证了它在定义域内是连续的。在DminDDmax时：在D=Dmax处，除某些特例外，S将从某一个负值跳到0，S在此点不连续。在D的定义域0,Dmax内，除某些

26、特例外，S将是D的连续函数。4.2离散信源的信息率失真函数4.2.1离散信源信息率失真函数离散信源信息率失真函数的参量表达式的参量表达式11)(),(1jibaSdniiieapi),(1)(1jibaSdmjjiebp)(jbp),()()(jibaSdijijebpabpnimjbaSdjiijijiebadbpapSD11),(),()()()(iniiapSSDSRln)()()(1)(ijabp验证 是否大于等于零)(ijabp23456),()(minmin1maxjiniijjjbadapDD70,00D21,1)( 21pppaaXPXjjDDminmaxnijiij,bada

27、pD1)()(,)11()ijnSd a biiip a e )1 (1pDpD 2pDD2max1)1 (21sepp1)1 (21ppeS)1 (11Sep)1)(1 (12SepijijmjbaSdebp1)(1),()1 ()()(21SSepebpbp)1)(1 ()()(21SSepbpebpSSeeppbp1)1 ()(1SSepepbp1)1 ()(2),()()/(jijiijbaSdebpabp)1 ()1 ()/(211SSepeppabp)1)(1 ()1 ()/(212SSepeppabp)1 ()1 ()/(221SSeppepabp)1)(1 ()1 ()/(22

28、2SSeppepabpnimjjbiaSdjijiiebadbpapSD11),(),()()()(SSee1)1ln()1 ()1ln(ln1 ln)()()(1ppeppeeSapSSDSRSSSniii)1ln()1 (ln )1ln()1ln(ln)(ppppDDDDDDR/1/ln21DDS容忍失真允许压缩的信息率)()(DHpH15 . 02maxDS(D)DD0.50.25P=0.25P=0.5()R D第四章信息率失真函数(2) 信息率失真函数曲线图说明若=1，把d(ai , bj)当成了误码个数，即X和Y不一致时，认为误了一个码元，所以d(ai , bj)的数学期望就是平均误码率。能容忍的失真等效于能容忍的误码率。4.2.2二元及等概率离散信源的信息率失真函数4.2离散信源的信息率失真函数第四章信息率失真函数R(D)不仅与D有关，还与p有关。概率分布不同， R(D)曲线就不一样。当p=0.