第七章限失真的信源编码.ppt

第7章 限失真的信源编码n实际需求特点：n信宿对真实度的要求：n实际语音信号：20Hz～8KHz人耳能够分辨：300Hz～3400Hzn图象色差：可达足够多视觉分辨：256级（黑白）已足够n可以允许一定的失真度n完全保真没必要限失真的信源编码问题允许一定的失真度下，能将信源信息压缩到什么 程度？（最少需要多少比特才能在收端描述信源 ？）一定的信息传输率R下，允许的最大失真是多少 ？相关问题n失真如何度量？n率失真函数如何计算？7.1 失真测度 7.1.1 失真函数•假如某一信源X,输出样值xi , xi∈{a1,a2,…an}, 经信道传输后变成yj , yj ∈{b1, b2,…bm},如果:xi ＝ yj 没有失真 xi ≠ yj 产生失真•失真的大小,用一个量来表示,即失真函数 d(xi,yj),以衡量用yj代替xi所引起的失真程度•失真函数定义为：•将所有的d(xi,yj)排列起来,用矩阵表示为:•失真函数d(xi,yj)：–描述了某个信源符号通过传输后失真的大 小•例：设信源符号序列为X={0,1},接收端收 到符号序列为Y= {0,1,2},规定失真函数为d(0,0)＝d(1,1)= 0d(0,1)＝d(1,0)= 1d(0,2)＝d(1,2)= 0.5w 失真函数形式可以根据需要任意选取,最常用的有 :w 均方失真 :w 绝对失真 : w 相对失真 : w 误码失真 :适于 连续 信源适于 离散 信源假设离散矢量N长符号序列为 X=[X1,X2,X3,…,XN] (Xi取值为{x1,x2,…,xn} 经信道传输后，接收端收到的N长符号序列为Y=[Y1,Y2,Y3,…,YN] (Yj取值为 {x1,x2,…,xn}则失真函数定义为7.1.2平均失真设离散信源经信道传输后输出序列为 Y=[Y1,Y2,Y3,…,YN]失真矩阵为•xi和yj都是随机变量,所以失真函数d(xi,yj)也是 随机变量,限失真时的失真值只能用数学期望表示•将失真函数的数学期望称为平均失真：描述某个信源在某一试验信道传输下的失真大 小,它对信源和信道进行了统计平均,是从总体 上描述整个系统的失真。

假设离散矢量N长符号序列为 X=[X1,X2,X3,…,XN](Xi取值为{x1,x2,…,xn} 经信道传输后，接收端收到的N长符号序列为 Y=[Y1,Y2,Y3,…,YN](Yj取值为{x1,x2,…,xn}则平均失真度为7.2 7.2 信息率失真函数信息率失真函数 7.2.17.2.1D D允许信道（试验信道）允许信道（试验信道）w 无论是无噪信道还是有噪信道:R＜C总能找到一种编码使在信道上能以任意 小的错误概率,以任意接近C的传输率来传送信息R＞C就必须对信源压缩,使其压缩后信息传输 率R’小于信道容量C,但同时要保证压缩所引入 的失真不超过预先规定的限度 w 信息压缩问题就是对于给定的信源,在满足平均 失真 的前提下,使信息率尽可能小 若平均失真度不大于我们所允许的失真,即•则称此为保真度准则将满足保真度准则的所有信道称为失真度D 允许信道（也称D允许的试验信道）记为对于离散无记忆信道，相应地有7.2.2 7.2.2 信息率失真函数的定义信息率失真函数的定义在D失真允许的试验信道中寻找一个信道， 使给定的信源经过此信道传输时，其信道传 输率I(X;Y)达到最小，定义为信息率失真函 数R(D),也称为率失真函数，即对于离散无记忆信道w 例已知编码器输入的概率分布为p(x)={0.5 ,0.5} w 信道矩阵w 求互信息w 编码器输入的概率分布为p(x)={0.5 ,0.5} w 信道矩阵w 求互信息w 可见当p(x)一定时,I (X,Y)随p(yj|xi)而变。

w 因为p(x)分布一定时,信道受干扰不同所能传递 的信息量是不同的 w 当p(x)一定时,I (X,Y)是关于p(yj|xi)的下凸函 数 w 因此当改变p(yj|xi)时,I (X,Y)有一极小值w 平均互信息I(X;Y)： n信源的概率分布p(xi)的上凸函数n信道传递概率p(yj|xi)的下凸函数w 信道容量： w 信息率失真函数： 信道容量w w 信道容量：信道容量：n假定信道固定的前提下,选择一种试验信源使 信息传输率最大n它所反映的是信道传输信息的能力,是信道可靠传送 的最大信息传输率 w 一旦找到了信道容量,它就与信源不再有关,而 是信道特性的参量,随信道特性的变化而变化 w 不同的信道其信道容量不同信息率失真函数w w 信息率失真函数：信息率失真函数：n假定信源给定的情况下,用户可以容忍的失真度内再 现信源消息所必须获得的最小平均信息量n它反映的是信源可以压缩的程度,是在满足一定失真 度要求下信源可压缩的最低值 w 率失真函数一旦找到,就与求极值过程中选择的试验信 道不再有关,而只是信源特性的参量 w 不同的信源其R(D)不同w w 研究信道容量研究信道容量：n充分利用已给信道,使传输的信息量最大,而 发生错误的概率任意小。

w w 研究信息率失真函数研究信息率失真函数：n解决在已知信源和允许失真度D的条件下,使 信源必须传送给信宿的信息率最小即用尽 可能少的码符号尽快地传送尽可能多的信源 消息,以提高通信的有效性w 例：设信源的符号表为A={al,a2,…,a2n},概率 分布为p(ai)=1/2n,i=1,2…2n,失真函数规定 为 w 信源熵 w 如果对信源进行不失真编码,平均每个符号至少 需要log2n个二进制码元 w 现在假定允许有一定失真,假设失真限度为D=1/2 设想采用下面的编码方案： a1→a1， a2→a2， …an→anan+1→an ,an+2→ an ,…a2n→ anw 即不发生差错时失真为0,出错失真为1 w 研究在一定编码条件下信息压缩的程度w 平均失真 w 则输出熵H(Y)w 由该信道模型图4-3看出,它是一个确定信道 w pij=1(或0)，H(Y|X)=0 压缩7.2.3 信息率失真函数的性质 w 1、R(D)的定义域 w 率失真的定义域问题就是在信源和失真函数已 知的情况下,讨论允许平均失真度D的最小和最 大取值问题。

w 由于平均失真度是非负实数d(xi,yj)的数学期望 ,因此也是非负的实数,即 的下界是0w 允许平均失真度能否达到其下限值0,与单个符号 的失真函数有关R(D)的定义域w Dmin 和R(Dmin) w 信源的最小平均失真度：w 只有当失真矩阵的每一行至少有一个0元素时, 信源的平均失真度才能达到下限值0w 当Dmin = 0,即信源不允许任何失真时,信息率 至少应等于信源输出的平均信息量—信息熵 即 R(0) =H(X)R(D)的定义域w 因为实际信道总是有干扰的,其容量有限,要无 失真地传送连续信息是不可能的 w 当允许有一定失真时,R(D)将为有限值,传送才 是可能的w 对于连续信源：R(D)的定义域w R(D)的定义域为[Dmin，Dmax ]w 通常Dmin = 0， R(Dmin) = H(X)w 当 D≥Dmax时, R(D) = 0w 当 0 ≤D≤Dmax时, 0＜R(D) ＜H(X)R(D)的定义域w Dmax：定义域的上限w Dmax是满足R(D)=0时所 有的平均失真度中的最 小值w 由于I(X,Y)是非负函数,而R(D)是在约束条件下 的I(X,Y)的最小值,所以R(D)也是一个非负函数 ,它的下限值是零。

R(D)≥0R(D)的定义域 w 由于I(X,Y) = 0的充要条件是X与Y统计独立,即 ：w例4-3:设输入输出符号表为X=Y={0,1}, 输入概率分布p(x)={1/3,2/3},失真矩阵 w 求： Dmin 和Dmax w 失真矩阵的每一行至少有一个0元素时, Dmin=0w例:设输入输出符号表为X=Y={0,1},输 入概率分布p(x)={1/3,2/3},失真矩阵 w 求： Dmin 和Dmax 信息率失真函数的性质w 1、R(D)是非负的实数, R(D)≥0其定义域为0～Dmax , 其值为0～H(X)当D＞Dmax时,R(D)≡0 w 2、R(D)是关于D的下凸函数nR(D)在定义域内是失真度D的U型下凸函数 w 3、R(D)的单调递减性及连续性n容许的失真度越大，所要求的信息率越小反之亦然离散信源R(D)计算 w 给定信源概率pi和失真函数dij,就可以求 得该信源的R(D)函数 w 它是在保真度准则下求极小值的问题 w 但要得到它的显式表达式,一般比较困难 通常用参量表达式 w 即使如此,除简单的情况外实际计算还是 困难的,只能用迭代逐级逼近的方法 二元对称信源的R(D)函数 w 设二元对称信源X={0,1},其概率分布p(x)=[p,1- p],接收变量Y={0,1},汉明失真矩阵w 因而最小允许失真度Dmin=0。

w 并能找到满足该最小失真的试验信道,且是一个无噪 无损信道,其信道矩阵为w 这个试验信道能正确传送信 源符号x=1,而传送信源符号 x=0时,接收符号一定为y=1 w 凡发送符号x=0时,一定都错 了而x=0出现的概率为p,所 以信道的平均失真度为p w 在这种试验信道条件下，可 计算得R(Dmax) = R(p) = 07.3 限失真信源编码定理和逆定理定理7.3.1限失真信源编码定理 设离散n长序列无记忆信源为单字符失真函数为d（xik，yjk），给定单字符 失真度下的信息率失真函数R(D)，当n足够大时 ，其速率R为 码字数目M选取为R