信息率失真函数的定义

x
上式中第二项最小，所以令 p(b2 ) 1 ， p(b1 ) p(b3 ) 0 ，可得对应 Dmax 的试验信道转移概率矩阵为
0 1 0 0 1 0 p( y | x 0 1 0
2、 R(D)是关于平均失真度D的下凸函数 设
D1 , D2 为任意两个平均失真，0 a 1，则有：
d (u1 , v1 ) d (u1 , v 2 ) d (u , v ) d (u , v ) 2 1 2 2 D : : d (u r , v1 ) d (u r , v 2 )
... d (u1 , v s ) ... d (u 2 , v s ) ... : ... d (u r , v s )
3.2
信息率失真函数及其性质
一、信息率失真函数的定义
信源给定，且又具体定义了失真函数以后，总希望在满足 一定失真的情况下，使信源传输给收信者的信息传输率R尽可 能地小。即在满足保真度准则下，寻找信源必须传输给收信者 的信息率R的下限值-------------这个下限值与D有关。 从接收端来看，就是在满足保真度准则下，寻找再现信源 消息所必须获得的最低平均信息量。 而接收端获得的平均信息量可用平均互信息I(U;V)来表示 ，这就变成了在满足保真度准则的条件下，寻找平均互信息 I(U;V)的最小值。
i j
P(u ) P(v
/ ui )d (ui , v j ) D
等概率、对称失真信源的计算
对于等概、对称失真的信源，存在一个与失真矩阵具有 同样对称性的转移概率分布达到率失真R(D)。
[例5]有一个二元等概平稳无记忆信源 X 0,1 ，接收符号集为
Y 0,1,2 且失真矩阵为 ：
它为失真矩阵D，是 r×s 阶矩阵。
须强调: 这里假设U是信源，V是信宿，那么U和V之间必 有信道。 实际这里U指的是原始的未失真信源，而V是指失真以后 的信源。
因此，从U到V之间实际上是失真算法，所以这里的转移 概率p(vj/ui)是指一种失真算法，
有时又把p(vj/ui) 称为试验信道的转移概率，如图所示。 U 原始信源 p (vj/ui) 试验信道 V 失真信源 信道
第 3章
信息率失真函数
无失真信源编码和有噪信道编码告诉我们：只要信道的 信息传输速率小于信道容量，总能找到一种编码方法,使得 在该信道上的信息传输的差错概率任意小；反之，若信道 的信息传输速率大于信道容量，则不可能使信息传输差错 概率任意小。 但是，无失真的编码并非总是必要的。
香农首先定义了信息率失真函数R(D)，并论述了关于这个 函数的基本定理。 定理指出：在允许一定失真度D的情况下，信源输出的信息 传输率可压缩到R(D)值，这就从理论上给出了信息传输率与允 许失真之间的关系，奠定了信息率失真理论的基础。 信息率失真理论是进行量化、数模转换、频带压缩和数据 压缩的理论基础。 本章主要介绍信息率失真理论的基本内容，侧重讨论离散 无记忆信源。 首先给出信源的失真度和信息率失真函数的定义与性质； 然后讨论离散信源和连续信源的信息率失真函数计算；在这基 础上论述保真度准则下的信源编码定理。
二、信息率失真函数的性质
1、 R(D)的定义域 R(D)的定义域为
0 Dmin D Dmax
且：
Dmin p( x) mind ( x, y)
x y
Dmax min p( x)d ( x, y)
y x
• 允许失真度D的下限可以是零，即不允许任何失真的情况。
[例4] 设试验信道输入符号集 a1 , a2 , a3 ，各符号对应概率分 别为)={1/3,1/3,1/3} ，失真矩阵如下所示，求 Dmin和 Dmax 以及相应的试验信道的转移概率矩阵。 1 2 3 2 1 3 d 3 2 1 解： Dmin p( x) mind ( x, y)
寻找平均互信息I(U;V)的最小值。而BD是所有满足保真度 准则的试验信道集合，因而可以在D失真许可的试验信道集合 BD中寻找一个信道P(vj / ui) ，使I(U;V) 取极小值。
由于平均互信息I(U;V)是P(vj / ui)的U型凸函数，所以在BD
集合中，极小值存在。这个最小值就是在D D的条件下，信源 必须传输的最小平均信息量。即：
I (U ,V ) P(u i ) P(v j / u i ) log
i 1 j 1 r s
P (v j / u i )
P(u ) P(v
i 1 i
r
j
/ ui )
其约束条件为:
P(v j / ui ) 0
P (v
j 1 r s i 1 j 1
s
j
/ ui ) 1
i j i j js
除j=s以外所有的j和i 所有i
• 其中接收符号vs作为一个删除符号。
• 在这种情况下，意味着若把信源符号再现为删除符号vs时， 其失真程度要比再现为其他接收符号的失真程度少一半。
• 若二元删除信源s ＝2，r＝3， U＝{0,1}，V＝{0,1 ,2} 。 失真度为： d(0,0)=d(1,2)=0 d(0,2)=d(1,0)=1 d(0,1)=d(1,1)=1/2

