《限失真的信源编码.ppt》由会员分享，可在线阅读，更多相关《限失真的信源编码.ppt（36页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、限失真的信源编码现在学习的是第1页，共36页 限失真的信源编码问题限失真的信源编码问题允许一定的失真度下，能将信源信息压缩到什么程允许一定的失真度下，能将信源信息压缩到什么程度？（最少需要多少比特才能在收端描述信源？）度？（最少需要多少比特才能在收端描述信源？）一定的信息传输率一定的信息传输率R R下，允许的最大失真是多少？下，允许的最大失真是多少？相关问题相关问题n失真如何度量？失真如何度量？n率失真函数如何计算？率失真函数如何计算？现在学习的是第2页，共36页7.1 7.1 失真测度失真测度7.1.1 7.1.1 失真函数失真函数假如某一信源假如某一信源X,X,输出样值输出样值x xi i
2、,x xi ia a1 1,a a2 2,a an n,经信道经信道传输后变成传输后变成y yj j,y yj j b b1 1,b,b2 2,b bm m,如果如果:x xi i y yj j 没有失真没有失真 x xi i y yj j 产生失真产生失真失真的大小失真的大小,用一个量来表示用一个量来表示,即失真函数即失真函数d d(x xi i,y yj j),),以以衡量用衡量用y yj j代替代替x xi i所引起的失真程度。所引起的失真程度。失真函数定义为：失真函数定义为：现在学习的是第3页，共36页将所有的将所有的d d(x xi i,y yj j)排列起来排列起来,用矩阵表示为用
3、矩阵表示为:失真函数失真函数d d(x xi i,y yj j)：描述了某个信源符号通过传输后失真的大小描述了某个信源符号通过传输后失真的大小现在学习的是第4页，共36页例：设信源符号序列为例：设信源符号序列为X=0,1,X=0,1,接收端收到符接收端收到符号序列为号序列为Y=0,1,2,Y=0,1,2,规定失真函数为规定失真函数为 d(0,0)d(0,0)d(1,1)=0d(1,1)=0 d(0,1)d(0,1)d(1,0)=1d(1,0)=1 d(0,2)d(0,2)d(1,2)=0.5d(1,2)=0.5现在学习的是第5页，共36页w失真函数形式可以根据需要任意选取失真函数形式可以根据需
4、要任意选取,最常用的有最常用的有:w均方失真均方失真:w绝对失真绝对失真:w相对失真相对失真:w误码失真误码失真:适于适于连续连续信源信源适于适于离散离散信源信源现在学习的是第6页，共36页假设离散矢量假设离散矢量N N长符号序列为长符号序列为X=XX=X1 1,X,X2 2,X,X3 3,X,XN N (X(Xi i取值为取值为x1,x2,x1,x2,xn,xn经信道传输后，接收端收到的经信道传输后，接收端收到的N N长符号序列为长符号序列为Y=YY=Y1 1,Y,Y2 2,Y,Y3 3,Y,YN N (Y(Yj j取值为取值为x1,x2,x1,x2,xn,xn则失真函数定义为则失真函数定义
5、为现在学习的是第7页，共36页7.1.27.1.2平均失真平均失真设离散信源设离散信源经信道传输后输出序列为经信道传输后输出序列为Y=YY=Y1 1,Y,Y2 2,Y,Y3 3,Y,YN N 失真矩阵为失真矩阵为现在学习的是第8页，共36页x xi i和和y yj j都是随机变量都是随机变量,所以失真函数所以失真函数d d(x xi i,y yj j)也是随机也是随机变量变量,限失真时的失真值只能用数学期望表示限失真时的失真值只能用数学期望表示将失真函数的数学期望称为将失真函数的数学期望称为平均失真：平均失真：描述某个信源在某一试验信道传输下的失真大小描述某个信源在某一试验信道传输下的失真大小
6、,它对它对信源和信道进行了统计平均信源和信道进行了统计平均,是从总体上描述整是从总体上描述整个系统的失真。个系统的失真。现在学习的是第9页，共36页假设离散矢量假设离散矢量N N长符号序列为长符号序列为X=XX=X1 1,X,X2 2,X,X3 3,X,XN N(X(Xi i取值为取值为x1,x2,x1,x2,xn,xn经信道传输后，接收端收到的经信道传输后，接收端收到的N N长符号序列为长符号序列为Y=YY=Y1 1,Y,Y2 2,Y,Y3 3,Y,YN N(Y(Yj j取值为取值为x1,x2,x1,x2,xn,xn则平均失真度为则平均失真度为现在学习的是第10页，共36页7.2 7.2 信
7、息率失真函数信息率失真函数7.2.1D7.2.1D允许信道（试验信道）允许信道（试验信道）w无论是无噪信道还是有噪信道无论是无噪信道还是有噪信道:R RC C总能找到一种编码使在信道上能以任意小的错总能找到一种编码使在信道上能以任意小的错误概率误概率,以任意接近以任意接近C C的传输率来传送信息的传输率来传送信息 R RC C就必须对信源压缩就必须对信源压缩,使其压缩后信息传输率使其压缩后信息传输率R R小于信道容量小于信道容量C,C,但同时要保证压缩所引入的失真但同时要保证压缩所引入的失真不超过预先规定的限度。不超过预先规定的限度。w信息压缩问题就是对于给定的信源信息压缩问题就是对于给定的信
8、源,在满足平均失真在满足平均失真 的前提下的前提下,使信息率尽可能小。使信息率尽可能小。现在学习的是第11页，共36页若平均失真度不大于我们所允许的失真若平均失真度不大于我们所允许的失真,即即则称此为则称此为保真度准则保真度准则将满足保真度准则的所有信道称为失真度将满足保真度准则的所有信道称为失真度D D允允许信道（也称许信道（也称D D允许的试验信道）记为允许的试验信道）记为对于离散无记忆信道，相应地有对于离散无记忆信道，相应地有现在学习的是第12页，共36页7.2.2 7.2.2 信息率失真函数的定义信息率失真函数的定义在在D D失真允许的试验信道中寻找一个信道，使给定失真允许的试验信道中
9、寻找一个信道，使给定的信源经过此信道传输时，其信道传输率的信源经过此信道传输时，其信道传输率I(X;Y)I(X;Y)达到最小，定义为信息率失真函数达到最小，定义为信息率失真函数R(D),R(D),也称也称为率失真函数，即为率失真函数，即对于离散无记忆信道对于离散无记忆信道现在学习的是第13页，共36页w例已知编码器输入的概率分布为例已知编码器输入的概率分布为p p(x x)=0.5,0.5)=0.5,0.5w信道矩阵信道矩阵w求互信息求互信息现在学习的是第14页，共36页w编码器输入的概率分布为编码器输入的概率分布为p p(x x)=0.5,0.5)=0.5,0.5w信道矩阵信道矩阵w求互信息
10、求互信息w可见当可见当p p(x x)一定时一定时,I I(X,YX,Y)随随p p(y yj j|x|xi i)而变。而变。w因为因为p(x)p(x)分布一定时分布一定时,信道受干扰不同所能传递的信信道受干扰不同所能传递的信息量是不同的。息量是不同的。w当当p p(x x)一定时一定时,I I(X,YX,Y)是关于是关于p p(y yj j|x|xi i)的下凸函数。的下凸函数。w因此当改变因此当改变p p(y yj j|x|xi i)时时,I I(X,YX,Y)有一极小值。有一极小值。现在学习的是第15页，共36页w平均互信息平均互信息I I(X;YX;Y)：n信源的概率分布信源的概率分布
11、p p(x xi i)的上凸函数。的上凸函数。n信道传递概率信道传递概率p p(y yj j|x|xi i)的下凸函数。的下凸函数。w信道容量信道容量：w信息率失真函数：信息率失真函数：现在学习的是第16页，共36页信道容量信道容量w信道容量：信道容量：n假定信道固定的前提下假定信道固定的前提下,选择一种试验信源使选择一种试验信源使信息传输率最大。信息传输率最大。n它所反映的是信道传输信息的能力它所反映的是信道传输信息的能力,是信道可靠传送的最是信道可靠传送的最大信息传输率。大信息传输率。w一旦找到了信道容量一旦找到了信道容量,它就与信源不再有关它就与信源不再有关,而是信道而是信道特性的参量特
12、性的参量,随信道特性的变化而变化随信道特性的变化而变化w不同的信道其信道容量不同。不同的信道其信道容量不同。现在学习的是第17页，共36页信息率失真函数信息率失真函数w w信息率失真函数：信息率失真函数：信息率失真函数：信息率失真函数：n假定信源给定的情况下假定信源给定的情况下,用户可以容忍的失真度内再现信源用户可以容忍的失真度内再现信源消息所必须获得的最小平均信息量。消息所必须获得的最小平均信息量。n它反映的是信源可以压缩的程度它反映的是信源可以压缩的程度,是在满足一定失真度要是在满足一定失真度要求下信源可压缩的最低值。求下信源可压缩的最低值。w率失真函数一旦找到率失真函数一旦找到,就与求极
13、值过程中选择的试验信道不再有关就与求极值过程中选择的试验信道不再有关,而只是信源特性的参量而只是信源特性的参量w不同的信源其不同的信源其R(D)R(D)不同。不同。现在学习的是第18页，共36页w研究信道容量研究信道容量：n充分利用已给信道充分利用已给信道,使传输的信息量最大使传输的信息量最大,而而发生发生错误的概率任意小错误的概率任意小。w研究信息率失真函数研究信息率失真函数：n解决在已知信源和允许失真度解决在已知信源和允许失真度D D的条件下的条件下,使使信源必须传送给信宿的信息率最小。即用尽信源必须传送给信宿的信息率最小。即用尽可能少的码符号尽快地传送尽可能多的信源可能少的码符号尽快地传
14、送尽可能多的信源消息消息,以提高通信的以提高通信的有效性有效性。现在学习的是第19页，共36页w例：设信源的符号表为例：设信源的符号表为A=A=a al l,a a2 2,a a2n2n,概率分布概率分布为为p p(a ai i)=1/2n,)=1/2n,i=i=1,21,22 2n n,失真函数规定为失真函数规定为 w信源熵信源熵 w如果对信源进行不失真编码如果对信源进行不失真编码,平均每个符号至少需要平均每个符号至少需要log2nlog2n个二进制码元。个二进制码元。w现在假定允许有一定失真现在假定允许有一定失真,假设失真限度为假设失真限度为D=1/2D=1/2设想采设想采用下面的编码方案
15、：用下面的编码方案：a a1 1a a1 1，a a2 2a a2 2，a an na an n a an+1n+1a an n,a an+2n+2 a an n,a a2n2n a an nw即不发生差错时失真为即不发生差错时失真为0,0,出错失真为出错失真为1 1w研究在一定编码条件下信息压缩的程度。研究在一定编码条件下信息压缩的程度。现在学习的是第20页，共36页w平均失真平均失真 w则输出熵则输出熵H H(Y Y)w由该信道模型图由该信道模型图4-34-3看出看出,它是一个确定信道它是一个确定信道w p pijij=1(=1(或或0)0)，H H(Y Y|X X)=0)=0 压缩压缩现
16、在学习的是第21页，共36页7.2.3 7.2.3 信息率失真函数的性质信息率失真函数的性质w1 1、R R(D D)的定义域的定义域w率失真的定义域问题就是在信源和失真函数已知的情率失真的定义域问题就是在信源和失真函数已知的情况下况下,讨论允许讨论允许平均失真度平均失真度D D的的最小最小和和最大最大取值问题。取值问题。w由于平均失真度是非负实数由于平均失真度是非负实数d d(x xi i,y yj j)的数学期望的数学期望,因因此也是非负的实数此也是非负的实数,即即 的的下界是下界是0 0。w允许平均失真度能否达到其下限值允许平均失真度能否达到其下限值0,0,与单个符号的失与单个符号的失真
17、函数有关。真函数有关。现在学习的是第22页，共36页R(D)R(D)的定义域的定义域wD Dmin min 和和R R(D Dminmin)w信源的最小平均失真度：信源的最小平均失真度：w只有当失真矩阵的每一行至少有一个只有当失真矩阵的每一行至少有一个0 0元素时元素时,信源信源的的平均失真度平均失真度才能达到下限值才能达到下限值0 0。w当当D Dmin min=0,=0,即信源不允许任何失真时即信源不允许任何失真时,信息率至少信息率至少应等于信源输出的平均信息量应等于信源输出的平均信息量信息熵。即信息熵。即 R R(0)(0)=H H(X X)现在学习的是第23页，共36页R(D)R(D)
18、的定义域的定义域w因为实际信道总是有干扰的因为实际信道总是有干扰的,其容量有限其容量有限,要无失真要无失真地传送连续信息是不可能的。地传送连续信息是不可能的。w当允许有一定失真时当允许有一定失真时,R R(D D)将为有限值将为有限值,传送才是可能传送才是可能的。的。w对于连续信源：对于连续信源：现在学习的是第24页，共36页R(D)R(D)的定义域的定义域wR(D)R(D)的定义域为的定义域为DDminmin，D Dmaxmax 。w通常通常D Dminmin=0=0，R R(D Dminmin)=)=H H(X X)w当当 D DD Dmaxmax时时,R R(D D)=0)=0w当当 0
19、 0 D DD Dmaxmax时时,0,0R R(D D)H H(X X)现在学习的是第25页，共36页R(D)R(D)的定义域的定义域wD Dmaxmax：定义域的：定义域的上限上限。wD Dmaxmax是是满满足足R R(D D)=0)=0时时所所有有的的平均失真度中的平均失真度中的最小值最小值。w由于由于I I(X,YX,Y)是非负函数是非负函数,而而R R(D D)是在约束条件下的是在约束条件下的I I(X,YX,Y)的最小值的最小值,所以所以R R(D D)也是一个非负函数也是一个非负函数,它的它的下限值是零。下限值是零。R R(D D)0)0现在学习的是第26页，共36页R(D)R
20、(D)的定义域的定义域w由于由于I I(X,YX,Y)=0)=0的充要条件是的充要条件是X X与与Y Y统计独立统计独立,即：即：现在学习的是第27页，共36页w例例4-34-3:设输入输出符号表为设输入输出符号表为X=Y=0,1,X=Y=0,1,输入概率分布输入概率分布p p(x x)=1/3,2/3,)=1/3,2/3,失真矩阵失真矩阵 w求：求：D Dminmin 和和D Dmaxmax w失真矩阵的每一行至少有一个失真矩阵的每一行至少有一个0 0元素时元素时,D,Dminmin=0=0现在学习的是第28页，共36页w例例:设输入输出符号表为设输入输出符号表为X=Y=0,1,X=Y=0,
21、1,输入输入概率分布概率分布p p(x x)=1/3,2/3,)=1/3,2/3,失真矩阵失真矩阵 w求：求：D Dminmin 和和D Dmaxmax 现在学习的是第29页，共36页信息率失真函数的性质信息率失真函数的性质w1 1、R R(D D)是非负的实数是非负的实数,R(D)0,R(D)0。其定义域为其定义域为0 0D Dmax max,其值为其值为0 0H(X)H(X)。当当D DD Dmaxmax时时,R(D)0,R(D)0w2 2、R R(D D)是关于是关于D D的下凸函数的下凸函数nR R(D D)在定义域内是失真度在定义域内是失真度D D的的U U型下凸函数型下凸函数w3
22、3、R R(D D)的单调递减性及连续性的单调递减性及连续性n容许的失真度越大，所要求的信息率越小。反之亦然。容许的失真度越大，所要求的信息率越小。反之亦然。现在学习的是第30页，共36页现在学习的是第31页，共36页离散信源离散信源R(D)R(D)计算计算 w给定信源概率给定信源概率p pi i和失真函数和失真函数d dijij,就可以求就可以求得该信源的得该信源的R(D)R(D)函数。函数。w它是在保真度准则下求极小值的问题。它是在保真度准则下求极小值的问题。w但要得到它的显式表达式但要得到它的显式表达式,一般比较困难一般比较困难通常用参量表达式。通常用参量表达式。w即使如此即使如此,除简
23、单的情况外实际计算还是除简单的情况外实际计算还是困难的困难的,只能用迭代逐级逼近的方法。只能用迭代逐级逼近的方法。现在学习的是第32页，共36页二元对称信源的二元对称信源的R(D)R(D)函数函数 w设二元对称信源设二元对称信源X=0,1,X=0,1,其概率分布其概率分布p p(x x)=p,1-p,)=p,1-p,接接收变量收变量Y=0,1,Y=0,1,汉明失真矩阵汉明失真矩阵w因而最小允许失真度因而最小允许失真度D Dminmin=0=0。w并能找到满足该最小失真的试验信道并能找到满足该最小失真的试验信道,且是一个无噪无损且是一个无噪无损信道信道,其信道矩阵为其信道矩阵为现在学习的是第33
24、页，共36页w这个试验信道能正确传送信源这个试验信道能正确传送信源符号符号x x=1,=1,而传送信源符号而传送信源符号x x=0=0时时,接收符号一定为接收符号一定为y=1y=1w凡发送符号凡发送符号x x=0=0时时,一定都错了。一定都错了。而而x x=0=0出现的概率为出现的概率为p p,所以信道所以信道的平均失真度为的平均失真度为p p 。w在这种试验信道条件下，可计在这种试验信道条件下，可计算得算得 R(DR(Dmaxmax)=R()=R(p p)=0)=0现在学习的是第34页，共36页7.3 7.3 限失真信源编码定理和逆定理限失真信源编码定理和逆定理定理定理7.3.17.3.1限
25、失真信源编码定理限失真信源编码定理设离散设离散n n长序列无记忆信源为长序列无记忆信源为单字符失真函数为单字符失真函数为d d（x xikik，y yjkjk），给定单字符失真度），给定单字符失真度下的信息率失真函数下的信息率失真函数R(D)R(D)，当，当n n足够大时，其速率足够大时，其速率R R为为 码字数目码字数目M M选取为选取为RR(D)+M=2nR(D)+7.3.1 7.3.1 限失真信源编码定理限失真信源编码定理现在学习的是第35页，共36页7.3.2 7.3.2 限失真信源编码逆定理限失真信源编码逆定理定理定理7.3.27.3.2限失真信源编码逆定理限失真信源编码逆定理设离散设离散n n长序列无记忆信源为长序列无记忆信源为单字符失真函数为单字符失真函数为d d（x xikik，y yjkjk），给定单字符失真），给定单字符失真度下的信息率失真函数度下的信息率失真函数R(D)R(D)，则所有满足保真度准，则所有满足保真度准则则D D的信源码的速率都不小于的信源码的速率都不小于R R（D),D),即即R=logM/nR(D)现在学习的是第36页，共36页