信息论与编码第七章PPT讲稿.ppt

信息论与编码第七章第1页，共36页，编辑于2022年，星期四如果如果RC，在任意信道上都不可能实现错误译在任意信道上都不可能实现错误译码概率无线小的无失真传输；或者说要实现错误码概率无线小的无失真传输；或者说要实现错误译码概率任意小，在任何信道上传输都必然产生译码概率任意小，在任何信道上传输都必然产生失真。失真。在信道传输信息时，通常并不需要完全无失真。在信道传输信息时，通常并不需要完全无失真。信宿对真实度的要求：信宿对真实度的要求：实际语音信号：实际语音信号：20Hz20Hz8KHz8KHz人耳能够分辨：人耳能够分辨：300Hz300Hz3400Hz3400Hz图象色差：可达足够多图象色差：可达足够多视觉分辨：视觉分辨：256256级（黑白）级（黑白）已已足够足够 所以实际生活当中，通常总是要保证在一定质量所以实际生活当中，通常总是要保证在一定质量的前提下在信宿近似地再现信源输出的信息，或者说的前提下在信宿近似地再现信源输出的信息，或者说在保真度准则下允许信源输出存在一定的失真。在保真度准则下允许信源输出存在一定的失真。第2页，共36页，编辑于2022年，星期四 l失真如何度量？失真如何度量？l率失真函数如何计算？率失真函数如何计算？限失真的信源编码问题限失真的信源编码问题允许一定的失真度下，能将信源信息压缩到什么程度允许一定的失真度下，能将信源信息压缩到什么程度？（最少需要多少比特才能在收端描述信源？）？（最少需要多少比特才能在收端描述信源？）第3页，共36页，编辑于2022年，星期四7.1 7.1 失真测度失真测度7.1.1 7.1.1 失真函数失真函数失真的大小失真的大小,用一个量来表示用一个量来表示,即失真函数即失真函数d(xi i,yj j),),以衡以衡量用量用yj代替代替xi所引起的失真程度。所引起的失真程度。假设离散信号源为假设离散信号源为=经过信道传输后的输出序列为经过信道传输后的输出序列为Y=x xi i y yj j 产生失真产生失真x xi i y yj j 没有失真没有失真 第4页，共36页，编辑于2022年，星期四将所有的将所有的d(xi,yj)排列起来排列起来,用矩阵表示为用矩阵表示为:失真函数失真函数d(xi,yj)：描述了某个信源符号通过传输后失真描述了某个信源符号通过传输后失真的大小。的大小。失真函数的定义为：失真函数的定义为：=第5页，共36页，编辑于2022年，星期四【例【例7.17.1】设信源符号序列为设信源符号序列为X=0,1,=0,1,接收端接收端收到符号序列为收到符号序列为Y=0,1,2,=0,1,2,规定失真函数为规定失真函数为 0 0 1 1 0.50.5 求失真序列求失真序列解：由失真矩阵得解：由失真矩阵得=第6页，共36页，编辑于2022年，星期四w失真函数形式可以根据需要任意选取失真函数形式可以根据需要任意选取,最常用的有最常用的有:w均方失真均方失真:w绝对失真绝对失真:w相对失真相对失真:w误码失真误码失真:适于连适于连续信源续信源适于适于离散离散信源信源第7页，共36页，编辑于2022年，星期四假设离散矢量假设离散矢量N长符号序列为长符号序列为经信道传输后，接收端收到的经信道传输后，接收端收到的N长符号序列为长符号序列为则失真函数定义为则失真函数定义为失真函数的定义可以推广到矢量传输的情况，失真函数的定义可以推广到矢量传输的情况，X=Y=第8页，共36页，编辑于2022年，星期四【例【例 7.27.2】假定离散矢量信源假定离散矢量信源N=3，输出矢量序列为，输出矢量序列为 ,其中其中 ，的取值为的取值为 ；经信道传输后的输出为；经信道传输后的输出为 ，其中，其中 ，的取值为的取值为 。定义失真函数为。定义失真函数为求矢量失真矩阵求矢量失真矩阵 解：由矢量失真函数的定义得解：由矢量失真函数的定义得第9页，共36页，编辑于2022年，星期四类似的可以得到其他元素数值，矢量矩阵为类似的可以得到其他元素数值，矢量矩阵为第10页，共36页，编辑于2022年，星期四7.1.27.1.2平均失真平均失真假定离散信源为假定离散信源为经信道传输后输出序列为经信道传输后输出序列为失真矩阵为失真矩阵为第11页，共36页，编辑于2022年，星期四w 和和 都是随机变量都是随机变量,所以失真函数所以失真函数 也也是随机变量是随机变量,限失真时的失真值只能用数学期限失真时的失真值只能用数学期w望表示将失真函数的数学期望称为平均失真：望表示将失真函数的数学期望称为平均失真：描述某个信源在某一试验信道传输下的失真大小描述某个信源在某一试验信道传输下的失真大小,它对信源和信道进行了统计平均它对信源和信道进行了统计平均,是从总体上描述是从总体上描述整个系统的失真。整个系统的失真。第12页，共36页，编辑于2022年，星期四假设离散矢量假设离散矢量N长符号序列长符号序列经信道传输后，接收端收到的经信道传输后，接收端收到的N长符号序列为长符号序列为Y=YY=Y1 1,Y,Y2 2,Y,Y3 3,Y,YN N X=XX=X1 1,X,X2 2,X,X3 3,X,XN N 则平均失真度为则平均失真度为平均失真平均失真是对给定信源分布是对给定信源分布 在给定转移概率分在给定转移概率分布布 为的信道中传输时的失真总体量度。为的信道中传输时的失真总体量度。第13页，共36页，编辑于2022年，星期四7.2 7.2 信息率失真函数信息率失真函数7.2.1 7.2.1 允许信道（试验信道）允许信道（试验信道）w无论是无噪信道还是有噪信道无论是无噪信道还是有噪信道:R RC C总能找到一种编码使在信道上能以任意小的总能找到一种编码使在信道上能以任意小的错误概率错误概率,以任意接近以任意接近C C的传输率来传送信息的传输率来传送信息 R RC C就必须对信源压缩就必须对信源压缩,使其压缩后信息传输率使其压缩后信息传输率R R小于信道容量小于信道容量C C,但同时要保证压缩所引入的失真不但同时要保证压缩所引入的失真不超过预先规定的限度。超过预先规定的限度。w信息压缩问题就是对于给定的信源信息压缩问题就是对于给定的信源,在满足平均失真在满足平均失真 的前提下的前提下,使信息率尽可能小。使信息率尽可能小。第14页，共36页，编辑于2022年，星期四若平均失真度不大于我们所允许的失真若平均失真度不大于我们所允许的失真,即即则称此为则称此为保真度准则保真度准则将满足保真度准则的所有信道称为失真度将满足保真度准则的所有信道称为失真度D允许信允许信道（也称道（也称D允许的试验信道）记为允许的试验信道）记为对于离散无记忆信道，相应地有对于离散无记忆信道，相应地有第15页，共36页，编辑于2022年，星期四7.2.2 7.2.2 信息率失真函数的定义信息率失真函数的定义在在 失真允许的试验信道失真允许的试验信道 中寻找一个信道，使给定的信中寻找一个信道，使给定的信源经过此信道传输时，其信道传输率源经过此信道传输时，其信道传输率 达到最小，定义为信息率失真函数达到最小，定义为信息率失真函数 ,也称为也称为率失真函数，即率失真函数，即对于离散无记忆信道对于离散无记忆信道第16页，共36页，编辑于2022年，星期四例已知编码器输入的概率分布为例已知编码器输入的概率分布为p p(x x)=0.5,0.5)=0.5,0.5信道矩阵信道矩阵求互信息求互信息第17页，共36页，编辑于2022年，星期四编码器输入的概率分布为编码器输入的概率分布为p p(x x)=0.5,0.5)=0.5,0.5信道矩阵信道矩阵求互信息求互信息可见当可见当p(x)一定时一定时,I(X,Y)随随p(yj|xi)而变。而变。第18页，共36页，编辑于2022年，星期四平均互信息平均互信息I(X;Y)：n信源的概率分布信源的概率分布p(xi)的上凸函数。的上凸函数。n信道传递概率信道传递概率p(yj|xi)的下凸函数。的下凸函数。w信道容量信道容量：w信息率失真函数：信息率失真函数：第19页，共36页，编辑于2022年，星期四 w一旦找到了信道容量一旦找到了信道容量,它就与信源不再有关它就与信源不再有关,而是信而是信道特性的参量道特性的参量,随信道特性的变化而变化随信道特性的变化而变化w不同的信道其信道容量不同。不同的信道其信道容量不同。假定信道固定的前提下假定信道固定的前提下,选择一种试验信源使信选择一种试验信源使信息传输率最大。它所反映的是信道传输信息的息传输率最大。它所反映的是信道传输信息的能力能力,是信道可靠传送的最大信息传输率。是信道可靠传送的最大信息传输率。信息率失真函数：信息率失真函数：信息率失真函数：信息率失真函数：假定信源给定的情况下假定信源给定的情况下,用户可以容忍的失真度内再用户可以容忍的失真度内再现信源消息所必须获得的最小平均信息量。现信源消息所必须获得的最小平均信息量。它反映的是信源可以压缩的程度它反映的是信源可以压缩的程度,是在满足一定是在满足一定失真度要求下信源可压缩的最低值。失真度要求下信源可压缩的最低值。第20页，共36页，编辑于2022年，星期四w率失真函数一旦找到率失真函数一旦找到,就与求极值过程中选择的试验信就与求极值过程中选择的试验信道不再有关道不再有关,而只是信源特性的参量而只是信源特性的参量w不同的信源其不同的信源其R(D)不同。不同。研究信道容量研究信道容量研究信道容量研究信道容量：充分利用已给信道充分利用已给信道,使传输的信息量最大使传输的信息量最大,而发生而发生错错误的概率任意小误的概率任意小。研究信息率失真函数研究信息率失真函数研究信息率失真函数研究信息率失真函数：解决在已知信源和允许失真度解决在已知信源和允许失真度D的条件下的条件下,使信源使信源必须传送给信宿的信息率最小。即用尽可能少的必须传送给信宿的信息率最小。即用尽可能少的码符号尽快地传送尽可能多的信源消息码符号尽快地传送尽可能多的信源消息,以提高通以提高通信的信的有效性有效性。第21页，共36页，编辑于2022年，星期四例例:设信源的符号表为设信源的符号表为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,失真函数规定为失真函数规定为 信源熵信源熵 如果对信源进行不失真编码如果对信源进行不失真编码,平均每个符号至少需要平均每个符号至少需要log2nlog2n个二进制码元。个二进制码元。现在假定允许有一定失真现在假定允许有一定失真,假设失真限度为假设失真限度为D=1/2D=1/2设想设想采用下面的编码方案：采用下面的编码方案：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 n即不发生差错时失真为即不发生差错时失真为0,0,出错失真为出错失真为1 1研究在一定编码条件下信息压缩的程度。研究在一定编码条件下信息压缩的程度。第22页，共36页，编辑于2022年，星期四w平均失真平均失真 w则输出熵则输出熵H H(Y Y)w由该信道模型图看出由该信道模型图看出,它是一个确定信道它是一个确定信道w p pijij=1(=1(或或0)0)，H H(Y Y|X X)=0)=0 压缩压缩第23页，共36页，编辑于2022年，星期四7.2.3 7.2.3 信息率失真函数的性质信息率失真函数的性质1 1、R(D)的定义域的定义域 率失真的定义域问题就是在信源和失真函数已知率失真的定义域问题就是在信源和失真函数已知的情况下的情况下,讨论允许平均失真度讨论允许平均失真度D的最小和最大取的最小和最大取值问题。值问题。由于平均失真度是非负实数由于平均失真度是非负实数d d(x xi i,y yj j)的数学期望的数学期望,因因此也是非负的实数此也是非负的实数,即即 的下界是的下界是0 0。允许平均失真度能否达到其下限值允许平均失真度能否达到其下限值0,0,与单个符号的失真与单个符号的失真函数有关。函数有关。第24页，共36页，编辑于2022年，星期四信源的最小平均失真度信源的最小平均失真度：w只有当失真矩阵的每一行至少有一个只有当失真矩阵的每一行至少有一个0 0元素时元素时,信信源的平均失真度才能达到下限值源的平均失真度才能达到下限值0 0。w当当Dmin=0,即信源不允许任何失真时即信源不允许任何失真时,信息率至少应信息率至少应等于信源输出的平均信息量等于信源输出的平均信息量信息熵。即信息熵。即 R(0)=H(X)w当不满足失真矩阵的每一行至少有一个当不满足失真矩阵的每一行至少有一个0 0元素时元素时,第25页，共36页，编辑于2022年，星期四通常通常wDmin=0=0，R(Dmin)=H(X)w当当 DDmax时时,R(D)=0w当当 0 DDmax时时,0R(D)H(X)R(D)的定义域为的定义域为 Dmin，Dmax 。第26页，共36页，编辑于2022年，星期四wDmax：定义域的上限。定义域的上限。wDmax是是满满足足R(D)=0时时所所有有的的平均失真度中的最小值。平均失真度中的最小值。R R(D D)0)0 由于由于I(X,Y)是非负函数是非负函数,而而R(D)是在约束条件下的是在约束条件下的I(X,Y)的最小值的最小值,所以所以R(D)也是一个非负函数也是一个非负函数,它的下限值是零。它的下限值是零。第27页，共36页，编辑于2022年，星期四 由于由于I(X,Y)=0的充要条件是的充要条件是X与与Y统计独立统计独立,即即：第28页，共36页，编辑于2022年，星期四 例例:设输入输出符号表为设输入输出符号表为X=Y=0,1,=0,1,输入概率分输入概率分布布p(x)=1/3,2/3,=1/3,2/3,失真矩阵失真矩阵 求：求：Dmin 和和Dmax 失真矩阵的每一行至少有一个失真矩阵的每一行至少有一个0 0元素时元素时,Dmin=0=0第29页，共36页，编辑于2022年，星期四 例例:设输入输出符号表为设输入输出符号表为X=Y=0,1,X=Y=0,1,输入概率分输入概率分布布p(x)=1/3,2/3,1/3,2/3,失真矩阵失真矩阵 求：求：Dmin 和和Dmax 第30页，共36页，编辑于2022年，星期四信息率失真函数的性质信息率失真函数的性质w1 1、R(D)是非负的实数是非负的实数,R(D)00。其定义域为其定义域为0 0Dmax,其值为其值为0 0H(X)。当当DDmax时时,R(D)00w2 2、R(D)是关于是关于D的下凸函数的下凸函数 R(D)在定义域内是失真度在定义域内是失真度D的的U U型下凸函数型下凸函数w3 3、R(D)的单调递减性及连续性的单调递减性及连续性 容许的失真度越大，所要求的信息率越小。反容许的失真度越大，所要求的信息率越小。反之亦然。之亦然。第31页，共36页，编辑于2022年，星期四第32页，共36页，编辑于2022年，星期四离散信源离散信源R(D)计算计算 w给定信源概率给定信源概率pi和失真函数和失真函数dij,就可以求得该信源的就可以求得该信源的R(D)函数函数。w它是在保真度准则下求极小值的问题。它是在保真度准则下求极小值的问题。w但要得到它的显式表达式但要得到它的显式表达式,一般比较困难通常用参量表一般比较困难通常用参量表达式。达式。w即使如此即使如此,除简单的情况外实际计算还是困难的除简单的情况外实际计算还是困难的,只只能用迭代逐级逼近的方法。能用迭代逐级逼近的方法。第33页，共36页，编辑于2022年，星期四7.3 7.3 限失真信源编码定理和逆定理限失真信源编码定理和逆定理定理定理7.1 7.1 限失真信源编码定理限失真信源编码定理设离散设离散n长序列无记忆信源为长序列无记忆信源为单字符失真函数为单字符失真函数为 ，给定单字符失真度下的信，给定单字符失真度下的信息率失真函数息率失真函数 ，对任意对任意 和和 ，可以找到满足，可以找到满足保真度准则保真度准则 的允许码的允许码 ，当，当n足够大时足够大时，其速率其速率R为为7.3.1 7.3.1 限失真信源编码定理限失真信源编码定理码字数目码字数目 为：为：第34页，共36页，编辑于2022年，星期四7.3.2 7.3.2 限失真信源编码逆定理限失真信源编码逆定理定理定理7.2 7.2 限失真信源编码逆定理限失真信源编码逆定理设离散设离散n长序列无记忆信源为长序列无记忆信源为单字符失真函数为单字符失真函数为 ，给定单字符失真度下的信，给定单字符失真度下的信息率失真函数息率失真函数 ，则所有满足保真度准则，则所有满足保真度准则D的信源的信源码的速率都不小于码的速率都不小于 即即第35页，共36页，编辑于2022年，星期四7.4 7.4 信息率失真函数的计算信息率失真函数的计算已知信源的概率分布已知信源的概率分布 和失真函数和失真函数 ，就可，就可以确定信源的信息率失真函数以确定信源的信息率失真函数 ,它是在约束它是在约束条件，即保真度准则下，求极小值问题，一条件，即保真度准则下，求极小值问题，一般情况下难于求的闭式解，常采用般情况下难于求的闭式解，常采用参量表示参量表示法法，或采用，或采用迭代算法求解迭代算法求解。第36页，共36页，编辑于2022年，星期四