x
y
p(a1 ) min(1, 2,3) p(a2 ) min(2,1,3) p(a3 ) min(3, 2,1)
令对应最小失真度 d (ai , b j )的 p(b j | ai ) 1，其它为“0”，可 得对应 Dmin 的试验信道转移概率矩阵为
1 0 0 0 1 0 p( y | x) 0 0 1
求率失真函数R(D) 。 解：由
0 1 [d ] 0 1
Dmin p( x) mind ( x, y) 0
Dmax min p( x)d ( x, y) 1
y x
x
y
由于信源等概分布，失真函数具有对称，因此，存在着与失真 矩阵具有同样对称性的转移概率分布达到率失真R(D) ，该转 移概率矩阵可写为：
[例1] 离散对称信源(r=s)。信源变量U＝{u1,u2,…ur} ，接收变 量V＝ {v1,v2,…vs}。定义单个符号失真度：
0 d (u i , v j ) 1
ui v j ui v j
这种失真称为汉明失真。汉明失真矩阵是一方阵，对角线上的 元素为零，即：
0 1 ... 1 1 0 ... 1 D : : ... : 1 1 ... 0 rr
R(aD1 (1 a) D2 ) aR( D1 ) (1 a) R( D2 )
3 、 R(D) 是 ( Dmin , Dmax ) 区间上的连续和严格单调递减函 数。 由信息率失真函数的下凸性可知， R(D)在 ( Dmin , Dmax ) 上连续。又由R(D)函数的非增性且不为常数知， R(D)是区 间 ( Dmin , Dmax ) 上的严格单调递减函数。
p( y x) , 1 由于 d (0,1) d (1,0) ，因此对于任何有限平均失真，必 须 0 。于是转移概率矩阵变为：
UV i 1 j 1
r
s
• 若平均失真度D不大于我们所允许的失真D，即： DD 称此为保真度准则。
信源固定(给定P(u))，单个符号失真度固定时(给定 d(ui,vj)) ，选择不同试验信道，相当于不同的编码方法，所得 的平均失真度是不同的。 有些试验信道满足D D，而有些试验信道D＞D。 凡满足保真度准则----平均失真度D D的试验信通称为--D失真许可的试验信道。 把所有D失真许可的试验信道组成一个集合，用符号BD表 示，即： BD={P (vj / ui)： D D}
3.1 失真测度
一、失真度
• 从直观感觉可知，若允许失真越大，信息传输率可 越小；若允许失真越小，信息传输率需越大。
• 所以信息传输率与信源编码所引起的失真(或误差) 是有关的。
失真的测度
离散无记忆信源U，信源变量U＝{u1,u2,…ur}， 概率传输到某接收端，接收端的接 收变量V＝ {v1,v2,…vs} 。
对应于每一对(u,v)，我们指定一个非负的函数：
i j 0 d (ui , v j ) ( 0) i j
称为单个符号的失真度(或失真函数)。 通常较小的d值代表较小的失真，而d(ui,vj)＝0 表示没有失真。
若信源变量U有r个符号，接收变量V有s个符号， 则d(ui,vj)就有r×s个,它可以排列成矩阵形式，即：
R( D)
H (U ) R(0)
连续 离散
D
0
R( D) R( Dmax )
信息率失真函数的一般形状
0
Dmin
Dmax
D
3.3离散无记忆信源的信息率失真函数
已知信源的概率分布P(u)和失真函数d(u,v)，就可求得信源 的R(D)函数。原则上它与信道容量一样，即在有约束条件下求 极小值的问题。 也就是适当选取试验信道P(v/u)使平均互信息最小化，
D E[d (ui , v j )] E[d (u, v)]
在离散情况下，信源U＝{u1,u2,…ur} ，其概率分布P(u)＝ [P(u1),P(u2),…P(ur)] ，信宿V＝ {v1,v2,…vs} 。 若已知试验信道的传递概率为P(vj/ui)时，则平均失其度为：
D P(uv)d (u, v) P(ui ) P(v j / ui )d (ui , v j )
• 对二元对称信源(s＝r＝2)，信源U＝{0,1}，接收变量V＝ 0 1 {0,1}。在汉明失真定义下，失真矩阵为：
D 1 0
[例2] 删除信源。信源变量U＝{u1,u2,…ur} ，接收变量V＝ {v1,v2,…vs} (s = r+1) 。定义其单个符号失真度为：