信息论与编码-第5章《限失真信源编码》

第五章 保真度准则下的信源编码,前 言第一节 失真度和平均失真度第二节 信息率失真函数第三节 信息率失真函数的性质第四节 二元信源和离散对称信源的R(D)函数第五节 保真度准则下的信源编码定理第六节 标量量化编码第七节 矢量量化编码,前 言,无失真离散信源编码定理: 无论是无噪信道还是有噪信道, 信息传输率小于信道容量, 总能以任意接近信道容量的传输率来传送信息;但若信息传输率大于信道容量, 就不可能实现无失真传输.,前 言,无失真传输存在的问题: 实际信源的输出常常是连续的, 如语言、图像等. 因为连续信源的绝对熵为无限大, 若要无失真地传送连续信源, 则信息传输率也必须无限大。信道带宽是有限的, 即信道容量是受限的. 为此实际通信中信息传输率总是远大于信道容量的, 因此不可能实现完全无失真地传输信源信息。,前 言,失真传输的必要性: 无失真信源编码定理: 描述信源所需的最少比特数是信源的熵值. 那么连续信源需要用无穷多个比特数才能无失真地描述, 这是绝对不可能的.若用有限的比特数来描述连续的消息就会带来失真.,前 言,失真传输的必要性: 数字系统需要传送、存储和处理大量的数据. 如实际数字通信系统中, 普通电话的数码率为64 kb/s; 可视电话的数码率为8.448 Mb/s; 黑白电视的数码率为60 Mb/s等. 传输信号质量要求越高, 数码率也越高. 数码率高, 不仅对传输不利, 而且也增加了存储和处理的困难. 为了提高传输和存储的效率, 就必须对有待传送和存储的数据进行压缩, 这样也会损失一定的信息, 带来失真.,前 言,失真传输的可能性: 实际生活中信宿一般并不要求完全无失真地恢复消息. 通常总是要求在保证一定质量(一定保真度)的条件下近似地再现原来的消息, 也就是允许有一定的错误(失真)存在. 例如:传送语音时, 由于人耳接受带宽和分辨率有限, 可把频谱范围从20 Hz8 kHz的语音信号去掉低端和高端的频率, 看成带宽只有300 Hz3.4 kHz的信号. 这样, 即使传输的语音信号会有一些失真, 人耳还是可以分辨或感觉出原来的语音, 满足语音信号传输的要求, 所以这种失真是允许的.,前 言,失真传输的可能性: 传送图像时, 也并不是需要全部精确地把图像传送到观察者. 只需将电视信号每一像素的黑白灰度级分成256级, 屏幕上的画面就已足够清晰悦目. 对于静止图像或活动图像, 从空间频域来看, 每一帧一般只含有大量的低频域分量, 高频域分量很少. 若将高频分量丢弃, 只传输或存储低频分量, 数据率便大大减少, 而图像质量仍能令人满意. 这是因为人眼有一定的主观视觉特征, 允许传送图像时有一定的误差存在.,前 言,失真传输的研究方向: 在允许一定程度失真的条件下, 能把信源信息压缩到什么程度, 即最少需要多少比特数才能描述信源; 也就是说, 在允许一定程度失真的条件下, 如何能快速地传输信息, 这是本章要讨论的问题。,前 言,这个问题在香农1948年最初发表的经典论文中已经有所体现, 但直到1959年香农又发表了“保真度准则下的离散信源编码定理”这篇重要文章之后, 它才引起了人们的注意.定理指出: 在允许一定失真度D的情况下, 信源输出信息传输率可压缩到R(D)值, 这就从理论上给出了信息传输率与允许失真之间的关系, 奠定了信息率失真理论的基础.,前 言,那么在允许一定程度失真的条件下, 能够把信源信息压缩到什么程度, 也就是, 允许一定程度失真的条件下, 如何能快速的传输信息, 这就是本章所要讨论的问题. 本章所讨论的内容是量化、数模转换、频带压缩和数据压缩的理论基础.,前 言,本章主要介绍信息率失真理论的基本内容, 侧重讨论离散无记忆信源. 首先给出信源的失真度和信息率失真函数的定义与性质, 然后讨论离散信源的信息率失真函数计算. 在这个基础上论述保真度准则下的信源编码定理.,1、失真度,信源,信源编码,信道编码,信道,信道译码,信源译码,信宿,干扰,失真范围: 由于只涉及信源编码问题, 所以可以将信道编码和信道译码看成是信道的一部分. 这样信宿收到消息的失真(或误差)只是由信源编码带来的.,第一节 失真测度,广义无扰信道,第一节 失真测度,试验信道: 由于是失真编码, 所以信道不是一一对应的, 可用信道传递概率描述编、译码前后关系, 这样通信系统可简化为下图所示.,第一节 失真测度,失真大小与信息传输率的关系: 从直观感觉可知, 若允许失真越大, 信息传输率可越小; 若允许失真越小, 信息传输率需越大. 所以信息传输率与信源编码所引起的失真(或误差)是有关的. 现在要研究在给定允许失真的条件下, 是否可以设计一种信源编码使信息传输率为最低. 为此, 我们首先讨论失真的测度.,第一节 失真测度,设信源变量为U=u1,ur, 接收端变量为V=v1,vs, 对于每一对(u,v), 指定一个非负函数d(ui,vj)0称为单个符号的失真度(或称失真函数). 失真函数用来表征信源发出符号ui, 而接收端再现成符号vj所引起的误差或失真. d越小表示失真越小, 等于0表示没有失真.,第一节 失真测度,可以将所有的失真函数排列成矩阵的形式:,我们称它为失真矩阵D (rs).,第一节 失真测度,失真函数可有多种形式, 但应尽可能符合信宿的主观特性, 即主观的失真感觉应与失真函数d(ui, vj)的值相对应. d越大, 所感觉到的失真也越大, 最好成正比;当ui=vj时, d应等于零, 表示没有失真;当uivj时, d应为正值.,第一节 失真测度,常用失真函数的类型:1）平方失真: d(x,y) = (x-y)22）绝对失真: d(x,y) = |x-y|3）相对失真: d(x,y) = |x-y|/|x|4）误码失真: d(x,y) = (x,y) 式中: x信源输出消息; y信宿收到消息.,第一节 失真测度,常用失真函数的特点:平方失真和绝对失真只与(x-y)有关, 而不是分别与x及y有关, 数学处理方便;相对失真与主观特性比较匹配, 因为主观感觉往往与客观量的对数成正比，但其数学处理困难得多.前三种失真函数适用于连续信源, 最后一种失真函数适用于离散信源.,第一节 失真测度？,下面给出三个典型例子说明失真函数及其相应的失真矩阵。例1: 离散对称信源(r=s). 信源变量U=u1,ur, 接收变量V=v1,vs. 定义单个符号失真度,失真矩阵为：,发送符号为ui, 再现的接收符号为vj(ij)所引起的失真d(ui,vj)(uivj)都相同, 为一常数, 常数为1时, 则称汉明失真.,在二元情况下：,第一节 失真测度,例2: 删除信源. 信源变量U=u1,ur, 接收变量V=v1,vs. 其中, s=r+1. 定义单个符号失真度如下:,其中, 接收符号vs作为一个删除符号. 在这种情况下, 意味着若把信源符号再现为删除符号vs时, 其失真程度要比再现成为其他错误接收符号的失真程度少一半.对于二元删除信源r=2,s=3,第一节 失真测度,例3: 对称信源r=s, 定义失真度为：,这里信源符号代表信源输出的幅值, 以方差表示失真度. 它意味着幅度差值大的要比幅度差值小引起的失真更为严重, 其程度用平方表示. 可用语音音量大小或图像灰度高低来理解. 当r=s=3时, U=0,1,2, V=0,1,2.,失真矩阵为:,第一节 失真测度,以上所举的三个例子说明了具体失真度的定义. 一般情况下根据实际信源的失真, 可以定义不同的失真和误差的度量. 另外还可按照其他标准, 如引起的损失、风险、主观感受上的差别大小等来定义失真度d(ui,vj).从实用意义上说, 研究符号实际信源主观要求的、合理的失真函数是很重要的.,第一节 失真测度,2、平均失真度: 传输一个符号引起的平均失真,若已知试验信道的传递概率p(vj|ui), 则平均失真度为:,第一节 失真测度,单个符号的失真度d(ui,vj) 描述了某个信源符号通过传输后失真的大小. 对于不同的信源符号和接收符号, 其值不同.平均失真度 对信源p(u)和信道p(v|u)进行了统计平均, 是描述某一信源在某一广义无扰信道(或试验信道)传输下的失真大小, 是从总体上(统计上)描述整个系统失真情况的.,第一节 失真测度,保真度准则: 平均失真度 不大于我们所允许的失真D, 即 当信源p(u)和失真度d(ui,vj)给定, 选择不同的信道(相当于选择不同编码方法), 所得平均失真度不同. D失真许可试验信道: 满足保真度的试验信道. 把所有D失真许可试验信道组成一个集合BD, 即,第二节 信息率失真函数,在信源和失真函数给定以后, 总希望在满足一定失真下, 使信息传输率R尽可能地小.或者说, 在满足保真度准则下, 寻找信源必须传输给信宿的信息率R的下限值, 这个下限值与D有关.,第二节 信息率失真函数,从接收端来看, 就是在满足保真度准则下, 寻找再现信源消息所必须获得的最低平均信息量. 接收端获得的平均信息量可用平均互信息量I(U;V)表示;这就变成了在满足保真度准则的条件下 , 寻找平均互信息量I(U;V)的最小值. 因为BD是所有满足保真度准则的试验信道集合, 即可以在D失真许可的试验信道集合BD中寻找某一个信道p(vj|ui), 使I(U;V)取最小值.,第二节 信息率失真函数,由于平均互信息量I(U;V)是p(vj|ui)的U型凸函数, 所以在BD集合中, I(U;V)的极小值存在. 这个最小值就是在 的条件下, 信源必须传输的最小平均信息量. 即,第二节 信息率失真函数,应该指出, 研究R(D)时, 条件概率p(v|u)并没有实际信道的含义. 只是为了求互信息的最小值而引用的、假想的可变试验信道. 实际上这些信道反映的仅是不同的有失真信源编码或信源压缩. 所以改变试验信道求平均互信息最小值, 实质上是选择编码方式使信息传输率为最小.,率失真理论与信息传输理论的对偶关系,平均互信息I(U;V)是信源分布p(u)的型凸函数; I(U;V)又是信道特性p(v|u)的U型凸函数; 因此, 信道容量C和信息率失真函数R(D)具有对偶性. 见下图,率失真理论与信息传输理论的对偶关系,第三节 信息率失真函数的性质,D是允许的失真度; R(D)是对应于D的一个确定的信息传输率; 对于不同D, R(D)就不同, 所以它是允许失真度的函数. 下面讨论函数R(D)的一些基本性质.,第三节 信息率失真函数的性质,1) R(D)的定义域是(Dmin=0, Dmax)(1) Dmin和R(Dmin)根据定义, 平均失真度 是非负实函数d(ui,vj)的数学期望, 因此平均失真度 也是一个非负的实数, 所以 的下限必须是零. 那么, 允许失真度D的下限也必然是零, 这就是不允许任何失真的情况.,第三节 信息率失真函数的性质,一般, 当给定信源u,p(u), 及给定失真度矩阵D, 信源的最小平均失真度为: 其中,第三节 信息率失真函数的性质,允许失真度D是否能够达到零, 这与单个符号的失真函数有关.只有当失真矩阵D中每行至少有一个零元素时, 信源的平均失真度 才能够达到零值. 否则, 信源的最小平均失真不等于零值.假设Dmin=0可不失其普遍性.在实际情况中, 一般Dmin=0.另外, 假如Dmin0时, 可以适当改变单个符号的失真度,令 , 使Dmin=0. 而对信息率失真函数来说, 它只是起了坐标平移作用.,第三节 信息率失真函数的性质,当Dmin=0时, 表示信源不允许任何失真存在. 一般直观地理解就是, 若信源要求无失真地传输, 则信息传输率至少应等于信源输出的信息量信息熵, 即R(Dmin)=R(0)=H(U). 上式能否成立与失真矩阵形式有关, 只有当失真矩阵中每行至少有一个零时, 并且每一列最多只有一个零时, 等式成立.否则, R(0)小于H(U), 它表示这时信源符号集中有些符号可以压缩、合并, 而不带来任何失真.,第三节 信息率失真函数的性质,例4 删除信源U0,1, V0,1,2, 而失真矩阵D 最小允许失真度为满足最小允许失真度的试验信道是无噪无损, 信道转移矩阵P若允许失真度D=Dmin=0, 则BD中只有这个信道是唯一可取试验信道, 即无失真一一对应编码. 那么,第三节 信息率失真函数的性质,例5 设信源U0,1,2且等概率分布, 信宿V0,1. 失真矩阵D为Dmin=1/3*0+1/3*1/2+1/3*0=1/6使平均失真度达到最小值(D=1/6)的信道必须满足第二个条件限制的p(v1|u2)和p(v2|u2)可有无穷多个, 其最小平均失真度都是1/6, 即(BD)min集合中试验信道有无数个. 其共同特征是信道矩阵中每列有不止一个非零元素, 所以其信道疑义度H(U|V)0，则,第三节 信息率失真函数的性质？,(2) Dmax和R(Dmax)平均失真度也有一上界值Dmax. 根据R(D)的定义知,R(D)随 D 增加而递减的函数. R(D)是在一定的约束条件下平均互信息I(U;V)的极小值. I(U;V)是非负的, 其下限值为零. R(D)也是非负的, 下限值也为零. 因此, 当R(D)等于零时, 所对应的平均失真度的下界就是上界值Dmax, 如右图所示.,第三节 信息率失真函数的性质,求上界值Dmax: 允许失真D越大, 信息传输率R(D)越小, 最小为0; 当D再大时, 由于R(D)是非负的, 也只能为0. 即I(U;V)=0. 此时, 信源与接收符号已经统计独立, 即: p(v|u)=q(v) 失真度函数变为：,第三节 信息率失真函数的性质,所以, Dmax就是在R(D)=0的情况下, 求 的最小值,当DDmax, R(D)=0; 当DminR(D)0,这就是求Ed(v)的最小值. 可以这样选q(v), 当d(v)最小时, 取q(v)等于1, 其它为零, 则:,第三节 信息率失真函数的性质,2)、R(D)是允许失真度D的U型凸函数; 3)、R(D)函数的单调递减性和连续性.,0,D,R(D),R(D)的非增性是很容易理解的. 因为允许的失真越大, 所要求的信息传输速率可以越小.,第四节 二元信源和离散对称信源的R(D)函数,1、二元对称信源的R(D)函数设二元信源U=0,1, 其分布概率p(0)=, p(1)=1-, 0.5. 接收变量V=0,1, 设汉明失真矩阵D为:因而最小失真度Dmin=0, 并能找到满足该最小失真的试验信道, 且是一个无噪无损信道, 其信道矩阵为:,第四节 二元信源和离散对称信源的R(D)函数,要达到最大允许失真的试验信道, 唯一确定为,即这个试验信道无论传输信源信号是u=1, 还是u=0, 接收符号一定为v=1. 也就是说接收符号与发送的信源符号无关. 此时, 可计算得信息传输率得,q(v)选取: 当d(v)最小时, 取q(v)等于1, 其它为零,第四节 二元信源和离散对称信源的R(D)函数,其中, PE是信道传输的平均错误概率. 这说明在汉明失真的情况下, 平均失真度等于平均错误概率.可以计算得: 二元信源得信息率失真函数为,一般情况下, 当0D0, 以及任意足够长的码长k, 则一定存在一种信源编码C, 其码字个数为M=ekR(D)+而编码后的平均失真度为 d(C)D+.如果用二元编码, R(D)取比特为单位, 则M可写成:M=2kR(D)+,第五节 保真度准则下的信源编码定理,该定理又称为香农第三定理. 它告诉我们, 对于任何失真度D0, 只要码长k足够长, 总可以找到一种编码C, 使编码后的每个信源符号的信息传输率 而码的平均失真度d(C)D.,第五节 保真度准则下的信源编码定理,定理7.2 (信源编码逆定理) 不存在平均失真度为D, 而平均信息传输率RD. 逆定理告诉我们: 如果编码后平均每个信源符号的信息传输率R小于信息率失真函数R(D), 就不能在保真度准则下再现信源的消息.,第五节 保真度准则下的信源编码定理,意义: 这两个定理证实了允许失真D确定后, 总存在一种编码方法, 使编码的信息传输率R大于R(D)且可任意接近于R(D), 而平均失真度小于允许失真D. 反之, 若RR(D), 编码的平均失真度将大于D.如果用二元码符号编码, 允许一定失真D, 平均每个信源符号所需二元码符号的下限值为R(D).,第五节 保真度准则下的信源编码定理,比较香农第一和第三定理可知, 当信源给定后, 无失真信源压缩的极限值是信源熵H(S); 有失真信源压缩的极限值是信息率失真函数R(D). 在给定D后, 一般有R(D)a0+/2或an-/2, 失真较大.空载区: -/2x-ai/2,第六节 标量量化编码,量化器设计准则: 将样本值量化总要带来误差, 因此, 设计量化器时, 总希望其误差越小越好, 即寻求最优量化误差.最优量化: