第4章信息论与编码

《第4章信息论与编码》由会员分享，可在线阅读，更多相关《第4章信息论与编码（42页珍藏版）》请在装配图网上搜索。

1、信息率失真函数信息率失真函数 24.14.1 平均失真和信息率失真函数平均失真和信息率失真函数4.24.2 离散信源和连续信源的离散信源和连续信源的R(D)计算计算内容内容3 失真失真o 信道编码定理信道编码定理欲无失真，必欲无失真，必 R C，必失真，必失真o 失真失真必要性必要性连续信源连续信源R趋向于无穷大，必有失真趋向于无穷大，必有失真压缩亦有失真压缩亦有失真o 失真失真可能性可能性终端性能有限，如人眼终端性能有限，如人眼,人耳人耳 研究：研究：信息率允许失真信息率允许失真信息率失真理论44.14.1 平均失真和平均失真和信息率失真函数信息率失真函数54.1.1 4.1.1 失真函数失

2、真函数 假如某一信源假如某一信源X,输出样值输出样值xi,xia1,a2,an,经信经信道传输后变成道传输后变成yj,yj b1,b2,bm,如果如果:xi yj 没有失真没有失真 xi yj 产生失真产生失真 失真的大小失真的大小,用一个量来表示用一个量来表示,即即失真函数失真函数d(xi,yj),以以衡量用衡量用yj代替代替xi所引起的失真程度所引起的失真程度。失真函数定义为：失真函数定义为：jijijiyx0aa,yx0,)y,d(x6失真函数失真函数 将所有的将所有的d(xi,yj)排列起来排列起来,用矩阵表示为用矩阵表示为:1111(,)(,)d(,)(,)mnnmd a bd a

3、bd a bd a b 失真矩阵失真矩阵 例：设信源符号序列为例：设信源符号序列为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.50 1 0.51 0 0.5d 失真矩阵失真矩阵72(,)()ijijd x yxy 失真函数形式可以根据需要任意选取失真函数形式可以根据需要任意选取,最常用的最常用的有有:(,)|ijijd x yxy (,)|/|ijijid x yxyx 0,(,)()1,ijijijxyd x yxy 其其他他 均方均方失真失真:绝对

4、绝对失真失真:相对相对失真失真:误码误码失真失真:(汉明失真函数汉明失真函数)适于适于连续连续信源信源适于适于离散离散信源信源失真函数失真函数8 汉明失真矩阵汉明失真矩阵 011101110d 对于二元对称信源对于二元对称信源(m=n),X=0,1,Y=0,1,汉明汉明失真矩阵失真矩阵:0110d94.1.2 4.1.2 平均失真平均失真 将失真函数的数学期望称为将失真函数的数学期望称为平均失真平均失真：()(|)(,)ijiijijDp a p b a d a b 失真函数失真函数d(xi,yj)：描述了描述了某个信源符号某个信源符号通过传输后失真的大小通过传输后失真的大小 平均失真平均失真

5、 ：描述描述某个信源某个信源在某一试验信道传输下的失真在某一试验信道传输下的失真大小大小,它对它对信源和信道进行了统计平均信源和信道进行了统计平均,是从总是从总体上描述整个系统的失真体上描述整个系统的失真D10 对于连续随机变量同样可以定义平均失真对于连续随机变量同样可以定义平均失真(,)(,)xyDpx y d x y dxdy ix信源编码器信源编码器jy)(ijxyp11L长序列编码长序列编码 如果假定离散信源输出符号序列如果假定离散信源输出符号序列XX1X2 Xl XL,其中其中L长符号序列长符号序列xi=xi1xi2xiL,经信经信源编码后源编码后,输出符号序列输出符号序列Y=Y1Y

6、2YlYL,其中其中L长符号序列长符号序列yj=yj1yj2yjL,则则失真函数失真函数定义为定义为11LLllDDL 平均失真平均失真11(x,y)(,)LLijiljlldd xyL 124.1.3 信息率失真函数信息率失真函数R(D)naaax,21信源编码器信源编码器nbbby,21XY假想信道假想信道将信源编码器看作信道将信源编码器看作信道134.1.3 4.1.3 信息率失真函数信息率失真函数R(D)无论是无噪信道还是有噪信道无论是无噪信道还是有噪信道:RC 总能找到一种编码使在信道上能以任意小的错总能找到一种编码使在信道上能以任意小的错误概率误概率,以任意接近以任意接近C的传输率

7、来传送信息的传输率来传送信息 RC 就必须对信源压缩就必须对信源压缩,使其压缩后信息传输率使其压缩后信息传输率R小于信道容量小于信道容量C,但同时要保证压缩所引入的失但同时要保证压缩所引入的失真不超过预先规定的限度。真不超过预先规定的限度。信息压缩问题就是对于给定的信源信息压缩问题就是对于给定的信源,在满足平均失在满足平均失真真 的前提下的前提下,使信息率尽可能小。使信息率尽可能小。DD 14信息率失真函数信息率失真函数R(D)若平均失真度若平均失真度 不大于我们所允许的失真不大于我们所允许的失真,即即DDD 则称此为则称此为保真度准则保真度准则 当信源当信源p(xi)给定给定,单个符号失真度

8、单个符号失真度d(xi,yj)给定时给定时,选选择不同的试验信道择不同的试验信道p(yj|xi),相当于不同的编码方相当于不同的编码方法法,其所得的平均失真度不同。其所得的平均失真度不同。假想信道假想信道DDDD满足保真度准则15 满足满足 条件的所有转移概率分布条件的所有转移概率分布pij,构成构成了一个信道集合了一个信道集合DD|(DDabpPijD）：D失真允许的试验信道：失真允许的试验信道：满足保真度准则的试验信道。满足保真度准则的试验信道。PD：所有所有D失真允许的试验信道失真允许的试验信道组成的一个集合。组成的一个集合。16信息率失真函数信息率失真函数R(D)R(D)：在限定失真为

9、在限定失真为D的条件下信源输出的最小信的条件下信源输出的最小信息率。息率。),(min)(YXIDRDP 在信源给定后在信源给定后,我们希望在满足一定失真的情况下我们希望在满足一定失真的情况下,使信使信源必须传输给收信者的源必须传输给收信者的信息传输率信息传输率R尽可能地小。尽可能地小。若从接收端来看若从接收端来看,就是在满足保真度准则下就是在满足保真度准则下,寻找再现信寻找再现信源消息所必须获得的源消息所必须获得的最低平均信息量最低平均信息量。即在满足保真度即在满足保真度准则的条件下寻找平均互信息准则的条件下寻找平均互信息I(X,Y)I(X,Y)的最小值。的最小值。17信息率失真函数信息率失

10、真函数 PD是所有满足保真度准则的试验信道集是所有满足保真度准则的试验信道集合合,因而可以在集合因而可以在集合PD中寻找某一个信道中寻找某一个信道pij,使使I(X,Y)取极小值。取极小值。离散无记忆信源离散无记忆信源ijjijijiPpbpabpabpapDRDji)()|(log)|()(min)(18 例已知编码器输入的概率分布为例已知编码器输入的概率分布为p(x)=0.5,0.5 信道矩阵信道矩阵8.02.04.06.0ijp 求互信息求互信息)|()()(ijijixypxpyxp4.0)(,1.0)(,2.0)(,3.0)(22122111yxpyxpyxpyxp6.0)(,4.0

11、)(21ypyp32)|(,41)|(,31)|(,43)|(22122111yxpyxpyxpyxp符号/125.0)()|(log)();(bitxpyxpyxpYXIijijiji19 编码器输入的概率分布为编码器输入的概率分布为p(x)=0.5,0.5 信道矩阵信道矩阵8.02.01.09.0ijp 求互信息求互信息符号/397.0)()|(log)();(bitxpyxpyxpYXIijijiji 可见当可见当p(x)一定时一定时,I(X,Y)随随p(yj|xi)而变。而变。因为因为p(x)分布一定时分布一定时,信道受干扰不同所能传递的信道受干扰不同所能传递的信息量是不同的。信息量是

12、不同的。可以证明，当可以证明，当p(x)一定时一定时,I(X,Y)是关于是关于p(yj|xi)的的下凸函数。下凸函数。因此当改变因此当改变p(yj|xi)时时,I(X,Y)有一极小值。有一极小值。20平均互信息平均互信息 平均互信息平均互信息I(X;Y)：信源的概率分布信源的概率分布p(xi)的上凸函数。的上凸函数。p(yj|xi)一定一定 信道传递概率信道传递概率p(yj|xi)的下凸函数。的下凸函数。p(xi)一定一定);(max)(YXICixp 信道容量：信道容量：信息率失真函数：信息率失真函数：);(min)(YXIDRDP21率失真函数与信道容量的比较率失真函数与信道容量的比较信道

13、容量C率失真函数R(D)数学上数学上 固定固定 p(yj/xi),改变改变p(xi),求得求得I(X;Y)最大值最大值固定固定p(xi),改变改变p(yj/xi),求得求得I(X;Y)最小值最小值概念上概念上(反映反映)固定信道，改变信源，固定信道，改变信源，使信息率最大使信息率最大（信道传输能力信道传输能力）固定信源，改变信道，固定信源，改变信道，使信息率最小使信息率最小（信源可压缩程度信源可压缩程度）通信上通信上使传输信息量最大，使传输信息量最大，Pe0信道编码信道编码用尽可能少的码符号用尽可能少的码符号传送传送信源编码信源编码224.1.4 4.1.4 信息率失真函数的信息率失真函数的性

14、质性质 1、R(D)的定义域的定义域 率失真的定义域问题就是在信源和失真函数已率失真的定义域问题就是在信源和失真函数已知的情况下知的情况下,讨论允许讨论允许平均失真度平均失真度D的的最小最小和和最最大大取值问题。取值问题。由于平均失真度是非负实数由于平均失真度是非负实数d(xi,yj)的数学期望的数学期望,因此也是非负的实数因此也是非负的实数,即即 的的下界是下界是0。允许平均失真度能否达到其下限值允许平均失真度能否达到其下限值0,与单个符号与单个符号的失真函数有关。的失真函数有关。DD,023R(D)的定义域的定义域 Dmin 和和R(Dmin)信源的最小平均失真度：信源的最小平均失真度：n

15、ijijiyxdxpD1min),(min)(只有当失真矩阵的每一行至少有一个只有当失真矩阵的每一行至少有一个0元素时元素时,信源的信源的平均失真度平均失真度才能达到下限值才能达到下限值0。当当Dmin=0,即信源不允许任何失真时即信源不允许任何失真时,信息率至信息率至少应等于信源输出的平均信息量少应等于信源输出的平均信息量信息熵。即信息熵。即 R(0)=H(X)24R(D)的定义域的定义域 因为实际信道总是有干扰的因为实际信道总是有干扰的,其容量有限其容量有限,要无失要无失真地传送连续信息是不可能的。真地传送连续信息是不可能的。当允许有一定失真时当允许有一定失真时,R(D)将为有限值将为有限

16、值,传送才是传送才是可能的。可能的。对于连续信源：对于连续信源：)(lim)(0minDRDRD25R(D)的定义域的定义域 R(D)的定义域为的定义域为Dmin，Dmax。通常通常Dmin=0，R(Dmin)=H(X)当当 DDmax时时,R(D)=0 当当 0 DDmax时时,0R(D)H(X)26R(D)的定义域的定义域 Dmax：定义域的定义域的上限。上限。Dmax是满足是满足R(D)=0时所时所有的平均失真度中的有的平均失真度中的最最小值。小值。DDDR0)(maxmin 由于由于I(X,Y)是非负函数是非负函数,而而R(D)是在约束条件下的是在约束条件下的I(X,Y)的最小值的最小

17、值,所以所以R(D)也是一个非负函数也是一个非负函数,它它的下限值是零。的下限值是零。R(D)027R(D)的定义域的定义域 由于由于I(X,Y)=0的充要条件是的充要条件是X与与Y统计独立统计独立,即：即：)()|(jijypxypjijiijypjjijiiypyxdxpypyxdypxpDjj),()()(min),()()(min)()(maxnijiimjyxdxpD12,1max),()(min28 例例4-3:设输入输出符号表为设输入输出符号表为X=Y=0,1,输入概率分布输入概率分布p(x)=1/3,2/3,失真矩阵失真矩阵 0110d 求：求：Dmin 和和Dmax 31)3

18、1,32(min)032131,132031(minmin212,1maxjjijiijdpD 失真矩阵的每一行至少有一个失真矩阵的每一行至少有一个0元素时元素时,Dmin=0此时输出符号概率此时输出符号概率p(b1)0，p(b2)1，2221,baba29 例例:设输入输出符号表为设输入输出符号表为X=Y=0,1,输入输入概率分布概率分布p(x)=1/3,2/3,失真矩阵失真矩阵 1212/1d 求：求：Dmin 和和Dmax 1)1,23(min)132131,2322131(minmin212,1maxjjijiijdpD651322131),(min)(1minnijijiyxdxpD

19、30信息率失真函数的性质信息率失真函数的性质 1、R(D)是非负的实数是非负的实数,R(D)0。其定义域为其定义域为0Dmax,其值为其值为0H(X)。当当DDmax时时,R(D)0 2、R(D)是关于是关于D的下凸函数的下凸函数 R(D)在定义域内是失真度在定义域内是失真度D的的U型下凸函数型下凸函数 3、R(D)的单调递减性及连续性的单调递减性及连续性 容许的失真度越大，所要求的信息率越小。容许的失真度越大，所要求的信息率越小。反之亦然。反之亦然。31R(D)H(X)R(D)0 D Dmax DR(D)0 Dmax D 信息率失真曲线信息率失真曲线由以上三点结论，对一般由以上三点结论，对一

20、般R(D)曲线的形态可以画出来：曲线的形态可以画出来：324.2 离散信源和连续信源离散信源和连续信源R(D)计算计算 给定信源概率给定信源概率pi和失真函数和失真函数dij,就可以求就可以求得该信源的得该信源的R(D)函数。函数。它是在保真度准则下求极小值的问题。它是在保真度准则下求极小值的问题。但要得到它的显式表达式但要得到它的显式表达式,一般比较困难一般比较困难通常用参量表达式。通常用参量表达式。即使如此即使如此,除简单的情况外实际计算还是除简单的情况外实际计算还是困难的困难的,只能用迭代逐级逼近的方法。只能用迭代逐级逼近的方法。33 某些特殊情况下某些特殊情况下R（D）的表示式为：）的

21、表示式为：（1）当）当d(x,y)=(x-y)2，时时，22221)(xexpDDRlog)(4.2 离散信源和连续信源离散信源和连续信源R(D)计算计算 34(2)当当d(x,y)=|x-y|，时，时，xexp2)(DDR1log)(3)当当d(x,y)=(x,y)，p(x=0)=p，p(x=1)=1-p时，时，R(D)=H(p)H(D)35这些这些R（D）可画成三条曲线）可画成三条曲线 0 Dmax D R(D)H(3)(1)(2)图图4-5 信息率失真函数信息率失真函数R(D)36二元对称信源的二元对称信源的R(D)函数函数 设二元对称信源设二元对称信源X=0,1,其概率分布其概率分布p

22、(x)=p,1-p,接收变量接收变量Y=0,1,失真矩阵失真矩阵0110d 因而最小允许失真度因而最小允许失真度Dmin=0。并能找到满足该最小失真的试验信道并能找到满足该最小失真的试验信道,且是一个无噪且是一个无噪无损信道无损信道,其信道矩阵为其信道矩阵为1001P37 计算得：计算得：R(0)=I(X;Y)=H(p)最大允许失真度为最大允许失真度为pppdpdpdpdpdpDjijiij),1(min)1,1()1()1,0()0(),0,1()1()0,0()0(minmin101,0max 要达到最大允许失真度的试验信道要达到最大允许失真度的试验信道,唯一确定为唯一确定为1010P38

23、 这个试验信道能正确传送信源符号这个试验信道能正确传送信源符号x=1,而而传送信源符号传送信源符号x=0时时,接收符号一定为接收符号一定为y=1 凡发送符号凡发送符号x=0时时,一定都错了。而一定都错了。而x=0出现出现的概率为的概率为p,所以信道的平均失真度为所以信道的平均失真度为p。在这种试验信道条件下，可计算得在这种试验信道条件下，可计算得 R(Dmax)=R(p)=039 0.1 0.2 0.3 0.4 0.5 D1.00.80.60.40.20.0R(D)/bitp=0.5p=0.3p=0.2p=0.1图图46 R(D)=H(p)H(D)，p为参数为参数40例：一个四元信源，输入与输

24、出符号集例：一个四元信源，输入与输出符号集X X、Y Y均取均取值于值于0,1,2,30,1,2,3，且输入信号的分布为，且输入信号的分布为失真矩阵为失真矩阵为 求：求：Dmin、Dmax 和和R(Dmin)、R(Dmax),以以及相应的编码器转移概率矩阵。及相应的编码器转移概率矩阵。411 (/)0 10000100 00100001jiijp yxij，min0D即无失真即无失真R(Dmin)=R(0)=H(X)=log24=2bit/符号符号424max1,2,3,41min()(,)11111111 (0111,1011,4444444411111111 1101,1110)444444443 (j=1234)4iijjiDp x d x y 或 或 或(/)()(/)()10000100001000011000010000100001(/)10000100001000011000010000100001jiijijjip yxp xp yxp yp yx与无关=或或或R(Dmax)=R(3/4)=0