信息论与编码课件第四章

1、24.14.1 平均失真和信息率失真函数平均失真和信息率失真函数4.24.2 离散信源和连续信源的离散信源和连续信源的R(D)计算计算341、失真函数的定义 假如某一信源X,输出样值xi , xia1,a2,an,经信道传输后变成yj , yj b1, b2,bm,如果: xi yj 没有失真 xi yj 产生失真 失真函数的含义: 即失真函数d(xi,yj),此函数衡量用yj代替xi所引起的失真程度。即失真的大小。 失真函数定义为：jijijiyxyxyxd00),(52、失真矩阵 将所有的d(xi,yj)排列起来,用矩阵表示为:),(),(),(),(1111mnnmbadbadbadba

2、dd失真矩阵 例1：设信源符号序列为X=0,1,接收端收到符号序列为Y= 0,1,2,规定失真函数为 d(0,0)d(1,1)= 0 d(0,1)d(1,0)= 1 d(0,2)d(1,2)= 0.55 . 0015 . 010d失真矩阵62)(),(jijiyxyxd3、失真函数的形式：（常用的）|),(jijiyxyxd| / |),(ijijixyxyxd0,( ,)1,ijijxyd x y其他 均方失真: 绝对失真: 相对失真: 误码失真:适于连续信源适于离散信源74、汉明失真矩阵（也是一种误码失真）： 011101(,)110ijd xy 对于二元对称信源X=0,1,Y=0,1,汉

3、明失真矩阵（二元误码失真）:0110d81、单符号离散信源的平均失真 xi和yj都是随机变量,所以失真函数d(xi,yj)也是随机变量,有限失真时的信源（总体）失真值只能用数学期望表示 将失真函数的数学期望称为平均失真：( ,) ( ,)ijijijDp a b d a b 92、两者的区别l 失真函数d(xi,yj)： 描述了某个信源符号通过传输后失真的大小l平均失真 ： 描述某个信源在某一试验信道传输下的失真大小,它对信源和信道进行了统计平均,是从总体上描述整个系统的失真D103、L长序列编码 如果假定离散信源输入符号序列XX1X2 Xl Xn,其中L长符号序列xi =xi1xi2xiL,

4、经信源编码后,输出符号序列Y=Y1Y2YlYm,其中L长符号序列yj=yj1yj2yj L 失真函数定义为jjijiLLLyxdLyxd),(1),(111 (,)LLLLijljlDE d xyDLL 平均失真111、保真度准测 若平均失真度 不大于我们所允许的失真,即DD 则称此为保真度准则 当信源p(xi)给定,单个符号失真度d(xi,yj) 给定时,选择不同的试验信道p(yj|xi), 相当于不同的编码方法,其所得的平均失真度不同。122、D失真允许的实验信道 -满足保真度准则的试验信道。 满足 条件的所有转移概率分布pij ,构成了一个信道集合DD |(DDabpPijD）： PD：

5、 所有D失真允许的试验信道组成的一个集合。133、信息率失真函数R(D)： 在限定失真为D的条件下，信源输出的最小信息速率。 ),(min)(YXIDRDP 在信源给定后,我们希望在满足一定失真的情况下,使信源必须传输给收信者的最小信息量。 若从接收端来着,就是在满足保真度准则下,寻找再现信源消息所必须获得的最低平均信息量。即在满足保真度准则的条件下，接受端Y需要获得发送端 X的最小信息量144、信息率失真函数的求法： PD是所有满足保真度准则的试验信道集合,因而可以在集合PD中寻找某一个信道pij,使I (X,Y)取极小值。 离散无记忆信源( )min ( )(| )min ( )( |)(

6、|)min( ) (|)log( )jiDjiDjiDpPpPjiijipPijjR DH XH X YH YH Y Xp bap a p b ap b15例2 已知编码器输入的概率分布为p(x)=0.5 ,0.5信道矩阵8 . 02 . 04 . 06 . 0ijp求互信息)|()()(ijijixypxpyxp11122122()0.3()0.2()0.1()0.4p x yp x yp x yp x y6 . 0)(4 . 0)(21ypyp( ; )( )(| )( )( |)0.125/I X YH XH X YH YH Y Xbit符号16 若编码器输入的概率分布不变仍为p(x)=

7、0.5 ,0.5 但信道矩阵8 . 02 . 01 . 09 . 0ijp 求互信息符号/397. 0)()|(log)();(bitypyxpyxpYXIijijiji 可见当p(x)一定时,I (X,Y)随信道矩阵p(yj|xi)而变。 因为p(x)分布一定时,信道受干扰不同所能传递的信息量是不同的。 当p(x)一定时,I (X,Y)是关于p(yj|xi)的下凸函数。 因此当改变p(yj|xi)时,I (X,Y)有一极小值。171、计算不同l 平均互信息I(X;Y)： 信源的概率分布p(xi)的上凸函数。 信道传递概率p(yj|xi)的下凸函数。);(max)(YXICixpl 信道容量：

8、 l信息率失真函数： );(min)(YXIDRDP182、反映的事物不同 假定信道固定的前提下,选择一种试验信源使信息传输率最大。 它所反映的是信道传输信息的能力,是信道可靠传送的最大信息传输率。 一旦找到了信道容量,它就与信源不再有关,而是信道特性的参量,随信道特性的变化而变化 不同的信道其信道容量不同。19 假定信源给定的情况下,用户可以容忍的失真度内再现信源消息所必须获得的最小平均信息量。 它反映的是信源可以压缩的程度,是在满足一定失真度要求下信源可压缩的最低值。 一旦找到信息率失真函数,就与选择的试验信道不再有关,而只是信源特性的参量 不同的信源其R(D)不同。203、目地不同： 充

9、分利用已给信道,使传输的信息量最大，以提高通信的正确性 解决在已知信源和允许失真度D的条件下,使信源必须传送给信宿的信息率最小。即用尽可能少的码符传送尽可能多的信源消息,以提高通信的有效性。21 例1：设信源的符号表为A=al,a2,a2n,概率分布为p(ai)=1/2n,i=1,22n,失真函数规定为 jijiaadji10),( 信源熵 nnnnH2log)2121,21( 如果对信源进行不失真编码,平均每个符号至少需要log2n个二进制码元。 现在假定允许有一定失真,假设失真限度为D=1/2设想采用下面的编码方案： a1a1， a2a2， anan an+1an ,an+2 an ,a2

10、n an 即不发生差错时失真为0,出错失真为1 研究在一定编码条件下信息压缩的程度。2221),()|()(ijjiijiaadaapapD 而信宿Y的概率分布为111 11( , )( )(,)log2log(1)22222nnI X YH YHnnnnnnn 由该信道模型图4-3(P75)看出,它是一个无噪有损信道，且满足保真准则 ，噪声熵H(Y|X)=0 )()|()(),(YHXYHYHYXI压缩DDYa1a2anP1/2n1/2n(1+n)/2n23 1、R(D)的定义域 信息率失真函数的定义域问题就是在信源和失真函数已知的情况下,允许平均失真度D的最小和最大取值问题。 由于平均失真

11、度是非负实数d(xi,yj)的数学期望,因此也是非负的实数,即 的下界是0。 允许平均失真度能否达到其下限值0,与单个符号的失真函数有关。DD, 0242、平均失真度的最小值 Dmin 信源的最小平均失真度：min11minmin( ,) ( ,) ( )min ( ,)nijijijiijjDp x y d x yXYDp xd x y若 和 相互独立，则 只有当失真矩阵的每一行至少有一个0元素时, 信源的平均失真度才能达到下限值0。 当Dmin = 0,即信源不允许任何失真时,此时噪声熵为0，信息率至少应等于信源输出的平均信息量信息熵。即 R(0) =H(X)253、 R(D)的值域 R(

12、D)的定义域为Dmin，Dmax 。 通常Dmin = 0， R(Dmin) = R(0)=H(X) 当 DDmax时, R(D) = 0 当 0=Dmin DDmax时, 0 R( Dmax) R(D) H(X), 因此： 0 R(D) H(X),26 Dmax：定义域的上限。 由于当 DDmax时, R(D) = 0 因此Dmax是满足R(D)=0时 所有的平均失真度中 的最小值。DDDR0)(maxmin 4、平均失真度的最大值 Dmax 275、平均失真度的最大值 Dmax的计算 由于R(D) = 0 时，I(X,Y) = 0，而I(X,Y) = 0的充要条件是X与Y统计独立,即：(,

13、 )( ) ()jiijp y xp x p ymax() 0()()min=min( ) () ( ,)min()( ) ( ,)jjijijR Dp yijjiijp yjiDDp x p y d x yp yp x d x y nijiimjyxdxpD12 , 1max),()(min28 例1:设输入输出符号表为X=Y=0,1,输入概率分布p(x)=1/3,2/3,失真矩阵 0110d 求： Dmin 和Dmax max1,211212min( ) ( ,)min(01,10)33332 11min( , )3 33niijjjijDp x d x y 失真矩阵的每一行至少有一个0元

14、素时, Dmin=029 例2:设输入输出符号表为X=Y=0,1,输入概率分布p(x)=1/3,2/3,失真矩阵 1212/ 1d 求： Dmin 和Dmax 1) 1 ,23(min) 132131, 2322131(minmin212, 1maxjjijiijdpD651322131),(min)(1minnijijiyxdxpD30 1、R(D)是非负的实数, R(D)0。 其定义域为0Dmax , 其值为0H(X)。 当DDmax时,R(D)0 2、R(D)是关于D的下凸函数 R(D)在定义域内是失真度D的U型下凸函数 3、R(D)的单调递减性及连续性 容许的失真度越大，所要求的信息率

15、越小。反之亦然。31 Step1:给定信源概率pi和失真函数dij,就可以求得该信源的R(D)的函数表达式。 Step2: 求R(D)函数满足保真度准则下极小值的问题。 但要得到它的显式表达式,一般比较困难通常用参量表达式。 即使如此,除简单的情况外实际计算还是困难的,只能用迭代逐级逼近的方法。 32 设二元对称信源X=0,1,其概率分布p(x)=p,1-p,接收变量Y=0,1,汉明失真矩阵0110d 因而最小允许失真度Dmin=0。 并能找到满足该最小失真的试验信道,且是一个无噪无损信道,其信道矩阵为1001p33 计算得：R(0)=I(X;Y)=H(X) 最大允许失真度为pppdpdpdp

16、dpdpDjijiij),1(min)1 , 1 () 1 () 1 , 0()0(),0 , 1 () 1 ()0 , 0()0(minmin101 , 0max 要达到最大允许失真度的试验信道,唯一确定为1010p34 这个试验信道能正确传送信源符号x=1,而传送信源符号x=0时,接收符号一定为y=1 凡发送符号x=0时,一定都错了。而x=0出现的概率为p,所以信道的平均失真度为p 。 在这种试验信道条件下，可计算得 R(Dmax) = R(p) = 035 失真函数，失真函数矩阵 平均失真 -单符号离散信源平均失真 jijijiyxyxyxd00),(),(),(),(),(1111mnnmbadbadbadbadd( ,) ( ,)ijijijDp a b d a b 36jjijiLLL