信息论基础——限失真信源编码--率失真函数

1第5章限失真信源编码和率失真函数2无失真信源编码和有噪信道编码表明：只要信道的信息传输速率小于信道容量，总能找到一种编码方法，使得在该信道上的信息传输的差错概率任意小；反之，若信道的信息传输速率大于信道容量，则不可能使信息传输差错概率任意小．但是，无失真的编码并非总是必要的：例如在传送语音信号时，由于人耳接受的带宽和分辨率是有限的，从而可以把频谱范围从20Hz~8kHz的语音信号去掉低端和高端的频率，视为带宽只有从300Hz~3400Hz的信号；这样，即使传输的语音信号有一些失真，人耳还是可以分辨或感觉出来，已满足语音信号传输的要求．3在允许一定程度失真的条件下，能够把信源信息压缩到什么程度，即最少需要多少比特数才能描述信源，是本章将要讨论的问题．45.1限失真信源编码模型和率失真函数一、失真测度从直观感觉可知，若允许失真越大，信息传输率可越小；若允许失真越小，信息传输率需越大．所以信息传输率与信源编码所引起的失真(或误差)是有关的．51.定义信源编码器输入X∈{x1,x2,…,xi,…,xn}输出（复制）X^∈{x^1,x^2,…,x^j,…,x^n}若xi=x^j——则无失真若xi≠x^j——则有失真[定义][含义]衡量用x^代替x所引起的失真程度．ˆ0ˆ(,)ˆ0xxdxxxx通常较小的d代表较小的失真，d＝0表示没有失真—单符号失真度！6若信源变量X有n个符号，接收变量X^有n个符号，则d(x,x^)就有n×n个,它可以排列成矩阵形式，即：它为失真矩阵D．111212122212ˆˆˆ(,)(,)...(,)ˆˆˆ(,)(,)...(,)::...:ˆˆˆ(,)(,)...(,)nnnnnndxxdxxdxxdxxdxxdxxDdxxdxxdxx7[例1]离散对称信源．信源变量x＝{x1,x2,…xn}，接收变量X^＝{x^1,x^2,…x^ｎ}。定义单个符号失真度：这种失真称为汉明失真．汉明失真矩阵＿对角线上的元素为零，即：ˆ0ˆ(,)ˆ1iiiiiixxdxxxx01...110...1::...:11...0nnD•对二元对称信源(n＝2)，信源X＝{0,1}，接收变量X^＝{0,1}．在汉明失真定义下，失真矩阵为：0110D8[例２]对称信源．信源变量Ｘ＝{ｘ1,ｘ2,…ｘｎ}，接收变量Ｘ^＝{ｘ^1,ｘ^2,…ｘ^ｎ}。失真度定义为：若信源符号代表信源输出信号的幅度值，这就是一种以方差表示的失真度。它意味着幅度差值大的要比幅度差值小的所引起的失真更为严重，严重程度用平方来表示。当ｎ＝3时，Ｘ＝{0,1,2}，Ｘ^＝{0,1,2}，则失真矩阵为：2ˆˆ(,)()dxxxx014101410D上述例子说明了具体失真度的定义．一般情况下根据实际信源的失真，可以定义不同的失真和误差的度量．另外还可以按其他标准，如引起的损失、风险、主观感觉上的差别大小等来定义失真度d(ｘ,ｘ^)．9须强调:假设Ｘ是信源，Ｘ^是信宿，那么两者之间必有信道：转移概率p(ｘ^|ｘ)实际这里Ｘ指的是原始的未失真信源，而Ｘ^是指失真以后的信源．有时又把p(ｘ^|ｘ)称为试验信道的转移概率，如图所示：原始信源失真信源试验信道信道ＸＸ^p(ｘ^|ｘ)10二、平均失真测度信源Ｘ和信宿Ｘ^都是随机变量，故单个符号失真度d(ｘ,ｘ^)也是随机变量．显然，规定了单个符号失真度后，传输一个符号引起的平均失真，即信源平均失真度：在离散情况下，信源Ｘ＝{x1,x2,…xn}，其概率分布P(x)＝[P(x1),P(x2),…P(xn)]，信宿X^＝{X^1,X^2,…X^n}．若已知试验信道的传递概率为P(x|x^)时，则平均失真度为：ˆˆ[(,)][(,)]DEdxxEdXXˆˆˆˆˆˆˆ()(,)()(|)(,)xXXXxXDPxxdxxPxPxxdxx11若平均失真度D不大于我们所允许的失真D，即：DD称此为保真度准则（定义5.1.2）．信源固定(给定P(x))，单个符号失真度固定时(给定d(x,x^))，选择不同试验信道，相当于不同的编码方法，所得的平均失真度是不同的。有些试验信道满足DD，而有些试验信道D＞D.凡满足保真度准则----平均失真度DD的试验信通称为---D失真许可的试验信道．平均失真是对给定信源分布,在给定转移概率分布的信道中传输时的失真的总体量度12[说明]①是在平均意义上，对系统失真的总体描述②是信源统计特性p(x)的函数是信道统计特性p(x/x^)的函数是规定失真度d(x,x^)的函数若保持p(x)、d(x,x^)不变，则平均失真度就是信道特性p(x/x^)的函数研究：在满足保真度准则前提下，求信息率最小值13三、信息率失真函数的定义1.率失真函数问题产生?对于信息容量为C的信道传输信息传输率为R的信源时，如果R＞C，就必须对信源压缩，使其压缩后信息传输率R’小于信道容量C，但同时要保证压缩所引人的失真不超过预先规定的限度——信息压缩问题就是对于给定的信源，在满足平均失真的前提下，使信息率尽可能小。DD14三、信息率失真函数的定义信源给定，且又具体定义了失真函数以后，总希望在满足一定失真的情况下，使信源传输给收信者的信息传输率R尽可能地小．即在满足保真度准则下，寻找信源必须传输给收信者的信息率R的下限值-------------这个下限值与D有关．从接收端来看，就是在满足保真度准则下，寻找再现信源消息所必须获得的最低平均信息量．而接收端获得的平均信息量可用平均互信息I(X;X^)来表示，这就变成了在满足保真度准则的条件下，寻找平均互信息I(X;X^)的最小值．15由于平均互信息I(U;V)是P(x^/x)的凹函数，所以极小值存在．这个最小值就是在D¯D的条件下，信源必须传输的最小平均信息量．即：ˆ(/):ˆ()(;)minPxxDDRDIXXR(D)-------信息率失真函数或简称率失真函数。单位是奈特／信源符号或比特／信源符号16率失真函数与信道容量的比较信道容量C率失真函数R(D)数学上固定p(x^/x),改变p(x),求得I(X;X^)最大值固定p(x),改变p(x^/xi),求得I(X;X^)最小值概念上(反映)固定信道，改变信源，使信息率最大（信道传输能力）固定信源，改变信道，使信息率最小（信源可压缩程度）通信上使传输信息量最大，Pe→0——信道编码用尽可能少的码符号传送——信源编码()DD17四、信息率失真函数的性质•允许失真度D的下限可以是零，即不允许任何失真的情况.1、R(D)的定义域R(D)的定义域为且：minmax0DDDmin()min(,)yxDpxdxymaxmin()(,)yxDpxdxy当失真矩阵中每行至少一个零元．180D()RDmaxDminDmax()RD19解：[例３]设试验信道输入符号集，各符号对应概率分别为)={1/3,1/3,1/3}，失真矩阵如下所示，求和以及相应的试验信道的转移概率矩阵。123,,aaaminDmaxD123213321d123()min(1,2,3)()min(2,1,3)()min(3,2,1)papapamin()min(,)yxDpxdxy令对应最小失真度的，其它为“0”，可得对应的试验信道转移概率矩阵为(,)ijdab(|)1jipbaminD100(|)010001pyx20max123123123min()(,)min()1()2()3,()2()1()2,()3()3()1yxDpxdxypapapapapapapapapa上式中第二项最小，所以令，，可得对应的试验信道转移概率矩阵为2()1pb13()()0pbpbmaxD010(|)010010pyx214.1.3率失真函数R(D)性质(续)[计算][例４]离散二元信源，求Dmax[解]maxmax11minˆmin()(,)ˆ()(,)jjnniijjijiijiDDDpxdxxDpxdxx0112(),,1033pxD1max22122011333121310333jDDDD222、R(D)是关于平均失真度D的（下）凸函数设为任意两个平均失真，，则有：12,DD01a1212((1))()(1)()RaDaDaRDaRD3、R(D)是区间上的连续和严格单调递减函数由信息率失真函数的下凸性可知，R(D)在上连续；又由R(D)函数的非增性且不为常数知，R(D)是区间上的严格单调递减函数。minmax(,)DDminmax(,)DDminmax(,)DD23４R(D)的值域①R(D)min=0②R(D)max=R(0)，D=0即无失真传输——熵保持编码(1)对离散信源、无噪信道，R(D)max=H(X)(2)对连续信源，R(D)max→H∞当且仅当D不小于Dmax24)0()(RUH连续离散0D()RD信息率失真函数的一般形状255.2离散信源率失真函数的计算已知信源的概率分布P(X)和失真函数d(x,x^)，就可求得信源的R(D)函数；原则上它与信道容量一样，即在有约束条件下求极小值的问题．也就是适当选取试验信道P(x^|x)使平均互信息最小化：其约束条件为：ˆ(|)0Pxxˆˆˆ(/)1xXPxxˆˆˆˆ()(|)(,)xXxXDPxPxxdxxDˆˆ1ˆ(|)ˆˆ(,)()(|)logˆ()(|)rxXxXiPxxIXXPxPxxPxPxx26一、信息率失真函数的参量表述应用拉格朗日乘子法，原则上可以求出解来．27•但是，如果要求得到明显的解析表达式，则比较困难，通常只能用参量形式来表达．即便如此，除简单情况外，实际计算仍然是相当困难的．尤其是第三个约束条件，它是求解R(D)函数最主要的障碍．•因为应用拉格朗日乘子法解得的一个或某几个P(x^|x)很可能是负的．在这情况下，必须假设某些P(x^|x)=0，然后重新计算，这就使得计算复杂化了．•目前，可采用收敛的迭代算法在电子计算机上求解R(D)函数．•下面介绍用拉格朗日乘子法求解R(D)函数，并用λ作为参量来表述率失真函数R(D)和失真函数D(λ)：28•由式(1)知，当信源的概率分布P(x)固定，平均互信息仅仅是试验信道P(x^|x)的函数.•若先不考虑式(2)的约束，约束条件式(3)包含n个等式，取拉格朗日乘子α分别与之对应；并取拉氏乘子λ与式(4)对应.由此构成辅助函数：ˆˆˆ(;)(|)(5)xJIXXPxxDˆ(|)0Pxxˆˆˆ(|)1xXPxxˆˆˆˆ()(|)(,)xXxXDPxPxxdxxD(2)(3)(4)ˆˆ1ˆ(|)ˆˆ(,)()(|)logˆ()()|)(1rxXxXiPxxIXXPxPxxPxPxx29求极值，就是求辅助函数一阶导数等于零的方程组的解.即求：ˆ(|)0ˆ(|0,)whenPxxletJPxx所以原则上只需求解式(6)、(3)和(4)的方程组，即可求出I(U;V)在约束条件下的极小值．ˆ(|)ˆ()log(,)()0ˆˆ((|()))6JPxxPxdxxxPxxPx()()log()xPxx令代入（6）得到30ˆ(,)ˆˆ(|)()()(*)dxxPxxPxxe对x^求和，得ˆ1(,)ˆˆ()()(**)dxxxxPxeˆ(,)ˆ(,)ˆˆ()ˆ(|)ˆ()dxxdxxxPxePxxPxe将（**）代入（*）得到乘P(x),对x求和，最后同除以P(x^)得到3