信息科学基础文2015fis

1、第7章信源的率失真函数与熵压缩编码7.17.2熵压缩编码和信源的率失真函数率失真函数的基本性质2015/6/2马尽文17.1熵压缩编码和信源的率失真函数信源的冗余度压缩编码无失真保熵信源的熵压缩编码有失真熵压缩n 离散信源熵率冗余度有效传输(压缩保熵)n 连续信源(及一些离散信源)可以有失真(无法保存全部信息)近似表示(减在失真不超过少信息量或降低熵率)一定限度下编码后熵率压缩到最小(熵率压缩)22015/6/2马尽文7.1熵压缩编码和信源的率失真函数常用的失真函数：(1)Hamming 失真若 x = y若 x ¹ yd (x, y) = (x - y)2d (x, y) = &#

2、236;0,íî1,(2)平方误差失真优点：简单，并且分别与差错概率或最小均方误差相。缺点：对于具有延时信号不合适，因为小的延时可能带来大的失真。32015/6/2马尽文7.1熵压缩编码和信源的率失真函数定义7.1.2 设x = (x1 ,K, xn ) 与 y = ( y1 ,K, yn )分别表示长度为n的源字和码字，那么x 与y之间的（平均或单字母）失真度量为码的平均失真：字失真的统计平均其中q(y | x) 为源字x 通过编码转换为y 的转移概率。实际上，若采用确定性编码规则，则有42015/6/2马尽文Ed (x, y) = åå p(x)q(

3、y | x)d (x, y)xynd (x, y) = 1 å d ( x , y )niii =17.1熵压缩编码和信源的率失真函数q(y | x) = ì1,如果y是x的编码其它í0，î通过q(y | x) 在输入序列与输出序列之间建立起了一种，其互信息为 I (X; Y) = I ( X n ;Y n ) = H (Y n ) - H (Y n | X n )若将编码器看作一个信道,则I (X n ;Y n ) 就是信源通过该信道传输的信息速率。理想的熵压缩编码器就是在失真限定的情况下信源通过该编码器达到最低的传输信息速率。该编码器取决于信源的分布

4、，分组码长度 n ，失真p(ak )52015/6/2马尽文7.1熵压缩编码和信源的率失真函数矩阵和的最大平均失真D 。Rn (D) = minI ( X;Y) : Ed (x, y) £ DnnQ其中，min是在平均失真满足:Ed (x, y) = åå p(x)q(y | x)d (x, y) £ Dxy的所有的转移概率矩阵 Q 中取的。1 RR(D) = inf(D)nnn称为信息速率失真函数，简称为率失真函数。率失真函数R(D)給出了熵压缩编码可能达到的最小熵率和失真的关系。它代表了一定失真水平下所能达 到的最小信息速率,其逆函数D(R)称为失真

5、率函数。62015/6/2马尽文7.2率失真函数的基本性质在具体计算离散无记忆信源的信息率失真函数R(D)之前，先对这一函数的一般性质作一些讨论，下面是R(D)的主要性质。性质7.2.1Rn (D)关于D是非负单调下降函数。证：从定义可得。性质7.2.2Rn (D)的定义域为(Dmin , ¥) 。证：根据失真的定义，码的平均失真为Ed (x, y) = åå p(x)q(y | x)d (x, y)xy= åå p(x, y)d (x, y)xy72015/6/2马尽文7.2率失真函数的基本性质n= åå p(x, y)

6、1 å d (x , y )iini=1xy= ååå 1 p(x , y )d (x , y )niiiini=1xiyi1nnååå p(xi )q( yi | xi )d (xi , yi )=i=1xiyi= åå p(xi )q( yi | xi )d (xi , yi )xiyi= åå p(x)q( y | x)d (x, y)xy若 d (x, y) = min d (x, y¢)y '其它ìï1 ,q( y | x) =若取

7、37;ïî0, 82015/6/2马尽文7.2率失真函数的基本性质则可得到可能的最小平均失真 D为min= å p(x)d (x, yx )Dminxd (x, y) = min d (x, y)其中。xy另一方面，定义= min å p(x)d (x, y)Dmaxyx并使编码器在任何输入的源字下都取使得上式成立的码字 y ，则此时有Ed (x, y) = åå p(x)q(y | x)d (x, y)xyåx= minyp(x)d (x, y) = Dmax92015/6/2马尽文7.2率失真函数的基本性质则I ( X

8、n ;Y n ) = H (Y n ) - H (Y n | X n )= H (Y n ) = 0这说明当D = Dmax时，Rn (D) = 0。反之，若 Rn (D) = 0 ，则达到此信息速率的熵压缩编码器的输入x 和输出y之间是统计的，此时码的平均失真为Ed (x, y) = åå p(x)q(y | x)d (x, y)xy= åå p(x) p(y)d (x, y) = å p(y)å p(x)d (x, y)xy³ å p(y) × Dmaxyyx= Dmax102015/6/2马尽文7.

