本_信息论及编码A_第5章有失真信源编码

1、1第第5章章 有失真信源编码有失真信源编码信息论与编码 Information and Coding Theory 2第第5 5章章 有失真信源编码有失真信源编码5.1 5.1 信息率失真函数信息率失真函数5.2 5.2 信息率失真函数的性质信息率失真函数的性质5.3 5.3 限失真信源编码定理限失真信源编码定理35.1 5.1 信息率失真函数信息率失真函数l 编码器输入编码器输入X：xi a1, a2,an.l 编码器输出编码器输出Y：yj b1, b2,bm.u无失真无失真: xi=yju有失真有失真: xiyjl 失真函数失真函数d(xi,yj)0,( ,)0,ijijijxyd x y

2、xy45.1 5.1 信息率失真函数信息率失真函数l 失真矩阵失真矩阵111212122212(,)(,)(,)(,)(,)(,)(,)(,)(,)mmnnnmd abd abd abd abd abd abdd abd abd ab55.1 5.1 信息率失真函数信息率失真函数l 例例5.1.1. 设信源符号X0,1, 编码器输出符号Y0,1,2, 规定失真函数为 d(0,0 )= d(1,1)=0 d(0,1 )= d(1,0)=1 d(0,2 )= d(1,2)=0.5则失真矩阵为0 1 0.5.1 0 0.5d65.1 5.1 信息率失真函数信息率失真函数l 均方失真：均方失真：l 绝

