第5章 率失真函数与限失真信源编码
一、失真测度与失真矩阵
1．失真函数
从直观感觉可知，若允许失真越大，信息传输率可 越小；若允许失真越小，信息离散无记忆信源U，信源变量U＝{u1,u2,?ur}，概率分布为P(u)＝[P(u1),P(u2),?
传输率越大。所以信息传输率与信源编码所引起的失真(或误差)是有关的。
P(ur)] 。信源符号通过信道传输到某接收端，接收端的接收变量V＝{v1,v2,?vs} 。对应于每一对(u,v), 指定一个非负的函数：
ui?uj?0d(ui,vj)??
u?u?(?0)ij?
称为单个符号的失真度(或失真函数)。
通常较小的d值代表较小的失真，而d(ui,vj)＝0表示没有失真。
失真函数是根据人们的实际需要和失真引起的损失、风险大小等人为规定的。常1)汉明失真
在离散对称信道(r=s)中，定义单个符号失真函数为d(ui,vj)???0?1ui?ujui?uj用的失真函数有：
，称
为汉明失真。
2)平方误差失真函数
如果信源符号代表信源输出信号的幅度值，则上式意味着较大的幅度差值要比较
小的幅度差值引起的失真更为严重，严重程度用平方表示。
d(ui,vj)?(ui?vj)2对?i,j
2. 失真矩阵
若信源变量U有r个符号，接收变量V有s个符号，则d(ui,vj)就有r×s个,它可以排列成矩阵形式，即：
?d(u1,v1)?d(u2,v1)?D??:??d(ur,v1)d(u1,v2)d(u2,v2):d(ur,v2)............d(u1,vs)??d(u2,vs)? ?:?d(ur,vs)?为失真矩阵D，是 r×s 阶矩阵。
3．平均失真度
1)试验信道
假设U是信源，V是信宿，那么U和V之间必有信道。实际这里U指的是原始的未失真信源，而V是指失真以后的信源。因此，从U到V之间实际上是失真算法，所以这里的转移概率p(vj/ui)是指一种失真算法，有时又把p(vj/ui) 称为试验信道的转移概率，如图所示：
U 原始信源 p (vj/ui) 试验信道 V 失真信源 信道
2)平均失真度
信源U和信宿V都是随机变量，故单个符号失真度d(ui,vj)也是随机变量。显然，规定了单个符号失真度d(ui,vj) 后，传输一个符号引起的平均失真，即信源平均失真度：
D?E[d(ui,vj)]?E[d(u,v)]
在离散情况下，信源U＝{u1,u2,…ur} ，其概率分布P(u)＝[P(u1),P(u2),…P(ur)] ，信宿V＝ {v1,v2,…vs} 。
若已知试验信道的传递概率为P(vj/ui)时，则平均失其度为：
rsijD??P(uv)d(u,v)???P(u)P(vUVi?1j?1/ui)d(ui,vj)
二、率失真函数
1．D失真许可信道
若平均失真度D不大于我们所允许的失真D，即：D ? D， 称此为保真度准则。 信源固定(给定P(u))，单个符号失真度固定时(给定d(ui,vj)) ，选择不同试验信道，相当于不同的编码方法，所得的平均失真度是不同的。
有些试验信道满足D ? D，而有些试验信道D＞D。
凡满足保真度准则----平均失真度D ? D的试验信通称为---D失真许可的试验信道。
把所有D失真许可的试验信道组成一个集合，用符号BD表示，即： BD={P (vj / ui)： D ? D}
2．率失真函数的定义
信源给定，且又具体定义了失真函数以后，总希望在满足一定失真的情况下，使信源传输给收信者的信息传输率R尽可能地小。即在满足保真度准则下，寻找信源必须传输给收信者的信息率R的下限值—这个下限值与D有关。
从接收端来看，就是在满足保真度准则下，寻找再现信源消息所必须获得的最低平均信息量。
而接收端获得的平均信息量可用平均互信息I(U;V)来表示，这就变成了在满足保真度准则的条件下，寻找平均互信息I(U;V)的最小值。
寻找平均互信息I(U;V)的最小值。而BD是所有满足保真度准则的试验信道集合，因而可以在D失真许可的试验信道集合BD中寻找一个信道P(vj / ui) ，使I(U;V) 取极小值。
由于平均互信息I(U;V)是P(vj / ui)的U型凸函数，所以在BD集合中，极小值存在。这个最小值就是在D ? D的条件下，信源必须传输的最小平均信息量。即：
R(D)?P(vj/ui)?BDmin?I(U;V)?
R(D)—信息率失真函数或简称率失真函数。
3．信息率失真函数的性质
1)R(D)函数的定义域
R(D)的定义域为：0?Dmin?D?Dmax 且：
Dmin??p(x)min(d(x,y))
xyyDmax?min?xp(x)d(x,y)
允许失真度D的下限可以是零，即不允许任何失真的情况。
Dmin的理解：失真矩阵每一行的最小值求加权和，即是对试验信道转移矩阵将输出x以概率为1转移到y使得d(x,y)的值最小。此时对应于所确定的失真矩阵所求的平均失真为最小，即Dmin。
确定了Dmin之后，就可以求得对应的信道转移矩阵，因此也就可以求得相应的R（D）值。
Dmax的理解：对所有的输出x以概率1转移到同一个y，所求得的平均失真最小的那个平均失真即为Dmax。
确定了Dmax之后，就可以求得对应的信道转移矩阵，因此也就可以求得相应的R（D）值。
2)R(D)是关于平均失真度D的下凸函数
3)R(D) 是(Dmin，Dmax)区间上的连续和严格单调递减函数
R(D)H(U)?R(0)连续离散0R(D)R(Dma)xD
0DminDmDax
信息率失真函数的一般形状
三、率失真函数的计算
已知信源的概率分布P(u)和失真函数d(u,v)，就可求得信源的R(D)函数。原则上它与信道容量一样，即在有约束条件下求极小值的问题。
也就是适当选取试验信道P(v/u)使平均互信息最小化：
I(U,V)???ijp(ui)p(vj|ui)logp(vj|ui)?ip(ui)p(vj|ui)
??p(vj|ui)?0??其约束条件：??p(vj|ui)?1?j??p(ui)p(vj|ui)d(ui,vj)?D???ij
一种特殊情况下的率失真函数的计算：对于等概、对称失真的信源，存在一个与失真矩阵具有同样对称性的转移概率分布达到率失真R(D)。
计算步骤：
①判断失真矩阵的情况，如果是对称失真等概分布的信源，则假设一个与失真矩阵具有同样对称性的转移概率矩阵；
②以假设的转移概率矩阵及输入概率分布求平均失真度D，并用D表示转移概率矩阵中的未知数，并重新表示转移概率矩阵；
③利用所求得的转移概率矩阵及输入概率分布求I（X；Y），即R（D）。
四、限失真信源编码定理
对于无失真信源编码来说，在允许一定失真的情况下，信源输出信息率最少可减少到信息率失真函数R(D) ，有可能是多个信源符号（符号序列）对应一个码字（码字序列）。失真信源编码定理就是关于信息率和失真关系的一个极限定理，也称香农第三定理，保真度准则下的离散信源编码定理。
定理：设R(D)是离散无记忆信源的信息率失真函数并且失真函数为有限值．对于任意的允许失真度D?0和任意小的正数ε>0，当信源序列长度N足够长时，一定存在一种编码C，其码字个数M?exp{N[R(D)??]}，而编码后的平均失真度
D(Ck)?D??。
五、计算
1．设输入符号集与输出符号集为X=Y={0，1，2，3}，且输入信源分布为等概率分布，设失真矩阵为
?0?1?d????1??1101111011??1?1??0?
求Dmax,Dmin及R(D)。 解：Dmin??p(x)min(d(x,y))?0
xyDmax?min(?p(x)d(x,y))?yx34
由于失真矩阵对称且输入信源等概分布，则有与之相同的信道转移矩阵，设为：
?1?3??????????1?3???1?3???????? ???1?3???平均失真度为：
D??14?p(xy)d(xy)??p(y|x)p(x)d(xy)?1?4p(y|x)d(xy)?12??3?13D
得??