9、2率失真函数的基本性质故当 Rn (D) = 0 时，必有D ³ Dmax 。由此可知，Rn (D) 的定义域为(Dmin , ¥)，并在 D ³ Dmax之后，Rn (D) = 0。性质7.2.3Rn (D) 为D 的凸函数，即若有l1 , l2 , D1, D2，其中l1 + l2= 1, 0 £ l1 £ 1, D = l1 D1 + l2 D2和 D，则有证：设q1 (y | x) 是达到Rn ( D1) 的转移概率，q2 (y | x) 为达到Rn (D2 ) 的转移概率，且这两个转移概率下的互信息分别为 1nn和I ( X n ;Y

10、 n )，从而有I ( X ;Y )2I ( X n ;Y n ) = R ( D ) ,E d (x, y) £ D1n111I ( X n ;Y n ) = R ( D ) ,E d (x, y) £ D2n222112015/6/2马尽文7.2率失真函数的基本性质重新定义转移概率如下：1(y | x) + l2 q2 (y | x)在此转移概率下编码的平均失真满足：Ed (x,y) = l1E1d (x, y) + l2 E2d (x, y)£ l1 D1 + l2 D2 = D又设在上述转移概率下编码器的输入/输出互信息为 I ( X n ;Y n )，则

11、R (D) = R (l D + l D ) £ I ( X n ;Y n )nn1122而由于互信息是转移概率的凸函数，即I ( X ;Y ) £ l;Y ) + lI ( X ;Y ) = lR ( D ) + l R ( D )nnnnnnI ( X1 1221n12n2122015/6/2马尽文7.2率失真函数的基本性质故有Rn ( D) £ l1Rn ( D1) + l2Rn ( D2 )性质7.2.4 对于离散无记忆信源，有证：对于任意的n ，我们分两步证明，即分别证明Rn (D) ³ n R1 (D)和。Rn (D) £ n R1

12、(D)（1）取定 D ，设 q(y | x)为达到 Rn (D) 的转移概率， 此时有I ( X n ;Y n ) = R (D), 且 Ed (x, y) £ Dnnp(x) = Õ p(xi )i=1由于是离散无记忆信源，从而有132015/6/2马尽文7.2率失真函数的基本性质故反复利用公式 H ( X ,Y ) = H ( X | Y ) + H (Y ) ，有I ( X n ;Y n ) = H ( X n ) - H ( X n | Y n )n= å H ( X ) - H ( X n | Y n )ii=1n= å H ( X ) - H

13、 ( X| Y n ) - H ( X,Y n )L| Xi121i=1n³ åH ( Xi ) - H ( Xi | Yi )i=1= å I ( Xi ;Yi )i=1n若记Di为信源字和码字中第 i 个位置字母之间142015/6/2马尽文7.2率失真函数的基本性质I ( Xi ;Yi ) ³ R1 (Di )£ D，于是有的平均失真，则有n而Ed ( X n ,Y n ) = 1 åDini=1nnR (D) = I ( X n ;Y n ) ³ å I ( X ;Y ) ³ å R (

14、 D )nii1ii=1i=1利用 Rn (D) 的凸性，有1nR ( D ) ³ R ( 1nnåååD ) ³ R ( D) ÞR ( D ) ³ nR (D)1i1i11i1nni=1i=1i=1故 Rn (D) ³ nR1(D) 。（2）"D ，设q( y | x)为达到R1 (D) 的字母转移概率，即 I ( X ;Y ) = R1 (D), Ed ( X ,Y ) £ D ，并且取定n编码器的转移概率为( y | x )iii=1152015/6/2马尽文7.2率失真函数的基本性质这时，编码器相当于一个离散无记忆信道，根据定理5.1.1，则nI ( X n ;Y n ) £ å I ( X ;Y )iii=1所以 I ( X n ;Y n ) £ n R (D)1而此时的平均失真为n1nåEd ( X ,Y ) £D = Dnni=1Rn (D) £ I ( X;Y) &