3、对失真：绝对失真： l 相对失真：相对失真： l 误码失真误码失真（适用于离散信源）：2,)()ijijd x yxy（适用于连续信源适用于连续信源,) |ijijd x yxy（,)| |ijijid x yxyx（0,(,)(,)1,ijijijijxyd x yx yxy75.1 5.1 信息率失真函数信息率失真函数l 平均失真：平均失真：l 平均失真平均失真 是对给定信源分布是对给定信源分布p(xi) 经过某一转移概率分布经过某一转移概率分布为为p(yj |xi) 的有失真信源编码器后产生失真的总体量度。的有失真信源编码器后产生失真的总体量度。1111( ( ,)( ,) ( ,)(

4、) (|) ( ,)nmijijijijnmijiijijDE d x yp x y d x yp x p yx d x y85.1 5.1 信息率失真函数信息率失真函数l 序列编码的失真序列编码的失真u输入：输入：X=(X1, X2,XL)，样值为，样值为: x=(x1, x2, xL)u输出：输出：Y=(Y1, Y2,YL)，样值为，样值为: y=(y1, y2, yL)u失真函数定义为：失真函数定义为：11( , )( ,).LLllldx yd x yLu序列编码的平均失真：序列编码的平均失真：11 = (,).LLlllDE d x yL95.1 5.1 信息率失真函数信息率失真函数

5、l 有失真信源编码器模型有失真信源编码器模型u信源编码目的信源编码目的 寻找一种编码方案，使编码后所需的信息传输率R尽量小。u问题问题 R越小，引起的平均失真就越大。u解决方法解决方法 给出一个失真限制值失真限制值D,在满足平均失真小于D的条件下，寻找一种编码案使得信息率R最小.DD105.1 5.1 信息率失真函数信息率失真函数信源编码器 有干扰的假想信道 信息传输率R I(X;Y)l 有失真信源编码器模型有失真信源编码器模型信源编码器信源编码器X Y假想信道假想信道xia1,anyjb1,bm115.1 5.1 信息率失真函数信息率失真函数11( ) (|) ( ,)nmijiijijDp

6、 a p ba d a b若p(ai)和d(ai,bj)已定，则平均失真由信道转移概率p(bj|ai)完全确定，所有满足平均失真小于等于门限D的信道集合信道集合(|):,1,1DjiPp b aDDinjm 125.1 5.1 信息率失真函数信息率失真函数l 信息率失真函数信息率失真函数l 信息率失真函数信息率失真函数R(D)的物理意义：的物理意义： 对于给定信源，在平均失真不超过失真限度对于给定信源，在平均失真不超过失真限度D的的情况下，信息率允许压缩的最小值为情况下，信息率允许压缩的最小值为R(D) 。()min (, )DPR DI X Yl 离散无记忆信源的信息率失真函数离散无记忆信源

7、的信息率失真函数()min (, )(|)min() (|)log()DDPjiijiPjR DI X Yp bap a p bap b135.1 5.1 信息率失真函数信息率失真函数l 例例. 设信源符号集为A=a1, a2, a2n, 概率分布为: p(ai)=1/2n (i=1,2,2n) ，失真函数为:1,( ,)0,ijijd a aij 信源熵H(X)=log(2n) bit/符号. 如果对信源进行无失真编码，平均每个符号至少需要log(2n) 个二进制码元. 现讨论有失真编码. 假设失真度为D=1/2. 编码方案为: a1a1, a2 a2, ,an an, an+1 an, ,

8、a2n an 对应一个确定信道确定信道. H(Y|X)=0, I(X; Y)=H(Y)H(Y|X)=H(Y). 信道输出Y的概率分布为: p(a1)= p(a2)= p(an-1)=1/2n, p(an)=(1+n)/2n I(X; Y)=H(Y) = log(2n) (1+n)/2nlog(1+n).145.1 5.1 信息率失真函数信息率失真函数l 例例. 信源传输的信息率由log(2n)压缩到 H(Y)=log(2n) (1+n)/2nlog(1+n).平均失真: （收到100个符号时，允许出错的符号个数50） 111( ) (|) ( ,)2nmijiijijDp a p b a d

9、a b15第第5 5章章 有失真信源编码有失真信源编码5.1 5.1 信息率失真函数信息率失真函数5.2 5.2 信息率失真函数的性质信息率失真函数的性质5.3 5.3 限失真信源编码定理限失真信源编码定理165.2 5.2 信息率失真函数的性质信息率失真函数的性质( ) min ( , ),R DI X Y D Dl 单调性单调性0 Dmax DR(D)1212()()DDR DR D175.2 5.2 信息率失真函数的性质信息率失真函数的性质l R(D)的定义域的定义域: Dmin, Dmaxu0 Dmin；R(Dmin)=H(X).min(|)11(|)111min() (|) (,)m

10、in()(|) (,)()min (,)jijinmijiijp b aijnmijiijp b aijniijjiDp a p ba d a bp ap ba d a bp ad a b185.2 5.2 信息率失真函数的性质信息率失真函数的性质max(|)11(|)111()0(; )0( ,)( )()min( ) () ( ,)min()( ) ( ,)min( ) ( ,)jijiijijnmijijp b aijmnjiijp b ajiniijjiR DI X Yp a bp ap bDp a p b d a bp bp a d a bp a d a buDmax: 195.2

11、5.2 信息率失真函数的性质信息率失真函数的性质l R(D)的值域的值域 0 R(D) H(X).205.2 5.2 信息率失真函数的性质信息率失真函数的性质0110),(),(),(),(12122111badbadbadbaddl 例：例：设输入输出符号表示为X=Y=0,1, 输入概率分布p(x)= 1/3,2/3, 失真矩阵为 求Dmin, R(Dmin), Dmax, R(Dmax)以及相应的编码器转移概率? 解解: 当Dmin=0时, R(Dmin)=H(X)=H(1/3,2/3)=0.91bit/符号. 这时信源编码器无失真, a1 b1, a2b2,编码器的转移矩阵为:10.01

12、P215.2 5.2 信息率失真函数的性质信息率失真函数的性质 这时的编码方案为：a1 b2, a2b2,输出符号概率p(b1)=0, p(b2)=1, 编码器的转移矩阵为:0 1.0 1P 当R(Dmax) =0时, 有2max1112211122221,21minmin, 12121 min01, 10.33333iijjiDp dp dp dp dp d 225.2 5.2 信息率失真函数的性质信息率失真函数的性质l R(D)是关于是关于D的下凸函数的下凸函数(01)l R(D)是关于是关于D的连续函数的连续函数11()()DDR DR D1212(1)( )() (1) ()DDDR

13、DR DR D 235.2 5.2 信息率失真函数的性质信息率失真函数的性质l R(D)是关于是关于D的严格递减函数的严格递减函数u允许的失真越大,所要求的信息率越小0 Dmax DR(D)H(X)离散系统信息率失真曲线离散系统信息率失真曲线0 Dmax DR(D)连续系统信息率失真曲线连续系统信息率失真曲线245.2 5.2 信息率失真函数的性质信息率失真函数的性质)/(),()|()()|(log)/()()()|(log)();(11111,ijiriijiijrisjijijijrisjjixypxpfxypxpxypxypxpypxypyxpYXIl 信道容量与信息率失真函数的比较信

14、道容量与信息率失真函数的比较255.2 5.2 信息率失真函数的性质信息率失真函数的性质u当当p(xi)固定，互信息量固定，互信息量I(X;Y)是信道转移概率概率是信道转移概率概率分布分布p(yj|xi)的下凸函数的下凸函数,存在极小值。存在极小值。信息率失真函数就是假定信源给定的情况下,在试验信道（满足保真度准则的信道）中求平均互信息的极小值,即(/)()min(, )jiDp yxPR DI X Y),(max)(YXICixpl 信道容量与信息率失真函数的比较信道容量与信息率失真函数的比较u当p(yj|xi)固定，互信息量I(X;Y)是输入符号概率p(xi)的上凸函数,存在极大值.信道容

15、量就是假定信道固定的前信道容量就是假定信道固定的前提下提下,选择一种试验信源，使平均互信息（信息率）最选择一种试验信源，使平均互信息（信息率）最大大,即即 265.2 5.2 信息率失真函数的性质信息率失真函数的性质u信道容量反映的是信道传输信息的能力，即信道可传输的最大信息率。研究信道容量目的是充分利用已给信道，使传输的信息量最大而发生错误的概率任意小，即信道编码问题。信道容量是为了解决通信的可靠性问题，是信息传输的理论基础，通过信道编码增加信息的冗余度来实现。u信息率失真函数反映的是信源可压缩的程度，即在可以容忍的失真度内再现信源消息所必须获得的最小平均信息量。研究信息率失真函数目的是用尽

16、可能少的码符号尽快地传送尽可能多的信源消息，以提高通信的有效性问题，即信源编码问题，是信源压缩的理论基础，通过信源编码减少信息的冗余度来实现。l 信道容量与信息率失真函数的比较信道容量与信息率失真函数的比较275.2 5.2 信息率失真函数的性质信息率失真函数的性质u信道容量只与信道转移概率分布有关，反映信道特性，与信源无关。u信息率失真函数只与信源概率分布有关，反映信源特性，与信道特性无关。l 信道容量与信息率失真函数的比较信道容量与信息率失真函数的比较28第第5 5章章 有失真信源编码有失真信源编码5.1 5.1 信息率失真函数信息率失真函数5.2 5.2 信息率失真函数的性质信息率失真函数的性质5.3 5.3 限失真信源编码定理限失真信源编码