(信息论)第7章限失真信源编码

第7章限失真信源编码7.1失真测度本章主要讨论信息率失真理论，它主要是研究在允许的失真条件下信源压缩的问题。信息率失真理论是信号量化、模数转换、频带压缩和数据压缩的理论基础。7.1.1失真函数失真函数的定义假设离散信源为nnxpxpxpxxxPX2121经过信道传输后的输出序列为，用一个非负的函数表示信源发出符号，接收端收到符号的失真度的定量描述，将所有的，，排列起来，用矩阵表示为称为失真矩阵。myyyY21jiyxd,ixjymjni,,2,1;,,2,1jiyxd,mnnnmmyxdyxdyxdyxdyxdyxdyxdyxdyxdd,,,,,,,,,212221212111d(7.1)失真函数的形式：平方代价函数绝对代价函数均匀代价函数等等jiyxd,①②③失真函数定义的推广对于离散矢量信源N长符号矢量序列为其中第i个符号的取值为，经信道传输后，接收端收到的N长符号矢量序列为其中第i个符号的取值为，则相应的失真函数定义为矢量失真函数矩阵共有个元素。NXXXX,,,,321XiXnxxx,,,21NYYYY,,,,321YiYnyyy,,,21NiiiNYXdNd1,1YX,NNmn(7.2)7.1.2平均失真假设离散信源为平均失真的定义nnxpxpxpxxxPX2121经过信道传输后的输出序列为，失真矩阵为mnnnmmyxdyxdyxdyxdyxdyxdyxdyxdyxdd,,,,,,,,,212221212111myyyY21d由于和都是随机变量，所以失真函数也是随机变量，称失真函数的数学期望为平均失真，记为ixjyjiyxd,jiijnimjijinimjjiyxdxypxpyxdyxpdED,|,1111其中是联合分布，是信源符号概率分布是转移概率分布。jiyxpixpmjni;,,2,1;,,2,1ijxypni|;,,2,1mjni,,2,1;,,2,1平均失真D的意义：是表示给定信源分布在给定转移概率分布为的信道中传输时的失真的总体量度。ixpijxyp|(7.3)矢量信源平均失真的定义对于矢量传输情况，若信源输出和经过信道传输到接收端的N长符号序列为，其中第i个位置上的符号取值分别为，则平均失真度为其中是第i个位置上符号的平均失真。显然，如果矢量信源是离散无记忆N次扩展信源，且矢量信道是离散无记忆N次扩展信道，则每个位置上符号的平均失真相等，且等于矢量平均失真NXXX,,,21XNYYY,,,21Y,,,,21nixxxXmiyyyY,,,21NiiNiiiNNDNYXdENdED111,1iDNiDDiN,,2,1,(7.4)iD7.2信息率失真函数7.2.1允许信道(试验信道)D问题的提出对于信息容量为C的信道传输信息传输率为R的信源时，如果，就必须对信源进行压缩，使其压缩后信息传输率小于信道容量C，但同时要保证压缩所引入的失真不超过预先规定的限度。保真度准则如果预先规定的平均失真度为，则称信源压缩后的失真度D不大于的准则为保真度准则，即保真度准则满足CRRDDDD允许信道(试验信道)的定义D信息压缩问题就是对于给定的信源，在满足保真度准则的前提下，使信息率尽可能小。将满足保真度准则的所有信道称为失真度允许信道(也称允许的试验信道)，记为对于离散无记忆信道，相应地有DDDDDDxypBD:|mjniDDxypBD,,2,1;,,2,1:|(7.5)7.2.2信息率失真函数的定义在允许信道中可以寻找一个信道，使给定的信源经过此信道传输时，其信道传输率达到最小，定义为信息率失真函数，也称为率失真函数，即对于离散无记忆信源，率失真函数可写成其中，是信源符号概率分布，是转移概率分布，是接收端收到符号概率分布，。对于给定的信源，在满足保真度准则的前提下，信息率失真函数是信息率允许压缩到的最小值。DDBXYp|YXI,DRYXIDRDBxyp,min|DRjijijnimjiBxypypxypxypxpDRDij|log|min11|ixpijxypni|;,,2,1jypmjni;,,2,1;,,2,1mj,,2,1DDDR(7.6)7.2.3信息率失真函数的性质DR是非负函数，其定义域为，其值为；当时，。是关于失真度D的下凸函数。是关于失真度D的严格递减函数。由离散信源信息率失真函数的一般曲线可见，当限定失真度大于时，率失真函数是信息压缩所允许的最低限度。若，则必有，即若信息率压缩至，则失真度D必大于限定失真度。所以说信息率失真函数给出了限失真条件下信息压缩允许的下界。DRDRDRmax~0DXH~0maxDD0DRDRDDRDRDDDRDRD7.3限失真信源编码定理和逆定理7.3.1限失真信源编码定理问题提出及分析假定离散n长序列无记忆信源为使收端n长序列为，信源发送序列和接收序列均为n长序列，称Y是分组码长度为n、码字数目为M的分组码，Y中的元素称为码字。如果单字符传输时的失真函数为，则矢量传输时的失真函数为NNxpxpxpxxxPX2121MyyyY21kxlykkjiyxd,nkjijinkkyxdnyxd1,1,信源编码过程是这样进行的：当信源发送序列时，就从分组码Y中选取一个码字，使失真最小，即所以分组码Y的平均失真度为由于信源是无记忆的，所以有如果是预先给定的失真度，则称分组码Y是满足保真度准则D的允许码，把具有最少的码字数目的允许码记为。ixjyjinYyinyxdYxdj,min|YxdxpYXdEYdinNiijinn|,1nkiikxpxp1DDYdn,DnM,(7.8)(7.7)当采用随机编码方法时，考虑到接收端输出序列分布，则分组码Y的平均失真度为对于分组码，其最大速率为jyqYxdyqxpYdEYdinjNiMjinn|11nM,MnRlog1(7.10)(7.9)定理7.3.1限失真信源编码定理设离散n长序列无记忆信源为单字符失真函数为，给定单字符失真度下的信息率失真函数为，则对于任意的和可以找到满足保真度准则的允许码，当n足够大时，其速率R为码字数目M选取为NNxpxpxpxxxPX2121kkjiyxd,DR00DDnM,DRRDRneM(7.11)(7.12)7.3.2限失真信源编码逆定理定理7.3.1限失真信源编码逆定理设离散n长序列无记忆信源为NNxpxpxpxxxPX2121单字符失真函数为，给定单字符失真度下的信息率失真函数为，则所满足保真度准则D的信源码的速率都不小于，即kkjiyxd,DRDRDRDnMn,log17.4信息率失真函数的计算在已知信源的概率分布和失真函数，就可以确定信源的信息率失真函数，它是在约束条件，即保真度准则下，求极小值问题。一般情况下难于求得闭式解，常采用的解题方法有：xpyxd,DR参量表示法迭代算法0DRXHDRDmaxDD离散信源信息率失真函数的一般曲线图DR